Search Results

Documents authored by van Lieshout, Rolf Nelson

Document
DOI: 10.4230/OASIcs.ATMOS.2025.1
The Fair Periodic Assignment Problem

Authors: Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
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.
Cite as

Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum. The Fair Periodic Assignment Problem. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanlieshout_et_al:OASIcs.ATMOS.2025.1,
  author =	{van Lieshout, Rolf Nelson and van Rossum, Bartholome\"{u}s Theodorus Cornelis},
  title =	{{The Fair Periodic Assignment Problem}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{1:1--1:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.1},
  URN =		{urn:nbn:de:0030-drops-247574},
  doi =		{10.4230/OASIcs.ATMOS.2025.1},
  annote =	{Keywords: Cyclic scheduling, Fairness, Traveling Salesman Problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.4
Periodic Event Scheduling with Flexible Infrastructure Assignment

Authors: Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances.
Cite as

Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner. Periodic Event Scheduling with Flexible Infrastructure Assignment. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2024.4,
  author =	{Bortoletto, Enrico and van Lieshout, Rolf Nelson and Masing, Berenike and Lindner, Niels},
  title =	{{Periodic Event Scheduling with Flexible Infrastructure Assignment}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{4:1--4:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.4},
  URN =		{urn:nbn:de:0030-drops-211929},
  doi =		{10.4230/OASIcs.ATMOS.2024.4},
  annote =	{Keywords: Periodic Event Scheduling, Periodic Timetabling, Railway Timetabling, Matchings, Infrastructure Assignments, Platform Assignments, Station Capacities}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact