Hyeong Soo Chang, Robert Givan, and Edwin K. P. Chong
We consider the problem of scheduling an unknown sequence of tasks for a single server as the tasks arrive with the goal off maximizing the total weighted value of the tasks served before their deadline is reached. This problem is faced for example by schedulers in packet communication networks when packets have deadlines and rewards associated with them. We make the simplifying assumptions that every task takes the same fixed amount of time to serve, that every task arrives with the same initial latency to its deadline. We also assume that future task arrivals are stochastically described by a Hidden Markov Model (HMM). The resulting decision problem can be formally modelled as a Partially Observable Markov Decision Process (POMDP). We first present and analyze a new optimal off-line scheduling algorithm called Prescient Minloss scheduling for the problem just described, but with "prescient" foreknowledge of the future task arrivals. We then discuss heuristically adapting this off-line algorithm into an on-line algorithm by sampling possible future task sequences from the HMM. We discuss and empirically compare scheduling methods for this on-line problem, including previously proposed sampling-based POMDP solution methods. Our heuristic approach can be used to adapt any off-line scheduler into an on-line scheduler.