Exact Energetic Reasoning in O(n^2 log^2 n)
Please always quote using this URN: urn:nbn:de:0297-zib-60367
- In this paper, we address the Energetic Reasoning propagation rule for the Cumulative Scheduling Problem (CuSP). An energetic reasoning propagation algorithm is called exact, if it computes the maximum possible energetic reasoning propagation for all the jobs. The currently best known exact energetic reasoning algorithm has complexity O(n^3). In this paper, we present a new exact energetic reasoning propagation algorithm with improved complexity of O(n^2 \log^2 n).
Author: | Alexander TeschORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | Constraint Programming; Cumulative Scheduling; Energetic Reasoning; Sweep Line |
Date of first Publication: | 2016/09/07 |
Series (Serial Number): | ZIB-Report (16-46) |
ISSN: | 1438-0064 |
Notes: | Preprint Version |