Skip to content
Preprint

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

Aug 2026 · 0 citations · 24 references
Computer Science

TL;DR

This paper develops the first exact SAT and constraint programming (CP) formulations for the JSPPR, and provides corrected optimal makespans and a complete set of certified optimal results for the JSPPR benchmark, establishing a reliable reference for future studies.

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.

View source

Similar papers

Preprint Sep 2026

Minimizing the makespan in job shop scheduling under conflict graph constraints

This work establishes a polynomial equivalence between JSC and a variant of the resource-constrained job shop problem with unit-capacity resources and proposes a genetic algorithm using permutation-with-repetition encoding and active, non-delay, and hybrid schedule evaluation procedures.

Nour ElHouda Tellache, Abdenour Azerine · 0 citations
Preprint Aug 2026

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

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...

Gia-Ho-Ang Bao, Tuyen Van Kieu, Khanh Van To · 0 citations
Open access Sep 2026

Efficient exact formulations for the flexible job shop scheduling with flexible maintenance

In modern manufacturing systems, integrating preventive maintenance into production scheduling is essential to ensure operational efficiency and equipment reliability. This paper addresses the flexible job shop scheduling problem under machine unavailability constraints caused by non‐fixed maintenance tasks. We propo...

Tom Perroux, T. Arbaoui, Leila Merghem Boulahia et al. · 0 citations
Open access 2026

From Feasibility to Multi-Criteria Optimization in Service Team Transport Scheduling: A Declarative and Metaheuristic Perspective

The scalability of a multi-criteria optimization for the Service Team Transport Scheduling (STTS) problem is investigated, minimizing total travel time, maximum vehicle worktime, and total vehicle engagement time to define scale-aware algorithmic boundaries essential for real-time decision support systems.

Jarosław Rudy, G. Radzki · 0 citations
Open access Aug 2026

An Adaptive Co-Evolutionary Memetic Algorithm for a Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup and Transportation Times

The hybrid flow shop scheduling problem (HFSP) with unrelated parallel machines (UPMs), sequence-dependent setup times (SDSTs), and inter-stage transportation times has recently emerged as a prominent research topic. To address this scheduling problem with the objective of minimizing the maximum completion time (makesp...

De-Kun Wang, Yue-Chang Lei, Zheng Yuan et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.