The basic cyclic scheduling problem with deadlines

The purpose of this paper is to study the latest schedule existence, calculation and properties of a basic cyclic scheduling problem with deadlines. First it is shown that, in the general case, a latest schedule exists but may be difficult to compute. Then a special case, called the optimal cyclic production problem, is focused upon. An upper bound is derived for the number of maximal-path values needed to compute the latest starting times and the K-periodic structure of the latest starting time sequences is shown.