4.5 Article

Effective constructive heuristics for distributed no-wait flexible flow shop scheduling problem

期刊

COMPUTERS & OPERATIONS RESEARCH
卷 136, 期 -, 页码 -

出版社

PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2021.105482

关键词

Factory assignment rules; Dispatch rules; Constructive heuristics; Distributed no-wait flexible flow shop scheduling problem; Makespan; Variable neighborhood search

资金

  1. National Natural Science Foundation of China [62003203, 61772279]
  2. Natural Science Basic Research Program of Shaanxi [2020JQ-425]
  3. Fundamental Research Funds for the Central Universities [GK202003073]
  4. Natural Science Foundation of the Jiangsu Higher Education Institutions of China [19KJB520042]
  5. Jiangsu Natural Science Foundation
  6. Youth Talent Support Program of Association for Science and Technology in Xi'an, China [095920211321]
  7. Research Startup Fund of Shaanxi Normal University
  8. Nanjing Normal University

向作者/读者索取更多资源

This paper investigates a distributed no-wait flexible flow shop scheduling problem with makespan criterion, presenting a mixed-integer linear programming model and machine selection method, as well as developing greedy factory assignment rules and dispatch rules. Multiple constructive heuristics are obtained by combining different rules, and a variable neighborhood descend constructive heuristic version is designed to tackle the problem.
The distributed shop scheduling has gained a great deal of attention due to its high-efficient collaboration and production. This paper studies a distributed no-wait flexible flow shop scheduling problem (DNWFFSP) with the makespan criterion, where each factory includes an identical flexible flow shop with no-wait constraint that requires each job to be processed without any waiting time between consecutive stages. A mixed-integer linear programming model for the DNWFFSP is presented. A machine selection method based on the first earliest available machine rule is presented. Three greedy factory assignment rules incorporating NEH (Nawaz-Enscore-Ham) heuristic are developed to allocate jobs into factories. Fourteen dispatch rules involving simple sorting and decomposition method are developed to construct a priority sequence of jobs. Thus, several constructive heuristics are obtained by combining dispatch rules and factory assignment rules. Furthermore, a constructive heuristic version of variable neighborhood descend is designed to address the DNWFFSP. One of constructive heuristics is selected to generate an initial solution, and five neighborhood search methods are used as the local search procedure. A comprehensive numerical comparison and statistical analysis are carried out to investigate the performance of the proposed approaches. The distributed NEH2 with smallest largest-medium rule obtains better results than other constructive heuristics for large-size instances.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据