Dynamic Control of a Single Server System with
Abandonments

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


Douglas G. Down
Department of Computing and Software
McMaster University
1280 Main Street West
Hamilton, ON L8S 4L7, Canada


Ger Koole
Faculty of Sciences, Department of Mathematics
VU University
Amsterdam, The Netherlands

In this paper we discuss the dynamic control of a two-class service system with abandonments.
Two models are considered. In the first case, rewards are received upon service completion
and there are no abandonment costs (other than the lost opportunity to gain rewards). In the
second, holding costs per customer per unit time are accrued and each abandonment involves
a fixed cost. Both cases are considered under the discounted or average reward/cost criterion.
These are extensions of the classic scheduling question (without abandonments) where it is
well-known that simple priority rules hold.

The contributions in this paper are twofold. First, we show that the classic results do not
hold in general. An added condition on the ordering of the abandonment rates is sufficient
to recover the priority rule. Counter-examples show that this condition is not necessary, but
when it is violated significant loss can occur. In the reward case, we show that the decision
involves an intuitive tradeoff between getting more rewards and avoiding idling. Second,
we note that traditional solution techniques are not directly applicable. Since customers may
leave in between services an interchange argument cannot be applied. Since the abandonment
rates are unbounded we cannot apply uniformization – and thus cannot use the usual discretetime
Markov decision process techniques. After formulating the problem as a continuous-time
Markov decision process (CTMDP), we use sample path arguments in the reward case and a
savvy use of truncation in the holding cost case to yield the results. As far as we know, this
is the first time that either have been used in conjunction with the CTMDP to show structure
in a queueing control problem. The insights made in each model are supported by a detailed
numerical study.