Scheduling on identical machines with conflicts to minimize the mean flow time
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918080163086336 |
|---|---|
| author | Tellache, Nour ElHouda Aoudia, Lydia Boudhar, Mourad |
| author_facet | Tellache, Nour ElHouda Aoudia, Lydia Boudhar, Mourad |
| contents | 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 mean flow time. We show that the problem is NP-hard even on two machines and two distinct processing times. For unit-time jobs, the problem becomes NP-hard when the number of machines increases to three. We also identify polynomial-time 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01759 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scheduling on identical machines with conflicts to minimize the mean flow time Tellache, Nour ElHouda Aoudia, Lydia Boudhar, Mourad Discrete Mathematics Optimization and Control 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 mean flow time. We show that the problem is NP-hard even on two machines and two distinct processing times. For unit-time jobs, the problem becomes NP-hard when the number of machines increases to three. We also identify polynomial-time 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. |
| title | Scheduling on identical machines with conflicts to minimize the mean flow time |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2507.01759 |