×

A discrete inter-species cuckoo search for flowshop scheduling problems. (English) Zbl 1348.90248

Summary: This paper presents a discrete version of the Inter-Species Cuckoo Search (ISCS) algorithm and illustrates its use for solving two significant types of the flow-shop scheduling problems. These are Hybrid Flow-shop Scheduling (HFS) and Permutation Flow-shop Sequencing Problems (PFSP). Hybrid flowshop scheduling problems are a generalization of flowshops having parallel machines in some stages and these problems are known to be NP-hard. A heuristic rule called the Smallest Position Value (SPV) is used to enable the continuous inter-species cuckoo search to be applied to most types of sequencing problems. Makespan and mean flow time are the objective functions considered and computational experiments are carried out to compare the proposed Discrete Inter-Species Cuckoo Search (DISCS) with other state-of-the-art meta-heuristic algorithms. Experimental results confirm the superiority of DISCS with respect to many other existing metaheuristic search algorithms.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

AS 136
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pinedo, M., Scheduling theory, algorithms and systems (1995), Prentice Hall, Englewood: Prentice Hall, Englewood Clifls, NJ · Zbl 1145.90393
[2] Arthanari, T. S.; Ramamurthy, K. G., An extension of two machines sequencing problem, Oper Res, 8, 4, 10-22 (1971)
[3] Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Math Oper Res, 1, 117-129 (1976) · Zbl 0396.90041
[4] Rajendran, C., A heuristics for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria, Int J Prod Res, 32, 2541-2558 (1994) · Zbl 0904.90076
[5] Rinnooy Kan, A. H.G., Machine scheduling problems: classification, complexity, and computations (1976), The Hague: The Hague Nijhoff · Zbl 0366.90092
[6] Rajendran, C.; Chaudhuri, D., A multi-stage parallel- processor flowshop problem with minimum flowtime, Eur J Oper Res, 57, 1, 111-122 (1992) · Zbl 0767.90040
[7] Hoogeveen, J. A.; Lenstra, J. K.; Veltman, B., Preemptive scheduling in a two-stage flow shop NP-Hard, Eur J Oper Res, 89, 1, 172-175 (1996) · Zbl 0908.90164
[8] Gupta, J. N.D., Two-stage, hybrid flowshop scheduling problem, J Oper Res Soc, 39, 4, 359-364 (1988) · Zbl 0639.90049
[9] 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)
[10] Campbell, H. G.; Dudek, R. A.; Smith, M. L., A heuristic algorithm for the n job, m machine sequencing problem, Manag Sci, 16, 10, B630-B637 (1970) · Zbl 0194.50504
[11] Dannenbring, D. G., An evaluation of flow shop sequencing heuristics, Manag Sci, 23, 11, 1174-1182 (1977) · Zbl 0371.90063
[12] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, OMEGA, 11, 1, 91-95 (1983)
[13] Taillard, E., Some efficient heuristic methods for the flowshop sequencing problems, Eur J Oper Res, 47, 65-74 (1990) · Zbl 0702.90043
[14] Framinan, J. M.; Leisten, R.; Ruiz-Usano, R., Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation, Eur J Oper Res, 141, 559-569 (2002) · Zbl 1081.90555
[15] Framinan, J. M.; Leisten, R., An efficient constructive heuristic for flowtime minimisation in permutation flowshops, OMEGA, 31, 311-317 (2003)
[16] Chang, Y.-L.; Ho, J. C., A new heuristic for the n-job, m machine flowshop problem, Eur J Oper Res, 52, 194-202 (1991) · Zbl 0725.90045
[17] Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion, Comput Oper Res, 31, 11 (2004) · Zbl 1068.68143
[18] Watson, J. P.; Barbulescu, L.; Whitley, L. D.; Howe, A. E., Contrasting structured and random permutation flowshop scheduling problems search space topology and algorithm performance, ORSA J Comput, 14, 2, 98-123 (2002) · Zbl 1238.90072
[19] Tseng, L.-Y.; Lin, Y.-T., A hybrid genetic local search algorithm for the permutation flowshop scheduling problem, Eur J Oper Res, 198, 1, 84-92 (2009) · Zbl 1163.90532
[20] Chen, S.-H.; Chang, P.-C.; Cheng, T. C.E.; Zhang, Q., A self-guided genetic algorithm for permutation flowshop scheduling problems, Comput Oper Res, 39, 7, 1450-1457 (2012) · Zbl 1251.90122
[21] Xu, R.; Chen, H.; Li, X., Makespan minimization on single batch-processing machine via ant colony optimization, Comput Oper Res, 39, 3, 582-593 (2012) · Zbl 1251.90201
[22] Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, Eur J Oper Res, 155, 2, 426-438 (2004) · Zbl 1045.90032
[23] Tseng, C.-T.; Liao, C.-J.; Luarn, P., A discrete version of particle swarm optimization for flowshop scheduling problems, Comput Oper Res, 34, 10, 3099-3111 (2007) · Zbl 1185.90083
[24] Pan, Q.-K.; Ruiz, R., Local search methods for the flowshop scheduling problem with flowtime minimization, Eur J Oper Res, 222, 1, 31-43 (2012) · Zbl 1253.90114
[25] Dong, X.; Huang, H.; Chen, P., An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion, Comput Oper Res, 36, 5, 1664-1669 (2009) · Zbl 1177.90153
[26] Taillard, E., Benchmarks for basic scheduling problems, Eur J Oper Res, 64, 278-285 (1993) · Zbl 0769.90052
[27] Gelders, L. F.; Sambandam, N., Four simple heuristics for scheduling a flow-shop, Int J Prod Res, 16, 221-231 (1978)
[28] Miyazaki, S.; Nishiyama, N.; Hashimoto, F., An adjacent pairwise approach to the mean flowtime scheduling problem, J Oper Res Soc Jpn, 21, 287-299 (1978)
[29] Miyazaki, S.; Nishiyama, N., Analysis for minimizing weighted mean flowtime in flowshop scheduling, J Oper Res Soc Jpn, 23, 118-132 (1980) · Zbl 0451.90074
[31] Tasgetiren, M. F.; Liang, Y.-C.; Sevkli, M.; Gencyilmaz, G., A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, Eur J Oper Res, 177, 3, 1930-1947 (2007) · Zbl 1110.90044
[32] Rajendran, C.; Chaudhuri, D., An efficient heuristic approach to the scheduling of jobs in a flowshop, Eur J Oper Res, 61, 318-325 (1991) · Zbl 0757.90036
[33] Rajendran, C., Heuristic algorithm for scheduling in a flowshop to minimize total flowtime, Int J Prod Econ, 29, 65-73 (1993)
[34] Rajendran, C.; Ziegler, H., An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs, Eur J Oper Res, 103, 129-138 (1997) · Zbl 0922.90089
[35] Wang, C.; Chu, C.; Proth, J.-M., Heuristic approaches for n/m/WF//PCi scheduling problems, Eur J Oper Res, 96, 636-644 (1997) · Zbl 0917.90203
[36] Woo, D. S.; Yim, H. S., A heuristic algorithm for mean flowtime objective in flowshop scheduling, Comput Oper Res, 25, 175-182 (1998) · Zbl 0904.90090
[37] Li, X.; Yin, M., A hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problem, Int J Prod Res IEEE Transactions on Evolutionary Computation, 51, 16 (2013)
[38] Liu, J.; Reeves, C. R., Constructive and composite heuristic solutions to the PkPCi scheduling problem, Eur J Oper Res, 132, 439-452 (2001) · Zbl 1134.90389
[39] Allahverdi, A.; Aldowaisan, T., New heuristics to minimize total completion time in m-machine flowshops, Int J Prod Econ, 77, 71-83 (2002)
[40] Framinan, J. M.; Leisten, R.; Ruiz-Usano, R., Comparison of heuristics for flowtime minimization in permutation flowshops, Comput Oper Res, 32, 5, 1237-1254 (2005) · Zbl 1074.90017
[41] Pan, Q.-K.; Ruiz, R., A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime, Comput Oper Res, 40, 1, 117-128 (2013) · Zbl 1349.90386
[42] Solomon, M. M.; Guinet, A.; Dussauchoy, A.; Kedia, P. K., A computational study of heuristics for two-stage flexible flowshops, Int J Prod Res, 34, 5, 1399-1415 (1996) · Zbl 0947.90540
[43] Oguz, C.; Ercan, M. F.; Cheng, T. C.E.; Fung, Y. F., Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop, Eur J Oper Res, 149, 2, 390-403 (2003) · Zbl 1059.90072
[44] He, D.; Babayan, A., Solving the n-job 3-stage flexible flowshop scheduling problem using an agent-based approach, Int J Prod Res, 42, 4, 777-799 (2004) · Zbl 1069.90038
[45] Wang, X.; Tang, L., A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers, Comput Oper Res, 36, 3, 907-918 (2009) · Zbl 1157.90429
[46] Ulusoy, G.; Serifoglu, F. S., Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach, J Oper Res Soc, 55, 5, 504-512 (2004) · Zbl 1070.90046
[47] Jahandar, M.; Rashidi, E.; Zandieh, M., An improved hybrid multiobjective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines, Int J Adv Manuf Technol, 49, 9-12, 1129-1139 (2010)
[48] Lin, S. W.; Ying, K. C., Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach, Int J Prod Res, 44, 16, 3161-3177 (2006) · Zbl 1159.90409
[49] Rajendran, C.; Ziegler, H., An efficient heuristic for scheduling in flowshop to minimze total weighted flowtime of jobs, Eur J Oper Res, 103, 129-138 (1997) · Zbl 0922.90089
[50] Reodecha, M.; Chaovalitwongse, P.; Jungwattanakit, J.; Werner, F., A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times and dual criteria, Comput Oper Res, 36, 2, 358-378 (2009) · Zbl 1157.90417
[51] Vazquez-Rodriguez, J. A.; Ruiz, R., The hybrid flow shop scheduling problem, Eur J Oper Res, 205, 1, 1-18 (2010) · Zbl 1188.90110
[52] Marichelvam, M. K.; Prabaharan, T.; Yang, X. S., A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems, IEEE Trans Evolut Comput, 18, 2, 301-305 (2014)
[54] Gandomi, A. H.; Yang, X. S.; Alavi, A. H., Cuckoo search algorithm: a meta-heuristics approach to solve structural optimization problems, Eng Comput, 29, 1, 17-35 (2013)
[55] Yang, X. S.; Cui, Z. H.; Xiao, R. B.; Gandomi, A. H.; Karamanoglu, M., Swarm intelligence and bio-inspired computation theory and applications (2013), Elsevier
[56] Yang, X. S.; Deb, S., Multi-objective cuckoo search for design optimization, Comput Oper Res, 40, 6, 1616-1624 (2013) · Zbl 1348.90650
[57] Quaarab, A.; Ahiod, B.; Yang, X. S., Discrete cuckoo search algorithm for travelling salesman problem, Neural Comput Appl, 24, 1659-1669 (2013)
[58] Chetty, S..; Adewumi, A. O., Comparison study of swarm intelligence techniques for the annual crop planning problem, IEEE Trans Evolut Comput, 18, 2, 258-268 (2014)
[59] Das, S.; Dasgupta, P.; Panigrahi, B. K., Inter-species cuckoo search via different Lévy flights, Swarm, Evolutionary and Memetic Computing (SEMCCO), 8297, 515-526 (2013)
[60] Pavlyukevich, I., Cooling down Lévy flights, J Phys A: Math Theor, 40, 12299-12313 (2007) · Zbl 1142.60051
[61] Reynolds., A. M.; Frye, M. A., Free-flight odor tracking in Drosophila is consistent with an opti- mal intermittent scale-free search, PLoS One, 2, e354 (2007)
[62] Avlyukevich, I., Lévy flights, non-local search and simulated annealing, Comput Phys, 226, 1830-1844 (2007) · Zbl 1125.65009
[63] Barthelemy, P.; Bertolotti, J.; Wiersma, D. S., A Lévy flight for light, Nature, 453, 495-498 (2008), (22 May)
[64] Hartigan, J. A.; Wong, M. A., A k-means clustering algorithm, J R Stat Soc, Ser C (Appl Stat), 28, 1, 100-108 (1979), (JSTOR 2346830) · Zbl 0447.62062
[66] Benyettou, M.; Belkadi, K.; Gourgand, M., Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem, J Appl Math Decis Sci, 2006, 1-17 (2006) · Zbl 1172.90513
[67] Kahraman, C.; Engin, O.; Kaya, I.; Yilmaz, M., An application of effective genetic algorithms for solving hybrid flow shop scheduling problems, Int J Comput Intell Syst, 1, 2 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.