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.