CS Paper Radar

Exact SAT and Constraint Programming for Job Shop Scheduling with Time-Varying Peak Power Constraints

Huy Tuan Nguyen, Duc Trung Kim Nguyen, Khanh To Van

cs.LO ·submitted 2026-08-26 04:14 UTC · v1
benchmark

Abstract

The Job Shop Scheduling Problem with Power Requirements (JSPPR) extends the classical job shop scheduling problem by imposing time-varying limits on instantaneous power consumption. Previous studies have used a mixed-integer linear programming formulation and the GRASP x ELS metaheuristic, but no SAT-based exact approach or constraint programming model has been reported. This paper develops the first exact SAT and constraint programming (CP) formulations for the JSPPR. On the 35 published benchmark instances, both SAT and CP prove global optimality for all instances and obtain identical optimal makespans, substantially improving upon the best previously reported results. They also establish four improved makespan values over the GRASP x ELS results reported in the original study. CP proves optimality faster than SAT, while both exact approaches substantially improve the optimality coverage of the MILP formulations, which prove optimality on only 6 and 10 instances using CPLEX and Gurobi, respectively. The certified optimal solutions also reveal inconsistencies in several previously reported benchmark results, including makespans below the proven optimum. We provide corrected optimal makespans and a complete set of certified optimal results for the JSPPR benchmark, establishing a reliable reference for future studies.

Closest papers

Nearest neighbours by meaning across the whole index.

Solving Distributed Flexible Job Shop Scheduling Problem Using SAT

cs.LO ·2026-10-10 ·Phuong Dang Anh, Duc Nguyen Kim Trung, To Van Khanh
benchmark similarity 0.72
Abstract

The Distributed Flexible Job Shop Scheduling Problem (DFJSP) requires the joint determination of factory assignment, machine selection, and operation sequencing to minimize the makespan. This paper presents an exact SAT-based approach built on an efficient SAT formulation that exploits problem structure through propagation, symmetry breaking, and incremental SAT solving to effectively address these coupled decisions. The proposed method is evaluated on 76 standard benchmark instances from the Fattahi, Brandimarte, and rdata datasets under two- and three-factory configurations. Together with previously established results, the new SAT optimality certificates bring the total number of proven-optimal instances to 72 out of 76, including three newly certified instances; for two of these instances, SAT also improves the previous best-known makespans. Across the benchmark configurations, SAT achieves the best results on four of the five configurations and remains competitive with strong exact approaches such as CP and LBBD1_CPIL, as well as existing metaheuristic methods. These results demonstrate that the proposed SAT framework is an effective exact approach for the DFJSP, combining strong solution quality with rigorous optimality certification and offering a complementary exact method for future DFJSP studies and evaluations on additional benchmark instances.

0.13

Minimizing the makespan in job shop scheduling under conflict graph constraints

cs.DM math.OC ·2026-09-03 ·Nour Elhouda Tellache, Abdenour Azerine
similarity 0.64
Abstract

We study the job shop scheduling problem with a conflict graph, in which adjacent jobs cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. We establish a polynomial equivalence with a resource-constrained job shop problem having unit-capacity resources and binary resource requirements The problem is strongly NP-hard even on two machines with unit-time operations. For this setting, we derive an optimal-makespan formula and a linear-time algorithm when the conflict graph is a cluster graph, given the clique partition. We also develop a polynomial-time $4/3$-approximation algorithm for arbitrary conflict graphs on two machines when each job has exactly two unit-time operations. For the general problem, we propose four mixed-integer linear formulations, lower bounds, and a genetic algorithm with active, non-delay, and hybrid decoding procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks and on randomly generated generalized job shop instances evaluate the proposed methods and show that the genetic algorithm generally improves on constructive heuristics.

0.33

From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling

cs.AI math.OC ·2026-08-31 ·Vipul Patel, Anirudh Deodhar, Dagnachew Birru
published similarity 0.61
Abstract · 13 pages, 10 tables. Accepted at MODeM Workshop, IJCAI-ECAI 2026. Extends arXiv:2607.05177

Healthcare workforce scheduling is an NP-hard optimization problem requiring simultaneous satisfaction of labor regulations, coverage requirements, employee preferences and cost objectives. Existing approaches (genetic algorithms, integer programming, constraint programming) model 6-12 constraints at shift-level granularity and cannot guarantee regulatory compliance. They also lack support for multi-role, multi-skill heterogeneity, mandatory break scheduling with midpoint control, acuity-weighted workload equity, sub-shift granularity, inter-week stability, and cross-midnight shifts. This paper presents CP-SAT: a Constraint Programming formulation for multi-role, multi-skill healthcare scheduling. CP-SAT enforces 14 hard constraints guaranteeing zero regulatory violations, while optimizing 15 soft objectives via a unified weighted penalty function. Contributions include a shift-window decomposition enabling break scheduling with centrality control, acuity-weighted workload equity, multi-granularity resolution from 15 minutes to 1 day, inter-week stability, and grid-offset preprocessing mapping cross-midnight shifts into a single scheduling day without solver changes. CP-SAT is evaluated on 18 instances: five synthetic hospital units (10-33 nurses), 10 INRC-II benchmarks (5-80 nurses, up to 8-week horizons) and 3 NRP-23 compatible instances (10-25 nurses) with cross-midnight Night shifts. Results: zero hard-constraint violations across all 18 instances by construction; proven optimality on INRC-II n005w4 (objective 118, gap 0.0%, 104s); feasible schedules scaling to 179,800 variables and 351,425 constraints (80 nurses); service quality improved 50-67% over MOGA; and model size scaling near-linearly at approximately 4,400 variables per employee. The formulation enforces 29 total constraints (14 hard, 15 soft), nearly three times the industry average.

0.36

Cycle time minimization for the simple assembly line balancing problem under peak power constraints

cs.LO ·2026-08-25 ·Bao Gia Hoang, Tuyen Van Kieu, Khanh Van To
similarity 0.61
Abstract · Submitted to Engineering Optimization. This preprint has not yet undergone peer review

Peak power limits restrict concurrent tasks and may increase assembly-line cycle time. To the best of our knowledge, this study is the first to minimize cycle time for the simple assembly line balancing problem type 2 (SALBP-2) with a fixed number of workstations and a fixed limit on total instantaneous power. An exact satisfiability (SAT) method finds feasible schedules, searches systematically for shorter cycles, and proves optimality when possible. Two reproducible formulas define looser and tighter power limits for 72 cases based on the standard SALBP library, with Gurobi and CPLEX providing commercial MIP and CP comparisons. Relative to standard SALBP-2 optima, the two limits increase the best-known cycle time by 16.49% and 61.02% on average. The best-performing SAT configurations find a feasible solution for every case, solve more cases to optimality than each commercial solver, and when both prove optimality, are almost always faster under the reported settings.

0.33

System Strength-Constrained Scheduling with Switchable Grid-Forming and Grid-Following Generation Resources

eess.SY ·2026-09-24 ·Jiaxin Wang, Fei Teng, Huanhai Xin, Jing Dai, Tomislav Capuder +1 more
similarity 0.57
Abstract · 15 pages, 15 figures

Inverter-based resources (IBRs) are increasingly dominating modern power systems, posing significant challenges to cost-effectively maintain system strength for stability. At the same time, the operating behaviors of IBRs are software-defined, including both their steady-state power outputs and control modes, e.g. grid-forming (GFM) and grid-following (GFL). Such flexibility has not been fully explored to efficiently operate future power systems. This paper develops a novel framework that simultaneously optimizes IBR operating behaviors and ensures adequate system strength. A comprehensive solution is provided to integrate system strength constraints into scheduling models, despite their inherent strong non-convexities. We derive a rigorous linear-matrix-inequality (LMI) reformulation of the system strength constraint, effectively addressing non-explicit formulations and dimension variation issues caused by GFM/GFL mode switching of IBRs. Then, we equivalently convert the original non-convex implicit system strength-constrained scheduling problem into an explicit mixed-integer semi-definite programming (MISDP) problem by incorporating the reformulated system strength constraint along with other operational constraints. We further provide a Rayleigh Cut method, which is compatible with standard mixed-integer linear programming (MILP) solvers, to solve this system strength-constrained scheduling problem. Case studies on a modified IEEE 118-bus system and a practical Jiangsu power system demonstrate the performance of the proposed methods.

0.21

BOLT: Multi-Bottleneck Bound-Guided Learning for Flexible Job-Shop Scheduling with Time Lags and Resource-Coupled Transport

cs.LG math.OC ·2026-10-15 ·Ziheng Zhang, Wei Zhang, Yunyi Zhao, Zuming Liu, Wei Zhou +1 more
theorycode/data similarity 0.56
Abstract · 12 pages main text plus 18 pages of supplementary material appended after the references (30 pages total). Code, data, and trained models: h…

Flexible job-shop scheduling becomes resource-coupled when a scarce vehicle fleet moves jobs between stations, because the schedule sets the transport waits. BOLT (bound-oriented learning for transport-coupled scheduling) builds a lower bound from chain, machine-capacity, and fleet-capacity relaxations. The bound equals the makespan at termination, so its per-step changes form a reward that sums to a constant minus the makespan. Because it never exceeds the attainable makespan, each candidate's bound increase is a proven rise of the makespan floor, which the policy reads as a price. The root bound certifies a completed schedule's suboptimality gap without a solver. On industry-motivated 10-module prefabricated-construction instances, explicit transport coupling outperforms a transport-penalty policy in every tested cell where loaded moves occupy at least 66% of fleet time and in none at or below 56%. Across five zero-shot 50- and 80-module production batches, BOLT outperforms the best dispatching-rule pair on four and the penalty policy on the three with long moves. In the three-vehicle 80-module batch, its mean makespan is 13.0% below the best pair and 4.2% below an hour-budget constraint-programming solver whose proven gap averages 34%. BOLT decides in 2.3-5.9 ms per event on one processor core and re-plans a disruption in seconds.

0.40

An FPTAS for Two-Machine Open-Shop Scheduling with a Single Unavailability Interval

cs.DM ·2026-09-10 ·Hao Lu, Yuan Yuan, Xingwu Liu, Xin Han, Yong Zhou
similarity 0.54
Abstract

We consider the two-machine open-shop scheduling problem in which one machine is unavailable during a fixed interval. We study the resumable setting: an operation interrupted by the unavailability interval may resume, without penalty, when the machine becomes available. The objective is to minimize the makespan. Although the problem is NP-hard and several approximation algorithms are known, whether it admits a fully polynomial-time approximation scheme (FPTAS) has remained open for two decades. We resolve this question affirmatively by giving the first FPTAS, thereby strengthening the previously known polynomial-time approximation scheme (PTAS). As an intermediate result, we develop a new pseudo-polynomial dynamic program with seven state dimensions, improving on the ten-dimensional formulation in the literature.

0.33

Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation

cs.DS cs.CCcs.DM ·2026-10-05 ·Jonas Friemel, Tilo Hoitz, Phillip Keldenich, Arne Schmidt
similarity 0.54
Abstract

We consider a matching problem in which the cost of each edge is a vector with $k$ components. The cost of a matching is the sum of the bottlenecks over all components, and we ask whether there is a perfect matching of cost at most some value $Z$. This type of matching has applications in heavily synchronized job-shop scheduling problems and in reconfiguration problems, where movement is restricted to a single direction per step. In this paper, we analyze the problem from a parameterized complexity perspective and provide various results including FPT-membership for parameters $k$ and $Z$ combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually. The reduction also implies para-NP-hardness parameterized by either maximum degree or treewidth. We further show hardness of approximation within a super-logarithmic factor for the optimization variant and provide a $k/d$-approximation algorithm for any constant $d \leq k$ as well as an efficient approximation scheme parameterized by $k$. With parameter $Z$, we show that no FPT-time $F(Z)$-approximation algorithm is possible for any computable function $F$, unless W[1] = FPT.

0.20