Submitted manuscript, 304 KB, PDF document
Research output: Contribution to Journal/Magazine › Journal article
Research output: Contribution to Journal/Magazine › Journal article
}
TY - JOUR
T1 - An approximate dynamic programming approach to the development of heuristics for the scheduling of impatient jobs in a clearing system
AU - Li, D
AU - Glazebrook, K D
PY - 2010
Y1 - 2010
N2 - A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled πS) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (πM) is a myopic heuristic which works well 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 policy improvement step to the asymptotically optimal heuristic πS, in which we use a fluid model to obtain an approximation for the value function of πS. The performance of the proposed heuristic is investigated in an extensive numerical study.
AB - A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled πS) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (πM) is a myopic heuristic which works well 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 policy improvement step to the asymptotically optimal heuristic πS, in which we use a fluid model to obtain an approximation for the value function of πS. The performance of the proposed heuristic is investigated in an extensive numerical study.
U2 - 10.1002/nav.20395
DO - 10.1002/nav.20395
M3 - Journal article
VL - 57
SP - 225
EP - 236
JO - Naval Research Logistics
JF - Naval Research Logistics
SN - 0894-069X
ER -