Living with Hard Problems

# Python, Google OR-Tools CP-SAT: assign 6 support shifts to 4 agents, no one twice in a row, balance load
from ortools.sat.python import cp_model
m = cp_model.CpModel()
agents, shifts = range(4), range(6)
x = {(a, s): m.NewBoolVar(f"x{a}_{s}") for a in agents for s in shifts}
for s in shifts: m.AddExactlyOne(x[a, s] for a in agents)                       # every shift covered once
for a in agents:
    for s in range(5): m.Add(x[a, s] + x[a, s + 1] <= 1)                         # no back-to-back shifts
    m.Add(sum(x[a, s] for s in shifts) <= 2)                                      # at most 2 shifts each
solver = cp_model.CpSolver(); solver.parameters.max_time_in_seconds = 2.0
status = solver.Solve(m)                                                          # OPTIMAL / FEASIBLE / INFEASIBLE

// heuristic: first-fit decreasing bin packing (uses at most about 11/9 of the optimal bins plus a constant)
const pack = (sizes: number[], cap: number) => sizes.sort((a, b) => b - a).reduce((bins: number[], s) => {
  const i = bins.findIndex(b => b + s <= cap); i < 0 ? bins.push(s) : (bins[i] += s); return bins; }, []);