NP-hardness of compact scheduling in simplified open and flow shops
NP-hardness of compact scheduling in simplified open and flow shops
复制标题
简化开放式流水车间紧凑调度的 NP 难度
DOI：
10.1016/s0377-2217(00)00022-9
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
K. Giaro
中科院分区：
文献类型：
--
作者：
K. Giaro
在实际的任务调度中，有时需要系统的组件连续执行。这种调度被称为没有等待时段或无等待和/或无空闲的调度。在这篇文章中，我们研究了一些简化的调度问题的复杂性，这类在开放式车间和流水车间设置。特别是，我们表明，许多琐碎的问题存在的时间表成为NP-难，即使只有两台机器，或者如果一个系统的调度图是一个路径或一个周期。
In practical task scheduling it is sometimes required that the components of a system perform consecutively. Such a scheduling is called scheduling without waiting periods or no-wait and/or no-idle. In this article we study the complexity of some simplified scheduling problems of this kind in open shop and flow shop settings. In particular, we show that many trivial questions about the existence of schedule become NP-hard, even if there are only two machines or if the scheduling graph of a system is a path or a cycle.