solver.py

"""
OR-Tools CP-SAT single-machine (or multi-machine) scheduling.
Input: list of tasks with duration; output: start times and makespan.
"""

from ortools.sat.python import cp_model
from typing import List, Dict, Any, Optional


def solve_single_machine(tasks: List[Dict[str, Any]], horizon: int = 10000) -> Dict[str, Any]:
    """
    tasks: [ {"id": "A", "duration": 2}, ... ]
    Returns: {"schedule": [ {"id": "A", "start": 0, "end": 2} ], "makespan": int } or {"error": "..."}
    """
    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 tid, e in ends.items():
        model.Add(makespan >= e)
    model.Minimize(makespan)

    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status != cp_model.OPTIMAL and status != cp_model.FEASIBLE:
        return {"error": "No solution found", "status": str(status)}

    schedule = []
    for t in tasks:
        tid = t["id"]
        start = solver.Value(starts[tid])
        end = solver.Value(ends[tid])
        schedule.append({"id": tid, "start": start, "end": end})
    return {"schedule": schedule, "makespan": int(solver.ObjectiveValue())}