Routing jobs with deadlines to heterogeneous parallel servers

We consider a dispatching system, where jobs with deadlines for their waiting times are assigned to FCFS servers immediately upon arrival. The dispatching problem is to choose a server for each job so as to minimize the probability of deadline violation. We derive an efficient deadline-aware policy in the MDP framework by means of policy improvement, analyze it, and evaluate its performance with simulations. We find that the new policy offers significant improvements over traditional heuristic policies.