Online Scheduling: Generalized Pinwheel Problem

Eugene A. Feinberg; Michael T. Curry

Online Scheduling: Generalized Pinwheel Problem

Eugene A. Feinberg
, Michael T. Curry

Applied Mathematics and Statistics

Stony Brook University

Stony Brook University

Research output: Contribution to journal › Conference article › peer-review

1 Scopus citations

Abstract

Consider a non-preemptive infinite horizon service system with a single server characterized by a service time and a maximum allowable time between consecutive services. A rigorous Markov Decision Process formulation is provided in order to develop a dynamic programming algorithm for determining a feasible schedule. The constraints are then relaxed in order to invoke a semi-MDP. This semi-MDP is used to generate a non-randomized policy which generates a schedule of jobs. An algorithm that searches this schedule for a sub-sequence which is feasible and can be implemented periodically is presented.

Original language	English
Pages (from-to)	4333-4338
Number of pages	6
Journal	Proceedings of the IEEE Conference on Decision and Control
Volume	4
State	Published - 2003
Event	42nd IEEE Conference on Decision and Control - Maui, HI, United States Duration: Dec 9 2003 → Dec 12 2003

Keywords

Dynamic Programming
Markov
Pinwheel
Semi-Markov

Cite this

@article{887105921f2a44d882dfd0970d254e75,

title = "Online Scheduling: Generalized Pinwheel Problem",

abstract = "Consider a non-preemptive infinite horizon service system with a single server characterized by a service time and a maximum allowable time between consecutive services. A rigorous Markov Decision Process formulation is provided in order to develop a dynamic programming algorithm for determining a feasible schedule. The constraints are then relaxed in order to invoke a semi-MDP. This semi-MDP is used to generate a non-randomized policy which generates a schedule of jobs. An algorithm that searches this schedule for a sub-sequence which is feasible and can be implemented periodically is presented.",

keywords = "Dynamic Programming, Markov, Pinwheel, Semi-Markov",

author = "Feinberg, \{Eugene A.\} and Curry, \{Michael T.\}",

year = "2003",

language = "English",

volume = "4",

pages = "4333--4338",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0191-2216",

note = "42nd IEEE Conference on Decision and Control ; Conference date: 09-12-2003 Through 12-12-2003",

}

TY - JOUR

T1 - Online Scheduling

T2 - 42nd IEEE Conference on Decision and Control

AU - Feinberg, Eugene A.

AU - Curry, Michael T.

PY - 2003

Y1 - 2003

N2 - Consider a non-preemptive infinite horizon service system with a single server characterized by a service time and a maximum allowable time between consecutive services. A rigorous Markov Decision Process formulation is provided in order to develop a dynamic programming algorithm for determining a feasible schedule. The constraints are then relaxed in order to invoke a semi-MDP. This semi-MDP is used to generate a non-randomized policy which generates a schedule of jobs. An algorithm that searches this schedule for a sub-sequence which is feasible and can be implemented periodically is presented.

AB - Consider a non-preemptive infinite horizon service system with a single server characterized by a service time and a maximum allowable time between consecutive services. A rigorous Markov Decision Process formulation is provided in order to develop a dynamic programming algorithm for determining a feasible schedule. The constraints are then relaxed in order to invoke a semi-MDP. This semi-MDP is used to generate a non-randomized policy which generates a schedule of jobs. An algorithm that searches this schedule for a sub-sequence which is feasible and can be implemented periodically is presented.

KW - Dynamic Programming

KW - Markov

KW - Pinwheel

KW - Semi-Markov

UR - https://www.scopus.com/pages/publications/1542288953

M3 - Conference article

SN - 0191-2216

VL - 4

SP - 4333

EP - 4338

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

Y2 - 9 December 2003 through 12 December 2003

ER -

Online Scheduling: Generalized Pinwheel Problem

Abstract

Keywords

Other files and links

Fingerprint

Cite this