An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives.(English)Zbl 1137.90514

Summary: Iterated Greedy (IG) algorithms are based on a very simple principle, are easy to implement and can show excellent performance. In this paper, we propose two new IG algorithms for a complex flowshop problem that results from the consideration of sequence dependent setup times on machines, a characteristic that is often found in industrial settings. The first IG algorithm is a straightforward adaption of the IG principle, while the second incorporates a simple descent local search. Furthermore, we consider two different optimization objectives, the minimization of the maximum completion time or makespan and the minimization of the total weighted tardiness. Extensive experiments and statistical analyses demonstrate that, despite their simplicity, the IG algorithms are new state-of-the-art methods for both objectives.

MSC:

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

References:

 [1] Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y., in press. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, doi:10.1016/j.ejor.2006.06.060; Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y., in press. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, doi:10.1016/j.ejor.2006.06.060 · Zbl 1137.90474 [2] Cesta, A.; Oddi, A.; Smith, S. F., Iterative flattening: A scalable method for solving multi-capacity scheduling problems, (Proceedings of the Seventeenth National Conference on Artificial Intelligence (2000), AAAI Press/The MIT Press: AAAI Press/The MIT Press Menlo Park, CA, USA), 742-747 [3] Congram, R. K.; Potts, C. N.; van de Velde, S., An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem, INFORMS Journal on Computing, 14, 1, 52-67 (2002) · Zbl 1238.90061 [4] Corwin, B. D.; Esogbue, A. O., Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic-programming approach, Naval Research Logistics, 21, 3, 515-524 (1974) · Zbl 0289.90026 [5] Das, S. R.; Gupta, J. N.D.; Khumawala, B. M., A savings index heuristic algorithm for flowshop scheduling with sequence-dependent set-up times, Journal of the Operational Research Society, 46, 11, 1365-1373 (1995) · Zbl 0858.90074 [6] Gupta, J. N.D., Flowshop schedules with sequence dependent setup times, Journal of the Operations Research Society of Japan, 29, 3, 206-219 (1986) · Zbl 0625.90042 [7] Gupta, J. N.D.; Darrow, W. P., The two-machine sequence dependent flowshop scheduling problem, European Journal of Operational Research, 24, 3, 439-446 (1986) · Zbl 0601.90075 [8] Hasija, S.; Rajendran, C., Scheduling in flowshops to minimize total tardiness of jobs, International Journal of Production Research, 42, 11, 2289-2301 (2004) · Zbl 1059.90070 [9] Hoos, H. H.; Stützle, T., Stochastic Local Search: Foundations and Applications (2004), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco, CA · Zbl 1126.68032 [10] Jacobs, L. W.; Brusco, M. J., A local-search heuristic for large set-covering problems, Naval Research Logistics, 42, 7, 1129-1140 (1995) · Zbl 0839.90085 [11] Laurent, M.; Van Hentenryck, P., Iterative relaxations for iterative flattening in cumulative scheduling, (Zilberstein, S.; Koehler, J.; Koenig, S., Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004) (2004), AAAI Press/The MIT Press: AAAI Press/The MIT Press Menlo Park, CA, USA), 200-208 [12] Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G. A., Handbook of Metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 321-353 · Zbl 1116.90412 [13] Marchiori, E.; Steenbeek, A., An evolutionary algorithm for large scale set covering problems with application 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, Germany), 367-381 [14] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the $$m$$ machine, $$n$$ job flowshop sequencing problem, Omega—International Journal of Management Science, 11, 1, 91-95 (1983) [15] Osman, I. H.; Potts, C. N., Simulated annealing for permutation flowshop scheduling, Omega—International Journal of Management Science, 17, 6, 551-557 (1989) [16] Parthasarathy, S.; Rajendran, C., An experimental evaluation of heuristics for scheduling in a real-life flowshop with sequence-dependent setup times of jobs, International Journal of Production Economics, 49, 3, 255-263 (1997) [17] Parthasarathy, S.; Rajendran, C., A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs – a case study, Production Planning & Control, 8, 5, 475-483 (1997) [18] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice-Hall: Prentice-Hall Upper Saddle, NJ · Zbl 1145.90394 [19] Rajendran, C.; Ziegler, H., A heuristic for scheduling to minimize the sum of weighted flowtime of jobs in a flowshop with sequence-dependent setup times of jobs, Computers & Industrial Engineering, 33, 1-2, 281-284 (1997) [20] Rajendran, C.; Ziegler, H., Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times, European Journal of Operational Research, 149, 3, 513-522 (2003) · Zbl 1033.90043 [21] Rajendran, C.; 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 [22] Ríos-Mercado, R. Z.; Bard, J. F., Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups, Computers & Operations Research, 25, 5, 351-366 (1998) · Zbl 1040.90569 [23] Ríos-Mercado, R. Z.; Bard, J. F., Heuristics for the flow line problem with setup costs, European Journal of Operational Research, 110, 1, 76-98 (1998) · Zbl 0948.90070 [24] Ríos-Mercado, R. Z.; Bard, J. F., A branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times, IIE Transactions, 31, 8, 721-731 (1999) [25] Ríos-Mercado, R. Z.; Bard, J. F., An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup times, Journal of Heuristics, 5, 1, 53-70 (1999) · Zbl 0948.90071 [26] Ríos-Mercado, R. Z.; Bard, J. F., The flow shop scheduling polyhedron with setup times, Journal of Combinatorial Optimization, 7, 3, 291-318 (2003) · Zbl 1053.90045 [27] Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 2, 479-494 (2005) · Zbl 1066.90038 [28] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 3, 2033-2049 (2007) · Zbl 1110.90042 [29] 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, 1, 34-54 (2005) · Zbl 1112.90338 [30] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics, 159, 139-171 (2000) · Zbl 0997.90105 [31] Simons, J. V., Heuristics in flow shop scheduling with sequence dependent setup times, Omega—International Journal of Management Science, 20, 2, 215-225 (1992) [32] Srikar, B. N.; Ghosh, S., A MILP model for the $$n$$-job, $$m$$-stage flowshop with sequence dependent set-up times, International Journal of Production Research, 24, 6, 1459-1474 (1986) · Zbl 0605.90066 [33] Stafford, E. F.; Tseng, F. T., On the Srikar-Ghosh MILP model for the $$n$$×$$m$$ SDST flowshop problem, International Journal of Production Research, 28, 10, 1817-1830 (1990) [34] Stafford, E. F.; Tseng, F. T., Two models for a family of flowshop sequencing problems, European Journal of Operational Research, 142, 2, 282-293 (2002) · Zbl 1082.90530 [35] 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. [36] Taillard, E., Some efficient heuristic methods for the flow-shop sequencing problem, European Journal of Operational Research, 47, 1, 65-74 (1990) · Zbl 0702.90043 [37] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 2, 278-285 (1993) · Zbl 0769.90052 [38] Tseng, F. T.; Stafford, E. F., Two MILP models for the $$n$$×$$m$$ SDST flowshop sequencing problem, International Journal of Production Research, 39, 8, 1777-1809 (2001) · Zbl 1009.90042
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.