Balanced assignments of periodic tasks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915304387379200 |
|---|---|
| author | Gachet, Héloïse Meunier, Frédéric |
| author_facet | Gachet, Héloïse Meunier, Frédéric |
| contents | This work addresses the problem of assigning periodic tasks to workers in a balanced way, i.e., so that each worker performs every task with the same frequency over the long term. The input consists of a list of tasks to be repeated weekly at fixed times and a number of indistinguishable workers. In the basic version, the sole constraint is that no worker performs two tasks simultaneously. In the extended version, additional constraints can be introduced, such as limits on the total number of working hours per week.
Regarding the basic version, a necessary and sufficient condition for the existence of a balanced assignment is established. This condition can be verified in polynomial time. For the extended version, it is demonstrated that whenever a balanced assignment exists, a periodic balanced assignment exists as well, with a tighter bound on the period for the basic version. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Balanced assignments of periodic tasks Gachet, Héloïse Meunier, Frédéric Discrete Mathematics 90B35 G.2.3 This work addresses the problem of assigning periodic tasks to workers in a balanced way, i.e., so that each worker performs every task with the same frequency over the long term. The input consists of a list of tasks to be repeated weekly at fixed times and a number of indistinguishable workers. In the basic version, the sole constraint is that no worker performs two tasks simultaneously. In the extended version, additional constraints can be introduced, such as limits on the total number of working hours per week. Regarding the basic version, a necessary and sufficient condition for the existence of a balanced assignment is established. This condition can be verified in polynomial time. For the extended version, it is demonstrated that whenever a balanced assignment exists, a periodic balanced assignment exists as well, with a tighter bound on the period for the basic version. |
| title | Balanced assignments of periodic tasks |
| topic | Discrete Mathematics 90B35 G.2.3 |
| url | https://arxiv.org/abs/2407.05485 |