2026-08-18T07:58:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24757 2026-02-09T07:37:51Z ddc:004 open_access

The Fair Periodic Assignment Problem van Lieshout, Rolf Nelson van Rossum, Bartholomeüs Theodorus Cornelis Cyclic scheduling Fairness Traveling Salesman Problem We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a 𝒪(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a 𝒪(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum 2025 Is Part Of OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2025.1 urn:nbn:de:0030-drops-247574 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.1 eng https://creativecommons.org/licenses/by/4.0/legalcode