Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times
Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times
复制标题
DOI：
10.1002/nav.3800290311
复制
发表时间：
1982-09
期刊：
影响因子：
--
通讯作者：
I. Adiri;D. Pohoryles
中科院分区：
文献类型：
--
作者：
I. Adiri;D. Pohoryles
本文研究了在“无空闲”或“无等待”约束下的流水作业/完工时间和调度问题，前者要求机器连续工作而没有空闲时间间隔，后者要求工件连续加工而没有相邻机器之间的等待时间.在任何一个约束下，问题对于两台机器都是一元NP-完全的。我们证明了n/2/F，no‐idle/σCi的最优调度的一些性质。对于n/m/P，no-idle/σCi和n/m/P，no-wait/σCi，随着控制机的增加或减少，我们证明了多项式有界算法的基础定理。所有的定理证明数值。
This paper deals with flowshop/sum of completion times scheduling problems, working under a “no‐idle” or a “no‐wait” constraint, the former prescribes for the machines to work continuously without idle intervals and the latter for the jobs to be processed continuously without waiting times between consecutive machines. Under either of the constraints the problem is unary NP‐Complete for two machines. We prove some properties of the optimal schedule for n/2/F, no‐idle/σCi. For n/m/P, no‐idle/σCi, and n/m/P, no‐wait/σCi, with an increasing or decreasing series of dominating machines, we prove theorems that are the basis for polynomial bounded algorithms. All theorems are demonstrated numerically.