Portal de Periódicos da CAPES

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

2001; Elsevier BV; Volume: 130; Issue: 1 Linguagem: Inglês

10.1016/s0377-2217(00)00022-9

1872-6860

Krzysztof Giaro,

Optimization and Packing Problems

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.