Effective constructive heuristics for distributed no-wait flexible flow shop scheduling problem
Effective constructive heuristics for distributed no-wait flexible flow shop scheduling problem
复制标题
分布式无等待灵活流水车间调度问题的有效构造启发法
DOI：
10.1016/j.cor.2021.105482
复制
发表时间：
2021-12
影响因子：
4.6
通讯作者：
Pi Dechang
中科院分区：
文献类型：
--
作者：
Shao Weishi;Shao Zhongshi;Pi Dechang
分布式车间调度以其高效的协同和生产能力而受到广泛关注。研究了一个基于最大完工时间准则的分布式无等待柔性流水车间调度问题（DNWFFSP），其中每个工厂都有一个相同的柔性流水车间，每个车间都有一个无等待约束，要求每个工件在连续的工序之间没有任何等待时间.建立了DNWFFSP的混合整数线性规划模型。提出了一种基于最早可用机器规则的机器选择方法。开发了三种结合NEH（Nawaz-Enscore-Ham）启发式算法的贪婪工厂分配规则来将工作分配到工厂。提出了14条调度规则，利用简单的排序和分解方法构造了工件的优先顺序。因此，几个建设性的算法，通过结合派遣规则和工厂分配规则。此外，可变邻域下降的建设性启发式版本的设计，以解决DNWFFSP。选择一种构造性算法生成初始解，并使用五种邻域搜索方法作为局部搜索过程。一个全面的数值比较和统计分析进行了调查所提出的方法的性能。分布式NEH 2最小的最大-中等规则获得了更好的结果比其他建设性算法的大规模的实例。
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.
登录
查看更多内容
DOI：
10.1016/0305-0483(83)90088-9
发表时间：
1983-01-01
影响因子：
6.9
作者：
NAWAZ, M;ENSCORE, EE;HAM, I
通讯作者：
HAM, I
DOI：
10.1109/tase.2018.2886303
发表时间：
2019-01
影响因子：
5.6
作者：
W. Shao;D. Pi;Zhongshi Shao
通讯作者：
W. Shao;D. Pi;Zhongshi Shao
DOI：
10.1016/j.eswa.2017.01.006
发表时间：
2017-05
期刊：
Expert Syst. Appl.
影响因子：
--
作者：
Imma Ribas;R. Companys;X. Tort-Martorell
通讯作者：
Imma Ribas;R. Companys;X. Tort-Martorell
DOI：
10.1016/j.cie.2017.10.034
发表时间：
2018
期刊：
Comput. Ind. Eng.
影响因子：
--
作者：
M. Dios;Victor Fernandez-Viagas;J. Framiñan
通讯作者：
M. Dios;Victor Fernandez-Viagas;J. Framiñan
DOI：
10.1016/j.cor.2019.05.002
发表时间：
2019-09
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Victor Fernandez-Viagas;P. Perez-Gonzalez;J. Framiñan
通讯作者：
Victor Fernandez-Viagas;P. Perez-Gonzalez;J. Framiñan