Two exact computer methods reached the same optimal completion time in all 35 cases in a published benchmark for job-shop planning under changing power limits. Constraint programming proved every case optimal and used 263.12 seconds in total; a SAT-based method also proved every case optimal, but took 2,672.55 seconds.
On this test, that made constraint programming the faster route to a proof. The result does not establish how either exact method will perform on larger scheduling problems.
The work is a preprint, identified as arXiv:2608.25351v1 and dated 26 Aug 2026. It develops exact SAT and constraint-programming formulations for the JSPPR, job-shop scheduling with time-varying peak power constraints.
The proof was the point
The central measure is makespan, or the overall completion time for the schedule. An exact method must do more than produce a short timetable: it must certify that no shorter answer exists under the model. That certificate is what distinguishes a proven optimum from a merely good result.
Researchers used the complete published set of 35 benchmark instances. The three formulations received the same preprocessing and a 3,600-second limit for each instance, giving the comparison a common boundary.
The CP formulation recast the prior MILP model with interval variables and global constraints. The SAT formulation used an order-based encoding of operation start times and pseudo-Boolean power constraints, which express limits on combinations of yes-or-no choices.
The objective comparison was clear. SAT and CP returned identical optimal makespans across all 35 instances, and each matched the benchmark's best-known value. CP's cumulative proof time was roughly one tenth of SAT's, 263.12 seconds versus 2,672.55 seconds.
The MILP comparison produced far fewer optimality certificates: CPLEX proved optimality on six instances and Gurobi on 10. Historical solver results came from different experimental conditions, so these figures describe this evaluation rather than a universal ranking of the methods.
A benchmark under inspection
The paper's other major finding came from checking the benchmark's history. The re-evaluation uncovered discrepancies between historical values and verified optima, with the gap reaching 49 time units.
In four cases, the exact methods established new optimal makespans of 467, 638, 647 and 657. Those values were lower than the previous figures by 1, 1, 6 and 23 units, respectively.
An independent feasibility check found a more serious problem in the reported schedules. Nine schedules violated the power threshold when their reported start times, machine assignments and execution phases were checked, and seven of those schedules had makespans below the verified optima.
A shorter schedule is not a valid benchmark win if it breaks the constraint being tested. The audit therefore leaves earlier comparisons in need of correction, even though it does not identify a single cause for the discrepancies.
Parsing was part of the uncertainty as well. Ten inputs contained an extra reference to machine 4 even though the data set defines four machines. The authors' conclusions for those cases depend on the stated treatment of that reference.
A strong baseline with a narrow reach
The authors present SAT and CP as effective exact alternatives for this benchmark, with CP offering the better computational trade-off. But the evidence remains narrow: it comes from 35 relatively small instances, so it does not establish how well the methods scale to larger problems.
Nor does the result settle why the historical numbers diverged. The paper points to either errors in earlier results or a mismatch in how instances were parsed, but that question remains unresolved.
For future benchmark work, the practical contribution is a corrected set of optima and a warning that feasibility checks matter alongside headline completion times. The study's conclusions apply to the tested formulations, preprocessing and benchmark, not to every version of power-constrained job-shop scheduling.
The authors report no specific grant from a public, commercial or not-for-profit funding agency. The version assessed here is the first arXiv release, dated 26 Aug 2026.
Paper data and sources
Original title: Exact SAT and Constraint Programming for Job Shop Scheduling with Time-Varying Peak Power Constraints
Authors: Huy Tuan Nguyen, Duc Trung Kim Nguyen, Khanh To Van
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text