caa a22 4500 445838760 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s10951-010-0220-y doi (NATIONALLICENCE)springer-10.1007/s10951-010-0220-y Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays [Elektronische Daten] [Abir Benabid, Claire Hanen] 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 $\mathcal{NP}$-complete, in general. A guaranteed approach, called Decomposed Software Pipelining, has been proposed by Gasperoni and Schwiegelshohn (Parallel Process. Lett. 4:391-403, 1994), followed by the retiming method by Calland et al. (IEEE Trans. Parallel Distrib. Syst. 9(1):24-35, 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. Springer Science+Business Media, LLC, 2010 Scheduling nationallicence Cyclic scheduling nationallicence Software pipelining nationallicence Time-lags nationallicence Precedence delays nationallicence Resource constrained scheduling problem nationallicence Approximated algorithm nationallicence List algorithm nationallicence Benabid Abir LIP6, Pierre and Marie Curie University, Paris, France aut Hanen Claire LIP6, Pierre and Marie Curie University, Paris, France aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/5(2011-10-01), 511-522 1094-6136 14:5<511 2011 14 10951 https://doi.org/10.1007/s10951-010-0220-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0220-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Benabid Abir LIP6, Pierre and Marie Curie University, Paris, France aut NATIONALLICENCE 700 1- Hanen Claire LIP6, Pierre and Marie Curie University, Paris, France aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/5(2011-10-01), 511-522 1094-6136 14:5<511 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer