Minimizing the makespan in job shop scheduling under conflict graph constraints
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.
Related
- Bus Fleet Electrification Under Capital Cost and Scheduling Constraints: A Five-Agency Case Study
- Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
- Exponential random graph models with soft clique constraints
- Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
- The Car Resequencing Problem with Makespan Minimization
BibTeX
@misc{tellache2026minimizing,
title = {{Minimizing the makespan in job shop scheduling under conflict graph constraints}},
author = {Nour Elhouda Tellache and Abdenour Azerine},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.04161},
eprint = {2609.04161},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04161},
}
RIS
TY - UNPB
TI - Minimizing the makespan in job shop scheduling under conflict graph constraints
AU - Nour Elhouda Tellache
AU - Abdenour Azerine
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2609.04161
UR - https://arxiv.org/abs/2609.04161
AB - 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.
ER -