← 研踪 PaperTrailarXiv:2507.01759 · v2
Scheduling on identical machines with conflicts to minimize the total completion time
首次提交 2025-07-02 22:36
版本更新 2026-11-10 04:00
雷达观测 2026-11-11 11:04
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-10 04:00 · 最新观测版本
Scheduling on identical machines with conflicts to minimize the total completion time
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.
查看此版本解读 →查看此版本原文 ↗