Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2403.19197 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909154129477632 |
|---|---|
| author | Durand, Martin Pascual, Fanny |
| author_facet | Durand, Martin Pascual, Fanny |
| contents | We study the collective schedules problem, which consists in computing a one machine schedule of a set of tasks, knowing that a set of individuals (also called voters) have preferences regarding the order of the execution of the tasks. Our aim is to return a consensus schedule. We consider the setting in which all tasks have the same length -- such a schedule can therefore also be viewed as a ranking. We study two rules, one based on a distance criterion, and another one based one a binary criterion, and we show that these rules extend classic scheduling criteria. We also consider time constraints and precedence constraints between the tasks, and focus on two cases: the preferences of the voters fulfill these constraints, or they do not fulfill these constraints (but the collective schedule should fulfill them). In each case, either we show that the problem is NP-hard, or we provide a polynomial time algorithm which solves it. We also provide an analysis of a heuristic, which appears to be a 2 approximation of the Spearman's rule. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19197 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Ordering Collective Unit Tasks: from Scheduling to Computational Social Choice Durand, Martin Pascual, Fanny Computer Science and Game Theory 68Q25 I.2.8 We study the collective schedules problem, which consists in computing a one machine schedule of a set of tasks, knowing that a set of individuals (also called voters) have preferences regarding the order of the execution of the tasks. Our aim is to return a consensus schedule. We consider the setting in which all tasks have the same length -- such a schedule can therefore also be viewed as a ranking. We study two rules, one based on a distance criterion, and another one based one a binary criterion, and we show that these rules extend classic scheduling criteria. We also consider time constraints and precedence constraints between the tasks, and focus on two cases: the preferences of the voters fulfill these constraints, or they do not fulfill these constraints (but the collective schedule should fulfill them). In each case, either we show that the problem is NP-hard, or we provide a polynomial time algorithm which solves it. We also provide an analysis of a heuristic, which appears to be a 2 approximation of the Spearman's rule. |
| title | Ordering Collective Unit Tasks: from Scheduling to Computational Social Choice |
| topic | Computer Science and Game Theory 68Q25 I.2.8 |
| url | https://arxiv.org/abs/2403.19197 |