摘要
This study focused on the no-wait jobshop scheduling problem (NWJSP), which is NP-hard in the strong sense. A new benchmarking algorithm, named backtracking multi-start simulated annealing (BMSA), is presented in this study for minimizing the total completion time in NWJSPs. To effectively and efficiently find (near-) optimal schedules, the simulated annealing algorithm is strengthened by integrating the multi-start and backtracking mechanisms that enable the search processes to escape from the local optimum. The performance of the BMSA algorithm is assessed by comparing its experimental results to those of the best available metaheuristics on three well-known benchmark problem sets. Computational results and statistical analyses confirm that the BMSA algorithm significantly outperforms these benchmark metaheuristics. This study mainly contributes to providing an innovative approach for solving this highly intractable scheduling problem, which is also worth applying to solve a practical NWJSP.
学科与关键词
- Solving no-wait job-shop scheduling problems using a multi-start simulated annealing with bi-directional shift timetabling algorithmYing, Kuo-Ching; Lin, Shih-Wei*COMPUTERS & INDUSTRIAL ENGINEERING, 2020, 146: 106615.被引 16
- A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterionDeng, Guanlong*; Su, Qingtang; Zhang, Zhiwang; Liu, Huixia; Zhang, Shuning; Jiang, TianhuaENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2020, 88: 103369.被引 34
- MINIMIZING TOTAL FLOW TIME IN PERMUTATION FLOWSHOP ENVIRONMENTLin, Shih-Wei; Huang, Chien-Yi; Lu, Chung-Cheng; Yng, Kuo-Ching*International Journal of Innovative Computing, Information and Control, 2012, 8(10A): 6599-6612.被引 5
