Original title: Minimizing the makespan in job shop scheduling under conflict graph constraints
Nour Elhouda Tellache, Abdenour Azerine · September 2026
Scheduling tasks across multiple machines is tricky, especially when certain tasks cannot run at the same time. This paper studies the job shop scheduling problem with a conflict graph. In this setup, jobs connected on a conflict graph cannot run at once on different machines, and the goal is to finish everything in the shortest possible total time, known as the makespan. The researchers showed this problem matches a setup where jobs share single-capacity resources. Although running the general problem on two machines is extremely hard to solve quickly, they found a special case that can be solved efficiently. Finally, they designed math-based optimization models, mathematical lower bounds, and a genetic algorithm to find good schedules.
You're cooking several dishes for a family dinner, and each dish requires a specific sequence of pots and pans. Some dishes can't be cooked at the same time because they need the same pan, so you have to plan carefully to avoid waiting around. In this paper, the jobs are like dishes, the machines are like stoves, and the conflict graph shows which dishes compete for the same pan. The researchers work on scheduling these jobs to minimize the total time, just like you'd try to get dinner ready as quickly as possible.
This problem affects factory managers and schedulers who need to allocate shared resources like tools or workers efficiently. By understanding which cases can be solved quickly, they can reduce production time and costs.
The abstract doesn't state explicit limitations, but the study is limited to the JSC model and tested on specific benchmarks like Lawrence and Taillard instances. The general NP-hard nature means efficient solutions aren't guaranteed for every case.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Minimizing the makespan in job shop scheduling under conflict graph constraints — Nour Elhouda Tellache, Abdenour Azerine
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.