An approximative criterion for the potential of energetic reasoning. (English) Zbl 1325.90035

Berthold, Timo; Heinz, Stefan; Schulz, Jens

Marchetti-Spaccamela, Alberto (ed.) et al., Theory and practice of algorithms in (computer) systems. First international ICST conference, TAPAS 2011, Rome, Italy, April 18–20, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19753-6/pbk). Lecture Notes in Computer Science 6595, 229-239 (2011).

Summary: Energetic reasoning is one of the most powerful propagation algorithms in cumulative scheduling. In practice, however, it is not commonly used because it has a high running time and its success highly depends on the tightness of the variable bounds. In order to speed up energetic reasoning, we provide an easy-to-check necessary condition for energetic reasoning to detect infeasibilities.
We present an implementation of energetic reasoning that employs this condition and that can be parametrically adjusted to handle the trade-off between solving time and propagation overhead. Computational results on instances from the PSPLib are provided. These results show that using this condition decreases the running time by more than a half, although more search nodes need to be explored.
For the entire collection see [Zbl 1213.68050].

MSC:

90B35

Deterministic scheduling theory in operations research

Software:

PSPLIB