Abstract
This paper studies a non-preemptive infinite-horizon scheduling problem with a single server and a fixed set of recurring jobs. Each job is characterized by two given positive numbers: job duration and maximum allowable time between the job completion and its next start. We show that for a feasible problem there exists a periodic schedule. We also provide necessary conditions for the feasibility, formulate an algorithm based on dynamic programming, and, since this problem is NP-hard, formulate and study heuristic algorithms. In particular, by applying the theory of Markov Decision Process, we establish natural necessary conditions for feasibility and develop heuristics, called frequency based algorithms, that outperform standard scheduling heuristics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Feinberg, E., Curry, M. Generalized Pinwheel Problem. Math Meth Oper Res 62, 99–122 (2005). https://doi.org/10.1007/s00186-005-0443-4
Issue Date:
DOI: https://doi.org/10.1007/s00186-005-0443-4