#!/usr/bin/env python3

# JobShop_Intervalle.py
"""
Kapitel CP-SAT: Job-Shop-Scheduling mit Intervallvariablen.
Zeigt NewIntervalVar, AddNoOverlap und die Minimierung des Makespan.
"""

import collections

from ortools.sat.python import cp_model

# (Maschine, Dauer) je Arbeitsgang, in der Reihenfolge des Auftrags
AUFTRAEGE = [
    [(0, 3), (1, 2), (2, 2)],      # Auftrag 0
    [(0, 2), (2, 1), (1, 4)],      # Auftrag 1
    [(1, 4), (2, 3)],              # Auftrag 2
]
MASCHINENNAMEN = ["Fraese", "Dreherei", "Lackiererei"]


def loese_jobshop():
    anzahl_maschinen = 1 + max(m for auftrag in AUFTRAEGE for m, _ in auftrag)
    horizont = sum(dauer for auftrag in AUFTRAEGE for _, dauer in auftrag)

    modell = cp_model.CpModel()
    Gang = collections.namedtuple("Gang", "start ende intervall")
    plaene = {}
    maschinen_intervalle = collections.defaultdict(list)

    # --- Intervallvariablen anlegen --------------------------------------
    for a, auftrag in enumerate(AUFTRAEGE):
        for g, (maschine, dauer) in enumerate(auftrag):
            start = modell.NewIntVar(0, horizont, f"start_{a}_{g}")
            ende = modell.NewIntVar(0, horizont, f"ende_{a}_{g}")
            # Ein Intervall koppelt start + dauer == ende automatisch
            intervall = modell.NewIntervalVar(start, dauer, ende, f"intervall_{a}_{g}")
            plaene[a, g] = Gang(start, ende, intervall)
            maschinen_intervalle[maschine].append(intervall)

    # --- H1: eine Maschine bearbeitet nur einen Gang gleichzeitig --------
    for maschine in range(anzahl_maschinen):
        modell.AddNoOverlap(maschinen_intervalle[maschine])

    # --- H2: Reihenfolge innerhalb eines Auftrags einhalten -------------
    for a, auftrag in enumerate(AUFTRAEGE):
        for g in range(len(auftrag) - 1):
            modell.Add(plaene[a, g + 1].start >= plaene[a, g].ende)

    # --- Ziel: Makespan minimieren ---------------------------------------
    makespan = modell.NewIntVar(0, horizont, "makespan")
    modell.AddMaxEquality(makespan, [plaene[a, len(auftrag) - 1].ende
                                     for a, auftrag in enumerate(AUFTRAEGE)])
    modell.Minimize(makespan)

    loeser = cp_model.CpSolver()
    loeser.parameters.max_time_in_seconds = 10.0
    # Es gibt mehrere Plaene mit demselben kuerzesten Makespan. Welchen CP-SAT
    # findet, haengt sonst davon ab, welcher seiner parallelen Suchstraenge
    # zuerst fertig wird - dasselbe Programm liefert dann von Lauf zu Lauf
    # verschiedene (gleich gute) Plaene. Fuer ein reproduzierbares Buchbeispiel
    # fixieren wir beides. Im Produktivbetrieb laesst man die Standardwerte
    # stehen: Mehrere Arbeiter sind dort deutlich schneller.
    loeser.parameters.num_workers = 1
    loeser.parameters.random_seed = 1
    status = loeser.Solve(modell)

    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        print(f"Kein Plan gefunden: {loeser.StatusName(status)}")
        return

    print("=" * 74)
    print("  JOB-SHOP-SCHEDULING MIT INTERVALLVARIABLEN")
    print("=" * 74)
    print(f"Status: {loeser.StatusName(status)} | "
          f"Kuerzeste Gesamtdauer (Makespan): {loeser.Value(makespan)} Zeiteinheiten\n")

    # --- Gantt-Diagramm als Text ------------------------------------------
    dauer_gesamt = loeser.Value(makespan)
    print(f"{'Maschine':<14}|" + "".join(f"{t:<3}" for t in range(dauer_gesamt)))
    print("-" * (15 + 3 * dauer_gesamt))
    for maschine in range(anzahl_maschinen):
        zeile = [" . "] * dauer_gesamt
        for a, auftrag in enumerate(AUFTRAEGE):
            for g, (m, dauer) in enumerate(auftrag):
                if m == maschine:
                    beginn = loeser.Value(plaene[a, g].start)
                    for t in range(beginn, beginn + dauer):
                        zeile[t] = f" A{a}"
        print(f"{MASCHINENNAMEN[maschine]:<14}|" + "".join(zeile))

    print("\n--- Detailplan ---")
    for a, auftrag in enumerate(AUFTRAEGE):
        teile = []
        for g, (maschine, dauer) in enumerate(auftrag):
            beginn = loeser.Value(plaene[a, g].start)
            teile.append(f"{MASCHINENNAMEN[maschine]} {beginn}-{beginn + dauer}")
        print(f"  Auftrag {a}: " + "  ->  ".join(teile))

    # --- Untere Schranke zum Vergleich ------------------------------------
    laengster_auftrag = max(sum(d for _, d in a) for a in AUFTRAEGE)
    hoechste_maschinenlast = max(
        sum(d for auftrag in AUFTRAEGE for m, d in auftrag if m == maschine)
        for maschine in range(anzahl_maschinen))
    schranke = max(laengster_auftrag, hoechste_maschinenlast)
    print(f"\nUntere Schranke (laengster Auftrag / hoechste Maschinenlast): {schranke}")
    print(f"Erreichter Makespan: {loeser.Value(makespan)}"
          f"{'  -> beweisbar bestmoeglich' if loeser.Value(makespan) == schranke else ''}")
    print("=" * 74)


if __name__ == "__main__":
    loese_jobshop()