摘要
The distributed scheduling problem (DSP) becomes particularly important with the popularization of the distributed manufacturing mode. The distributed job shop scheduling problem (DJSP) is a typical representative of the DSP. It consists of two subproblems, assigning jobs to factories and determining the operation sequence on machines. Some benchmark instances have been proposed to test the performance of the DJSP approach, but most instances have not found the optimal solution. In this paper, an iterated greedy algorithm integrating job insertion (IGJI) is proposed to solve the DJSP. Firstly, a job insertion strategy based on idle time (JIIT) is designed for the insertion of a job into a factory. Secondly, JIIT is used in the reconstruction phase of IGJI, while three destruction-reconstruction methods are designed to balance the makespan among factories. Finally, tabu search is adopted in the local search phase of IGJI to improve the solution quality further. The performance of IGJI is tested on 240 benchmark instances, and the experimental results show that the solution quality of IGJI outperforms the other four state-of-the-art algorithms. In particular, IGJI has found 231 new solutions for these benchmark instances.
学科与关键词
- An effective iterated greedy method for the distributed permutation fl owshop scheduling problem with sequence-dependent setup timesHuang, Jiang-Ping; Pan, Quan-Ke*; Gao, LiangSwarm and Evolutionary Computation, 2020, 59: 100742.被引 96
- An iterated greedy algorithm with acceleration of job allocation probability for distributed heterogeneous permutation flowshop scheduling problemLi, Haoran; Li, Xinyu; Gao, Liang*Swarm and Evolutionary Computation, 2024, 88: 101580.被引 1
- Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problemShao, Weishi; Shao, Zhongshi*; Pi, DechangKnowledge-Based Systems, 2020, 194: 105527.被引 120
