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
**

Hamilton, ON L8S 4L7, Canada

Ger Koole

Faculty of Sciences, Department of
Mathematics

VU University

Amsterdam, The Netherlands

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.