Generalized Pinwheel Problem

Eugene A. Feinberg () and Michael T. Curry ()

Mathematical Methods of Operations Research, 2005, vol. 62, issue 1, 99-122

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. Copyright Springer-Verlag Berlin Heidelberg 2005

Date: 2005
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-005-0443-4 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:62:y:2005:i:1:p:99-122

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-005-0443-4

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().