Online Scheduling with Hard Constraints: A Semi-Markov Decision Process Approach

E.A. Feinberg and M.T. Curry (USA)


Pinwheel, Dynamic Programming, Markov, semi-Markov


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. We provide a rigorous Markov Decision Process formu lation and develop a dynamic programming algorithm for determining a feasible schedule. We then relax the con straints in order to invoke a semi-MDP. This semi-MDP is used to generate a non-randomized policy which generates a schedule of jobs. We have developed an algorithm which searches this schedule for a feasible sub-sequence which is feasible and can be implemented periodically.

Important Links:

Go Back