Article ID: | iaor20013913 |
Country: | Netherlands |
Volume: | 130 |
Issue: | 1 |
Start Page Number: | 90 |
End Page Number: | 98 |
Publication Date: | Apr 2001 |
Journal: | European Journal of Operational Research |
Authors: | Giaro Krzysztof |
Keywords: | computational analysis |
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.