{"id":"arxiv/2609.04161","url":"https://arxiv.org/abs/2609.04161","tags":["cs.DM","math.OC"],"score":0,"title":"Minimizing the makespan in job shop scheduling under conflict graph constraints","domain":"cs.DM","source":"arxiv","authors":["Nour Elhouda Tellache","Abdenour Azerine"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}