A Simple Heuristic for Load Balancing in Parallel Processing
Networks with Highly Variable Service Time Distributions

Mark E. Lewis
Cornell University
School of Operations Research and Industrial Engineering
226 Rhodes Hall
Ithaca, New York 14853

Luz A. Caudillo-Fuentes
Department of Industrial and Operations Engineering
University of Michigan
1205 Beal Avenue, Ann Arbor, MI 48109-2117

David L. Kaufman
RiskMetrics Group
117 North First, Suite 90, Ann Arbor, MI 48104

Suppose that customers arrive to a service center (call center, web server, etc.) with two stations in accordance

with independent Poisson processes. Service times at either station follow the same general distribution,

are independent of each other and are independent of the arrival process. The system is charged station

dependent holding costs at each station per customer per unit time. At any point in time, a decision-maker

may decide to move, at a cost, some number of jobs in one queue to the other. The goals of this paper are

twofold. First, we are interested in providing insights into this decision-making scenario. We do so, in the

important case that the service time distribution is highly variable or simply has a heavy tail. Second, we

propose that the savvy use of Markov decision processes can lead to easily implementable heuristics when

features of the service time distribution can be captured by introducing multiple customer classes. To this

end, we consider a two-station proxy for the original system, where the service times are assumed to be

exponential, but of one of two classes with different rates. We prove structural results for this proxy and

show that these results lead to heuristics that perform well.