Comparison of Three Meta Heuristics to Optimize Hybrid Flow Shop Scheduling Problem with Parallel Machines
This study compares three meta heuristics to minimize makespan (Cmax) for Hybrid Flow Shop (HFS) Scheduling Problem with Parallel Machines. This problem is known to be NP-Hard. This study proposes three algorithms among improvement heuristic searches which are: Genetic Algorithm (GA), Simulated Annealing (SA), and Tabu Search (TS). SA and TS are known as deterministic improvement heuristic search. GA is known as stochastic improvement heuristic search. A comprehensive comparison from these three improvement heuristic searches is presented. The results for the experiments conducted show that TS is effective and efficient to solve HFS scheduling problems.
[1] C. Y. Lee, L. Lei, M. Pinedo, "Current Trends in Deterministic
Scheduling," Annals of Operations Research, Vol. 70, pp. 1-41, 1997.
[2] M. L. Pinedo, "Scheduling: Theory, Algorithms, and Systems 3rd
Edition," New York: Springer Science and Business Media, 2008.
[3] D. P. Ronconi, L. R. R. Henriques, "Some Heuristic Algorithm for Total
Tardiness Minimization in a Flowshop with Blocking,"OMEGA The
International Journal of Management Science, vol. 37, pp. 272-281,
2009.
[4] E. Nowicki, C. Smutnicki,, "The Flow Shop with Parallel Machines: A
Tabu Search Approach," European Journal of Operational Research, vol.
106, pp. 226-253, 1998.
[5] S. A. Brah, L. L. Loo, "Heuristic for scheduling in a flow shop with
multiple processors," European Journal of Operation Research, vol. 113,
pp. 113-122, 1999.
[6] C. Kahraman, O. Engin, I. Kaya, M. K. Yilmaz, "An Application of
Effective Genetic Algorithm for Solving Hybrid Flowshop Scheduling
Problems," International Journal of Computational Intelligence Systems,
vol. 1, No. 2, pp. 134-147, 2008.
[7] C. Koulamas, "A New Constructive Heuristic for The Flowshop
Scheduling Problem," European Journal of Operational Research, vol.
105, pp. 66-71, 1998.
[8] D. P. Ronconi, "A Note on Constructive Heuristic for The Flowshop
Problem with Blocking," International Journal of Production Economics,
vol. 87, pp. 39-48, 2004.
[9] H. Zhou, W. Cheung, L. C. Leung, "Minimizing Weighted Tardiness of
Job-Shop Scheduling using Hybrid Genetic Algorithm," European
Journal of Operation Research, vol. 194, pp. 637-649, 2009.
[10] C. Low, Y. Yeh, "Genetic Algorithm-Based Heuristics for An Open
Shop Scheduling Problem with Setup, Processing, and Removal Times
Separated," Robotics and Computer-Integrated Manufacturing, vol. 25,
pp. 314-322, 2009.
[11] F. Chou, "An Experienced Learning Genetic Algorithm to Solve The
Single Machine Total Weighted Tardiness Scheduling Problem," Expert
System with Application, vol. 36, pp. 3857-3865, 2009.
[12] C. H. Martin, "A Hybrid Genetic Algorithm / Mathematical
Programming Approach to The Multi-Family Flow Shop Scheduling
Problem with Lot Streaming," OMEGA: The International Journal of
Management Science, vol. 37, pp. 126-137, 2009.
[13] T. Kellegoz, B. Toklu, J. Wilson, "Comparing Efficiencies of Genetic
Crossover Operators for One Machine Total Weighted Tardiness
Problem," Applied Mathematics and Computation, vol. 199, pp. 590-
598, 2008.
[14] Al-Harkan, I. M., 1997. "On Merging Sequencing and Scheduling
Theory with Genetic Algorithms to Solve Stochastic Job Shops",
Dissertation of doctor of philosophy, University of Oklahoma.
[15] http://ina.eivd.ch/Collaborateurs/etd/problemes.dir/ordonnancement.dir/
ordonnancement.html.
[1] C. Y. Lee, L. Lei, M. Pinedo, "Current Trends in Deterministic
Scheduling," Annals of Operations Research, Vol. 70, pp. 1-41, 1997.
[2] M. L. Pinedo, "Scheduling: Theory, Algorithms, and Systems 3rd
Edition," New York: Springer Science and Business Media, 2008.
[3] D. P. Ronconi, L. R. R. Henriques, "Some Heuristic Algorithm for Total
Tardiness Minimization in a Flowshop with Blocking,"OMEGA The
International Journal of Management Science, vol. 37, pp. 272-281,
2009.
[4] E. Nowicki, C. Smutnicki,, "The Flow Shop with Parallel Machines: A
Tabu Search Approach," European Journal of Operational Research, vol.
106, pp. 226-253, 1998.
[5] S. A. Brah, L. L. Loo, "Heuristic for scheduling in a flow shop with
multiple processors," European Journal of Operation Research, vol. 113,
pp. 113-122, 1999.
[6] C. Kahraman, O. Engin, I. Kaya, M. K. Yilmaz, "An Application of
Effective Genetic Algorithm for Solving Hybrid Flowshop Scheduling
Problems," International Journal of Computational Intelligence Systems,
vol. 1, No. 2, pp. 134-147, 2008.
[7] C. Koulamas, "A New Constructive Heuristic for The Flowshop
Scheduling Problem," European Journal of Operational Research, vol.
105, pp. 66-71, 1998.
[8] D. P. Ronconi, "A Note on Constructive Heuristic for The Flowshop
Problem with Blocking," International Journal of Production Economics,
vol. 87, pp. 39-48, 2004.
[9] H. Zhou, W. Cheung, L. C. Leung, "Minimizing Weighted Tardiness of
Job-Shop Scheduling using Hybrid Genetic Algorithm," European
Journal of Operation Research, vol. 194, pp. 637-649, 2009.
[10] C. Low, Y. Yeh, "Genetic Algorithm-Based Heuristics for An Open
Shop Scheduling Problem with Setup, Processing, and Removal Times
Separated," Robotics and Computer-Integrated Manufacturing, vol. 25,
pp. 314-322, 2009.
[11] F. Chou, "An Experienced Learning Genetic Algorithm to Solve The
Single Machine Total Weighted Tardiness Scheduling Problem," Expert
System with Application, vol. 36, pp. 3857-3865, 2009.
[12] C. H. Martin, "A Hybrid Genetic Algorithm / Mathematical
Programming Approach to The Multi-Family Flow Shop Scheduling
Problem with Lot Streaming," OMEGA: The International Journal of
Management Science, vol. 37, pp. 126-137, 2009.
[13] T. Kellegoz, B. Toklu, J. Wilson, "Comparing Efficiencies of Genetic
Crossover Operators for One Machine Total Weighted Tardiness
Problem," Applied Mathematics and Computation, vol. 199, pp. 590-
598, 2008.
[14] Al-Harkan, I. M., 1997. "On Merging Sequencing and Scheduling
Theory with Genetic Algorithms to Solve Stochastic Job Shops",
Dissertation of doctor of philosophy, University of Oklahoma.
[15] http://ina.eivd.ch/Collaborateurs/etd/problemes.dir/ordonnancement.dir/
ordonnancement.html.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:49836", author = "Wahyudin P. Syam and Ibrahim M. Al-Harkan", title = "Comparison of Three Meta Heuristics to Optimize Hybrid Flow Shop Scheduling Problem with Parallel Machines", abstract = "This study compares three meta heuristics to minimize makespan (Cmax) for Hybrid Flow Shop (HFS) Scheduling Problem with Parallel Machines. This problem is known to be NP-Hard. This study proposes three algorithms among improvement heuristic searches which are: Genetic Algorithm (GA), Simulated Annealing (SA), and Tabu Search (TS). SA and TS are known as deterministic improvement heuristic search. GA is known as stochastic improvement heuristic search. A comprehensive comparison from these three improvement heuristic searches is presented. The results for the experiments conducted show that TS is effective and efficient to solve HFS scheduling problems.
", keywords = "Flow shop, genetic algorithm, simulated annealing, tabu search.", volume = "4", number = "2", pages = "134-8", }
