Abstract
In the paper, we proposed a hybrid improvement heuristic for permutation flow-shop problem based on the idea of evolutionary algorithm. The approach also employs constructive heuristic that gives a good initial solution. Hybrid GA-based improvement heuristic is applied in conjunction with three well-known constructive heuristics, namely CDS, Gupta’s algorithm and Palmer’s Slope Index. We tested our approach on Reeves’ benchmark set of 21 problem instances range from 20 to 75 jobs and 5 to 20 machines. Subsequently, we compared obtained results to the best-known upper-bound solutions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Springer, New Jersey (2008)
Gupta, J.N.D.: Analysis of Combinatorial Approach to Flowshop Scheduling Problems (1975)
Johnson, S.M.: Optimal Two and Three Stage Production Schedules with Set-Up Times. Naval Research Logistics Quarterly 1, 61–68 (1954)
Garey, M.R.D., Johnson, D.S., Sethi, R.: The Complexity of Flowshop and Jobshop Scheduling. Mathematics of Operations Research 1, 117–129 (1976)
Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading (1967)
Hejazi, S.R., Saghafian, S.: Flowshop Scheduling Problems with Makespan Criterion: A Review. International Journal of Production Research 43(14), 2895–2929 (2005)
Palmer, D.S.: Sequencing Jobs through a Multi-Stage Process in the Minimum Total Time - A Quick Method of Obtaining a Near Optimum. Opers. Res. Q 16, 101–107 (1965)
Campbell, H.G., Dudek, R.A., Smith, M.L.: A Heuristic Algorithm for the n Job, m Machine Sequencing Problem. Management Science 16(10), 630–637 (1970)
Dannenbring, D.G.: An Evaluation of Flow Shop Sequencing Heuristics. Management Science 23(11), 1174–1182 (1977)
Brucker, P., Jurisch, B., Sievers, B.: A Branch and Bound Algorithm for the Job Shop Scheduling Problem. Discrete Applied Mathematics 49(1), 109–127 (1994)
Gendreau, M., Laporte, G., Semet, F.: A Tabu Search Heuristic for the Undirected Selective Travelling Salesman Problem. European Journal of Operational Research 106(2-3), 539–545 (1998)
Murata, T., Ishibuchi, H., Tanaka, H.: Genetic algorithms for flowshop scheduling problems. Computers & Industrial Engineering 30(4), 1061–1071 (1996)
Balas, E., Vazacopoulos, A.: Guided Local Search with Shifting Bottleneck for Job Shop Scheduling. Management Science 44(2), 262–275 (1998)
Blum, C., Sampels, M.: An Ant Colony Optimization Algorithm for Shop Scheduling Problems. Journal of Mathematical Modelling and Algorithms 3(3), 285–308 (2004)
Page, E.S.: An approach to scheduling of jobs on the machines. J. Royal Stat. Soc. 23, 484–492 (1961)
Gupta, J.N.D.: Heuristic Algorithms for Multistage Flowshop Scheduling Problem. AIIE Transactions 4(1), 11–18 (1972)
Nawaz, M.E., Enscore, I., Ham, I.: A Heuristic Algorithm for the m Machine, n Job Flow Shop Sequence Problem. OMEGA 11(1), 91–95 (1983)
Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y.: A Survey of Scheduling Problems with Setup Times or Costs. European Journal of Operational Research 187, 985–1032 (2008)
Hendizadeh, S.H., ElMekkawy, T.Y., Wang, G.G.: Bi-Criteria Scheduling of a Flowshop Manufacturing Cell with Sequence Dependent Setup Time. European Journal of Industrial Engineering 1, 391–413 (2007)
Zobolas, G.I., Tarantilis, C.D., Ioannou, G.: Minimizing Makespan in Permutation Flow Shop Scheduling Problems Using a Hybrid Metaheuristic Algorithm. Computers and Operations Research 36(4), 1249–1267 (2009)
Ogbu, F.A., Smith, D.K.: The Application of the Simulated Annealing Algorithm to the Solution of the n/m/Cmax Flowshop Problem. Computers & Operations Research 17, 3243–3253 (1990)
Taillard, E.: Benchmarks for basic scheduling problems. European Journal of Operational Research 64, 278–285 (1993)
Nagar, A., Heragu, S.S., Haddock, J.: A Combined Branch-and-Bound and Genetic Algorithm Based Approach for a Flowshop-Scheduling Problem. Annal. Oper. Res. 63, 397–414 (1996)
Neppalli, V.R., Chen, C.L., Gupta, J.N.D.: Genetic Algorithms for the Two-Stage Bicriteria Flowshop Problem. Eur. J. Oper. Res. 95, 356–373 (1996)
Engin, O., Doyen, A.: A New Approach to Solve Hybrid Flow Shop Scheduling Problems by Artificial Immune System. Future Generation Computer Systems 20, 1083–1095 (2004)
Ribas, R., Leisten, J.M.: Review and Classification of Hybrid Flow Shop Scheduling Problems from a Production System and a Solutions Procedure Perspective. Computers and Operations Research 37(8), 1439–1454 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Semančo, P., Modrák, V. (2011). Hybrid GA-Based Improvement Heuristic with Makespan Criterion for Flow-Shop Scheduling Problems. In: Cruz-Cunha, M.M., Varajão, J., Powell, P., Martinho, R. (eds) ENTERprise Information Systems. CENTERIS 2011. Communications in Computer and Information Science, vol 220. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24355-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-24355-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24354-7
Online ISBN: 978-3-642-24355-4
eBook Packages: Computer ScienceComputer Science (R0)