Flow shop scheduling with flexible processing times
Flow shop scheduling with flexible processing times
复制标题
DOI：
10.1007/s00291-018-0520-8
复制
发表时间：
2018-04
期刊：
影响因子：
2.7
通讯作者：
Matthias Bultmann;S. Knust;S. Waldherr
中科院分区：
文献类型：
--
作者：
Matthias Bultmann;S. Knust;S. Waldherr
在众多的流水作业变型中，操作的处理时间不是预先固定的，而是可以在机器之间以一定的灵活性进行分配。在本文中，我们介绍了一个通用的模型，这是表达足以涵盖几个模型的文献。虽然在大多数情况下，它是很难找到一个工作的置换和相应的处理时间的分布最小化的完工时间，我们表明，对于一个固定的工作置换的最佳处理时间分布可以计算在多项式时间的线性规划。在此基础上，我们提出了一个禁忌搜索过程中使用的所有工作排列的集合作为搜索空间。在计算研究中，我们展示了新模型的力量。除了经典的置换流水作业环境，我们研究的变种阻塞，无等待和同步运动的限制。
In numerous flow shop variants, the processing times of the operations are not fixed in advance, but may be distributed with some flexibility among the machines. In this paper, we introduce a general model which is expressive enough to cover several models from the literature. While in most cases it is-hard to find a job permutation and a corresponding distribution of processing times minimizing the makespan, we show that for a fixed job permutation a best processing time distribution can be calculated in polynomial time by linear programming. Based on this, we propose a tabu search procedure using the set of all job permutations as search space. In a computational study, we show the power of the new model. Besides the classical permutation flow shop environment, we study variants with blocking, no-wait and synchronous movement constraints.