Scheduling on identical machines with conflicts to minimize the total completion time
Nour ElHouda Tellache, Lydia Aoudia, Mourad Boudhar
原文摘要
This paper addresses the problem of scheduling jobs on identical machines with conflict constraints, where certain jobs cannot be scheduled simultaneously on different machines. We focus on the case where conflicts can be represented by a simple undirected graph, and the objective is to minimize the total completion time. We establish that the problem is strongly NP-hard even on two machines with two distinct processing times. For unit-time jobs, we prove that the problem is polynomially solvable on two machines for any conflict graph, but becomes strongly NP-hard on three machines. We further identify polynomially solvable cases for specific classes of conflict graphs. For the general problem, we propose mathematical models, lower bounds, and a genetic algorithm. We evaluate their performance through computational experiments on a wide range of instances derived from well-known benchmark instances in the literature.
cs.DM · math.OC