Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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

  • 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.
Metadaten
Author:Alexander TeschORCiD
Document Type:In Proceedings
Parent Title (English):Principles and Practice of Constraint Programming (CP 2016)
Volume:22
First Page:493
Last Page:519
Series:Lecture Notes in Computer Science
Year of first publication:2016
Preprint:urn:nbn:de:0297-zib-59332
DOI:https://doi.org/10.1007/978-3-319-44953-1_32
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.