Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

Xiao-Lu Liu; Hong-Yun Xu; Jia-Ming Chen; Zhou-Xing Su; Zhi-Peng Lyu; Jun-Wen Ding

doi:10.1007/s11390-023-2007-6

AI Chat Paper

Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.

Chat more with AI

| Sign up

Browse by Subject

Search for peer-reviewed journals with full access.

Journals A - Z

About Us

Discover the SciOpen Platform and Achieve Your Research Goals with Ease.

About Us

Publish with Us

Support

Search articles, authors, keywords, DOl and etc.

Published Date

Reset Search

{{expandStatus?'Exit ':''}}Advanced Search

Journals A - Z

About Us

Publish with Us

Support

Article Link

Cite

EndNote(RIS) BibTeX

Collect

Submit Manuscript

Show Outline

Outline

Show full outline

Hide outline

Outline

Show full outline

Hide outline

Regular Paper

Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

Xiao-Lu Liu^¹, Hong-Yun Xu^², Jia-Ming Chen^³, Zhou-Xing Su^⁴, Zhi-Peng Lyu^⁴, Jun-Wen Ding^⁴(

)

1College of System Engineering, National University of Defense Technology, Changsha 410015, China

2School of Artificial Intelligence, Jianghan University, Wuhan 430056, China

3Xi’an Satellite Control Center, Xi’an 710043, China

4School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Show 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 B1 $\cup$ B2) and token-ring search (denoted by B1 $\to$ B2), 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 ( ${I L S}_{n e w}$ ) and the Hybrid Evolutionary Algorithm (HEA $_{n e w}$ ) 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 $_{new}$ 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 $_{new}$ 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 $_{new}$ 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%.

Keywords

single-machine scheduling sequence-dependent setup time neighborhood combination search token-ring search hybrid evolutionary algorithm

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.

Crossref Google Scholar

[3]

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.

Crossref Google Scholar

[4]

Mladenović N, Hansen P. Variable neighborhood search. Computers & Operations Research , 1997, 24(11): 1097–1100. DOI: 10.1016/S0305-0548(97)00031-2.

Crossref Google Scholar

[5]

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.

Crossref Google Scholar

[6]

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.

Crossref Google Scholar

[7]

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.

Crossref Google Scholar

[8]

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.

Crossref Google Scholar

[9]

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.

Crossref Google Scholar

[10]

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.

Crossref

[11]

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.

Crossref Google Scholar

[12]

Chen C L. Iterated population-based VND algorithms for single-machine scheduling with sequence-dependent setup times. Soft Computing , 2019, 23(11): 3627–3641. DOI: 10.1007/s00500-018-3014-3.

Crossref Google Scholar

[13]

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.

Crossref Google Scholar

[14]

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.

Crossref Google Scholar

[15]

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.

Crossref Google Scholar

[16]

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.

Crossref Google Scholar

[17]

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.

Crossref Google Scholar

[18]

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.

Crossref Google Scholar

[19]

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.

Crossref Google Scholar

[20]

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.

Crossref Google Scholar

[21]

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.

Crossref Google Scholar

[22]

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.

Crossref Google Scholar

[23]

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.

Crossref Google Scholar

[24]

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.

Crossref Google Scholar

[25]

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.

Crossref Google Scholar

[26]

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.

Crossref Google Scholar

[27]

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.

Crossref Google Scholar

[28]

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.

Crossref Google Scholar

[29]

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.

Crossref

[30]

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.

Crossref Google Scholar

[31]

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.

Crossref Google Scholar

[32]

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.

Crossref Google Scholar

[33]

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.

Crossref Google Scholar

[34]

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.

Crossref Google Scholar

[35]

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.

Crossref

[36]

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.

Google Scholar

[37]

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.

Crossref Google Scholar

[38]

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.

Crossref Google Scholar

[39]

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.

Crossref Google Scholar

[40]

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.

Crossref Google Scholar

[41]

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.

Crossref Google Scholar

[42]

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.

Crossref Google Scholar

[43]

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.

Crossref Google Scholar

[44]

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.

Crossref Google Scholar

[45]

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.

Crossref Google Scholar

[46]

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.

Crossref Google Scholar

Journal of Computer Science and Technology

Volume 39 Issue 3,
May 2024

Pages 737-752

DOI: 10.1007/s11390-023-2007-6

Cite this article:

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

202

Views

Crossref

Web of Science

Scopus

CSCD

Google Scholar
Citation

Altmetrics

Received: 31 October 2021

Accepted: 14 April 2023

Published: 22 July 2024