Citation
Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays. Journal of Scheduling, 14 (5): 511-522, 2011.
Selected
Abstract
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 (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.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/s10951-010-0220-y You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@ARTICLE{2011-511-522-SI, author = {A. Benabid and C. Hanen},
title = {Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays},
journal = {Journal of Scheduling},
year = {2011},
volume = {14},
pages = {511--522},
number = {5},
note = {Selected},
abstract = {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 (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.},
doi = {10.1007/s10951-010-0220-y},
owner = {user},
timestamp = {2012.05.25} }