Buffered Resource Constraint: Algorithms and Complexity

Abstract : The notion of buffered resource is useful in many problems. A buffer contains a finite set of items required by some activities, and changing the content of the buffer is costly. For instance, in instruction scheduling, the registers are a buffered resource and any switch of registers has a significant impact on the total runtime of the compiled code. We first show that sequencing activities to minimize the number of switches in the buffer is NP-hard. We then introduce an algorithm which, given a set of already sequenced activities, computes a buffer assignment which minimizes the number of switches in linear time, i.e., $O(nd)$ where $n$ is the length of the sequence and $d$ the number of buffered items. Next, we introduce an algorithm to achieve bound consistency on the constraint \switch, that bounds the number of changes in the buffer, in $O(n^2d+n^{1.5}d^{1.5})$ time. Finally, we report the results of experimental evaluations that demonstrate the efficiency of this propagator.
Document type :
Conference papers
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01023267
Contributor : Emmanuel Hebrard <>
Submitted on : Friday, July 11, 2014 - 5:04:47 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Saturday, October 11, 2014 - 1:10:19 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Christian Bessière, Emmanuel Hébrard, Marc-André Ménard, Claude-Guy Quimper, Toby Walsh. Buffered Resource Constraint: Algorithms and Complexity. CPAIOR: Integration of AI and OR Techniques in Constraint Programming, May 2014, Cork, Ireland. pp.318-333, ⟨10.1007/978-3-319-07046-9_23⟩. ⟨hal-01023267⟩

Share

Metrics

Record views

409

Files downloads

222