Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 2 von 2
Zurück zur Trefferliste

Improving Energetic Propagations for Cumulative Scheduling

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-69331
  • We consider the Cumulative Scheduling Problem (CuSP) in which a set of $n$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades.

Volltext Dateien herunterladen

  • ZR-18-29eng
    (368KB)

    This version fixes a mistake in the original version.

Metadaten exportieren

Metadaten
Verfasserangaben:Alexander TeschORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Constraint Programming; Cumulative Scheduling; Propagation Algorithm
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Klassifikation:G. Mathematics of Computing
Datum der Erstveröffentlichung:26.06.2018
Schriftenreihe (Bandnummer):ZIB-Report (18-29)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.