Smith, Benjamin
(2025)
Periodic Scheduling
Pinwheels, Pareto Surfaces, and Polycules
(and Powersort)
PhD thesis, University of Liverpool.
|
Text
201381305_Aug2025.pdf - Author Accepted Manuscript Download (2MB) | Preview |
Abstract
Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks on a single machine subject to periodic deadlines or frequencies: maximal time spans between consecutive executions of each task. The density of a Pinwheel Scheduling instance is the sum of the inverses of these frequencies; in 1993, Chan and Chin conjectured that any Pinwheel Scheduling instance with a density of at most 5/6 is schedulable – this conjecture stood for 31 years before being proved by Akitoshi Kawamura in 2024. We provided key elements of this proof that will be reproduced here: a formalized notion of Pareto surfaces (finite sets of solutions capable of solving infinite classes of Pinwheel Scheduling instances), the state-ofthe-art oracle for arbitrary Pinwheel Scheduling instances, and 23 schedules which solve all Pinwheel Scheduling instances with at most 5 tasks. Polyamorous Scheduling is the related problem of scheduling pairwise meetings between members of a complex social group, represented as an edge-weighted graph. The goal of Polyamorous Scheduling is to find a schedule that minimises the maximal weighted waiting time between consecutive occurrences of the same edge. We introduce this problem, giving both a 5.24-approximation and the first hardness-of-approximation result presented for a Periodic Scheduling problem. We also introduce poly density – a generalization of the density of Pinwheel Scheduling that serves to define both upper and lower bounds for Polyamorous Scheduling. Our final topic is unrelated: Multiway Powersort, a stable mergesort variant that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This builds on Powersort (Munro & Wild, 2018), which has recently been adopted by the CPython reference implementation of Python, as well as by PyPy and other libraries. Multiway Powersort reduces the number of memory transfers, which increasingly determine the cost of internal sorting. We demonstrate that our 4-way Powersort implementation can achieve substantial speedups over 2-way Powersort and other stable sorting methods without compromising the optimally run-adaptive performance of Powersort.
| Item Type: | Thesis (PhD) |
|---|---|
| Uncontrolled Keywords: | Pinwheel Scheduling, Periodic Scheduling, Algorithms, Sorting, Scheduling, Powersort, Polyamorous Scheduling |
| Divisions: | Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 11 Feb 2026 09:23 |
| Last Modified: | 11 Feb 2026 10:24 |
| DOI: | 10.17638/03194461 |
| Supervisors: |
|
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3194461 |
| Disclaimer: | The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate. |
Altmetric
Altmetric