Introduction

Flow shop scheduling, a well-known combinatorial optimization problem, has been proved to be NP-hard (Garey et al, 1976). The permutation flow shop scheduling problem (PFSP) studied in the present paper is scheduling n jobs on m machines (denoted as M₁, ..., M_m) with the objective of minimizing the makespan, subject to the following four constraints: (i) each job is processed on all the machines according to the order of M₁, ..., M_m, (ii) the processing time of each job on each machine is given, (iii) each machine can process at most one job at a time, and (iv) once a sequence =((1), ..., (n)) of all jobs is given by workers, each machine has to process all jobs according to sequence . In other words, the PFSP is to find a job permutation with minimum makespan. Given a sequence =((1), ..., (n)) of all jobs, let p_i,(j) and t_i,(j) denote the processing time of job (j) on machine M_i and the start time of job (j) on machine M_i, respectively, then the schedule can be generated by the following formulas:

Haouari and Ladhari (2003) presented the mathematical statement of the PFSP while Tseng et al (2004) discussed four integer programming models for the PFSP.

Moreover, Pan and Chen (2003) discussed re-entrant permutation flow-shop scheduling problem (RPFSP), which is an extension of the PFSP.

So far, many optimization algorithms and approximation algorithms have been proposed to solve PFSP. Optimization algorithms require too much computing time and cannot be accepted by workers.

On the other hand, approximation algorithms are widely used by workers, since they may give optimal or near optimal permutations quickly. These heuristic methods can be divided into two main classes: construction methods and improvement methods. The literature on construction methods, includes the heuristics proposed by Campbell et al (1970), Dannenbring (1977), Nawaz et al (1983) and Lai (1994); the method of Nawaz et al (NEH for short) is considered as the best one. Improvement methods such as simulated annealing algorithms proposed by Ogbu and Smith (1990) and Osman and Potts (1989) genetic algorithms proposed by Reeves (1995) and Chen et al (1995), and tabu search algorithms proposed by Nowicki and Smutnicki (1996), Widmer and Hertz (1989), Taillard (1989) and Grabowski and Pempera (2001) start from an initial permutation, which is usually generated by a construction method, and then iteratively generate a sequence of improved permutations. It is obvious that improvement methods generate significantly better solutions than construction ones.

In this paper, we present a new local search (LS) heuristic for the PFSP, which is based on a hybrid neighbourhood structure and two escape-from-trap procedures. Our method has been tested on 29 benchmark problem instances with up to 75 jobs and 20 machines. The experimental results of our method are compared with those of an effective hybrid heuristic (HH) (Wang and Zheng, 2003) that combined NEH heuristic with a genetic algorithm (GA) and simulated annealing (SA). For 10 problem instances named Rec13, Rec15, Rec17, Rec19, Rec21, Rec25, Rec27, Rec29, Rec37 and Rec41, our method generates better permutations than the HH. For three problem instances named Rec31, Rec33 and Rec39, our method generates worse permutations than the HH. For the rest of the problem instances, our method generates permutations whose makespans were equal to those of the permutations generated by the HH. So our method generally outperforms the HH.

The rest of the paper is organized as follows. In the next section, we state the neighbourhood structure, the escape-from-trap procedures, and the algorithm. Then we discuss computational results on a standard set of test problem instances. Finally, some concluding remarks are provided.

The strategy

The heuristic proposed in this paper is based on a LS procedure and two escape-from-trap procedures.

Neighbourhood structure

Given a permutation =((1), ..., (n)) of all jobs, the neighborhood of is defined as follows.

Insertion

Given a permutation , a neighbour ' is generated by moving away any job from its position in permutation and inserting this job at any new position. Given a permutation (J₄, J₂, J₅, J₁, J₃) of five jobs, each job can be inserted at four possible new positions. For example, job J₅ can be inserted before J₄, or before J₂, or after J₁, or after J₃ so as to generate (J₅, J₄, J₂, J₁, J₃), or (J₄, J₅, J₂, J₁, J₃), or (J₄, J₂, J₁, J₅, J₃), or (J₄, J₂, J₁, J₃, J₅). Haouari et al (2003) discussed this kind of neighbourhood.

Block replacement

Given a permutation , a neighbour ' is generated by replacing any k₁ successive jobs of permutation with any new sequence of these k₁ jobs, where k₁ is a given constant. Consider the following example. We suppose that k₁=3. Given a permutation (J₄, J₂, J₅, J₁, J₃) of five jobs, a sequence (J₂, J₅, J₁), which consists of three successive jobs of , can be replaced by (J₂, J₁, J₅), or (J₅, J₂, J₁), or (J₅, J₁, J₂), or (J₁, J₂, J₅), or (J₁, J₅, J₂) so as to generate (J₄, J₂, J₁, J₅, J₃), or (J₄, J₅, J₂, J₁, J₃), or (J₄, J₅, J₁, J₂, J₃), or (J₄, J₁, J₂, J₅, J₃), or (J₄, J₁, J₅, J₂, J₃).

Escape-from-trap procedures

We suppose that =((1), ..., (n)) is a trap, that is, a local optimal permutation. Two escape-from-trap procedures are proposed in this paper.

Insertion

At first, job (i), which is chosen uniformly at random from all jobs, is removed from its position in permutation . Then a new position of job (i) is chosen uniformly at random from all positions. Finally, job (i) is inserted at this new position. This process is repeated c₁ times so as to move away from the local optimum, where c₁ is a given constant.

Block replacement

At first, a block b, which consists of k₂ successive jobs of permutation , is chosen uniformly at random from all blocks each of which consists of k₂ successive jobs of permutation , where k₂ is a given constant. Then a new block b' is chosen uniformly at random from all sequences of these k₂ successive jobs. Finally, block b is replaced with block b' so as to generate a new permutation of all jobs, that is, to move away from the local optimum.

In order to illustrate the escape-from-trap procedures, let us consider the following example. We suppose that (J₅, J₁, J₂, J₄, J₃) is a local optimal permutation.

Insertion: We suppose that c₁=2. At first, we choose job J₁ from all jobs, remove J₁ from its position in permutation (J₅, J₁, J₂, J₄, J₃), and insert J₁ before J₄. Then we choose job J₃ from all jobs, remove J₃ from its position in permutation (J₅, J₂, J₁, J₄, J₃), and insert J₃ before J₂. So a new permutation (J₅, J₃, J₂, J₁, J₃) is generated.

Block replacement

We suppose that k₂=4. We replace (J₁, J₂, J₄, J₃) with (J₄, J₃, J₁, J₂). So a new permutation (J₅, J₄, J₃, J₁, J₂) is generated.

Algorithm

Let T be the escape-from-trap counter, and T_m the maximum number of escape-from-trap allowed. Set T=0, T_m=1000, k₁=4, k₂=6, and c₁=5. We set k₁ to be a small number so as to limit the size of the neighbourhood. When a local optimal solution is found, the job sequence is softly perturbed. So k₂ and c₁ are also set to be small numbers.

Step 1:

A permutation of all jobs is generated at random. Go to 2.

Step 2:

Examine the permutations in the neighbourhood of permutation one by one. If a better permutation ' than is found, then =', go to 2. If all the permutations in the neighbourhood of permutation are no better than , then go to 3.

Step 3:

Set T=T+1. If T=T_m, then stop. If the makespan of permutation is equal to that of the best permutation (if the best permutation's makespan of the current problem instance is already presented in the literature), then stop. Move away from the local optimum as follows. A real number r is chosen uniformly at random from [0, 1]. If r0.5, use the first escape-from-trap procedure (insertion) to move away from the local optimum. And if r<0.5, use the second escape-from-trap procedure (block replacement) to move away from the local optimum. Go to 2.

Computational results

This LS algorithm combined with the escape-from-trap procedures is programmed in the C language and run on a Pentium III 500 Mhz personal computer. The algorithm has been tested on 29 problem instances, which can be found in the OR-Library (http://www.ms.ic.ac.uk/info.html) and which are divided into the following two classes:

1. Eight instances (named Car1–Car8) provided by Carlier (1978).
2. Twenty-one instances (named Rec01–Rec41) provided by Reeves (1995).

The instances of set (a) are the easiest instances of these 29 instances. Rec37, Rec39 and Rec41 are the most difficult instances of these 29 instances. Generally speaking, the smaller an instance is, the easier it is.

The makespan value of the optimal permutation is shown in Tables 1 and 2, except for Rec37, Rec39 and Rec41. The optimal permutations of Rec37, Rec39 and Rec41 are still unknown, so the best known lower bound value of the makespan value of the optimal permutation is shown in Table 2.

Table 1 - Results for the problem instances of class (a).

Full table

Table 2 - Results for the problem instances of class (b).

Full table

Both our algorithm and another HH presented by Wang and Zheng (2003), which is run on a Pentium II 366 Mhz personal computer, are executed 20 times independently and the statistical results and comparisons are summarized in Tables 1 and 2. For each run on each instance, the relative error RE (%) was calculated by following formula: (C-C^*)/C^* 100%, where C denotes the makespan value of the permutation found by the algorithm, and C^* denotes makespan value of the optimal permutation or best known lower bound value of it.

Table 1 shows that both of these two algorithms are able to find the optimal permutations to all the instances of class (a). Whereas Table 2 shows that the LS algorithm generally provides better solutions than HH for the instances of class (b): the mean best relative error (MBRE) of LS is 0.67%, while that of HH is 0.91%.

Our algorithm is run on a Pentium III 500 Mhz personal computer while HH is run on a Pentium II 366 Mhz personal computer. The speed of the former computer is slower than two times of that of the latter one. For 11 instances (Car1–Car8, Rec07, Rec11, and Rec35), our algorithm consumes less time than HH if both algorithms are run on the same computer. For other instances, our algorithm consumes more time than HH if both algorithms are run on the same computer.

Our algorithm generates, generally, no worse solutions than HH because the local search procedure is combined with random perturbation in our algorithm.

Conclusion

In this paper, a hybrid local search algorithm for the PFSP is presented. The experiments carried out on benchmark problems demonstrate that this algorithm is effective.

The local search method is widely used for solving the scheduling problems, and the escape-from-trap procedures presented in this paper enhances its efficiency. Because this hybrid algorithm is a method of generality, it can also be used for solving other hard combinatorial optimization problems.

References

1. Campbell HG, Dudek RA and Smith ML (1970). A heuristic algorithm for the n job m machine sequencing problem. Mngt Sci 16B: 630–637.
2. Carlier J (1978). Ordonnancements a contraintes disjonctives. RAIRO—Opns Res 12: 333–351.
3. Chen CL, Vempati VS and Aljaber N (1995). An application of genetic algorithms for flow shop problems. Eur J Opl Res 80: 389–396. | Article |
4. Dannenbring DG (1977). An evaluation of flowshop sequencing heuristics. Mngt Sci 23: 1174–1182.
5. Garey MR, Johnson DS and Sethi R (1976). The complexity of flow shop and job shop scheduling. Math Opns Res 1: 117–129.
6. Grabowski J and Pempera J (2001). New block properties for the permutation flowshop problem with application in tabu search. J Opl Res Soc 52: 210–220.
7. Haouari M and Ladhari T (2003). A branch-and-bound-based local search method for the flow shop problem. J Opl Res Soc 54: 1076–1084. | Article |
8. Lai TC (1994). A note on the heuristic flowshop scheduling. Opns Res 44: 648–652.
9. Nawaz M, Enscore EE and Ham I (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11: 91–95. | Article |
10. Nowicki E and Smutnicki C (1996). A fast tabu search algorithm for the permutation flow-shop problem. Eur J Opl Res 91: 160–175. | Article |
11. Ogbu FA and Smith DK (1990). Simulated annealing for the permutation flowshop problem. Omega 19: 64–67. | Article |
12. Osman IH and Potts CN (1989). Simulated annealing for permutation flow-shop scheduling. Omega 17: 551–557. | Article |
13. Pan JH and Chen JS (2003). Minimizing makespan in re-entrant permutation flow-shops. J Opl Res Soc 54: 642–653. | Article |
14. Reeves CR (1995). A genetic algorithm for flowshop sequencing. Comput Opns Res 22: 5–13. | Article |
15. Taillard E (1989). Some efficient heuristic methods for the flow shop sequencing problem. Eur J Opl Res 47: 65–74. | Article |
16. Tseng FT, Stafford EF and Gupta J (2004). An empirical analysis of integer programming formulations for the permutation flow shop. OMEGA 32: 285–293. | Article |
17. Wang L and Zheng DZ (2003). An effective hybrid heuristic for flow shop scheduling. Int J Adv Manuf Tech 21: 38–44. | Article |
18. Widmer M and Hertz A (1989). A new heuristic method for the flow shop sequencing problem. Eur J Opl Res 41: 186–193. | Article |

Appendices

Appendix

Notation

n

number of jobs

m

number of machines

C^*

makespan value of the optimal permutation, or best known lower bound value of it

RE

relative error to C^*, that is (C-C^*)/C^* 100%, where C denotes the makespan value of the permutation found by the algorithm

BRE

best relative error, that is (C_best-C^*)/C^* 100%, where C_best denotes the makespan value of the best permutation found by the algorithm

ARE

average relative error, that is (C_average-C^*)/ C^* 100%, where C_average denotes the average value of the makespans of the permutations found by the algorithm

WRE

worst relative error, that is (C_worst-C^*)/ C^* 100%, where C_worst denotes the makespan value of the worst permutation found by the algorithm

MBRE

mean best relative error

ART

average running time (s)

Performance measures evaluated over 20 runs for a given problem instance.

Acknowledgements

This research was supported by the National Natural Science Foundation of China under grant no. 10471051 and partially supported by the National Basic Research Program of China under grant no. 2004CB318000.