×

ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness. (English) Zbl 1435.90074

Summary: This paper addresses a single-machine scheduling problem with sequence-dependent family setup times. In this problem the jobs are classified into families according to their similarity characteristics. Setup times are required on each occasion when the machine switches from processing jobs in one family to jobs in another family. The performance measure to be minimized is the total tardiness with respect to the given due dates of the jobs. The problem is classified as \(\mathcal{NP}\)-hard in the ordinary sense. Since the computational complexity associated with the mathematical formulation of the problem makes it difficult for optimization solvers to deal with large-sized instances in reasonable solution time, efficient heuristic algorithms are needed to obtain near-optimal solutions. In this work we propose three heuristics based on the Iterated Local Search (ILS) metaheuristic. The first heuristic is a basic ILS, the second uses a dynamic perturbation size, and the third uses a Path Relinking (PR) technique as an intensification strategy. We carry out comprehensive computational and statistical experiments in order to analyze the performance of the proposed heuristics. The computational experiments show that the ILS heuristics outperform a genetic algorithm proposed in the literature. The ILS heuristic with dynamic perturbation size and PR intensification has a superior performance compared to other heuristics.

MSC:

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

Software:

PERL; TTTPLOTS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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, 3, 985-1032 (2008) · Zbl 1137.90474 · doi:10.1016/j.ejor.2006.06.060
[2] Allahverdi, A., The third comprehensive survey on scheduling problems with setup times/costs, European Journal of Operational Research, 246, 2, 345-378 (2015) · Zbl 1347.90031 · doi:10.1016/j.ejor.2015.04.004
[3] Wang, J.-B.; Wang, J.-J., Single machine group scheduling with time dependent processing times and ready times, Information Sciences, 275, 226-231 (2014) · Zbl 1341.90057 · doi:10.1016/j.ins.2014.02.034
[4] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[5] Du, J.; Leung, J. Y., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 3, 483-495 (1990) · Zbl 0714.90052 · doi:10.1287/moor.15.3.483
[6] Chantaravarapan, S.; Gupta, J. N. D.; Smith, M. L., A hybrid genetic algorithm for minimizing total tardiness on a single machine with family setups, Proceedings of the Production and Operations Management Society Meeting (POMS ’03)
[7] Rubin, P. A.; Ragatz, G. L., Scheduling in a sequence dependent setup environment with genetic search, Computers & Operations Research, 22, 1, 85-99 (1995) · Zbl 0813.90065 · doi:10.1016/0305-0548(93)e0021-k
[8] Armentano, V. A.; Mazzini, R., A genetic algorithm for scheduling on a single machine with set-up times and due dates, Production Planning & Control, 11, 7, 713-720 (2000) · doi:10.1080/095372800432188
[9] França, P. M.; Mendes, A.; Moscato, P., A memetic algorithm for the total tardiness single machine scheduling problem, European Journal of Operational Research, 132, 1, 224-242 (2001) · Zbl 0996.90042 · doi:10.1016/s0377-2217(00)00140-5
[10] Sioud, A.; Gravel, M.; Gagné, C., A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times, Computers & Operations Research, 39, 10, 2415-2424 (2012) · Zbl 1251.90189 · doi:10.1016/j.cor.2011.12.017
[11] Tan, K. C.; Narasimhan, R., Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach, Omega, 25, 6, 619-634 (1997) · doi:10.1016/s0305-0483(97)00024-8
[12] Gagné, C.; Price, W. L.; Gravel, M., Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times, Journal of the Operational Research Society, 53, 8, 895-906 (2002) · Zbl 1130.90326 · doi:10.1057/palgrave.jors.2601390
[13] Liao, C.-J.; Juan, H.-C., An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups, Computers & Operations Research, 34, 7, 1899-1909 (2007) · Zbl 1112.90030 · doi:10.1016/j.cor.2005.07.020
[14] Gupta, S. R.; Smith, J. S., Algorithms for single machine total tardiness scheduling with sequence dependent setups, European Journal of Operational Research, 175, 2, 722-739 (2006) · Zbl 1142.90399 · doi:10.1016/j.ejor.2005.05.018
[15] Akrout, H.; Jarboui, B.; Siarry, P.; Rebaï, A., A GRASP based on DE to solve single machine scheduling problem with SDST, Computational Optimization and Applications, 51, 1, 411-435 (2012) · Zbl 1245.90027 · doi:10.1007/s10589-010-9333-7
[16] Arroyo, J. E. C.; Nunes, G. V. P.; Kamke, E. H., Iterative local search heuristic for the single machine scheduling problem with sequence dependent setup times and due dates, Proceedings of the 9th International Conference on Hybrid Intelligent Systems (HIS ’09), IEEE · doi:10.1109/his.2009.104
[17] Ying, K.-C.; Lin, S.-W.; Huang, C.-Y., Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic, Expert Systems with Applications, 36, 3, 7087-7092 (2009) · doi:10.1016/j.eswa.2008.08.033
[18] Ragatz, G. L., A branch-and-bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times, Proceedings of the 24th Annual Meeting of the Decision Sciences Institute, John Wiley & Sons
[19] Luo, X.; Chu, F., A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness, Applied Mathematics and Computation, 183, 1, 575-588 (2006) · Zbl 1127.90354 · doi:10.1016/j.amc.2006.05.127
[20] Sewell, E. C.; Sauppe, J. J.; Morrison, D. R.; Jacobson, S. H.; Kao, G. K., A BB’R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times, Journal of Global Optimization, 54, 4, 791-812 (2012) · Zbl 1258.90043 · doi:10.1007/s10898-011-9793-z
[21] Tanaka, S.; Araki, M., An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times, Computers & Operations Research, 40, 1, 344-352 (2013) · Zbl 1349.90402 · doi:10.1016/j.cor.2012.07.004
[22] Kacem, D., Lower bounds for tardiness minimization on a single machine with family setup times, Proceedings of the IMACS Multiconference on Computational Engineering in Systems Applications · doi:10.1109/CESA.2006.4281799
[23] Schaller, J., Scheduling on a single machine with family setups to minimize total tardiness, International Journal of Production Economics, 105, 2, 329-344 (2007) · doi:10.1016/j.ijpe.2004.10.020
[24] Pan, J. C.-H.; Su, C.-S., Single machine scheduling with due dates and class setups, Journal of the Chinese Institute of Engineers, 20, 5, 561-572 (1997)
[25] Baker, K. R.; Magazine, M. J., Minimizing maximum lateness with job families, European Journal of Operational Research, 127, 1, 126-139 (2000) · Zbl 0991.90064 · doi:10.1016/S0377-2217(99)00328-8
[26] Schaller, J. E.; Gupta, J. N., Single machine scheduling with family setups to minimize total earliness and tardiness, European Journal of Operational Research, 187, 3, 1050-1068 (2008) · Zbl 1137.90516 · doi:10.1016/j.ejor.2006.06.061
[27] Gupta, J. N. D.; Chantaravarapan, S., Single machine group scheduling with family setups to minimize total tardiness, International Journal of Production Research, 46, 6, 1707-1722 (2008) · Zbl 1160.90398 · doi:10.1080/00207540601009976
[28] van der Veen, J. A.; Woeginger, G. J.; Zhang, S., Sequencing jobs that require common resources on a single machine: a solvable case of the TSP, Mathematical Programming, 82, 1-2, 235-254 (1998) · Zbl 0920.90076 · doi:10.1007/bf01585874
[29] Karabati, S.; Akkan, C., Minimizing sum of completion times on a single machine with sequence-dependent family setup times, Journal of the Operational Research Society, 57, 3, 271-280 (2006) · Zbl 1089.90026 · doi:10.1057/palgrave.jors.2601989
[30] Jin, F.; Song, S.; Wu, C., A simulated annealing algorithm for single machine scheduling problems with family setups, Computers & Operations Research, 36, 7, 2133-2138 (2009) · Zbl 1158.90348 · doi:10.1016/j.cor.2008.08.001
[31] Jin, F.; Shiji, S.; Cheng, W., Dominance property based tabu search for single machine scheduling problems with family setups, Journal of Systems Engineering and Electronics, 20, 6, 1233-1238 (2009) · Zbl 1266.90104
[32] Jin, F.; Gupta, J. N. D.; Song, S.; Wu, C., Single machine scheduling with sequence-dependent family setups to minimize maximum lateness, Journal of the Operational Research Society, 61, 7, 1181-1189 (2010) · Zbl 1193.90101 · doi:10.1057/jors.2009.63
[33] Sels, V.; Vanhoucke, M., A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups, Computers & Operations Research, 39, 10, 2346-2358 (2012) · Zbl 1251.90008 · doi:10.1016/j.cor.2011.12.014
[34] Herr, O.; Goel, A., Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, European Journal of Operational Research, 248, 1, 123-135 (2016) · Zbl 1346.90351 · doi:10.1016/j.ejor.2015.07.001
[35] Vansteenwegen, P.; Souffriau, W.; Vanden Berghe, G.; Van Oudheusden, D., Iterated local search for the team orienteering problem with time windows, Computers & Operations Research, 36, 12, 3281-3290 (2009) · Zbl 1175.90239 · doi:10.1016/j.cor.2009.03.008
[36] Penna, P. H. V.; Subramanian, A.; Ochi, L. S., An iterated local search heuristic for the heterogeneous fleet vehicle routing problem, Journal of Heuristics, 19, 2, 201-232 (2013) · doi:10.1007/s10732-011-9186-y
[37] Ribas, I.; Companys, R.; Tort-Martorell, X., An efficient iterated local search algorithm for the total tardiness blocking flow shop problem, International Journal of Production Research, 51, 17, 5238-5252 (2013) · doi:10.1080/00207543.2013.802390
[38] Vansteenwegen, P.; Mateo, M., An iterated local search algorithm for the single-vehicle cyclic inventory routing problem, European Journal of Operational Research, 237, 3, 802-813 (2014) · Zbl 1338.90036 · doi:10.1016/j.ejor.2014.02.020
[39] Brandão, J., A deterministic iterated local search algorithm for the vehicle routing problem with backhauls, TOP, 24, 2, 445-465 (2016) · Zbl 1393.90010 · doi:10.1007/s11750-015-0404-x
[40] Dong, X.; Huang, H.; Chen, P., An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion, Computers & Operations Research, 36, 5, 1664-1669 (2009) · Zbl 1177.90153 · doi:10.1016/j.cor.2008.04.001
[41] Fanjul-Peyro, L.; Ruiz, R., Iterated greedy local search methods for unrelated parallel machine scheduling, European Journal of Operational Research, 207, 1, 55-69 (2010) · Zbl 1205.90121 · doi:10.1016/j.ejor.2010.03.030
[42] Della Croce, F.; Garaix, T.; Grosso, A., Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem, Computers & Operations Research, 39, 6, 1213-1217 (2012) · Zbl 1251.90130 · doi:10.1016/j.cor.2010.10.017
[43] Xu, H.; Lü, Z.; Cheng, T. C., Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness, Journal of Scheduling, 17, 3, 271-287 (2014) · Zbl 1297.90061 · doi:10.1007/s10951-013-0351-z
[44] Dong, X.; Nowak, M.; Chen, P.; Lin, Y., Self-adaptive perturbation and multi-neighborhood search for iterated local search on the permutation flow shop problem, Computers & Industrial Engineering, 87, 176-185 (2015) · doi:10.1016/j.cie.2015.04.030
[45] Santos, V. L. A.; Arroyo, J. E. C.; Carvalho, T. F., Iterated local search based heuristic for scheduling jobs on unrelated parallel machines with machine deterioration effect, Proceedings of the Genetic and Evolutionary Computation Conference Companion, ACM · doi:10.1145/2908961.2909053
[46] Lourenço, H. R.; Martin, O. C.; Stützle, T.; Glover, F.; Kochenberger, G. A., Iterated local search, Handbook of Metaheuristics. Handbook of Metaheuristics, International Series in Operations Research & Management Science, 57, 320-353 (2003), Kluwer Academic · doi:10.1007/0-306-48056-5_11
[47] Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search: framework and applications, Handbook of Metaheuristics, 363-397 (2010), Berlin, Germany: Springer, Berlin, Germany
[48] Hansen, P.; Mladenović, N., Variable neighborhood search, Search Methodologies, 313-337 (2014), Berlin, Germany: Springer, Berlin, Germany
[49] Laguna, M.; Martí, R., GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS Journal on Computing, 11, 1, 44-52 (1999) · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44
[50] Glover, F.; Barr, R. S.; Helgason, R. V.; Kennington, J. L., Tabu search and adaptive memory programing-advances, applications and challenges, Interfaces in Computer Science and Operations Research. Interfaces in Computer Science and Operations Research, Operations Research/Computer Science Interfaces Series, 1-75 (1996), New York, NY, USA: Springer, New York, NY, USA
[51] 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) · doi:10.1016/0305-0483(83)90088-9
[52] Resende, M. G. C.; Ribeiro, C. C.; Gendreau, M.; Potvin, J. Y., Handbook of metaheuristics, Greedy Randomized Adaptive Search Procedures: Advances, Hybridizations, and Applications, 219-249 (2010), Berlin, Germany: Springer, Berlin, Germany
[53] Vallada, E.; Ruiz, R.; Minella, G., Minimising total tardiness in the m-machine flowshop problem: a review and evaluation of heuristics and metaheuristics, Computers & Operations Research, 35, 4, 1350-1373 (2008) · Zbl 1179.90160 · doi:10.1016/j.cor.2006.08.016
[54] Montgomery, D. C., Design and Analysis of Experiments (2006), New York, NY, USA: John Wiley & Sons, New York, NY, USA
[55] den Besten, M.; Stützle, T., Neighborhoods revisited: an experimental investigation into the effectiveness of variable neighborhood descent for scheduling, Proceedings of the 4th Metaheuristics International Conference
[56] Subramanian, A.; Battarra, M.; Potts, C. N., An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times, International Journal of Production Research, 52, 9, 2729-2742 (2014) · doi:10.1080/00207543.2014.883472
[57] Aiex, R. M.; Resende, M. G.; Ribeiro, C. C., Ttt plots: a perl program to create time-to-target plots, Optimization Letters, 1, 4, 355-366 (2007) · Zbl 1220.90102 · doi:10.1007/s11590-006-0031-4
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.