Minimizing the makespan in job shop scheduling under conflict graph constraints
2026-09-03 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a scheduling problem where certain jobs can't run at the same time because they share resources, called the job shop scheduling problem with a conflict graph (JSC). They show that solving JSC is as hard as another known tough scheduling problem and find a special easy case when there are only two machines. The authors create mathematical models and a genetic algorithm to find good schedules and test these methods on benchmark and random examples to see how well they work. Their work helps understand and tackle scheduling when jobs share resources but have separate machine routes.
job shop schedulingconflict graphmakespanNP-hardmixed-integer linear programminggenetic algorithmresource constraintslower boundsbenchmark instances
Authors
Nour Elhouda Tellache, Abdenour Azerine
Abstract
We study the job shop scheduling problem with a conflict graph (JSC), in which adjacent jobs in the conflict graph cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. The problem models settings where jobs share additional resources while retaining their individual machine routings. We first investigate its computational complexity and establish a polynomial equivalence between JSC and a variant of the resource-constrained job shop problem with unit-capacity resources. Although the general problem on two machines is NP-hard, we identify a polynomially solvable special case. For the general problem, we develop precedence-based and time-indexed mixed-integer linear formulations, along with lower bounds on the makespan. We also propose a genetic algorithm using permutation-with-repetition encoding and active, non-delay, and hybrid schedule evaluation procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks, as well as randomly generated generalized job shop instances, are conducted to evaluate the performance of the proposed formulations, lower bounds, and genetic algorithm.