Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective
Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective
复制标题
DOI：
10.1016/j.cor.2019.05.002
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Victor Fernandez-Viagas;P. Perez-Gonzalez;J. Framiñan
中科院分区：
文献类型：
--
作者：
Victor Fernandez-Viagas;P. Perez-Gonzalez;J. Framiñan
本文研究了带完工时间目标的经典混合流水作业调度问题。由于该问题是NP-Hard问题，并且是现实制造场景中非常常见的布局问题，因此文献中已经提出了许多研究来解决该问题。这些贡献使用可行时间表的不同解表示，每一种都有其优点和缺点。它们中的一些并不保证所有可行的半活动调度都被表示在解的空间中--从而在原则上限制了它们的有效性--但另一方面，这些更简单的解表示在具有一致的邻域和明确定义的邻域移动方面具有明显的优势。因此，在减少解空间和在此减少的解空间中执行有效搜索的能力之间存在权衡。这种权衡由两个方面决定，即解空间缩减的程度，以及这种解空间缩减所留下的调度的质量。在这篇文章中，我们分析了文献中使用的不同解表示法对于该问题的效率。更具体地说，我们首先建立了由不同解表示所获得的半活动调度空间的大小，然后利用几个MILP模型所给出的最优解和完全计数来讨论这些表示所能达到的调度的质量问题。所得结果可能有助于设计更有效的混合流水作业调度算法。
In this paper we address the classical hybrid flow shop scheduling problem with makespan objective. As this problem is known to be NP-hard and a very common layout in real-life manufacturing scenarios, many studies have been proposed in the literature to solve it. These contributions use different solution representations of the feasible schedules, each one with its own advantages and disadvantages. Some of them do not guarantee that all feasible semiactive schedules are represented in the space of solutions –thus limiting in principle their effectiveness– but, on the other hand, these simpler solution representations possess clear advantages in terms of having consistent neighbourhoods with well-defined neighbourhood moves. Therefore, there is a trade-off between the solution space reduction and the ability to conduct an efficient search in this reduced solution space. This trade-off is determined by two aspects, i.e. the extent of the solution space reduction, and the quality of the schedules left aside by this solution space reduction. In this paper, we analyse the efficiency of the different solution representations employed in the literature for the problem. More specifically, we first establish the size of the space of semiactive schedules achieved by the different solution representations and, secondly, we address the issue of the quality of the schedules that can be achieved by these representations using the optimal solutions given by several MILP models and complete enumeration. The results obtained may contribute to design more efficient algorithms for the hybrid flow shop scheduling problem.