NP-hardness of compact scheduling in simplified open and flow shops

NP-hardness of compact scheduling in simplified open and flow shops

0.00 Avg rating0 Votes
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:
Keywords: computational analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.