SOME COMPLEXITY RESULTS IN CYCLIC SCHEDULING

In this paper, we investigate the complexity of various cyclic schedul ing 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-har d, and in the process, we give a polynomial transformation of generic makespan minimization problems in static scheduling to cycle time mini mization in cyclic scheduling problems. Secondly, we show that when we try to schedule a single job type in a cyclic, reentrant flow shop, e ven 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.