Finite Pinwheel Scheduling: the \(\text{k}\)-Visits Problem

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, Ευριπίδης Μάρκου, Aris Pagourtzis
DOI: 10.1137/1.9781611978971.16
Cited by: 2

Abstract

Pinwheel Scheduling is a fundamental scheduling problem, in which each task \(i\) is associated with a positive integer deadline \(d_i\), and the objective is to schedule one task per time slot, ensuring each task perpetually appears at least once in every \(d_i\) time slots. Although conjectured to be PSPACE-complete, it remains open whether Pinwheel Scheduling is NP-hard (unless a compact input encoding is used) or even contained in NP.

Fields of Study & Subjects

Real-Time Systems Scheduling Optimization and Search Problems Scheduling and Optimization Algorithms

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Publisher
Society for Industrial and Applied Mathematics
Pages
355–371
Publication date
1 January 2026
Language
EN