Abstract
In this paper, a modified cuckoo search (MCS) algorithm is proposed for solving the permutation flow shop scheduling problem (PFSP). Firstly, to make CS suitable for solving PFSPs, the largest position value (LPV) rule is presented to convert the continuous values of individuals in CS to job permutations. Secondly, after the CS-based exploration, a simple but efficient local search, which is designed according to the PFSPs’ landscape, is applied to emphasize exploitation. In addition, the proposed algorithm is combined with the path relinking. Simulation results and comparisons based on benchmarks demonstrate the MCS is an effective approach for flow shop scheduling problems.
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
Similar content being viewed by others
References
Garey, E.L., Johnson, D.S., Sethi, R.: The complexity of flow-shop and job-shop scheduling. Math. Oper. Res. 1, 117–129 (1976)
Croce, F.D., Narayan, V., Tadei, R.: The two-machine total completion time flow shop problem. Eur. J. Oper. Res. 90, 227–237 (1996)
Croce, F.D., Ghirardim, M., Tadei, R.: An improved branch-and-bound algorithm for the two machine total completion time flow-shop problem. Eur. J. Oper. Res. 139, 293–301 (2002)
Palmer, D.S.: Sequencing jobs through a multistage process in the minimum total time: a quick method of obtaining a near-optimum. Oper. Res. Q. 16, 101–107 (1965)
Gupta, J.N.D.: Heuristic algorithms for multistage flowshop scheduling problem. AIIE Trans. 4, 11–18 (1972)
Zhou, J.-H., Ye, C.-M., Sheng, X.-H.: Research on permutation flow-shop scheduling problem by intelligent water drop algorithm. Comput. Sci. 40(9), 250–253 (2013)
Shen, J., Wang, L., Wang, S.: Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem. J. Tsinghua Univ. (Sci. Technol.) 55(11), 1184–1189 (2015)
Zheng, X., Wang, L., Wang, S.: A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem. Control Theor. Appl. 31(2), 159–164 (2014)
Yang, X.S., Deb, S.: Cuckoo search via Levy flights. In: Proceedings of World Congress on Nature and Biologically Inspired Computing, pp. 210–214. IEEE Publications, India (2009)
Carlier, J.: Ordonnancements a contraintes disjonctives. R.A.I.R.O. Recherche Operationelle/Oper. Res. 12, 333–351 (1978)
Reeves, C.R.: A genetic algorithm for flow-shop sequencing. Comput. Oper. Res. 22, 5–13 (1995)
Wang, L., Wu, H., Tang, F., Zheng, D.-Z.: A hybrid quantum-inspired genetic algorithm for flow shop scheduling. In: Huang, D.-S., Zhang, X.-P., Huang, G.-B. (eds.) ICIC 2005. LNCS, vol. 3645, pp. 636–644. Springer, Heidelberg (2005)
Lian, Z.G., Gu, X.S., Jiao, B.: A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos, Solitons Fractals 35, 851–861 (2008)
Acknowledgments
This work is supported by the Project of Guangxi High School Science Foundation under Grant no. KY2015YB539.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Zheng, HQ., Zhou, YQ., Xie, C. (2016). Modified Cuckoo Search Algorithm for Solving Permutation Flow Shop Problem. In: Huang, DS., Bevilacqua, V., Premaratne, P. (eds) Intelligent Computing Theories and Application. ICIC 2016. Lecture Notes in Computer Science(), vol 9771. Springer, Cham. https://doi.org/10.1007/978-3-319-42291-6_71
Download citation
DOI: https://doi.org/10.1007/978-3-319-42291-6_71
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-42290-9
Online ISBN: 978-3-319-42291-6
eBook Packages: Computer ScienceComputer Science (R0)