Zum Hauptinhalt springen

Globaler Optimierer (A-3 / A-5)

Bezug: Lastenheft §6.2 (weiche Ziele), §9 A-3/A-5 · Code: server/src/solver/ · Demo: cd server && npm run solve

Der Greedy-Scheduler (docs/datamodel.md §5) liefert je Auftrag das frühest-mögliche, §6.1-zulässige Set — aber nicht das global beste. Dieser Optimierer schließt die Lücke zu §6.2.

1. Die Problematik: Warum Taktung schwer ist​

Kernaussage: Eine optimale Werkstatt-Taktung zu finden ist ein NP-schweres Kombinatorik-Problem (verwandt mit Job-Shop-Scheduling) mit widersprüchlichen Zielen und stark gekoppelten harten Constraints. Es gibt keinen Algorithmus, der zugleich beweisbar optimal, in Millisekunden und überall lauffähig ist — diese drei Eigenschaften stehen im Konflikt. Genau daraus folgt (§2), warum mehrere Optimierer existieren.

Vier Treiber machen das Problem hart:

  1. Kombinatorische Explosion. Schon die reine Reihenfolge von N Aufträgen hat N! Varianten (7 Aufträge → 5 040, 10 → 3,6 Mio.). Der volle Entscheidungsraum ist weit größer: zusätzlich Startzeit, Bucht und Mitarbeiter-Zuweisung je Teilschritt. Brute-Force skaliert nicht.
  2. Widersprüchliche Ziele (§6.2). Kurze mittlere Durchlaufzeit (Kundensicht, SPT-artig) ↔ kleiner Makespan (Batch-Durchsatz) ↔ wenige Mitarbeiter-Wechsel (G-2) ↔ keine kleinen Lücken (G-3). Kein Plan ist in allem zugleich am besten — die Demo (§5) zeigt es: SPT senkt die Durchlaufzeit, erhöht aber den Makespan. „Optimal" braucht daher eine bewusste, lexikografische Reihenfolge der Kriterien (§4).
  3. Harte, gekoppelte Constraints (§6.1). Skill-Match, Bucht-No-Overlap inkl. Cool-down, Mitarbeiter-No-Overlap, Schichten/Sperren, Abhängigkeiten (nach_vorherigem), Standzeit, getypte Parkplatz-Pools (Luxus → nur Indoor). Diese Entscheidungen koppeln: eine Bucht-Zuweisung verschiebt Cool-downs, blockiert Parkplätze und verschiebt abhängige Schritte — lokale Optima sind selten global gut.
  4. Dynamik & Laufzeit-Umgebung. Laufende harte Reservierungen (aktiv/pausiert/blockiert) sind fix und müssen respektiert werden; Eilaufträge (R7-F06) drängeln vor; neu geplant wird live. Und der Code läuft im Cloudflare Worker / Durable Object — kein nativer C++/Python-Code, begrenzte CPU-Zeit, synchron erwartete Antwort. Der mathematisch stärkste Solver (OR-Tools) ist dort gar nicht ausführbar.

2. Warum es mehrere Optimierer gibt​

Kernaussage: Weil sich Optimalität, Antwortzeit und Lauffähigkeit im Worker nicht gleichzeitig maximieren lassen, staffelt Taktano drei Optimierer entlang dieser Achsen zu einer Kaskade mit Fallback. So bekommt der Normalfall das beste Ergebnis, der Störfall behält ein lauffähiges System — graceful degradation statt Totalausfall.

OptimiererCodeFreiheitsgradeOptimalitätTempoIm Worker?Rolle
Greedy-SchedulerscheduleSequence (datamodel.md §5)je Auftrag frühest-möglichzulässig (§6.1), nicht global optimalO(n), sub-ms✅Baustein & Decoder für die beiden anderen
TS-Decoder-Optimierersolver/solve.tsnur Reihenfolgeexakt für N ≤ 7, sonst Heuristik< 1 s✅Worker-Zwischenstufe · Fallback · Referenz-Testfall
CP-SAT-Solversolver-service/model.py (OR-Tools)voll: Reihenfolge + Startzeit + Bucht + Mitarbeiteroptimal/feasible (timeout-begrenzt)~Sek., netzabhängig❌ (separater Fly.io-Service)Bestes Ergebnis, unterstützt Pins (3b)

Die Stufen bauen aufeinander auf: Der Greedy ist der Decoder, der jede Reihenfolge in einen zulässigen Plan übersetzt (§3); der TS-Decoder sucht darüber die beste Reihenfolge und dient zugleich als Worker-kompatibler Fallback und als gegenseitige Validierung des CP-SAT (beide liefern in der Demo Σ Durchlauf 78.5 h, §6); der CP-SAT öffnet den vollen Entscheidungsraum für das real beste Ergebnis, lebt aber als eigener Service, weil OR-Tools nicht im Worker läuft.

Der Leitstand (§7) wählt zur Laufzeit:

Warum nicht nur einer? Ein einziger Solver müsste einen der Konflikte aus §1 verlieren: Nur CP-SAT → kein Plan, sobald der Service/das Netz weg ist (oder im lokalen/Worker-Pfad gar nicht ausführbar). Nur TS-Decoder → nie das real beste Ergebnis, da Startzeiten/Zuweisungen fix bleiben und Pins (3b) fehlen. Nur Greedy → schnell und robust, aber blind gegenüber §6.2. Die Kaskade kombiniert die Stärken: CP-SAT wenn möglich, TS-Decoder wenn nötig, Greedy als gemeinsames Fundament.

Die Detail-Abschnitte unten vertiefen die Kaskade von unten nach oben: §3–§5 der TS-Decoder (Ansatz, Zielfunktion, Demo), §6 der CP-SAT-Service, §7 die Verdrahtung im Leitstand inkl. Fallback.

3. Ansatz: Decoder-basierte exakte Suche​

Entscheidungsvariable ist die Einplan-Reihenfolge der Aufträge. Der Greedy (scheduleSequence) ist der Decoder: jede Reihenfolge → ein vollständiger, harter-Constraints-zulässiger Plan (§6.1). Bewertet wird das Ergebnis mit der Zielfunktion (§6.2).

  • Exakt für kleine N: alle Permutationen der nicht-Eil-Aufträge (MAX_EXAKT = 7).
  • Eilaufträge (R7-F06) werden als harte Vorrang-Bedingung vorangestellt und nicht permutiert.
  • Größeres N → Fallback auf die Priority-Reihenfolge (Heuristik), klar markiert (exakt: false).

4. Zielfunktion (§6.2, objective.ts)​

Lexikografisch (istBesser): mehr machbar → kleinere Σ Durchlaufzeit → kleinerer Makespan → kleinere Wechsel-Pönale (G-2) → weniger Lücken < 15 Min (G-3).

  • Σ Durchlaufzeit = Σ (Fertigstellung − Anlieferung) — mittlere Durchlaufzeit/Kundensicht; SPT-artig.
  • Makespan = späteste Fertigstellung — Batch-Durchsatz.
  • Wechsel-Pönale (G-2, 5 Min) und Lücken < 15 Min (G-3) aus den rekonstruierten Mitarbeiter-Timelines.

Die Reihenfolge der Kriterien ist die Geschäftsentscheidung „was heißt optimal" — der Komparator ist explizit und austauschbar.

5. Demo-Ergebnis​

3 Aufträge, gleicher Termin, gemischter Umfang (1 Premium mit Keramik, 2 Basic ohne):

ReihenfolgeΣ DurchlaufzeitMakespan
Priority-GreedyPremium → Basic → Basic82.5 hMi 15:00
OptimumBasic → Basic → Premium78.5 hDo 08:30

Der Optimierer findet die SPT-Reihenfolge (kurze Jobs zuerst) und senkt die mittlere Durchlaufzeit um 4 h. Trade-off: der Makespan steigt (Premium rutscht ans Ende) — genau die Abwägung, die die Zielfunktions-Reihenfolge festlegt. Wer Batch-Durchsatz priorisiert, stellt Makespan vor Σ Durchlaufzeit; das ist eine Ein-Zeilen-Änderung in istBesser.

6. Echter CP-SAT-Solver — separater Service (A-5) ✅​

Der TS-Decoder lässt nur die Reihenfolge frei. Der vollwertige Solver hat Startzeiten und Zuweisungen als freie Variablen — realisiert als separater Python-Service mit OR-Tools CP-SAT in solver-service/, da OR-Tools (C++/Python) nicht in Cloudflare Workers läuft.

  • Arbeitsteilung: server/src/solver/problem.ts expandiert die Domäne (Schichten−Abwesenheiten, Sperren, Prozess→Schritte) zu einem flachen CpSatProblem (Zeiten ab Horizont-Start); model.py ist ein reiner CP-SAT-Solver; cpsat-client.ts ruft per HTTP und rebasiert die Zeiten zurück.
  • Modelliert (§6.1): Skill-Match, distinkte Skills/Helfer, Bay-No-Overlap inkl. Cool-down (Cumulative bei Kapazität > 1), Mitarbeiter-No-Overlap, Schichten/Sperren als blockierte Intervalle, Abhängigkeit, Standzeit, getypte Parkplatz-Pools (siehe unten). Ziel §6.2: flow/makespan + Wechsel-Pönale (G-2).
  • Getypte Parkplatz-Pools: Ein Fahrzeug parkt in den Lücken seines on-site-Aufenthalts (vor erstem Schritt, zwischen Schritten, nach letztem Schritt = späte Abholung). Jede Lücke wird einem erlaubten Pool zugewiesen (order.allowedParkTypes, Luxus → nur Indoor); pro Pool eine Kapazitäts-Cumulative. Verschiedene Lücken dürfen verschiedene Pools nutzen (= Umparken fällt automatisch heraus). Self-Test: 2 Luxusfahrzeuge bei Indoor-Kapazität 1 → INFEASIBLE, bei 2 → OK. Annahme: Schritte sequenziell (gilt für nach_vorherigem-Prozesse). Noch nicht: Parkplatz-Sperren.
  • G-2 (Wechsel-Pönale) als Ziel-Term: Proxy „distinkte Fahrzeuge je Mitarbeiter − 1" × 5 Min (tractabel ohne Sequencing). Die exakten Kennzahlen wechsel/smallGaps (G-3) werden zusätzlich aus der Lösung berechnet und im metrics-Feld zurückgegeben (Parität zur TS-objective.ts).
  • Verifiziert: CP-SAT liefert Σ Durchlauf 78.5 h wie der TS-Optimierer (gegenseitige Validierung) plus konkrete Zuweisung und metrics (Parkplatz-Kapazität 10, Wechsel 4 = 20 min, Lücken<15 = 0). Self-Tests: Skill-Distinktheit, Abhängigkeit, getypte Parkplatz-Kapazität (Luxus/Indoor). npm run solve:cpsat (mit Service) bzw. Fallback ohne.
  • Indoor-Trocknung-Pflicht (F07a) ✅ (OP-OPT-5 Slice 1): ein Schritt mit coolDownIndoorPflicht (Aushärtung muss indoor, Auto bleibt in der Bucht) wird im CP-SAT auf Indoor-Buchten beschränkt — buildProblem verengt allowedBays (geteiltes INDOOR_TYP_RE mit dem TS-Scheduler); kein Modell-Eingriff, da der Cool-down die Bucht ohnehin hält. Self-Test npm run test:indoor.
  • Folierbucht-als-Überlauf-Parkplatz ✅ (OP-OPT-5 Slice 2): freie Folierbuchten dienen als Indoor-Stellplatz. buildProblem führt sie als zusätzliche Pools (mit bayId, nach den dedizierten); model.py legt ihre Park-Intervalle in die bestehende Bucht-No-Overlap → eine Bucht hostet zu einem Zeitpunkt Arbeit ODER einen Parker. Self-Tests npm run test:overflow (Builder) + python model.py (Modell: Standzeit-Lücke ohne Pool INFEASIBLE, mit Überlauf parkbar). Bewusst (noch) nicht: Präferenz „dedizierte vor Überlauf" als Pönale (heute nur Reihenfolge, der Solver ist indifferent solange machbar).
  • Noch nicht im CP-SAT-Modell (→ Ausbau, OP-OPT-5): G-3 als harte/penalisierte Bedingung (nur gemeldet), Nacht-Scheduling — im TS-Greedy/-Optimierer bereits abgebildet.

Der TS-Decoder-Optimierer bleibt als Worker-kompatible Zwischenstufe, Fallback und Referenz/Testfall erhalten.

7. Anbindung im Leitstand (Durable Object)​

Der DO (server/party/leitstand.ts) ruft den Solver bei der Mehrauftrags-Planung selbst auf — Wire-Message auftraege.optimieren, Methode optimiereOffene():

  1. Sammelt die offenen (unbestätigten) Aufträge; harte Reservierungen (aktiv/pausiert/blockiert) werden via belegeWorkshop zu belegten Ressourcen und in buildProblem(…, belegt) aus der Verfügbarkeit geschnitten (§6.3 — harte gewinnen, bleiben fix).
  2. Versucht CP-SAT über env.SOLVER_URL (solveViaCpSat); bei Erfolg wird die Lösung je Auftrag mit applyPlanung übernommen (Status/IDs bleiben).
  3. Fallback ohne erreichbaren Service: TS-Scheduler gegen dieselben belegten harten Ressourcen.

Der Client zeigt solverInfo (welcher Pfad lief) und einen Button „Offene optimieren (CP-SAT)". SOLVER_URL wird als Worker-Var gesetzt (lokal z. B. http://127.0.0.1:8090); ohne Var läuft der Fallback. Verifiziert: Glue (toAuftragInput → buildProblem(belegt) → CP-SAT → applyPlanung) end-to-end gegen den laufenden Service; Server-tsc, Client-ng build, Worker-Bundle (wrangler --dry-run). Live-Verhalten im Browser nicht visuell geprüft.

↩ Zurück zur Doku-Landkarte · Lesepfade · Register (alle OPs)