Synchronous flow shop scheduling with pliable jobs
Synchronous flow shop scheduling with pliable jobs
复制标题
DOI：
10.1016/j.ejor.2018.04.024
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Matthias Bultmann;S. Knust;S. Waldherr
中科院分区：
文献类型：
--
作者：
Matthias Bultmann;S. Knust;S. Waldherr
在本文中，我们考虑的同步流水车间调度问题的加工时间是不固定的。相反，对于每个作业，给出了可以在机器之间自由分配的总处理时间，尊重操作的处理时间的一些下限和/或上限。我们证明，即使没有额外的界限，最小化的完工时间是NP-困难的两台机器。另一方面，我们可以利用一个更一般的结果来表明，对于一个固定的工件排列，最佳的相应的处理时间可以通过多项式时间的线性规划来确定。但是，对于较大的问题实例，这会导致大量的运行时间。作为一个更有效的替代方案，我们提出了直接的组合算法来确定处理时间。我们将这些算法嵌入到一个两阶段的方法中，使用所有作业排列的集合作为搜索空间，并在第二步中计算相应的处理时间。随机生成的数据具有不同程度的允许的灵活性的计算结果。
In this paper, we consider synchronous flow shop scheduling problems where the processing times of the operations are not fixed in advance. Instead, for each job a total processing time is given which can be distributed freely among the machines, respecting some lower and/or upper bounds on the processing times of the operations. We prove that even if no additional bounds are given, minimizing the makespan is NP-hard already for two machines. On the other hand, we can draw on a more general result to show that for a fixed job permutation optimal corresponding processing times can be determined via a linear program in polynomial time. However, for larger problem instances, this leads to large run times. As a more efficient alternative, we propose direct combinatorial algorithms to determine the processing times. We embed these algorithms in a two-stage approach using the set of all job permutations as search space and calculating corresponding processing times in a second step. Computational results are presented for randomly generated data with varying degrees of allowed flexibility.