solver.py

"""
OR-Tools CP-SAT single-machine scheduling.
"""
from ortools.sat.python import cp_model
from typing import List, Dict, Any


def solve_single_machine(tasks: List[Dict[str, Any]], horizon: int = 10000) -> Dict[str, Any]:
    model = cp_model.CpModel()
    starts = {}
    ends = {}
    intervals = []
    for t in tasks:
        tid = t["id"]
        dur = int(t.get("duration", 1))
        start = model.NewIntVar(0, horizon, f"s_{tid}")
        end = model.NewIntVar(0, horizon, f"e_{tid}")
        interval = model.NewIntervalVar(start, dur, end, f"i_{tid}")
        starts[tid] = start
        ends[tid] = end
        intervals.append(interval)
    model.AddNoOverlap(intervals)
    makespan = model.NewIntVar(0, horizon, "makespan")
    for e in ends.values():
        model.Add(makespan >= e)
    model.Minimize(makespan)
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return {"error": "No solution found", "status": str(status)}
    schedule = [{"id": t["id"], "start": solver.Value(starts[t["id"]]), "end": solver.Value(ends[t["id"]])} for t in tasks]
    return {"schedule": schedule, "makespan": int(solver.ObjectiveValue())}