Paper Info
Title
Effective constructive heuristic and iterated greedy algorithm for distributed mixed blocking permutation flow-shop scheduling problem
Abstract
Distributed permutation flow-shop scheduling problem (DPFSP) has achieved much attention in recent years, which always assumes that there are infinite buffers between any consecutive machines. However, in many practical industrials, no buffers exist between some consecutive machines due to space constraint or technological requirement, which generate various types of blocking constraint. Hence, a distributed mixed permutation blocking flow-shop scheduling problem (DMBPFSP) is investigated in this paper, which considers three types of blocking constraint and without blocking. The objective is to minimize the maximum makespan among all factories. To address this problem, an improved NEH heuristic (NEH_P) is proposed, which incorporates the re-optimization of partial solutions. Afterwards, an efficient iterated greedy (EIG) algorithm is proposed. In the proposed EIG, the NEH_P heuristic is employed to generate the initial solution with high quality. A problem-specific knowledge based destruction–construction is used to explore the solution space. Three efficient local search procedures are designed to implement exploitation around the critical factory and exploitation across multi-factory. We compare the proposed methods against the closely relevant and high-performing methods in the literature. The computational results indicate that both NEH_P and EIG are very effective for addressing the considered problem.
Year
DOI
Venue
2021
10.1016/j.knosys.2021.106959
Knowledge-Based Systems
Keywords
DocType
Volume
Distributed manufacturing,Flow-shop scheduling,Blocking constraints,Constructive heuristic,Iterated greedy method
Journal
221
ISSN
Citations 
PageRank 
0950-7051
0
0.34
References 
Authors
47
3
Name
Order
Citations
PageRank
Zhongshi Shao1927.91
Weishi Shao2333.44
De-Chang Pi317739.40