Optimal Routing of Fixed Size Jobs to Two Parallel Servers

Abstract

We consider a heterogeneous two-server system processing fixed size jobs. This includes the scheduling system, where jobs wait in a common queue, and the dispatching system, where jobs are assigned to server-specific queues upon arrival. The optimal policy with respect to the delay in both systems is a threshold policy characterized by a single parameter. In this special case, the scheduling and dispatching systems achieve the same performance with the optimal threshold. The optimal threshold depends on the arrival rate and the service rates. It can be determined by means of dynamic programming, where the required value functions can be evaluated only at the necessary points by means of efficient Monte Carlo simulations. We also give the optimal threshold at three different limits, which yield a simple closed-form expression for a near-optimal threshold. The optimal policy is illustrated and compared with several heuristic dispatching policies.

Keywords:

• parallel servers
• slow server problem
• task assignment
• latency
• MDP
• LWL
• FPI
• Lookahead

Acknowledgments

This work was supported by the Academy of Finland in the Top-Energy project (grant no. 268992). The author would like to thank Prof. R. Righter and the anonymous reviewers for their valuable comments that greatly improved the manuscript.

Notes

1 Strictly speaking, this is true for systems with a finite state-space, whereas in our case the state-space is continuous and infinite. Nonetheless, we apply the methodology and assume that the iteration converges to the globally optimal policy.

2 We note that this general technique to compare a stochastic system with two different initial states is known as the coupling method, and it was first proposed by Döblin already in 1938 (Lindvall, 1992).

3 The policy given by FPI depends on the basic policy, and some other choice, e.g., RND with optimal split, may yield better results. Here we have, however, chosen RND with load balancing for the sake of compact expressions.