College of System Engineering, National University of Defense Technology, Changsha 410015, China
School of Artificial Intelligence, Jianghan University, Wuhan 430056, China
Xi’an Satellite Control Center, Xi’an 710043, China
School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
Show Author Information
Hide Author Information
Abstract
In a local search algorithm, one of its most important features is the definition of its neighborhood which is crucial to the algorithm’s performance. In this paper, we present an analysis of neighborhood combination search for solving the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness (SMSWT). First, We propose a new neighborhood structure named Block Swap (B1) which can be considered as an extension of the previously widely used Block Move (B2) neighborhood, and a fast incremental evaluation technique to enhance its evaluation efficiency. Second, based on the Block Swap and Block Move neighborhoods, we present two kinds of neighborhood structures: neighborhood union (denoted by B1B2) and token-ring search (denoted by B1B2), both of which are combinations of B1 and B2. Third, we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms: the Iterated Local Search Algorithm () and the Hybrid Evolutionary Algorithm (HEA) to investigate the performance of the neighborhood union and token-ring search. Extensive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods. Tested on the 120 public benchmark instances, our HEA has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics. We have also tested the HEA algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time. HEA is able to match the optimal or the best known results for all the 64 instances. In particular, the computational time for reaching the best well-known results for five challenging instances is reduced by at least 61.25%.
No abstract is available for this article. Click the button above to view the PDF directly.
Electronic Supplementary Material
Download File(s)
JCST-2110-12007-Highlights.pdf (287.2 KB)
References
[1]
Hoos H H, Stützle T. Stochastic Local Search: Foundations and Applications. Elsevier, 2004.
[2]
Lin S, Kernighan B W. An effective heuristic algorithm for the traveling-salesman problem. Operations Research , 1973, 21(2): 498–516. DOI: 10.1287/opre.21.2.498.
Peng B, Lü Z P, Cheng T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers & Operations Research , 2015, 53: 154–164. DOI: 10.1016/j.cor.2014.08.006.
Lü Z P, Hao J K, Glover F. Neighborhood analysis: A case study on curriculum-based course timetabling. Journal of Heuristics , 2011, 17(2): 97–118. DOI: 10.1007/s10732- 010-9128-0.
Xu H Y, Lü Z P, Cheng T C E. Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness. Journal of Scheduling , 2014, 17(3): 271–287. DOI: 10.1007/s10951-013- 0351-z.
Xu H Y, Lü Z P, Yin A H, Shen L J, Buscher U. A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times. Computers & Operations Research , 2014, 50: 47–60. DOI: 10.1016/j.cor.2014.04.009.
González M, Palacios J J, Vela C R, Hernández-Arauzo A. Scatter search for minimizing weighted tardiness in a single machine scheduling with setups. Journal of Heuristics , 2017, 23(2/3): 81–110. DOI: 10.1007/s10732-017-9325-1.
González M A, Vela C R. An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups. Applied Soft Computing , 2015, 37: 506–518. DOI: 10.1016/j.asoc.2015.07.050.
Tasgetiren M F, Pan Q K, Ozturkoglu Y, Chen A H L. A memetic algorithm with a variable block insertion heuristic for single machine total weighted tardiness problem with sequence dependent setup times. In Proc. the 2016 IEEE Congress on Evolutionary Computation, Jul. 2016, pp.2911–2918. DOI: 10.1109/cec.2016.7744157.
Subramanian A, Farias K. Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times. Computers & Operations Research , 2017, 79: 190–206. DOI: 10.1016/j.cor.2016.10.008.
Graham R L, Lawler E L, Lenstra J K, Kan A H G R. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics , 1979, 5: 287–326. DOI: 10.1016/s0167-5060(08)70356-x.
Tanaka S, Araki M. An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research , 2013, 40(1): 344–352. DOI: 10.1016/j.cor.2012.07.004.
Tanaka S, Fujikuma S. A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. Journal of Scheduling , 2012, 15(3): 347–361. DOI: 10.1007/s10951-011-0242-0.
Abdul-Razaq T S, Potts C N, Van Wassenhove L N. A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Applied Mathematics , 1990, 26(2/3): 235–253. DOI: 10.1016/0166-218x(90)90103-j.
Potts C N, Van Wassenhove L N. A branch and bound algorithm for the total weighted tardiness problem. Operations Research , 1985, 33(2): 363–377. DOI: 10.1287/opre.33.2.363.
Potts C N, Van Wassenhove L N. Dynamic programming and decomposition approaches for the single machine total tardiness problem. European Journal of Operational Research , 1987, 32(3): 405–414. DOI: 10.1016/s0377-2217(87)80008-5.
Luo X C, 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 , 2006, 183(1): 575–588. DOI: 10.1016/j.amc.2006.05.127.
Bigras L P, Gamache M, Savard G. The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optimization , 2008, 5(4): 685–699. DOI: 10.1016/j.disopt.2008.04.001.
Vepsalainen A P J, Morton T E. Priority rules for job shops with weighted tardiness costs. Management Science , 1987, 33(8): 1035–1047. DOI: 10.1287/mnsc.33.8.1035.
Lee Y H, Bhaskaran K, Pinedo M. A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Trans. , 1997, 29(1): 45–52. DOI: 10.1080/07408179708966311.
Tan K C, Narasimhan R. Minimizing tardiness on a single processor with sequence-dependent setup times: A simulated annealing approach. Omega , 1997, 25(6): 619–634. DOI: 10.1016/s0305-0483(97)00024-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 , 2000, 11(7): 713–720. DOI: 10.1080/095372800432188.
França P M, Mendes A, Moscato P. A memetic algorithm for the total tardiness single machine scheduling problem. European Journal of Operational Research , 2001, 132(1): 224–242. DOI: 10.1016/s0377-2217(00)00140-5.
Liao C J, Juan H C. An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers & Operations Research , 2007, 34(7): 1899–1909. DOI: 10.1016/j.cor.2005.07.020.
Gupta S R, Smith J S. Algorithms for single machine total tardiness scheduling with sequence dependent setups. European Journal of Operational Research , 2006, 175(2): 722–739. DOI: 10.1016/j.ejor.2005.05.018.
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 , 2009, 36(3): 7087–7092. DOI: 10.1016/j.eswa.2008.08.033.
Tasgetiren M F, Sevkli M, Liang Y C, Gençyilmaz G. Particle swarm optimization algorithm for single machine total weighted tardiness problem. In Proc. the 2004 Congress on Evolutionary Computation, Jun. 2004, pp.1412–1419. DOI: 10.1109/cec.2004.1331062.
Fatih Tasgetiren M, Liang Y C, Sevkli M, Gencyilmaz G. Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem. International Journal of Production Research , 2006, 44(22): 4737–4754. DOI: 10.1080/00207540600620849.
Bilge Ü, Kurtulan M, Kıraç F. A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operational Research , 2007, 176(3): 1423–1435. DOI: 10.1016/j.ejor.2005.10.030.
Chou F D. An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem. Expert Systems with Applications , 2009, 36(2): 3857–3865. DOI: 10.1016/j.eswa.2008.02.040.
Wang X P, Tang L X. A population-based variable neighborhood search for the single machine total weighted tardiness problem. Computers & Operations Research , 2009, 36(6): 2105–2110. DOI: 10.1016/j.cor.2008.07.009.
Cicirello V A, Smith S F. Enhancing stochastic search performance by value-biased randomization of heuristics. Journal of Heuristics , 2005, 11(1): 5–34. DOI: 10.1007/s10732-005-6997-8.
Cicirello V A. Non-wrapping order crossover: An order preserving crossover operator that respects absolute position. In Proc. the 8th Annual Conference on Genetic and Evolutionary Computation, Jul. 2006, pp.1125–1132. DOI: 10.1145/1143997.1144177.
Anghinolfi D, Paolucci M. A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. International Journal of Operations Research , 2008, 5(1): 44–60.
Lin S W, Ying K C. Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. The International Journal of Advanced Manufacturing Technology , 2007, 34(11/12): 1183–1190. DOI: 10.1007/s00170-006-0693-1.
Valente J M S, Alves R A F S. Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Computers & Operations Research , 2008, 35(7): 2388–2405. DOI: 10.1016/j.cor.2006.11.004.
Anghinolfi D, Paolucci M. A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. European Journal of Operational Research , 2009, 193(1): 73–85. DOI: 10.1016/j.ejor.2007.10. 044.
Tasgetiren M F, Pan Q K, Liang Y C. A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research , 2009, 36(6): 1900–1915. DOI: 10.1016/j.cor.2008.06.007.
Kirlik G, Oguz C. A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine. Computers & Operations Research , 2012, 39(7): 1506–1520. DOI: 10.1016/j.cor.2011.08.022.
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 , 2014, 52(9): 2729–2742. DOI: 10.1080/00207543.2014.883472.
Di Gaspero L, Schaerf A. Neighborhood portfolio approach for local search applied to timetabling problems. Journal of Mathematical Modelling and Algorithms , 2006, 5(1): 65–89. DOI: 10.1007/s10852-005-9032-z.
Glover F, McMillan C, Glover R. A heuristic programming approach to the employee scheduling problem and some thoughts on “managerial robots”. Journal of Operations Management , 1984, 4(2): 113–128. DOI: 10.1016/0272-6963(84)90027-5.
Rubin P A, Ragatz G L. Scheduling in a sequence dependent setup environment with genetic search. Computers & Operations Research , 1995, 22(1): 85–99. DOI: 10.1016/0305-0548(93)e0021-k.
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 , 2002, 53(8): 895–906. DOI: 10.1057/palgrave.jors.2601390.
Liu X-L, Xu H-Y, Chen J-M, et al. Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time. Journal of Computer Science and Technology, 2024, 39(3): 737-752. https://doi.org/10.1007/s11390-023-2007-6
