×

A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. (English) Zbl 1110.90042

Summary: Over the last decade, many metaheuristics have been applied to the flowshop scheduling problem, ranging from Simulated Annealing or Tabu Search to complex hybrid techniques. Some of these methods provide excellent effectiveness and efficiency at the expense of being utterly complicated. In fact, several published methods require substantial implementation efforts, exploit problem specific speed-up techniques that cannot be applied to slight variations of the original problem, and often re-implementations of these methods by other researchers produce results that are quite different from the original ones. In this work we present a new iterated greedy algorithm that applies two phases iteratively, named destruction, were some jobs are eliminated from the incumbent solution, and construction, where the eliminated jobs are reinserted into the sequence using the well known NEH construction heuristic. Optionally, a local search can be applied after the construction phase. Our iterated greedy algorithm is both very simple to implement and, as shown by experimental results, highly effective when compared to state-of-the-art methods.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldowaisan, T.; Allahvedi, A., New heuristics for no-wait flowshops to minimize makespan, Computers and Operations Research, 30, 8, 1219-1231 (2003) · Zbl 1047.90053
[2] Beasley, J.E., 2004. Available from: OR-Library. <http://mscmga.ms.ic.ac.uk/info.html>; Beasley, J.E., 2004. Available from: OR-Library. <http://mscmga.ms.ic.ac.uk/info.html>
[3] Campbell, H. G.; Dudek, R. A.; Smith, M. L., A heuristic algorithm for the \(n\) job, \(m\) machine sequencing problem, Management Science, 16, 10, B630-B637 (1970) · Zbl 0194.50504
[4] Chandrasekharan, R.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 2, 426-438 (2004) · Zbl 1045.90032
[5] Chen, C.-L.; Vempati, V. S.; Aljaber, N., An application of genetic algorithms for flow shop problems, European Journal of Operational Research, 80, 2, 389-396 (1995)
[6] Dannenbring, D. G., An evaluation of flow shop sequencing heuristics, Management Science, 23, 11, 1174-1182 (1977) · Zbl 0371.90063
[7] Framinan, J. M.; Leisten, R.; Rajendran, C., Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem, International Journal of Production Research, 41, 1, 121-148 (2003) · Zbl 1038.90027
[8] Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, Computers and Operations Research, 31, 11, 1891-1909 (2004) · Zbl 1068.68143
[9] Jacobs, L. W.; Brusco, M. J., A local search heuristic for large set-covering problems, Naval Research Logistics Quarterly, 42, 7, 1129-1140 (1995) · Zbl 0839.90085
[10] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[11] Lourenço, H. R.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G., Handbook of Metaheuristics (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 321-353 · Zbl 1116.90412
[12] Marchiori, E.; Steenbeek, A., An evolutionary algorithm for large set covering problems with applications to airline crew scheduling, (Cagnoni, S.; etal., Real-World Applications of Evolutionary Computing, EvoWorkshops 2000. Real-World Applications of Evolutionary Computing, EvoWorkshops 2000, Lecture Notes in Computer Science, vol. 1803 (2000), Springer-Verlag: Springer-Verlag Berlin), 367-381
[13] Moccellin, J. V.; dos Santos, M. O., An adaptive hybrid metaheuristic for permutation flowshop scheduling, Control and Cybernetics, 29, 3, 761-771 (2000) · Zbl 0989.90067
[14] Montgomery, D. C., Design and Analysis of Experiments (2000), John Wiley & Sons
[15] Murata, T.; Ishibuchi, H.; Tanaka, H., Genetic algorithms for flowshop scheduling problems, Computers and Industrial Engineering, 30, 4, 1061-1071 (1996)
[16] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem, OMEGA, The International Journal of Management Science, 11, 1, 91-95 (1983)
[17] Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research, 91, 1, 160-175 (1996) · Zbl 0947.90590
[18] Osman, I.; Potts, C., Simulated annealing for permutation flow-shop scheduling, OMEGA, The International Journal of Management Science, 17, 6, 551-557 (1989)
[19] Pinedo, M., Scheduling: Theory, Algorithms and Systems (2002), Prentice Hall: Prentice Hall New Jersey · Zbl 1145.90394
[20] Reeves, C.; Yamada, T., Genetic algorithms, path relinking, and the flowshop sequencing problem, Evolutionary Computation, 6, 1, 45-60 (1998)
[21] Reeves, C. R., Improving the efficiency of tabu search for machine scheduling problems, Journal of the Operational Research Society, 44, 4, 375-382 (1993) · Zbl 0775.90238
[22] Reeves, C. R., A genetic algorithm for flowshop sequencing, Computers and Operations Research, 22, 1, 5-13 (1995) · Zbl 0815.90097
[23] Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification, Complexity and Computations (1976), Martinus Nijhoff: Martinus Nijhoff The Hague, The Netherlands · Zbl 0366.90092
[24] Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 479-494 (2005) · Zbl 1066.90038
[25] Ruiz, R.; Maroto, C., A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility, European Journal of Operational Research, 169, 781-800 (2006) · Zbl 1079.90061
[26] Ruiz, R.; Maroto, C.; Alcaraz, J., Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, European Journal of Operational Research, 165, 34-54 (2005) · Zbl 1112.90338
[27] Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, OMEGA, the International Journal of Management Science, 34, 461-476 (2006)
[28] Stützle, T., 1998. Applying iterated local search to the permutation flow shop problem. Technical report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt.; Stützle, T., 1998. Applying iterated local search to the permutation flow shop problem. Technical report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt.
[29] Stützle, T., An ant approach to the flow shop problem, (Proceedings of the Sixth European Congress on Intelligent Techniques and Soft Computing (EUFIT’98), vol. 3 (1998), Verlag Mainz, Wissenschaftsverlag: Verlag Mainz, Wissenschaftsverlag Aachen, Germany), 1560-1564
[30] Suliman, S., A two-phase heuristic approach to the permutation flow-shop scheduling problem, International Journal of Production Economics, 64, 1-3, 143-152 (2000)
[31] Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research, 47, 1, 67-74 (1990) · Zbl 0702.90043
[32] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 2, 278-285 (1993) · Zbl 0769.90052
[33] Taillard, E., 2004. Summary of best known lower and upper bounds of Taillard’s instances. Available from: <http://ina.eivd.ch/collaborateurs/etd/problemes.dir/ordonnancement.dir/ordonnancement.html>; Taillard, E., 2004. Summary of best known lower and upper bounds of Taillard’s instances. Available from: <http://ina.eivd.ch/collaborateurs/etd/problemes.dir/ordonnancement.dir/ordonnancement.html>
[34] Turner, S.; Booth, D., Comparison of heuristics for flow shop sequencing, OMEGA, The International Journal of Management Science, 15, 1, 75-78 (1987)
[35] Wang, L.; Zheng, D. Z., An effective hybrid heuristic for flow shop scheduling, The International Journal of Advanced Manufacturing Technology, 21, 38-44 (2003)
[36] Werner, F., On the heuristic solution of the permutation flow shop problem by path algorithms, Computers and Operations Research, 20, 7, 707-722 (1993) · Zbl 0793.90030
[37] Widmer, M.; Hertz, A., A new heuristic method for the flow shop sequencing problem, European Journal of Operational Research, 41, 2, 186-193 (1989) · Zbl 0671.90040
[38] Wodecki, M.; Bożejko, W., Solving the flow shop problem by parallel simulated annealing, (Wyrzykowski, R.; Dongarra, J.; Paprzycki, M.; Waśniewski, J., Parallel Processing and Applied Mathematics, 4th International Conference, PPAM 2001. Parallel Processing and Applied Mathematics, 4th International Conference, PPAM 2001, Lecture Notes in Computer Science, vol. 2328 (2002), Springer-Verlag), 236-244 · Zbl 1057.68750
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.