Efficient heuristics for the parallel blocking flow shop scheduling problem
Efficient heuristics for the parallel blocking flow shop scheduling problem
复制标题
DOI：
10.1016/j.eswa.2017.01.006
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Imma Ribas;R. Companys;X. Tort-Martorell
中科院分区：
文献类型：
--
作者：
Imma Ribas;R. Companys;X. Tort-Martorell
我们考虑了在完全相同的并行流水线车间中调度作业的NP-Hard问题，每个流水线车间由一系列机器组成，并且是在阻塞约束下进行的。应用的准则是最小化完工时间，即流水作业(生产线)中所有作业的最大完成时间。并行Flow Shop调度问题(PFSP)在概念上类似于文献中所知的另一个问题，即分布式置换Flow Shop调度问题(DPFSP)，该问题允许在拥有多于一个工厂的公司中对调度过程进行建模，每个工厂都具有Flow Shop配置。因此，所提出的方法可以解决两种情况下的阻塞约束下的调度问题，据我们所知，这是以前没有研究过的。本文提出了一种求解并行阻塞流水作业问题(PBFSP)的数学模型以及一些构造性和改进型启发式算法，从而最小化生产线间的最大完工时间。拟议的建设性程序使用了两种与文献中提议的完全不同的方法。这些方法被用作迭代局部搜索(ILS)和迭代贪婪算法(IGA)的初始解过程，两者都与可变邻域搜索(VNS)相结合。拟议的建设性程序和改进的方法考虑到了问题的特点。计算评估表明，这两种算法--特别是免疫遗传算法--的性能都比DPFSP文献中的算法好得多。
We consider the NP-hard problem of schedulingnjobs inFidentical parallel flow shops, each consisting of a series ofmmachines, and doing so with a blocking constraint. The applied criterion is to minimize the makespan, i.e., the maximum completion time of all the jobs inFflow shops (lines). The Parallel Flow Shop Scheduling Problem (PFSP) is conceptually similar to another problem known in the literature as the Distributed Permutation Flow Shop Scheduling Problem (DPFSP), which allows modeling the scheduling process in companies with more than one factory, each factory with a flow shop configuration. Therefore, the proposed methods can solve the scheduling problem under the blocking constraint in both situations, which, to the best of our knowledge, has not been studied previously. In this paper, we propose a mathematical model along with some constructive and improvement heuristics to solve the parallel blocking flow shop problem (PBFSP) and thus minimize the maximum completion time among lines. The proposed constructive procedures use two approaches that are totally different from those proposed in the literature. These methods are used as initial solution procedures of an iterated local search (ILS) and an iterated greedy algorithm (IGA), both of which are combined with a variable neighborhood search (VNS). The proposed constructive procedure and the improved methods take into account the characteristics of the problem. The computational evaluation demonstrates that both of them –especially the IGA– perform considerably better than those algorithms adapted from the DPFSP literature.