A New Ant Algorithmic Approach for Solving PFSP

Abstract

In this paper, a new ant algorithmic approach is presented for solving $n$-job, $m$-machine permutation flow shop scheduling problem. The main objective is to find a permutation of $n$ given jobs, i.e., $\sigma {:}\,\left\{ {1,2, \ldots ,n} \right\} \to \left\{ {1,2, \ldots ,n} \right\}$. This permutation minimizes the maximum completion time of the schedule arising from $\sigma$. An illustration of using the presented heuristic algorithm for finding a good initial sequence of jobs is given. The proposed method is an ant-based approach to permutation flow shop scheduling problem by the behavior of real ants, but it is different with the pheromone trail concept. The presented model is compared against the one by NEH which has been considered the best constructive algorithm so far. Regarding the quality of results, the superiority of the proposed method over NEH is demonstrated by computational evaluation. The comparison is produced on generated random test problems. This comparison is drawn in domain of feasible instances. It is easy to implement the produced method as a metaheuristic.

1 Introduction

A permutation flow shop scheduling problem (PFSP) is known to determine a sequence of $n$ jobs that are processed on $m$ independent machines such that the makespan or $C_{\max }$ is minimized. Makespan is the distance in time that elapses from the start of processing to the end.

Although the result of $n \times m$ PFSP for $m = 2$ was obtained in polynomial time, it was proved that problem is NP-complete in the strong sense for $m \ge 3$ (Garey et al. 1976). Therefore, when $m$ and $n$ are increased, the methods giving the optimum solutions are impractical. That is why there is a preference for heuristic algorithm.

Initial sequences of jobs are derived in many heuristic algorithms; thereafter, the heuristic approach consists of its performance evaluation. Framinan et al. (2003) proposed 177 different initial orders in NEH-insertion approach. The execution of Kurz and Askin (2004), Leung et al. (2005), Allahverdi and Al-Anzi (2006), Alaykýran et al. (2007), Kalczynski and Kamburowski (2008), Rad et al. (2009), Ancău (2012), Malik and Dhingra (2013), Xu et al. (2014), Liu et al. (2016), Brum and Ritt (2018), Nurdiansyah et al. (2019) and Sauvey and Sauer (2020) heuristics was proposed after obtaining suitable initial sequences.

A PFSP is supposed in conditions below:

• 1. All jobs are processed on the same machines.

• 2. Each job is processed at most once on machines number 1 to $m$ with the same order.

• 3. All jobs are independent and ready for processing in zero time.

• 4. There is one-to-one correspondence between the processing of jobs and machines.

• 5. Buffering storage between every two machines is infinite.

• 6. There are not parallel machines.

• 7. Machines are available continuously.

• 8. The processing of jobs cannot pass each other.

Since all jobs are processed on the same machines, the number of results for a $n \times m$ problem is reduced from $\left( {n!} \right)^{m}$ to $n!$. Let $a_{ij}$ be the processing time of $i$th job on $j$th machine.

Suppose the matrix of processing times is $M = \left[ {a_{ij} } \right]_{n \times m}$. Consider the following weighted directed graph (Fig. 1).

Fig. 1

The weighted directed graph of processing times

In a PFSP for minimizing the $C_{\max }$, a suitable ordering of jobs is searched. According to the mentioned conditions, the columns of matrix $M$ or the graph cannot be replaced, because columns are corresponding machines. The rows must be permuted such that $C_{\max }$ becomes minimized. The weight of the vertex situated in $i$th row and $j$th column is equal to $a_{ij}$, ($i = 1,2, \ldots ,n$) and ($j = 1,2, \ldots ,m$). The weight of every path in the graph is the total of weights of its vertices.

For every permutation denoted by $\pi$, $\pi \left( j \right)$ is the job in $j$th row. Then

$$C_{i,\pi \left( j \right)} = {\text{max}}\left\{ {C_{i - 1,\pi \left( j \right)} ,C_{{i,\pi \left( {j - 1} \right)}} } \right\} + a_{i\pi \left( j \right)} ,$$

$C_{{{\text{max}}}} = C_{m,\pi \left( n \right)} .$

In these relations, $C_{ji}$ is the completion time of $i$th job on $j$th machine. It can also be written for every $\pi$ and $j = 1,2, \ldots ,m$

$$\begin{aligned} C_{0\pi \left( j \right)} & = 0,\,C_{1\pi \left( j \right)} = a_{1\pi \left( 1 \right)} + \cdots + a_{1\pi \left( j \right)} \\ C_{i,\pi \left( 0 \right)} & = 0,\,C_{i\pi \left( 1 \right)} = a_{1\pi \left( 1 \right)} + \cdots + a_{i\pi \left( 1 \right)} . \\ \end{aligned}$$

2 Bellman, Esogbue, Nabeshima Theorem

In every PFSP with the time matrix $M = \left[ {a_{ij} } \right]$, makespan is equal to the weight of the heavy path that is traced between $a_{11}$ and $a_{nm}$ in corresponding directed graph (Bellman et al. 2014).

According to this theorem, let every vertex $a_{ij}$ be the food with $a_{ij}$ weight in the mentioned graph. An ant wants to go from $a_{11}$ to $a_{nm}$ after collecting the heaviest foods with knowing all the weight of $a_{ij}$s.

The objective is giving an order of rows in $M$ or graph such that the collected food be minimized.

Based on this intuition, the heavy entries must be out of access. Indeed, whenever ant obtains food in a vertex, other heavy foods get out of reach. Hence, if ant reaches $a_{ij}$, it does not attain the vertex with less column and row numbers. In fact, there will be no loop. Therefore, as the following figure is shown, if the line that connects two vertices has positive slope, ant does not receive both of them (Fig. 2).

Fig. 2

The path of the ant

With due attention to this idea, the heavy entries are considered and rows are permuted such that the line that connects these vertices has positive slope. This is certainly impossible for all vertices. In this situation, the best permutation of rows is resulted from the amount of makespans. These are the motivation of the presented algorithm.

3 The Proposed Algorithm

All of the prior concepts lead to the following steps. These steps will result in a good initial order of jobs.

• 1. The greatest entry in $M$ is chosen, and the corresponding row and column of it are deleted.

• 2. The above step is repeated on the rest of entries, and the greatest chosen entries in total make a finite sequence of m members.

• 3. All of $m$ elected members in the last step are deleted in $M$.

• 4. The loop is continued n times.

For each sequence of entries, m corresponding rows are arranged. Suppose the sequence $a_{{i_{1} j_{1} }} , \ldots ,a_{{i_{m} j_{m} }}$ is the resulted one in the above process. Since $m \le n$ and $j_{1} , \ldots ,j_{m}$ are distinct, $j_{1} ,j_{2} , \ldots ,j_{m}$ is a permutation of $1,2, \ldots ,m$. The indices $j_{1} ,j_{2} , \ldots ,j_{m}$ are distinct plus they are not all of the $1,2, \ldots ,n$.

The rows $r_{{i_{1} }} , \ldots ,r_{{i_{m} }}$ are arranged such that the slope of lines connecting each elected two entries is positive.

The furthest row is $r_{{i_{h} }}$ with $j_{{i_{h} }} = m$. The next row is $r_{{i_{h - 1} }}$ with $j_{{i_{h - 1} }} = m - 1$, and it will be repeated in this manner for the next rows until the last one being $r_{{i_{1} }}$ with $j_{{i_{1} }} = 1$. Since the column numbers of elected entries in a group are all of the numbers $1,2, \ldots ,m$, these entries can be numerated in the from $a_{{i_{1} 1}} , \ldots ,a_{{i_{m} m}}$. Hence, smaller row means the row that is under the greater one.

A distinguished ordering among the rows of elected entries has been constructed. But for every such ordering, a value can be allocated. For determining the value of ordering $r_{{i_{l} }} < r_{{i_{h} }}$, the profit of this ordering must be checked. Based on Bellman’s theorem (2014), only the bigger one in the $a_{{i_{l} l}}$, $a_{{i_{h} h}}$ is chosen. In the inverse ordering, both of entries can be chosen. Thus, the profit of this ordering can be defined $\min \left\{ {a_{{i_{h} h}} ,a_{{i_{l} l}} } \right\}$. This means that the inverse ordering, i.e., $r_{{i_{h} }} < r_{{i_{l} }}$ has a disadvantage that is equal to $\min \left\{ {a_{{i_{l} l}} ,a_{{i_{h} h}} } \right\}$. The negative of this number is proposed as the profit of $r_{{i_{l} }} < r_{{i_{h} }}$ ordering. Now for each group that has been obtained, there are $m$ rows with distinguishing ordering. Then, for every two rows in it, the obtained profit is constructed from the order of them. In the inverse ordering of these two rows, the profit becomes negative. Therefore, the square matrix $P = \left[ {p_{ij} } \right]$ is defined. Every $p_{ij}$ denotes the sum of $r_{i} < r_{j}$ ordering profits $\left( {\hat{P}_{ij} } \right)$ and $r_{j} < r_{i}$ ordering disadvantages $\left( {\hat{\hat{P}}_{ij} } \right)$. Indeed, for every two indices i and j, it is possible that $r_{i}$ and $r_{j}$ arise in the some of the mentioned corresponding sequences. Clearly $p_{ij} = - p_{ji}$, $P_{ij} = \hat{P}_{ij} + \hat{\hat{P}}_{ij}$.

For every arrangement of rows in $M$ that is obtained from a permutation $\sigma {:}\,\left\{ {1,2, \ldots ,n} \right\} \to \left\{ {1,2, \ldots ,n} \right\}$, matrix $P$ denotes the amount of correctness for place and order of each row. For example, suppose there is $r_{\sigma \left( i \right)}$ of $M$ in $i$th row. Then, the amount of correctness for place of $r_{\sigma \left( i \right)}$ in $i$th row is

$$p_{ij} = p_{\sigma \left( n \right)\sigma \left( i \right)} + \cdots + p_{{\sigma \left( {i + 1} \right)\sigma \left( i \right)}} + p_{{\sigma \left( i \right)\sigma \left( {i - 1} \right)}} + \cdots + p_{\sigma \left( i \right)\sigma \left( 1 \right)} ,\,\,\left( {i = 1,2, \ldots ,n} \right),\,\left( {j = 1,2, \ldots ,n} \right).$$

Obviously $p_{ij} = 0$ when $i = j$.

4 Example for Constructing Matrix P

Let the processing times of four jobs on three machines be as the following:

Consider the lines connecting two entries of (59, 80, 44) and other resulted sequences. The slopes of these must be positive, therefore;

$$\begin{aligned} & A \Rightarrow r_{1} < r_{3} < r_{2} \Rightarrow \hat{P}_{13} = {\text{min}}\left\{ {50,44} \right\} = 44,\hat{P}_{12} = {\text{min}}\left\{ {50,89} \right\} = 50, \\ & \hat{P}_{32} = {\text{min}}\left\{ {44,89} \right\} = 44 \Rightarrow \hat{\hat{P}}_{31} = - 44,\hat{\hat{P}}_{21} = - 50,\hat{\hat{P}}_{23} = - 44 \\ & B \Rightarrow r_{4} < r_{2} < r_{1} \Rightarrow \hat{P}_{42} = {\text{min}}\left\{ {36,84} \right\} = 36,\hat{P}_{41} = {\text{min}}\left\{ {36,62} \right\} = 36, \\ & \hat{P}_{21} = {\text{min}}\left\{ {84,62} \right\} = 62 \Rightarrow \hat{\hat{P}}_{24} = - 36,\hat{\hat{P}}_{14} = - 36,\hat{\hat{P}}_{12} = - 62 \\ & C \Rightarrow r_{2} < r_{4} < r_{3} \Rightarrow \hat{P}_{24} = {\text{min}}\left\{ {5,14} \right\} = 5,\hat{P}_{23} = {\text{min}}\left\{ {5,22} \right\} = 5, \\ & \hat{P}_{43} = {\text{min}}\left\{ {14,22} \right\} = 14 \Rightarrow \hat{\hat{P}}_{42} = - 5,\hat{\hat{P}}_{32} = - 5,\hat{\hat{P}}_{34} = - 14 \\ & D \Rightarrow r_{3} < r_{1} < r_{4} \Rightarrow \hat{\hat{P}}_{31} = {\text{min}}\left\{ {1,13} \right\} = 1,\hat{\hat{P}}_{34} = {\text{min}}\left\{ {1,19} \right\} = 1, \\ & \hat{P}_{14} = {\text{min}}\left\{ {13,19} \right\} = 13 \Rightarrow \hat{\hat{P}}_{13} = - 1,\hat{\hat{P}}_{43} = - 1,\hat{\hat{P}}_{41} = - 13\,. \\ & P_{ij} = \hat{P}_{ij} + \hat{\hat{P}}_{ij} ,\,1 \le i \le 4,\,1 \le j \le 4 \\ & P = \left[ {p_{ij} } \right] = \left[ {\begin{array}{*{20}l} 0 \hfill & {50 - 62} \hfill & {44 - 1} \hfill & { - 36 + 13} \hfill \\ {62 - 50} \hfill & 0 \hfill & { - 44 + 5} \hfill & { - 36 + 5} \hfill \\ { - 44 + 1} \hfill & {44 - 5} \hfill & 0 \hfill & { - 14 + 1} \hfill \\ {36 - 13} \hfill & { - 5 + 36} \hfill & {14 - 1} \hfill & 0 \hfill \\ \end{array} } \right] \\ & P = \left[ {\begin{array}{*{20}l} 0 \hfill & { - 12} \hfill & {43} \hfill & { - 26} \hfill \\ {12} \hfill & 0 \hfill & { - 39} \hfill & { - 31} \hfill \\ { - 43} \hfill & {39} \hfill & 0 \hfill & { - 13} \hfill \\ {26} \hfill & {31} \hfill & {13} \hfill & 0 \hfill \\ \end{array} } \right]. \\ \end{aligned}$$

It is possible that $p_{ij} > 0$ or $p_{ij} < 0$. The best place for a row is where the corresponding $p_{ij}$ has the greatest amount, and thus, the row with the least amount of $p_{ij}$ is in the worst place.

After constructing the matrix $P = \left[ {p_{ij} } \right]$, the row with the worst place is determined, and the best place for it is obtained with a local search. Then, the penultimate row can be chosen, and the mentioned operations are repeated.

These operations are continued till the last row. At the end, a well ordering is found in which every replacement of its rows does not provide a better solution. A situation improves when a better makespan is found.

A suitable initial sequence for processing $n$ jobs on $m$ machines can be obtained from $P = \left[ {p_{ij} } \right]$. The Bellman et al. theorem (Bellman et al. 2014) is used to determine makespans.

5 Computational Evaluation

The heuristic algorithm was implemented in Visual Basic and carried on a Pentium IV PC/AT computer running at 3.2 GHz with 2 GB RAM memory. The proposed algorithm was tested on 100 generated random problems with the sizes $n = 10,20,30,40,50,60,70,80,90,100$ and $m = 10,20,30,40,50$ in the feasible domain. The results of these tests are shown in Table 1 and were compared with the results of NEH [the best heuristic algorithm in classic methods (Nawaz et al. 1983)] on the same random problems. There are two numbers in each table cell. These numbers represent how many times corresponding algorithm has better results than the other.

Table 1 The frequency of the superior results in 100 random problems

The main conclusion to be drawn from this table is that in 82% of times, the heuristic algorithm has better results than NEH. Also in large-scale problems, this improvement is increased.

The results are compared in the following figures (Figs. 3, 4).

Fig. 3

Three-dimensional histogram of NEH superior results

Fig. 4

Three-dimensional histogram of heuristic algorithm’s superior results

In Table 2, the running times of the problems are in second.

Table 2 Running times of heuristic algorithms

The approximate relation $T_{{{\text{Heu}}}} \cong 0/15 \times m\,T_{{{\text{NEH}}}}$ is resulted on the basis of the data in Table 2. Notations $T_{{{\text{Heu}}}}$ and $T_{{{\text{NEH}}}}$ are, respectively, referred to the running times of heuristic algorithm and NEH in each allocation of the table.

6 Time Complexity

The complexity of sorting $mn$ entries of the matrix $M$ is $O\left( {m^{2} n^{2} } \right)$. There is less running time for dividing these entries into $m$ groups and counting the number of operations. The calculation of $p_{ij}$ s has less computational used time in the construction of matrix $P = \left[ {p_{ij} } \right]$. Therefore, the complexity of the presented heuristic algorithm is $O\left( {m^{2} n^{2} } \right)$.

7 Conclusions

In this paper, a reasonably good initial sequence was obtained for solving PFSP with minimizing makespan criterion. After running the heuristic algorithm on 100 random problems, the results in 82% of times were better than NEH. For future researching lines, the presented algorithm with due attention to its mathematical properties could be used as a metaheuristic.