A Hybrid Genetic Algorithm for the Sequence Dependent Flow-Shop Scheduling Problem
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:55854", author = "Mohammad Mirabi", title = "A Hybrid Genetic Algorithm for the Sequence Dependent Flow-Shop Scheduling Problem", 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", volume = "5", number = "7", pages = "1335-7", }
