Neuer Algorithmus liefert bound‑konsistente Lösung für No‑Overlap‑Constraint

In der Welt der Scheduling‑Probleme gilt die Erreichung von Bound‑Consistency für das No‑Overlap‑Constraint als NP‑schwer. Trotz dieser Komplexität haben Forscher bisher nur polynomielle Verfeinerungstechniken wie Edge‑Finding, Not‑First‑Not‑Last‑Reasoning und Energetic‑Reasoning entwickelt. Der neue Ansatz nutzt die bereits bekannte MDD‑Struktur für No‑Overlap, um zeitliche Grenzen der Aufträge exakt zu bestimmen. Durch die Extraktion von Start‑ und Endzeit‑Bounds in polynomieller Zeit, die von der Anzahl der MDD‑Knoten abhängt, wird die Filterung signifikant verbessert.

Um die Größe und Laufzeit weiter zu kontrollieren, wird die Breite der MDD auf einen festgelegten Schwellenwert beschränkt. Diese „relaxierte“ MDD kann ebenfalls zur Bound‑Consistent‑Filterung eingesetzt werden, ohne die Genauigkeit zu stark zu beeinträchtigen. In Experimenten mit einem Sequenzierungsproblem, das Zeitfenster und ein Just‑in‑Time‑Ziel umfasst, zeigte sich, dass die neue Filterung – selbst bei eingeschränkter Breite – die Anzahl der besuchten Knoten im Suchbaum deutlich reduziert. Im Vergleich zum vorherigen Präzedenz‑Erkennungs‑Algorithmus von Ciré und van Hoeve ist die Verbesserung besonders stark.

Darüber hinaus ergänzt die neue Methode klassische Propagationsverfahren für das No‑Overlap‑Constraint. Durch die Kombination beider Ansätze lassen sich sowohl die Knotenzahl als auch die Gesamtlösungszeit auf mehreren Testinstanzen erheblich senken. Dieser Fortschritt eröffnet neue Möglichkeiten für effiziente Scheduling‑Algorithmen in der Praxis.