A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n)

Please always quote using this URN: urn:nbn:de:0297-zib-59332
  • In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.

Download full text files

Export metadata

Metadaten
Author:Alexander Tesch
Document Type:ZIB-Report
Tag:Cumulative Scheduling; Energetic Reasoning; Sweep Line Algorithm
Date of first Publication:2016/05/02
Series (Serial Number):ZIB-Report (16-25)
ISSN:1438-0064
Published in:Appeared in: Principles and Practice of Constraint Programming (CP 2016)
DOI:https://doi.org/10.1007/978-3-319-44953-1_32