Efficient heuristics for the hybrid flow shop scheduling problem with missing operations
Efficient heuristics for the hybrid flow shop scheduling problem with missing operations
复制标题
DOI：
10.1016/j.cie.2017.10.034
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Dios;Victor Fernandez-Viagas;J. Framiñan
中科院分区：
文献类型：
--
作者：
M. Dios;Victor Fernandez-Viagas;J. Framiñan
本文研究了基于最大完工时间最小化的混合流水车间调度问题。更具体地说，我们感兴趣的是缺少操作的特殊情况，即跳过一些阶段，这是在塑料制造商中发现的现实问题中得到的启发。我们论文的主要贡献有两个方面。一方面，通过计算分析研究了含缺失作业的混合流水车间调度问题与经典混合流水车间调度问题的硬度。另一方面，我们提出了一套启发式算法来捕捉缺失操作的一些特殊特征，并将这些算法与已有的用于经典混合流水车间问题的启发式算法进行了比较，并对具有缺失操作的混合流水车间问题进行了比较。大量的计算经验表明，我们的建议优于现有的问题方法，表明有可能通过与缺少操作的作业交互来提高完工时间。
In this paper, we address the hybrid flowshop scheduling problem for makespan minimisation. More specifically, we are interested in the special case where there are missing operations, i.e. some stages are skipped, a condition inspired in a realistic problem found in a plastic manufacturer. The main contribution of our paper is twofold. On the one hand we carry out a computational analysis to study the hardness of the hybrid flowshop scheduling problem with missing operations as compared to the classical hybrid flowshop problem. On the other hand, we propose a set of heuristics that captures some special features of the missing operations and compare these algorithms with already existing heuristics for the classical hybrid flowshop, and for the hybrid flowshop problem with missing operations. The extensive computational experience carried out shows that our proposal outperforms existing methods for the problem, indicating that it is possible to improve the makespan by interacting with the jobs with missing operations.