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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328906Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1705
 C. Y. Lee, L. Lei, M. Pinedo, "Current Trends in Deterministic Scheduling," Annals of Operations Research, Vol. 70, pp. 1-41, 1997.
 M. L. Pinedo, "Scheduling: Theory, Algorithms, and Systems 3rd Edition," New York: Springer Science and Business Media, 2008.
 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.
 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.
 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.
 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.
 C. Koulamas, "A New Constructive Heuristic for The Flowshop Scheduling Problem," European Journal of Operational Research, vol. 105, pp. 66-71, 1998.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 http://ina.eivd.ch/Collaborateurs/etd/problemes.dir/ordonnancement.dir/ ordonnancement.html.