A Hybrid Genetic Algorithm for the Sequence Dependent Flow-Shop Scheduling Problem

Authors: Mohammad Mirabi

Abstract:

Flow-shop scheduling problem (FSP) deals with the scheduling of a set of jobs that visit a set of machines in the same order. The FSP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To meet the requirements on time and to minimize the make-span performance of large permutation flow-shop scheduling problems in which there are sequence dependent setup times on each machine, this paper develops one hybrid genetic algorithms (HGA). Proposed HGA apply a modified approach to generate population of initial chromosomes and also use an improved heuristic called the iterated swap procedure to improve initial solutions. Also the author uses three genetic operators to make good new offspring. The results are compared to some recently developed heuristics and computational experimental results show that the proposed HGA performs very competitively with respect to accuracy and efficiency of solution.

Keywords: Hybrid genetic algorithm, Scheduling, Permutationflow-shop, Sequence dependent

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332578

References:

[1] B. Ekşioğlu, S.D. Ekşioğlu and P. Jain, "A tabu search algorithm for the flow-shop scheduling problem with changing neighborhoods", Computers & Industrial Engineering, Vol. 54, 2008, pp. 1-11.
[2] Allahverdi, C.T. Ng, T.C.E. Cheng and M.Y. Kovalyov, "A survey of scheduling problems with setup times or costs", European Journal of Operational Research, Vol. 187, 2008, pp. 985-1032.
[3] J.N.D. Gupta, "Flow-shop schedules with sequence dependent setup times" Journal of the Operations Research Society of Japan, Vol. 29, 1986, pp. 206-219.
[4] J.N.D. Gupta and W.P. Darrow, "The two-machine sequence dependent flow-shop scheduling problem", European Journal of Operational Research, Vol. 24, 1986, pp. 439-446.
[5] S.M. Johnson, "Optimal two- and three-stage production schedules with setup times included", Naval Research Logistics Quarterly, Vol. 1, 1954, pp. 61-68.
[6] M.R. Garey, D.S. Johnson and R. Sethi, "The complexity of flow-shop and jobshop scheduling", Mathematics of Operations Research, Vol. 1, 1976, pp. 117-129.
[7] H.G. Campbell, R.A. Dudek and M.L. Smith, "A heuristic algorithm for the n job, m machine sequencing problem", Management Science, Vol. 16, 1970, pp. B630-B637.
[8] M. Nawaz, E.E. Enscore and I. Ham, "A heuristic algorithm for the mmachine, n-job flow-shop sequencing problem", OMEGA, The International Journal of Management Science, Vol. 11, 1983, pp. 91-95.
[9] I.H. Osman and C.N. Potts, "Simulated annealing for permutation flowshop scheduling", OMEGA, The International Journal of Management Science, Vol. 17, 1989, pp. 551-557.
[10] M. Widmer and A. Hertz, "A new heuristic method for the flow shop sequencing problem", European Journal of Operational Research, Vo. 41, 1989, pp. 186-193.
[11] C.R. Reeves, "A genetic algorithm for flow-shop sequencing" Computers and Operations Research, Vol. 22, 1995, pp. 5-13.
[12] B.N. Srikar and S. Ghosh, "A MILP model for the n-job M-stage flowshop with sequence dependent set-up times", International Journal of Production Research, Vo. 24, 1986, pp. 1459-1474.
[13] E.F. Stafford and T.F. Tseng, "On the Srikar-Ghosh MILP model for the N×M SDST flow-shop problem", International Journal of Production Research, Vol. 28, 1990, pp. 1817-1830.
[14] R.Z. Ríos-Mercado and J.F. Bard, "Computational experience with a branch-and-cut algorithm for flow-shop scheduling with setups", Computers & Operations Research, Vol. 25, 1998, pp. 351-366.
[15] F.T. Tseng and E.F. Stafford, "Two MILP models for the N×M SDST flow-shop sequencing problem", International Journal of Production Research, Vol. 39, 2001, pp. 1777-1809.
[16] R.Z. Ríos-Mercado and J.F. Bard, "A branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times", IIE Transactions, Vol. 31, 1999a, pp. 721-731.
[17] R.Z. Ríos-Mercado and J.F. Bard, An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup times, Journal of Heuristics, Vol. 5, 1999b, pp.53-70.
[18] R. Ruiz, C. Maroto and J. Alcaraz, "Solving the flow-shop scheduling problem with sequence dependent setup times using advanced metaheuristics", European Journal of Operational Research, Vol. 165, 2005, pp. 34-54.
[19] R. Ruiz and T. Stutzle, "An iterated greedy heuristic for the sequence dependent setup times flow-shop with makespan and weighted tardiness objectives", European Journal of Operational Research, Vol. 87, 2008, pp. 1143-1159.
[20] R.Z. Ríos-Mercado and J.F. Bard, "The flow shop scheduling polyhedron with setup times", Journal of Combinatorial Optimization, Vol. 7, 2003, pp. 291-318.
[21] E.F. Stafford and F.T. Tseng, "Two models for a family of flow-shop sequencing problems", European Journal of Operational Research, Vol. 142, 2002, pp. 282-293.
[22] F.T. Tseng, J.N.D. Gupta and E.F. Stafford, "A penalty-based heuristic algorithm for the permutation flow-shop scheduling problem with sequence-dependent set-up times", Journal of the Operational Research Society, Vol. 57, 2005, pp. 541-551.
[23] J.U. Sun, and H. Hwang, "Scheduling problem in a twomachine flow line with the N-step prior-job-dependent set-up times", International Journal of Systems Science, Vol. 32, 2001, pp. 375-385.
[24] X. Li, Y. Wang and C. Wu, "Heuristic algorithms for large flow-shop scheduling problems", Intelligent Control and Automation, Vol. 4, 2004, pp. 2999 - 3003.
[25] D. Laha and U.K. Chakraborty, "An efficient stochastic hybrid heuristic for flow-shop scheduling", Engineering Applications of Artificial Intelligence, Vol. 20, 2007, pp. 851-856.
[26] K. Sheibani, "A fuzzy greedy heuristic for permutation flow-shop scheduling" Journal of the Operational Research Society, Vol. 61, 2010, pp. 813-818.
[27] I.H. Osman and J.P. Kelly, Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, Boston, 1996.
[28] W. Ho and P. Ji, "Component scheduling for chip shooter machines: a hybrid genetic algorithm approach", Computers and Operations Research, Vol. 30, 2003, pp. 2175-2189.
[29] W. Ho and P. Ji, "A hybrid genetic algorithm for component sequencing and feeder arrangement", Journal of Intelligent Manufacturing, Vol. 15, 2004, pp. 307-315.
[30] D.E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning", Addison-Wesley, New York, 1989.
[31] M. Gen and R. Cheng, "Genetic Algorithms and Engineering Design", Wiley, New York, 1997.