Some complexity results in cyclic scheduling

https://doi.org/10.1016/0895-7177(94)90210-0Get rights and content
Under an Elsevier user license
open archive

Abstract

In this paper, we investigate the complexity of various cyclic scheduling problems in flow-shop, job-shop and other environments. We review existing results and provide proofs for two new complexity results: we show that maximizing throughput in a flexible assembly line is NP-hard, and in the process, we give a polynomial transformation of generic makespan minimization problems in static scheduling to cycle time minimization in cyclic scheduling problems. Secondly, we show that when we try to schedule a single job type in a cyclic, reentrant flow shop, even if we are given the sequence of operations on each machine, it is still NP-hard to figure out how to place the operations onto cycles of a given length so as to minimize flow time (or, equivalently, work in process). This paper may also be viewed as a classification of cyclic scheduling research from the perspective of computational complexity.

Cited by (0)

The research of the first author was partially supported by an NSERC Operating Grant, and the research of the second author by NSF Grant DD-8819542 at Cornell University.