Buffered Resource Constraint: Algorithms and Complexity

International audienceThe 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