Some complexity results in cyclic scheduling

precedence constraints graph 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 pro-vide 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 transfor-mation 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, re-entrant flow shop, even if we are given the se-quence 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 can also be viewed as a classification of cyclic scheduling research from the perspective of computational complexity.