A Hybrid Iterated Greedy Algorithm for No-Wait Flowshop with Sequence Dependent Setup Times to Minimize Makespan

Abstract:

In this paper, the widespread no-wait flowshop in industries is considered with sequence dependent setup times to minimize makespan. A hybrid iterated greedy framework is constructed. A destruction-reconstruction procedure and a composite local search are introduced to improve the initial solution, respectively. To enhance the diversification of the proposal, a solution acceptance criterion is adopted to accept a worse solution with a probability. An efficient hybrid iterated greedy algorithm is investigated for the considered problem. The proposal is compared with the existing best deterministic heuristics and non-deterministic algorithm on Taillards benchmark instances. Experimental results show that the proposal gets best performance against the deterministic heuristics. The proposed algorithm outperforms the non-deterministic one on most instances with the same computation-time.

• Periodical: Advanced Materials Research (Volume 933)
• Pages: 459-466
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.933.459
• Online since: May 2014
• Authors: Wei Jin Zhuang*, Tao Xu, Ming Yang Sun
• Keywords: Iterated Greedy, Local Search, Make Span, No-Wait Flowshop, Sequence Dependent Setup Time

References

[1] S.M. Johnson. Optimal two and three-state production schedules with setup times included. Naval Research Logistics Quarterly, 1954, 1: 61-68.

DOI: 10.1002/nav.3800010110

[2] J.N.D. Gupta. Flowshop schedules with sequence dependent setup times. Journal of Operations Research Society of Japan, 1986, 29 (3): 206-219.

DOI: 10.15807/jorsj.29.206

[3] L. Bianco, P. Dell'Olmo, and S. Giordani. Flow shop no-wait scheduling with sequence dependent setup times and release dates. INFOR, 1999, 37(1): 3-19.

DOI: 10.1080/03155986.1999.11732365

[4] C.A. Daniella and S.N. Marcelo. A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem. International Journal of Industrial Engineering Computations, 2011, 2: 155-166.

DOI: 10.5267/j.ijiec.2010.05.003

[5] S.I. Brown, R. Mcgarvey and J. A. Ventura. Total flowtime and makespan for a no-wait m-machine flowshop with set-up times separated. Journal of the Operational Research Society, 2004, 55 (6): 614-621.

DOI: 10.1057/palgrave.jors.2601695

[6] P.M. FranÇa, G. Tin, and L.S. Buriol. Genetic algorithms for the no-wait flowshop sequencing problem with time restrictions. International Journal of Production Research, 2006, 44(5): 939-957.

DOI: 10.1080/00207540500282914

[7] T. Aldowaisan and A. Allahverdi. New heuristic for no-wait flowshop to minimize makespan. Computers and Operations Research, 2003, 30 (8): 1219-1231.

DOI: 10.1016/s0305-0548(02)00068-0

[8] R. Ruiz, C. Maroto, and J. Alcaraz. Solving the flowshop scheduling problem with sequence-dependent setup times using advanced metaheuristics. European Journal of Operational Research, 2005, 187 (3): 1143-1159.

DOI: 10.1016/j.ejor.2004.01.022

[9] Y Gajpal, C Rajendran, and H Ziegler. An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. International Journal of Advanced Manufacturing Technology, 2006, 30: 416–424.

DOI: 10.1007/s00170-005-0093-y

[10] R. Ruiz and T. Stützle. An Iterated Greedy heuristic for sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 2008, 187(3): 1143-1159.

DOI: 10.1016/j.ejor.2006.07.029

[11] C. Rajendran. Heuristic algorithm for scheduling in a flowshop to minimize total flowtime. International Journal of Production Economics, 1993, 29(1): 65-73.

DOI: 10.1016/0925-5273(93)90024-f

[12] M. Nawaz, E.E. Jr. Enscore, and I. Ham. A heuristic algorithm for the m machine, n job flowshop sequencing problem. Omega, 1983, 11(1): 91-95.

DOI: 10.1016/0305-0483(83)90088-9