Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Regular Paper
  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

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⋃B2) and token-ring search (denoted by B1 → 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 (ILSnew) and the Hybrid Evolutionary Algorithm (HEAnew) 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 HEAnew 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 HEAnew 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. HEAnew 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%.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

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: https://doi.org/10.1287/opre.21.2.498.

    Article  MathSciNet  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: https://doi.org/10.1016/j.cor.2014.08.006.

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  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: https://doi.org/10.1007/s10732-010-9128-0.

    Article  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: https://doi.org/10.1007/s10951-013-0351-z.

    Article  MathSciNet  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: https://doi.org/10.1016/j.cor.2014.04.009.

    Article  MathSciNet  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: https://doi.org/10.1007/s10732-017-9325-1.

    Article  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: https://doi.org/10.1016/j.asoc.2015.07.050.

    Article  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: https://doi.org/10.1109/cec.2016.7744157.

  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: https://doi.org/10.1016/j.cor.2016.10.008.

    Article  MathSciNet  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: https://doi.org/10.1007/s00500-018-3014-3.

    Article  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: https://doi.org/10.1016/s0167-5060(08)70356-x.

    Article  MathSciNet  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: https://doi.org/10.1016/j.cor.2012.07.004.

    Article  MathSciNet  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: https://doi.org/10.1007/s10951-011-0242-0.

    Article  MathSciNet  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: https://doi.org/10.1016/0166-218x(90)90103-j.

    Article  MathSciNet  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: https://doi.org/10.1287/opre.33.2.363.

    Article  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: https://doi.org/10.1016/s0377-2217(87)80008-5.

    Article  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: https://doi.org/10.1016/j.amc.2006.05.127.

    Article  MathSciNet  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: https://doi.org/10.1016/j.disopt.2008.04.001.

    Article  MathSciNet  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: https://doi.org/10.1287/mnsc.33.8.1035.

    Article  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: https://doi.org/10.1080/07408179708966311.

    Article  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: https://doi.org/10.1016/s0305-0483(97)00024-8.

    Article  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: https://doi.org/10.1080/095372800432188.

    Article  Google Scholar 

  25. Franca 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: https://doi.org/10.1016/s0377-2217(00)00140-5.

    Article  MathSciNet  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: https://doi.org/10.1016/j.cor.2005.07.020.

    Article  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: https://doi.org/10.1016/j.ejor.2005.05.018.

    Article  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: https://doi.org/10.1016/j.eswa.2008.08.033.

    Article  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: https://doi.org/10.1109/cec.2004.1331062.

  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: https://doi.org/10.1080/00207540600620849.

    Article  Google Scholar 

  31. Bilge Ü, Kurtulan M, Kiraç F. A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operational Research, 2007, 176(3): 1423–1435. DOI: https://doi.org/10.1016/j.ejor.2005.10.030.

    Article  MathSciNet  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: https://doi.org/10.1016/j.eswa.2008.02.040.

    Article  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: https://doi.org/10.1016/j.cor.2008.07.009.

    Article  MathSciNet  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: https://doi.org/10.1007/s10732-005-6997-8.

    Article  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: https://doi.org/10.1145/1143997.1144177.

  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.

    MathSciNet  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: https://doi.org/10.1007/s00170-006-0693-1.

    Article  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: https://doi.org/10.1016/j.cor.2006.11.004.

    Article  MathSciNet  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: https://doi.org/10.1016/j.ejor.2007.10.044.

    Article  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: https://doi.org/10.1016/j.cor.2008.06.007.

    Article  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: https://doi.org/10.1016/j.cor.2011.08.022.

    Article  MathSciNet  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: https://doi.org/10.1080/00207543.2014.883472.

    Article  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: https://doi.org/10.1007/s10852-005-9032-z.

    Article  MathSciNet  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: https://doi.org/10.1016/0272-6963(84)90027-5.

    Article  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: https://doi.org/10.1016/0305-0548(93)e0021-k.

    Article  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: https://doi.org/10.1057/palgrave.jors.2601390.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Xiao-Lu Liu  (刘晓路)

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

    Hong-Yun Xu  (徐宏云)

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

    Jia-Ming Chen  (陈嘉铭)

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

    Zhou-Xing Su  (苏宙行), Zhi-Peng Lyu  (吕志鹏) & Jun-Wen Ding  (丁俊文)

Authors
  1. Xiao-Lu Liu  (刘晓路)
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hong-Yun Xu  (徐宏云)
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jia-Ming Chen  (陈嘉铭)
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhou-Xing Su  (苏宙行)
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Zhi-Peng Lyu  (吕志鹏)
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jun-Wen Ding  (丁俊文)
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jun-Wen Ding  (丁俊文).

Ethics declarations

Conflict of Interest The authors declare that they have no conflict of interest.

Additional information

This work was supported by the National Natural Science Foundation of China under Grant Nos. 62202192, 71801218, and 72101094.

Xiao-Lu Liu received her B.E. degree in system engineering from the National University of Defense Technology, Changsha, in 2006, and her Ph.D. degree in management science and engineering from the National University of Defense Technology, Changsha, in 2011. She is an associate professor with College of System Engineering, National University of Defense Technology, Changsha. Her research mainly focuses on artificial intelligence and metaheuristics, solving distribution management and satellite scheduling problems.

Hong-Yun Xu received her Ph.D. degree in computer science and technology from Huazhong University of Science and Technology, Wuhan, in 2015. She is a senior laboratory master at School of Artificial Intelligence and Artificial Intelligence Institute of Jianghan University. Her research interests include scheduling problem, heuristic optimization, and combinatorial optimization.

Jia-Ming Chen received his B.E. degree in system engineering from the National University of Defense Technology, Changsha, in 2018, and his Master’s degree in management science and engineering from the National University of Defense Technology, Changsha, in 2020. His research interests include computation intelligence, evolutionary computation, and adaptive meta-heuristic or hyperheuristic for solving large-scale combinatorial optimization and resource scheduling problems.

Zhou-Xing Su received his B.E. degree in computer science and technology from Huazhong University of Science and Technology (HUST), Wuhan, in 2014, and his Ph.D. degree in computer software and theory from Laboratory of Smart Computing and Optimization (SMART) at HUST, Wuhan, in 2020. His research focuses on using metaheuristics to tackle classical NP-hard problems and real-world applications, such as placement, assignment, routing, scheduling, packing, covering, location, timetabling, and rostering.

Jun-Wen Ding received his B.S. degree in computer science from Wuhan Textile University, Wuhan, in 2011, and his M.Sc. and Ph.D. degrees in computer software and theory from Huazhong University of Science and Technology (HUST), Wuhan, in 2014 and 2017, respectively. He is currently in the postdoctoral program with the Institute of Artificial Intelligence and Optimization of HUST. His current research interests include metaheuristic algorithms and evolutionary computation for solving classical NP-hard problems and real-world applications, such as production scheduling, facility location, graph partition, and vehicle routing.

Zhi-Peng Lyu received his B.S. degree in applied mathematics from Jilin University, Changchun, in 2001, and his Ph.D. degree in computer software and theory from the Huazhong University of Science and Technology, Wuhan, in 2007. He was a Postdoctoral Research Fellow with the LERIA, Department of Computer Science, University of Angers, Angers, from 2007 to 2011. He is currently a professor with the School of Computer Science and Technology, and the director of the Institute of Artificial Intelligence and Optimization, Huazhong University of Science and Technology, Wuhan. His research interests include artificial intelligence, computational intelligence, operations research and adaptive metaheuristics for solving large-scale real-world and theoretical combinatorial optimization, and constrained satisfaction problems.

Electronic Supplementary Material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, XL., Xu, HY., Chen, JM. et al. Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time. J. Comput. Sci. Technol. 39, 737–752 (2024). https://doi.org/10.1007/s11390-023-2007-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11390-023-2007-6

Keywords

Search

Navigation