Exact Energetic Reasoning in O(n^2 log^2 n)
Zitieren Sie bitte immer diese 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).
Verfasserangaben: | Alexander TeschORCiD |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Constraint Programming; Cumulative Scheduling; Energetic Reasoning; Sweep Line |
Datum der Erstveröffentlichung: | 07.09.2016 |
Schriftenreihe (Bandnummer): | ZIB-Report (16-46) |
ISSN: | 1438-0064 |
Bemerkungen: | Preprint Version |