Journal
KNOWLEDGE-BASED SYSTEMS
Volume 137, Issue -, Pages 163-181Publisher
ELSEVIER
DOI: 10.1016/j.knosys.2017.09.026
Keywords
Distributed no-wait flow shop scheduling problem; Makespan; Iterated greedy algorithm; Neighborhood structures; Local search
Categories
Funding
- National Natural Science Foundation of China [U1433116]
- Funding of Jiangsu Innovation Program for Graduate Education [KYLX16_0382]
- Postgraduate Research & Practice Innovation Program of Jiangsu Province [KYCX17_0287]
- Fundamental Research Funds for the Central Universities [NP2017208]
Ask authors/readers for more resources
The distributed production lines widely exist in modern supply chains and manufacturing systems. This paper aims to address the distributed no-wait flow shop scheduling problem (DNWFSP) with the makespan criterion by using proposed iterated greedy (IG) algorithms. Firstly, several speed-up methods based on the problem properties of DNWFSP are investigated to reduce the evaluation time of neigh-borhood with O(1) complexity. Secondly, an improved NEH heuristic is proposed to generate a promising initial solution, where the iteration step of the insertion step of NEH is applied to the factory after inserting a new job. Thirdly, four neighborhood structures (i.e. Critical_swap_single, Critical_insert_single, Critical_swap_multi, Critical_insert_multi) based on factory assignment and job sequence adjustment are employed to escape from local optima. Fourthly, four local search methods based on neighborhood moves are proposed to enhance local searching ability, which contains LS_insert_critical_factory1, LS_insert_critical_factory2, LS_swap, and LS_insert. Finally, to organize neighborhood moves and local search methods efficiently, we incorporate them into the framework of variable neighborhood search (VNS), variable neighborhood descent (VND) and random neighborhood structure (RNS). Furthermore, three variants of IG algorithms are presented based on the designed VNS, VND and RNS. The parameters of the proposed IG algorithms are tuned through a design of experiments on randomly generated benchmark instances. The effectiveness of the initialize phase and local search methods is shown by numerical comparison, and the comparisons with the recently published algorithms demonstrate the high effectiveness and searching ability of the proposed IG algorithms for solving the DNWFSP. Ultimately, the best solutions of 720 instances from the well-known benchmark set of Naderi and Ruiz for the DNWFSP are proposed. (C) 2017 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available