An Approximate Dynamic Programming Approach to the Scheduling of Impatient Jobs in a Clearing System.

A single server is faced with a collection of jobs of varying duration and urgency. Before service starts, all jobs are subject to an initial triage, i.e., an assessment of both their urgency and of their service requirement, and are allocated to distinct classes. Jobs in one class have independent and identically distributed lifetimes during which they are available for service. Should a job's lifetime example before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximise the expected number served to completion. Two heuristic policies have been proposed in the literature. One works well in a "no loss" limit while the other does so when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a single policy improvement step to the first policy above, in which we use a fluid model to obtain an approximation for its value function. The performance of the proposed heuristic is investigated in an extensive numerical study. This problem is substantially complicated if the initial triage is subject to error. We take a Bayesian approach to this additional uncertainty and discuss the design of heuristic policies to maximise the Bayes' return. We identify problem features for which a high price is paid for poor initial triage and for which improvements in initial job assessment yield significant improvements in service outcomes. An analytical upperbound for the cost of imperfect classification is developed for exponentially distributed lifetime cases. An extensive numerical study is conducted to explore the behaviour of the cost in more general situations