Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Emmanuel Hebrard <>
Submitted on : Friday, July 11, 2014 - 5:04:47 PM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM
Long-term archiving on: : Saturday, October 11, 2014 - 1:10:19 PM


Files produced by the author(s)



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⟩



Record views


Files downloads