Comparison of Three Meta Heuristics to Optimize Hybrid Flow Shop Scheduling Problem with Parallel Machines

Authors: Wahyudin P. Syam, Ibrahim M. Al-Harkan

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.

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

References:

[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.