Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays

In this paper, we address a cyclic scheduling problem of finding a periodic schedule with minimal period for the unitary resource constrained cyclic scheduling problem. The main originality is in being able to cope with both precedence delays and complex resource settings which make the problem NP‐complete, in general. A guaranteed approach, called Decomposed Software Pipelining, has been proposed by Gasperoni and Schwiegelshohn (1994), followed by the retiming method by Calland et al. (1998) to solve the problem assuming parallel identical processors and ordinary precedence constraints. In this paper, an extension of this approach to unitary resource‐constrained cyclic scheduling problems with precedence delays, is analyzed and its worst case performance ratio is provided.