CS Paper Radar

Minimizing the makespan in job shop scheduling under conflict graph constraints

Nour Elhouda Tellache, Abdenour Azerine

cs.DM math.OC ·submitted 2026-09-03 17:49 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LO ·2026-08-26 ·Huy Tuan Nguyen, Duc Trung Kim Nguyen, Khanh To Van
benchmark similarity 0.64
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.

0.26

Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation

cs.DS ·2026-09-28 ·Shreyas Ghildiyal, Muralidhara V N
similarity 0.64
Abstract

In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. We study a variant in which every used machine must remain idle during a contiguous \emph{break} of prescribed length $x$ somewhere in the scheduling horizon. We show that this additional constraint makes the problem hard, except when $x\le1$. First, for every fixed $x\ge2$, deciding whether $k$ machines suffice for the assignment of a given set of jobs is NP-complete, even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard. Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. Finally, we give a deterministic polynomial-time algorithm that, on every feasible instance, outputs a schedule using at most $\OPT+1$ machines, where $\OPT$ is the true minimum. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm guarantees $\OPT$ machines for any fixed $x\ge2$, so the additive guarantee of one is best possible.

0.07

Diverse Schedules for Makespan Minimization on Unrelated Machines

cs.DS ·2026-10-20 ·Sebastian Bruchhold, Matthias Mnich, Karolina Tammemaa, Morten Weber, Michalis Xefteris +1 more
similarity 0.62
Abstract · Updated funding acknowledgment, scientific content unchanged

We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules: Instead of outputting a single schedule, we seek a collection of schedules with provable makespan guarantees and substantially different job assignments. Committing to a single schedule in advance may be undesirable. Processing times may be uncertain, and constraints or domain knowledge may emerge later, so $k$ schedules of similar quality offer meaningful alternatives. We measure pairwise diversity by the weighted Hamming distance between job assignments and study the two standard objectives in the diverse-solutions literature: max-sum diversity, which maximizes the total pairwise distance between schedules, and max-min diversity, which maximizes the smallest pairwise distance. For the max-sum objective, we show that optimal diversity can be achieved in polynomial time without sacrificing the classic makespan approximation factor. For every feasible makespan target $T$, we can compute $k$ schedules of makespan at most $2T$ whose max-sum diversity is optimal among all $k$ schedules of makespan at most $T$. Therefore, we match the classic factor-$2$ makespan guarantee of Lenstra, Shmoys, and Tardos (Math. Prog., 1990) and preserve optimal diversity. For the max-min objective, we show that the diversity problem is inherently harder. Namely, we show that, even without makespan constraints, deciding whether three schedules of given pairwise diversity exist is NP-hard. We complete this with two complementary bicriteria approximation algorithms for every fixed $k$ and $\varepsilon \in (0,1)$. The first preserves almost all of the optimal max-min diversity with makespan at most $(3\lceil12/\varepsilon\rceil+1)T$. The second keeps the makespan arbitrarily close to the classic $2$ guarantee while achieving a $\frac{1}{2}(1-\varepsilon)$ fraction of the optimal max-min diversity.

0.20

Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times

cs.CC cs.DMmath.CO ·2026-09-23 ·Zhi-Long Chen, Nicholas G. Hall
theory similarity 0.61
Abstract · 38 pages, 2 figures, 5 tables

We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective $Φ=F+p\sum_jw_j$, where $F$ is total weighted tardiness. The algorithm enumerates at most $N$ release-date residues modulo $p$, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in $O(N^5)$ arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term $p\sum_jw_j$ is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.

0.21

Approximation algorithms for identical parallel machine scheduling with assignment costs

cs.DS ·2026-10-24 ·Wei Li
similarity 0.61
Abstract

We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.

0.24

Minimizing the Makespan Approximately on Two Identical Parallel Machines with a Loading--Unloading Server

cs.DS math.OC ·2026-08-19 ·Keramat Hasani, Frank Werner
theory similarity 0.61
Abstract · 29 pages, 1 appendix

We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without interruption on its assigned machine, and unloaded immediately after processing, with a common positive integer duration for all loading and unloading operations. We prove that the decision problem is NP-complete for every fixed server-operation duration and strongly NP-complete when this duration is part of the input. We then analyse ordinary list scheduling and the longest-processing-time rule in the non-unit setting. List scheduling has a tight supremum ratio of two. For the longest-processing-time rule, we obtain the exact worst-case ratio when all processing times are at least the server-operation duration, and derive new parameter-dependent lower and upper bounds for unrestricted instances. The results show that both processing-time granularity and blocking generated by short jobs shape the approximation behaviour of the common-server problem.

0.08

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

Conflict-Free Cuts: Exploring the Boundaries of Tractability

cs.DS math.CO ·2026-11-11 ·Subrahmanyam Kalyanasundaram, Subodh Kumar
theory similarity 0.59
Abstract · 48 pages, 9 figures

A conflict-free cut of a host graph $G$ is an edge cut containing no conflicting pair of edges. The conflicts are specified by a conflict graph $\widehat G$ whose vertex set is $E(G)$. The conflict-free cut problem asks if the given instance $(G, \widehat G)$ has a conflict-free cut. When restricted to planar $G$ and 1-regular $\widehat G$, the problem is polynomial time solvable when $G$ has maximum degree 4, but NP-complete already at maximum degree 5. We study the complexity of conflict-free cut problem under restrictions on the degrees of $G$, the components of $\widehat G$, and the locality of the conflicts. A conflict is local if its two edges share an endpoint in $G$. We prove the following results. * For $Δ(\widehat G)\le1$, a directed-cycle formulation gives a polynomial-time algorithm when $|E(G)|\le2|V(G)|$, hence for maximum degree four. The problem is NP-complete on $5$-regular hosts with exactly $1$-regular conflicts. * For $Δ(\widehat G)\le1$, we give a constructive FPT algorithm in $s_4(G)=\sum_v\max\{0,d_G(v)-4\}$, single-exponential for planar hosts. For arbitrary conflicts, we give an XP algorithm in $η=\max\{0,|E(\widehat G)|-|V(G)|\}$. * On $4$-regular hosts, local exactly $2$-regular conflicts with components $C_3,C_4$ give NP-completeness. For local conflicts at maximum degree four, pair or triangle components separately permit polynomial algorithms, but mixing them gives NP-completeness. We classify cases where $\widehat G$ is a union of cliques. * An $a$-COC is a vertex set whose deletion leaves components of order at most $a$. For local conflicts, the problem is FPT in the minimum $2$-COC size, but NP-complete with a supplied $3$-COC of size six. Without locality, hardness holds with a supplied $2$-COC of size six. Both hardness results use exactly $1$-regular conflicts.

0.20