File size: 1,632 Bytes
7a0a17c | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | """
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())}
|