Solved at Scale

Solved with CP-SAT

An external CP-SAT solver solves the pinned job-shop instance under deterministic parameters and proves the makespan. The lesson quotes only the deterministic fields of the run, and the schedule shown is decoded from the run's own solution values.

highlighted = computed this step

Invocation

The invocation is cpsat_stream_solve solve job_shop.jsonl --params num_search_workers:1,random_seed:1, with the solution values written to a temporary --sol file. Why: a single search worker and a fixed seed make the run deterministic, so the schedule quoted below is reproducible rather than anecdotal.

one worker, one seed, deterministic solve\text{one worker, one seed, deterministic solve}
Instance handed to the solverThe parsed task table is the solver's input; no schedule is shown yet.3 jobs, 3 machines, 8 tasks, solver inputmachinedurationJ1 T113J1 T222J1 T332J2 T112J2 T231J2 T324J3 T124J3 T233

Solver result

The solver reports status OPTIMAL with objective value 11 and best objective bound 11. Why: the objective is the makespan, the latest task end; OPTIMAL means the solver proved no shorter schedule exists, not merely found a good one. The output also carries timing, conflict, and branch counts; those fields are omitted here because they vary from run to run, and only the status, the objective value, the bound, and the solution values are deterministic.

status OPTIMAL, makespan 11\text{status OPTIMAL, makespan }11
CP-SAT decoded scheduleOne row per machine, task blocks on a shared time axis; the makespan marker is labeled.makespan 11, certified optimalM1M2M3J1 T1[2,5]J1 T2[5,7]J1 T3[7,9]J2 T1[0,2]J2 T2[2,3]J2 T3[7,11]J3 T1[0,4]J3 T2[4,7]makespan 11011time

The decoded schedule

J1: T1 on M1 [2,5], T2 on M2 [5,7] and T3 on M3 [7,9]. J2: T1 on M1 [0,2], T2 on M3 [2,3] and T3 on M2 [7,11]. J3: T1 on M2 [0,4] and T2 on M3 [4,7]. Why: these are the literal decoded solution values from the real solve, not a hand-picked example; the labels J1 through J3, M1 through M3, and T1 through T3 are the diagram's own labels.

decoded values, exactly as solved\text{decoded values, exactly as solved}
CP-SAT decoded scheduleOne row per machine, task blocks on a shared time axis; the makespan marker is labeled.makespan 11, certified optimalM1M2M3J1 T1[2,5]J1 T2[5,7]J1 T3[7,9]J2 T1[0,2]J2 T2[2,3]J2 T3[7,11]J3 T1[0,4]J3 T2[4,7]makespan 11011time

Diagram note

Each row is one machine, M1 through M3, on a shared time axis from 0 to 11; each block is one task labeled by job and task with its start and end times, and the dashed line carries the word makespan with the certified value. Pixel positions are rounded for layout; every number shown is exact.

one row per machine, exact times\text{one row per machine, exact times}
CP-SAT decoded scheduleOne row per machine, task blocks on a shared time axis; the makespan marker is labeled.makespan 11, certified optimalM1M2M3J1 T1[2,5]J1 T2[5,7]J1 T3[7,9]J2 T1[0,2]J2 T2[2,3]J2 T3[7,11]J3 T1[0,4]J3 T2[4,7]makespan 11011time