Convexity Properties and Comparative Statics for
M/M/S Queues with Balking and Reneging
Mor Armony1 Erica Plambeck2 Sridhar Seshadri3
We use sample path arguments to derive convexity properties of an M/M/S queue with
impatient customers that balk and renege. First, assuming that the balking probability and
reneging rate are increasing and concave in the total number of customers in the system
(head-count), we prove that the expected head-count is convex decreasing in the capacity
(service rate). Second, with linear reneging and balking, we show that the expected lost sales
rate is convex decreasing in the capacity. Finally, we employ a sample-path sub-modularity
approach to comparative statics. That is, we employ sample path arguments to show how the
optimal capacity changes as we vary the parameters of customer demand and impatience.
We find that the optimal capacity increases in the demand rate and decreases with the
balking probability, but is not monotone in the reneging rate. This means, surprisingly, that
failure to account for customers’ reneging may result in over-investment in capacity. Finally,
we show that a seemingly minor change in system structure, customer commitment during
service, produces qualitatively different convexity properties and comparative statics.
1. Introduction and Overview of Results
This paper develops qualitative insights about how the optimal capacity investment for a
make-to-order system is influenced by customers’ impatience, which may lead them to cancel
an order (renege) or not to order at all (balk) when waiting is required. Technically, we prove
convexity and comparative statics properties for a M/M/S queue with quite general reneging
and balking behavior.
A dominant assumption in the manufacturing operations management literature is that
customers will wait for as long as necessary to obtain a product (infinite backordering). In
1Stern School of Business, New York University, marmony@stern.nyu.edu
2Graduate School of Business, Stanford University, elp@stanford.edu
3Stern School of Business, New York University, sseshadr@stern.nyu.edu
1
reality, only a subset of customers will wait, and only for a limited time. Unfortunately,
models that incorporate dynamic balking and reneging are notoriously intractable. There
exist many structural results and simple optimal policies for inventory management with
infinite backordering, but relatively few for systems with lost sales, and these few require
strong assumptions (e.g. at most one order may be outstanding (Johansen and Thorstenson,
1993; 1996; Moinzadeh and Nahmias, 1988)) or approximations (Nahmias, 1979; Cohen,
Kleindorfer and Lee, 1988; Johansen and Hill, 2000). The following papers provide analytic
results for make-to-order manufacturing systems in which the customer arrival process de-
pends on the static expected waiting cost, but not dynamic state information (Mendelson
and Whang, 1990; Van Mieghem 1995, 2000; Armony and Haviv 2000; Lederer and Li, 1997;
and Afeche 2004). Duenyas and Hopp (1995) were the first to study a make-to-order system
in which the customer arrival process is shaped by dynamically quoting delivery leadtimes.
Because dynamic leadtime quotation and scheduling in make-to-order systems is so complex,
researchers employ heuristic algorithms, simulation and approximations (Duenyas and Hopp,
1995; Hopp and Sturgis, 2001; Keskinocak, Ravi and Tayur, 2001; Kapusckinski and Tayur,
2002; Plambeck, 2003). All the aforementioned papers model the make-to-order system with
a single server queue. In contrast, we provide analytic results for multi-server systems.
Modeling dynamic balking and reneging is difficult but worthwhile, because one obtains
qualitatively different managerial insights, and structurally different control policies. For
example, Armony and Plambeck (2002) show that failure to account for duplicate ordering
and reneging can cause either over- or under-investment in capacity. By incorporating
capacity constraints and customer reneging into the well known Bass model, Ho, Savin, and
Terwiesch (2002) obtain qualitatively different insights. Kumar and Swaminathan (2003)
analyze a related model of new product introduction with balking rather than reneging and
find optimal control policies that are structurally different. Plambeck (2004) analyzes an
assemble-to-order system in which orders must be filled within a product-specific target
leadtime, or they are lost. A simple policy with independent control of each component is
near optimal. In contrast, when customers wait for as long as necessary to obtain the product,
optimal control becomes more complex: component production and assembly sequencing
depend upon the inventory positions for all components (Plambeck and Ward, 2003). In
(Li and Lee, 1994) two firms compete by setting prices; customers observe queue lengths
and jockey between the firms to minimize delivery-time. In contrast to traditional Bertrand
equilibrium with zero prices and profits, because customer orders depend dynamically on
2
the leadtime, the firms sustain strictly positive profits. In a dynamic Bayesian formulation,
Chen and Plambeck (2004) show the value of reducing inventory levels to learn about about
customer’s willingness to wait.
Most of the existing research assumes the simplest structure for reneging (customers
renege after an exponentially distributed amount of time) or balking (balk with probability
p if there is any wait, and with probability (1-p) wait until the product is delivered). Two
notable exceptions are Ward and Glynn (2004) and Zeltyn and Mandelbaum (2004). Both
papers allow general distributions for reneging and balking, and perform asymptotic analysis
of these systems under conventional heavy traffic and the many-servers heavy traffic regimes,
respectively. Mandelbaum and Shimkin (2000) derive complex dynamic customer behavior
from primitives on valuation and waiting costs, for an M/M/S queue with congestion/failure
shocks, assuming customers cannot observe the queue length.
Most of the literature on balking and reneging in queues focuses on performance evalua-
tion and estimation (see, for example, Baccelli and Hebuterne (1981), Garnett, Mandelbaum
and Reiman (2002), Mandelbaum and Zeltyn (1998) and Mandelbaum, Sakov and Zeltyn
(2000) and references therein). One exception, (Kumar and Ward, 2005) proposes an admis-
sion control policy for a system with reneging in which revenue from admitting a customer
is less than the penalty incurred if that customer later reneges. Recently, researchers have
made rapid progress in staffing for call centers (Harrison and Zeevi (2005); Mandelbaum and
Zeltyn (2005) and Borst, Mandelbaum, Reiman and Zeltyn (2005)), which involves determin-
ing the number of servers of possibly several pools and thus differs from our 1-dimensional
model of capacity planning for a make-to-order system.
We derive fundamental properties of an M/M/S queue with state-dependent balking and
reneging rates. We adopt the sample path approach of Shaked and Shanthikumar (1988)
to verify convexity of stochastic processes and related cost functions. First, in Section 3,
assuming that the balking probability and reneging rate are increasing and concave in the
head-count, we prove that the expected head-count is convex decreasing in the capacity
(service rate). This is complementary to the famous result that in a G/G/1 queue with a
convex increasing delay cost and without balking/reneging, a customers’ expected cost of
delay is a convex decreasing function of capacity (Weber, 1983). Second, in Section 4, we
assume linear reneging and constant balking probability, and show that the expected lost
sales rate is convex decreasing in the capacity. This is similar to the result by Fridgeirsdottir
and Chu (2005) that in a G/G/1 queue with convex nondecreasing delay cost and without
3
balking/reneging, the expected delay cost rate is convex increasing in the arrival rate, and
to the result by Janakiraman and Roundy (2004) that for an inventory system with lost
sales and stochastic sequential leadtimes, expected discounted cost is convex in the base
stock level. Establishing that the expected cost function is convex in the control parameter
(capacity, arrival rate and base stock level in the preceding examples) justifies using a simple
search procedure to compute the optimal parameter level and sets the stage for deriving
qualitative insights from comparative statics.
Inspired by Shaked and Shantikumar’s (1988) concept of sample-path convexity, in Sec-
tion 4 we employ a sample-path sub-modularity approach to comparative statics. That is,
we employ sample path arguments to show how the optimal capacity changes as we vary the
parameters of customer demand and impatience. We find that the optimal capacity increases
in the demand rate and decreases with the balking probability, but is not monotone in the
reneging rate. This means, surprisingly, that failure to account for customers’ impatience
and reneging may result in over-investment in capacity.
Finally, in Section 5, we assume commitment during service, i.e., customers cannot balk
or renege during service. This seemingly minor change in system structure produces qual-
itatively different results. The expected rate of reneging from the system in steady-state
is convex, but the expected rate of balking and hence expected cost is non-convex in some
parameter regions. Furthermore, the optimal capacity is no longer monotone in the balking
probability. We conclude that commitment during service strongly impacts the convexity
properties and comparative statics of make-to-order systems with impatient customers.
2. Notation and Model Formulation
Consider a make-to-order system modelled by a multi-server, infinite-buffer queue. Cus-
tomers arrive at the system according to a Poisson process with rate ¸. The service time has
an exponential distribution with rate ¹. We denote the number of customers in the system
(head-count) by Y . An arriving customer may decide to balk, namely, to leave upon arrival.
The balking probability is a function of the head-count, and is denoted by ¯(¢): Finally,
customers may decide to cancel their order (renege) at any point during their wait or while
being served. The reneging rate is a function of the head-count, and is denoted by ´(¢): All
arrivals, service times, balking and reneging are assumed to be independent. Therefore, the
head-count process is a continuous time Markov chain (CTMC).
4
The system manager knows the customers characteristics modelled here by ¸;¯; and ´;
wishes to choose the service capacity ¹ to minimize the cost associated with lost sales and
capacity investment:
C(¹) = C(¹; ¸;´;¯) = c[¸E¯(Y (1)) + E´(Y (1))] + k¹;
where Y (1) is the head-count in steady-state, and, without loss of generality, it is assumed
that c = 1.
Let µ be an arbitrary parameter, and let ¹currency1(µ) be a value of ¹ that minimizes a certain
function g(¹; µ): The meaning of the saying ‘¹currency1(µ) is increasing in µ’ when ¹currency1(µ) is not
necessarily unique, is that if µL < µH; and ¹H minimizes g(¹; µH) then there exists ¹L · ¹H,
such that ¹L minimizes g(¹; µL): Similarly, if ¹L minimizes g(¹; µL), then there exists ¹H ¸
¹L, such that ¹H minimizes g(¹; µH): Throughout the paper we use the term increasing to
mean non-decreasing, and the term decreasing to mean non-increasing.
3. Convexity of Cost in Capacity
In this section we address the issue of convexity of the cost function in the capacity variable
¹. We start by establishing the convexity of the expected head-count as a function of the
capacity. This convexity property is true for very general balking and reneging functions.
The only requirements is that both functions are non-decreasing and concave in the head-
count.
Proposition 1 Let Y (t) denote the head-count process for an M=M=S system with reneging
and balking. Suppose that the reneging rate ´(¢) and the balking probability ¯(¢) are both non-
decreasing and concave functions of Y , then the expected head-count in steady state, EY (1);
is convex in the service rate, ¹:
The proof of Proposition 1 is based on the sample path approach. In particular, we
prove that Y satisfies sample path convexity (a term that has been introduced by Shaked
and Shanthikumar (1988)). More specifically, for any service rates 0 · ¹1 · ¹2 · ¹3 · ¹4
such that ¹1 + ¹4 = ¹2 + ¹3, we show that there exist Y1;:::;Y4, which are versions of the
original head-count processes (Yi has service rate of ¹i), and which satisfy the following two
properties for all t ¸ 0:
1. Y1(t) + Y4(t) ¸ Y2(t) + Y3(t), a.s, and
5
2. Y1(t) ¸ maxfY2(t);Y3(t);Y4(t)g, a.s.
Then, according to Shaked and Shanthikumar (1988), Y is said to be stochastically
decreasing and convex in the sample path sense (SDCX(sp)). From Theorem 3.6, Proposition
2.11 and Remark 2.8 of Shaked and Shanthikumar (1988) it follows that EY (1) is decreasing
and convex in ¹. To prove that 1. and 2. hold, we discretize time, uniformize the transition
rates, and finally prove 1. and 2. using path-wise coupling and induction on time. Details
are given in the Appendix.
This convexity result is particularly interesting in the case that customers cannot observe
the head-count. Note that (with a slight abuse of notation) both simple functions ´(y) = ´y
for some constant ´ ¸ 0; and ¯(y) = ¯ for some constant 1 ¸ ¯ ¸ 0 satisfy the assumptions of
Proposition 1. Both these functions are likely scenarios when the head-count is unobservable.
The reneging function corresponds to the case where every order is cancelled if is not fulfilled
by an exponential amount of time with mean 1=´. Similarly, the balking probability function
corresponds to the case where the customer is not aware of the head-count and makes her
balking decision at random. The cost function that goes along with these reneging and
balking functions is C(¹; ¸;´;¯) = ¸¯ + ´EY (1) + k¹: It is easily verified (see Proposition
2) that Proposition 1 implies the convexity of this cost function in ¹:
A similar result to proposition 1 appears in Shaked and Shanthikumar (1988) (Theorem
5.5). The similarity is that both our result and theirs assume that the departure rate is
increasing and concave in the head-count. The difference is in the conclusions. They show
that for a single server queue the head-count is increasing and convex in the arrival rate,
while we show that for a multi-server queue the head-count is decreasing and convex in the
service rate.
Convexity of the cost as a function of capacity implies that efficient optimization algo-
rithms can be applied to find the capacity level which minimizes cost. In addition, this
convexity allows for comparative statics that evaluate the effect of changes in the model
parameters on the optimal capacity level. The latter is pursued in the next section.
4. Optimal Capacity Investment
In this section we investigate the effect of varying fundamental system parameters on the
optimal capacity investment. We assume that each customer balks with probability ¯ > 0
(regardless of the head-count upon arrival) and reneges after an exponential time with rate
6
´ > 0 (This is the case when the head-count is unobservable). As one would expect, we find
that the optimal capacity is increasing in ¸ and decreasing in ¯. Surprisingly, we find that
the optimal capacity may either increase or decrease in ´:
Theorem 1 Suppose that the balking probability function is constant at ¯(y) = ¯; for some
0 · ¯ < 1; and that the reneging rate function is ´(y) = ´y; for some ´ ¸ 0: Let
C(¹; ¸;´;¯) = ¸¯ + ´EY (1) + k¹; (1)
be the cost function associated with lost sales and capacity investment. Let ¹currency1(¸;´;¯) be
the optimal capacity that minimizes C(¹; ¸;´;¯). Then, ¹currency1(¸;´;¯) is non-decreasing in ¸;
non-increasing in ¯, but is not necessarily monotone in ´:
The proof of Theorem 1 is based on four propositions. The first shows that C(¹; ¸;´;¯)
is convex in ¹; therefore, for all given values of ¸, ´; and ¯; ¹currency1(¸;´;¯) is well defined
(although it may be non-unique), and any local minimum of C(¹; ¸;´;¯) is also a global
minimum. The second proposition shows that ¹currency1(¸;´;¯) is increasing in ¸. Similarly, the
third proposition shows that ¹currency1(¸;´;¯) is decreasing in the balking probability ¯: Finally,
in the fourth proposition we show that ¹currency1(¸;´;¯) may either increase or decrease in ´: Most
arguments are based on the sample path approach. Building on the concept of sample path
convexity, we define the sample-path sub-modularity property the implies monotonicity of
the expected-cost-minimizing value of one parameter in a second parameter (Theorem 2).
Proposition 2 Under the assumptions of Theorem 1, the cost function C(¹; ¸;´;¯) is con-
vex in ¹ for all values of ¸;´ and ¯:
Proof: Fix ¸;´ and ¯ and let f(¹) = ´EY (1): Clearly, the convexity of f in ¹ implies
that C is also convex in ¹. To establish the convexity of f, note that the reneging rate and
the balking probability functions are both non-decreasing and concave, and therefore, by
Proposition 1 it follows that f(¹) is convex in ¹: currency1
In order to show that the optimal capacity is increasing in ¸ and decreasing in ¯ we
introduce and utilize the following concept of sample-path sub-modularity.
Definition: Let X = X°;± be a stochastic process which depends on the two parameters °
and ±. We say that X is “path-wise sub-modular” with respect to ° and ± if for all °L < °H
and ±L < ±H we have four processes ˆ°;±; ° = °L;°H; ± = ±L;±H which are defined on the
same probability space, such that
7
1. ˆ°;± is a version of X°;± for every fixed pair (°;±) (that is, ˆ°;± st X°;±), and
2. ˆ°H;±H ¡ ˆ°H;±L · ˆ°L;±H ¡ ˆ°L;±L; a.s.
The next theorem establishes the connection between the sample-path sub-modularity
property and monotonicity.
Theorem 2 Let X = X°;± be a stochastic process, and let g(°;±) = EX°;± be its expected
value in steady-state. Suppose that g(¢) is convex in ° for every fixed ± and that it is path-wise
sub-modular with respect to these two variables. Let °currency1(±) be the (possibly non-unique) value
of ° that minimizes g(°;±) for every fixed value of ±, then °currency1(±) is increasing in ±.
Proof: Let ±L;±H be two values of ± such that ±L < ±H. Let °currency1(±L) be a value of °
that minimizes g(°;±L). We need to show that there is ˆ ¸ °currency1(±L) such that ˆ minimizes
g(°;±H). By contradiction, assume that for all optimal solutions °currency1(±H) of g(°;±H), we have
°currency1(±H) < °currency1(±L). In particular,
0 · g (°currency1(±H);±L) ¡ g (°currency1(±L);±L) · g (°currency1(±H);±H) ¡ g (°currency1(±L);±H) · 0; (2)
where the first inequality follows from the optimality of °currency1(±L), the second on follows from
the sample-path sub-modularity and the assumption that °currency1(±H) < °currency1(±L), and the third
one follows from the optimality of °currency1(±H). In particular, (2) implies that g (°currency1(±H);±H) =
g (°currency1(±L);±H), which in turn implies that °currency1(±L) is minimizes g(°;±H). This leads to a
contradiction. currency1
The next proposition establishes that the head-count process is path-wise sub-modular
in ¹ and ¸ (¯ and ´ will be omitted from the current expressions for expository purposes).
From Theorem 2 it then follows that ¹currency1(¸) is non-decreasing in ¸.
Proposition 3 For any values of ¸ and ¹, let Y¸;¹ represent the head-count process when
the arrival rate is ¸ and the service capacity is ¹. Then Y¸;¹ is path-wise sub-modular in ¸
and ¹.
Note that the proposition only establishes the path-wise sub-modularity of Y¸;¹: However,
it is straightforward to verify that this implies the sample-path sub-modularity of the entire
cost function in these two parameters. The proof of Proposition 3 follows the sample path
8
approach. More specifically, we show that for all ¸L < ¸H and ¹L < ¹H there exist versions
of Y¸;¹, for ¸ 2 f¸L;¸Hg and ¹ 2 f¹L;¹Hg; such that the following three properties hold at
all times t ¸ 0:
I. Y¸H;¹L(t) = max[Y¸;¹(t) : ¸ 2 f¸L;¸Hg; ¹ 2 f¹L;¹Hg]; a.s.,
II. Y¸L;¹H (t) = min[Y¸;¹(t) : ¸ 2 f¸L;¸Hg; ¹ 2 f¹L;¹Hg]; a.s., and
III. Y¸H;¹H (t)¡ Y¸H;¹L(t) · Y¸L;¹H (t)¡ Y¸L;¹L(t); a.s.
Similarly to the proof of Proposition 1, we show I. II. and III. using time discretization
and uniformization, and then establishing these properties using sample-path coupling and
induction on time. Details are given in the appendix.
The next proposition establishes the monotonicity of the optimal capacity in the balking
probability. Specifically, we show that if the balking probability function is constant then the
optimal capacity is decreasing (in fact, non-increasing) in this constant balking probability.
Proposition 4 Let ¸ and ´ be fixed. Then the optimal capacity ¹currency1(¯) which minimizes the
cost C(¹; ¸;´;¯) is non-increasing in ¯:
Proof: Consider another system with arrival rate equal to ¸(1 ¡ ¯); no balking (balking
probability = 0), and reneging rate ´: It is easy to see that the head-count process for the
new system evolves the same as the head-count process for the original system. According
to Proposition 3 the optimal capacity that minimizes C(¹; ¸(1 ¡ ¯);´;0) is non-decreasing
in ¸(1 ¡ ¯) and is, therefore, non-increasing in ¯: But the actual cost we seek to minimize
is C(¹; ¸;´;¯) = C(¹; ¸(1 ¡ ¯);´;0) + ¸¯: Since this additional term is not a function of ¹;
it follows that ¹currency1(¸;´;¯) = ¹currency1(¸(1 ¡ ¯);´;0); and hence is also non-increasing in ¯: currency1
Corollary 1 Let ´ be fixed. Then the optimal capacity ¹currency1(¸;¯) which minimizes the cost
C(¹; ¸;´;¯) is non-increasing in the balking rate (¸¯).
Proof: The proof follows immediately from the proof of Proposition 4. currency1
The final proposition establishes that ¹currency1(¸;´;¯) may be either increasing or decreasing
in ´: This counterintuitive result will be contrasted in the discussion with the traditional
model of infinite backordering, in which such phenomenon does not occur. This underlines
the importance of modelling order cancellation explicitly.
9
Proposition 5 Fix the values of ¸ and ¯; and let ¹currency1(´) be the optimal capacity which min-
imizes the cost function C(¹; ¸;´;¯), then ¹currency1(´) can either increase or decrease in ´:
Proof: Recall the cost function C(¹; ´) := C(¹; ¸;´;¯) = ¯¸+´EY (1)+k¹: Suppose that
S = 1 and ¯ = 0. In order to prove the proposition we first show that for arbitrary values of
¸ and k with 0 < k < 1, ¹currency1(´) may decrease in ´: To show that, we note that the definitions
C(¹; ´ = 0) = (¸ ¡ ¹)1f¹·¸g + k¹; and C(¹; ´ = 1) = ¸ + k¹ are continuous extensions
of the cost function C(¢) for all values ´ in the closed interval [0;1]: However, notice that
¹currency1(´ = 0) = ¸, whereas, ¹currency1(´ = 1) = 0, that is, ¹currency1(´) may decrease with ´:4
To show that ¹currency1(´) may also increase in ´; all we have to show is that there exist
0 < k < 1 and ´k > 0 such that ¹currency1k(´k) > ¸ (recall that ¹currency1(´ = 0) = ¸). We show that,
in fact, a stronger result applies; namely, that for every fixed value of ´ > 0; there exists
a value k = k(´), 0 < k < 1, such that ¹currency1k(´) > ¸, where ¹currency1k(´) stands for the optimal
capacity that minimizes the cost function C(¹; ¸;´;¯) = ´EY (1) + k¹: To show that, fix
the value of ´ > 0, and note that the function f(¹) = ´EY (1) is decreasing and convex in
¹ (Proposition 1). We claim that it is sufficient to show that:
There exists ¹0 such that: ¹0 > ¸; f(¹0) < f(¸) and f0(¹¡0 ) > ¡1; (3)
where f0(¹¡0 ) is the directional derivative of f at ¹ = ¹0 from below (exists due to Lemma
3.1.5 of Bazaraa, Sherali and Shetty (1993)). If (3) is true then the convexity of f(¹) implies
that f0(¹¡0 ) · f0(¹+0 ) (here, f0(¹+0 ) is the directional derivative of f at ¹ = ¹0 from above).
Let k be such that f0(¹¡0 ) · ¡k · f0(¹+0 ); then C0(¹¡0 ) = f0(¹¡0 ) + k · 0; and C0(¹+0 ) =
f0(¹+0 ) + k ¸ 0: In particular, ¹currency1k(´) = ¹0 is a local minimum for C(¢); and from convexity,
it is also a global minimum.
To establish (3), note that from flow conservation f(¹) = ´EY (1) = ¸¡¹P(Y (1) > 0):
In particular, f(¹ = ¸) > 0; and lim¹!1 f(¹) = 0: Since f(¹) is a non-increasing function of
¹, this implies that there exists ¹1 > ¸ such that f(¹) < f(¸), for all ¹ ¸ ¹1. Now note that
if f0(¹¡) · ¡1 for all ¹ ¸ ¹1; then f(¹) < 0 for ¹ large enough, which is a contradiction.
This shows that ¹0 is well defined. currency1
4The continuity of ¹currency1(´) (which follows from Theorem 3.1.3 of Bazaraa, Sherali and Shetty (1993) and
the implicit functions theorem) may be used to show that ¹currency1(´) indeed decreases for some points on the
interval (0;1):
10
5. Customer Commitment During Service
For many service systems and some make-to-order manufacturing systems, it is reasonable
to assume that customers will not balk or renege during service. According to Farlie (2004),
small manufacturers of customized computers charge a customer’s credit card before ini-
tiating assembly, to prevent cancellations during the assembly process. The assumption
that customers cannot balk or renege during service (which we call ‘customer commitment’)
makes derivation of convexity and comparative statics results much more difficult. In fact,
some of our previous results are no longer true under this assumption.
To illustrate the effect of customer commitment during service on convexity we use
the simplest form of balking and reneging that falls within this framework. Specifically,
throughout this section, we assume that the balking probability function is of the form
¯(Y ) = ¯1fY ¸Sg and the reneging rate function is of the form ´(Y ) = ´(Y ¡ S)+, for some
positive constants ¯ · 1 and ´. These balking and reneging functions are likely scenarios
when customers cannot observe the head-count but are aware of whether their service is
in progress, is about to begin, or is going to be delayed. Consequently, each customer will
balk with probability ¯ if and only if no server is available when she arrives. Similarly,
she will renege after an exponential time with rate ´ as long as she is waiting in line. The
expected balking rate and reneging rate in steady-state associated with the above functions
are b(¹; ¸;´;¯) = ¸¯P(Y (1) ¸ S) and r(¹; ¸;´;¯) = ´E[Y (1) ¡ S]+, respectively.
In this section we also allow for the cost associated with a customer balking (cb) to differ
from the cost associated with a customer reneging (cr). Let
C(¹; ¸;´;¯) = cb¸¯P(Y (1) ¸ S) + cr´E[Y (1) ¡ S]+ + k¹; (4)
denote the cost function associated with lost sales and capacity investment. It is straightfor-
ward to see that all our results in the previous sections hold when the cost of balking differs
from the cost of reneging. Surprisingly, with customer commitment during service, impor-
tant system properties (convexity of the cost (4) as a function capacity ¹ and monotonicity
of the optimal capacity ¹currency1 in the balking probability ¯) depend upon the relative costs of
balking and reneging.
We start by establishing that the expected reneging rate from the system in steady-state
is a convex function of ¹ for ¹ ¸ ´.
11
Proposition 6 Suppose that ´ > 0 and let
r(¹; ¸;´;¯) = ´E[Y (1) ¡ S]+; (5)
denote the expected reneging rate in steady-state. Then if either S = 1 or ¯ = 0 then r(¢) is
convex in ¹ for ¹ ¸ ´.
Before proving this proposition we introduce the following Lemma:
Lemma 1 Under the assumptions of Proposition 6, the head-count process Y is stochasti-
cally decreasing and convex in ¹ for ¹ ¸ ´.
The proof of Lemma 1 appears in the Appendix. It is similar to the proof of Proposition
1, but it does not follow for this proposition because the assumptions of the concavity of the
balking probability and reneging rate in the head-count do not hold.
Proof of Proposition 6: Suppose that ¹ ¸ ´. By Lemma 1 the head-count process Y
is stochastically decreasing and convex in ¹. Now, since the function ´(y) = ´(y ¡ S)+ is
increasing and convex in y, it follows that the process ´(Y ¡ S)+ is also stochastically de-
creasing and convex in ¹. Finally, it follows that r(¹; ¸;´;¯) = ´E[Y (1)¡S]+ is decreasing
and convex in ¹. currency1
In contrast, the expected balking rate from the system in steady-state is non-convex in
¹; when the reneging rate ´ is small. This result seems counter-intuitive, especially in light
of Lemma 1. However, note that in the customer commitment case, the balking probability
¯1fY ¸Sg is not convex in the head-count, and therefore the convexity of this rate in ¹ does
not follow from Lemma 1. The direct sample-path argument for convexity also fails. To see
this, note that the direct approach requires establishing sample path convexity for 1fY ¸Sg,
analogously to the proof of Proposition 1. However, the quantity 1fY ¸Sg does not carry
enough information for such arguments to work. For example, consider four systems with
service rates ¹1 ¸ ¹2 ¸ ¹3 ¸ ¹4, and ¹1 + ¹4 = ¹2 + ¹3. Pathwise convexity requires that
1fY1(t)¸Sg + 1fY4(t)¸Sg ¸ 1fY2¸Sg + 1fY3¸Sg; 8t ¸ 0: (6)
But (6) could work at time t0, with Y1(t0) = Y4(t0) = S and Y2(t0) = Y3(t0) = S + 1. In
this case, the next departure from all systems will result in Y1(t0) = Y4(t0) = S ¡ 1, and
Y2(t0) = Y3(t0) = S, which violates (6). The next proposition states the non-convexity of
the balking rate in ¹.
12
Proposition 7 Let
b(¹; ¸;´;¯) = ¸¯P(Y (1) ¸ S); (7)
denote the expected balking rate in steady-state. Then b(¢) is not necessarily convex in ¹. In
particular, if S = 1, then for sufficiently small values of ´, b(¢) is not convex in ¹.
Proof: Let S = 1, and fix ¸ and ¯. First we examine the limit of the balking rate function
as the reneging rate ´ approaches zero. Note that, from the monotone convergence theorem,
we have that
b(¹) := lim
´#0
b(¹; ¸;´;¯) =
(
¸¯; ¹ · ¸(1 ¡ ¯);
¸2¯
¹+¸¯ ; ¹ > ¸(1 ¡ ¯):
In particular, b(¹) is not convex at the point ¹0 = ¸(1 ¡ ¯). Moreover, if we let ¹1 =
¹0=2 and ¹2 = 3¹0=2, then ¹0 = (¹1 + ¹2)=2, but b(¹0) > (b(¹1) + b(¹2))=2. We next
show that for sufficiently small values of ´ > 0, b(¹; ´) := b(¹; ¸;´;¯) is not convex in ¹.
Let ² = b(¹0) ¡ (b(¹1) + b(¹2))=2. By the definition of b(¹), there exists ´(²) such that
j b(¹; ´) ¡ b(¹)j < ²=3, for all ´ · ´(²) and ¹ = ¹0;¹1;¹2. This implies, that for all ´ · ´(²)
b(¹0; ´) ¡ b(¹1; ´) + b(¹2; ´)2 ¸ b(¹0) ¡ ²3 ¡ b(¹1) +
²
3 + b(¹2) +
²
3
2 > 0:
currency1
Figure 1 illustrates the non-convexity of the balking rate as a function of ¹ for the special
case where S = 1, ¸ = 50, ´ = 0:5 and ¯ = 0:2.
In light of the proof of Proposition 7, one might think that the non-convexity in ¹ may
only occur if we allow for traffic intensity (½ := ¸(1 ¡ ¯)=¹) values which are greater than
or equal to 1. An exhaustive numerical search over the parameter values reveals that this
is not the case. Specifically, for high traffic intensity which is close to 1 (but still less than
1) and low reneging rate, the balking rate is not convex. This numerical result is illustrated
in Figure 2. The surface in the figure displays, for each pair of values of ¯ and (¸/¹); the
highest value of ´ for which the steady-state expected rate of balking is non-convex in the
capacity ¹. That is, nonconvexity occurs below the surface in Figure 2 and convexity above.
Note that for an arrival rate ¸ 6= 1, the value of ´ in the figure would be scaled by ¸, but
the region of non-convexity in the (¯;¸=¹) space will not change.
Finally, we prove that the convexity properties of the cost function (4) depend upon the
relative costs of balking and reneging. Proposition 8 focuses on the single-server case; we
conjecture that similar convexity properties hold for the multi-server case (S > 1) but have
not been able to prove this.
13
Figure 1: Steady-state expected balking rate is non-convex in capacity ¹
Figure 2: M/M/1 systems non-convexity region for steady-state expected balking rate as
function of capacity ¹ (for arrival rate ¸ = 1).
14
Proposition 8 Suppose that S = 1. If cr ¸ cb, then the cost function C(¢) defined in
(4) is convex in ¹ for all ¹ ¸ ´. Also, if cb¯ · cr < cb then C(¢) is convex in ¹ for
¹ ¸ maxf´;¸(1 ¡ ¯)g. On the other hand, if cr < cb¯, then, for sufficiently small ´ > 0,
C(¢) is non-convex in ¹.
Proof: Fix ¸;¯; and ´ > 0 (to be omitted as parameters of C(¢) for brevity). Suppose that
¹ ¸ ´ and that cr = cb = 1. We will prove that C00(¹) ¸ 0: From this, convexity of C(¢)
in ¹ for any cr and cb satisfying cr ¸ cb follows immediately from Proposition 6. From flow
conservation we have that
C(¹) = ¸ ¡ ¹P(Y ¸ 1) + k¹:
Let P(¹) = P(Y ¸ 1). Then,
C0(¹) = ¡¹P0(¹) ¡ P(¹) + k;
and
C00(¹) = ¡2P0(¹) ¡ ¹P00(¹):
Therefore, if
¡2P0(¹) ¸ ¹P00(¹); (8)
then C(¢) is convex. Notice that P(¢) is decreasing in ¹. Therefore, the right-hand-side of
(8) is non-negative. Hence, if the left-hand-side of (8) is negative the proof is complete.
Otherwise, if P00(¹) ¸ 0, then the balking rate ¸¯P(¹) is convex in ¹. In this case, by (4),
we only need to establish the convexity of the reneging rate in ¹. But this has been shown
in Proposition 6.
Suppose now that cb¯ · cr < cb and that ¹ ¸ maxf´;¸(1 ¡ ¯)g. We show that if cr = 1
and c¯ = 1=¯, then C(¢) is convex in ¹. Convexity for the general cb¯ · cr < cb case will
immediately follow from Proposition 6. If indeed cr = 1 and c¯ = 1=¯, then, from flow
conservation,
C(¹) = ¸ + (¸(1 ¡ ¯) ¡ ¹)P(Y ¸ 1) + k¹:
Recall that P(¹) = P(Y ¸ 1). Then,
C0(¹) = (¸(1 ¡ ¯) ¡ ¹)P0(¹) ¡ P(¹) + k;
and
C00(¹) = ¡2P0(¹) + (¸(1 ¡ ¯) ¡ ¹)P00(¹):
15
Therefore, if
¡2P0(¹) ¸ (¹ ¡ ¸(1 ¡ ¯))P00(¹); (9)
then C(¢) is convex. Following considerations similar to those in the previous case, and
noting that ¹ ¡ ¸(1 ¡ ¯) ¸ 0, we conclude the convexity of C(¢) in ¹ for this region.
Finally, suppose that cr < cb¯. We show that the limit of the cost of lost sales as ´ > 0
approaches zero is not convex. The rest will follow analogously to the proof of Proposition
7. Note that, from flow conservation and from the monotone convergence theorem, we have
that ˜
C(¹) : = lim´#0 fcb¸¯P(Y (1) ¸ 1) + cr´E[Y (1) ¡ 1]+g
=
(
cb¸¯ + cr(¸(1 ¡ ¯) ¡ ¹); ¹ · ¸(1 ¡ ¯);
cb ¸2¯¹+¸¯ ; ¹ > ¸(1 ¡ ¯):
Let ¹0 = ¸(1 ¡ ¯). Then the left derivative of ˜(¢) at ¹ = ¹0 is
˜C0(¹ = ¹¡0 ) = ¡cr:
Also, its right derivative at ¹ = ¹0 is
˜C0(¹ = ¹+0 ) = ¡cb¯:
Clearly, if cr < cb¯, then ˜(¢) is not convex at ¹0. currency1
In light of the above, one might think that convexity properties change but, fundamen-
tally, comparative statics do not. Surprisingly, customer commitment destroys one of the
monotonicity results obtained in the previous section. Recall that according to Theorem 1
the optimal capacity is increasing in the arrival rate and decreasing in the balking probability
for the non-commitment case. For the case of customer commitment during service, while
we believe that the monotonicity in the arrival rate still holds, we prove that the optimal
capacity is not necessarily monotone in the balking probability.
Proposition 9 Let C(¹; ¸;´;¯) be the cost function defined in (4) and let ¹currency1(¸;´;¯) be the
optimal capacity that minimizes C(¢). Then, ¹currency1(¢) is not necessarily monotone in the balking
probability ¯. In particular, with a single server (S = 1), for all sufficiently small ´; the
optimal capacity ¹currency1(¸;´;¢) exhibits non-monotonicity in ¯:
Proof: Suppose that S = 1, cb = cr = 1 and fix ¸ > 0. The limit of the cost function as
´ # 0 satisfies:
C(¹; ¯) := lim
´#0
C(¹; ¸;´;¯) =
( ¸ ¡ (1 ¡ k)¹; ¹ · ¸(1 ¡ ¯);
¸2¯
¹+¸¯ + k¹; ¹ > ¸(1 ¡ ¯):
16
Figure 3: The optimal capacity is non-monotone in the balking probability (S = 1;¸ =
1;k = 1 and ´ # 0).
It is easy to see that the optimal value of ¹ that minimizes C(¹; ¯) satisfies:
¹currency1(¯) =
8
<
:
¸(1 ¡ ¯); k ¸ ¯;
¸
³p
¯=k ¡ ¯
´
; k < ¯:
Suppose that ¸ = 1 and k = 0:1. In this case, as shown in Figure 3, ¹currency1(¯) is first decreasing
in ¯ and then it is increasing. In particular, for ¯1 = 0 < ¯2 = 0:1 < ¯3 = 0:2, we
have mucurrency1(¯1) > ¹currency1(¯2) < ¹currency1(¯3) and ¹currency1(¯) is non-monotone. Arguments analogous to the
proof of Proposition 7 show that for sufficiently small values of ´, ¹currency1(¯;´) is not necessarily
monotone in ¯. currency1
Intuitively, if ´ # 0, then for relatively small values of ¯, the dominant cost is the cost
of capacity. In this case, the optimal capacity is the minimum that guarantees stability
(¹ = ¸(1 ¡ ¯)), which is decreasing in ¯. For higher values of ¯, if k is sufficiently small,
then the dominant cost becomes the balking cost. In this case, to counteract the increasing
balking rate, the optimal ¹ is increasing in ¯.
We conclude that customer commitment during service strongly influences the convexity
properties and comparative statics of make-to-order systems with impatient customers.
17
6. Discussion
We have derived convexity properties for the cost of capacity and lost sales, as a function
of capacity, and evaluated how balking and reneging influence the optimal capacity invest-
ment. Some of our results (particularly Proposition 5) are counterintuitive. Furthermore,
we show that a seemingly minor change in system structure, customer commitment during
service, leads to qualitatively different results. These results underline the importance of
painstakingly accounting for balking and reneging in the design of make-to-order or service
systems.
Proposition 5 demonstrates an important difference between systems with backordering
costs and systems with reneging. It suggests that, before investing in capacity, managers need
to carefully model and estimate customers’ willingness to wait for their orders to be fulfilled.
Surprisingly, a larger reneging rate does not necessarily imply that greater capacity is needed.
To contrast this result with the more traditional models of inventory theory, suppose that
one assumes that customers will wait indefinitely for their order, but the manufacturer will
incur a backordering cost in addition to the cost of capacity. In this paper’s notation,
one can write down the cost function as e(¹; ¸) = cEY (1) + k¹; where c is the cost per
backlogged order per time unit, and no balking or reneging occurs. Note that e(¹; ¸) and
C(¹; ¸;´;¯ = 0) are almost identical in form. The one crucial difference is that EY (1) in
the infinite-backordering model is independent of its coefficient c, whereas EY (1) in our
model depends on its coefficient ´ in a non-trivial manner. In particular, in the infinite-
backordering model, the optimal capacity is always increasing in the backordering cost c: In
contrast, the optimal capacity in a system with reneging may decrease with the reneging rate.
The operations management literature widely assumes infinite backordering (rather than lost
sales) for analytic tractability. Customer impatience is represented by a high backordering
cost c, which is said to account for the “loss of good will” from forcing customers to wait.
The striking qualitative difference in results (that optimal capacity always increases with c in
infinite backordering model but may decrease with ´ in model with explicit reneging) shows
that, in deriving qualitative or structural insights, one cannot rely on a backorder penalty
to represent customers’ impatience. More specifically, in making decisions about capacity
investment for a make-to-order system, failure to explicitly account for reneging may result
in over-investment in capacity. Further research is needed to understand the implications of
balking and reneging for more general production-inventory systems.
18
A. Appendix: Proofs
Proof of Proposition 1: We first prove the proposition for the single-server case (S = 1).
The general multi-server case is dealt with at the end of this proof. The proof is based on the
sample path approach. Specifically, we prove that Y (viewed as a function of ¹) satisfies sam-
ple path convexity (a term that has been introduced by Shaked and Shanthikumar (1988)).
Specifically, let 0 · ¹1 · ¹2 · ¹3 · ¹4 be four service rates such that ¹1 + ¹4 = ¹2 + ¹3,
and fix ¸, ¯(¢) and ´(¢). Suppose that there exist Y1;:::;Y4, which are versions of the original
head-count processes (Yi has service rate of ¹i) that satisfy the following two properties for
all t ¸ 0:
1. Y1(t) + Y4(t) ¸ Y2(t) + Y3(t), a.s.
2. Y1(t) ¸ maxfY2(t);Y3(t);Y4(t)g, a.s.
Then, according to Shaked and Shanthikumar (1988), Y is said to be stochastically
decreasing and convex in the sample path sense (SDCX(sp)). From Theorem 3.6, Proposition
2.11 and Remark 2.8 of Shaked and Shanthikumar (1988) it follows that EY (1) is decreasing
and convex in ¹.
To construct the coupled versions Y1;:::;Y4 we wish to come up with appropriate uni-
formized discrete versions of the original processes. However, for uniformization to work one
needs bounded transition rates of the original Markov chain, which is not the case in this
paper (we do not assume boundedness of the reneging rates ´(y)). To resolve this problem
we define for all M > 0 a truncated reneging function ´M(y) = minf´(y);Mg. Clearly,
since ´(¢) is concave, and minf¢;Mg, is non-decreasing and concave, ´M(¢) is also concave.
Moreover, for any fixed M > 0, ´M(¢) is bounded. Let Y M1 ;:::;Y M4 be uniformized discrete
versions of the head-count processes with arrival rate ¸, balking probability function ¯(¢),
service capacity ¹i; i = 1;:::;4, and reneging rate function ´M(¢). We will show that for each
M > 0 and for every n 2 Z+ properties 1. and 2. hold at time n, with respect to Y M1 ;:::;Y M4 .
It will then follow that EY M(1) is decreasing and convex in ¹. But since Y M(1) weakly
converges to Y (1)5 it follows from Proposition 2.11 of Shaked and Shanthikumar (1988)
that EY (1) is a decreasing and convex function of ¹.
5This can be shown by writing down the stationary distributions of the corresponding birth and death
processes explicitly, and show that those distributions converge to the limiting one, with unbounded reneging
rates.
19
We now fix M > 0, and establish, by induction, that if 1. and 2. hold at time n = 0 for
Suppose that 1. and 2. hold for Y M1 ;:::;Y M4 , then they hold for all n = 1;2;:::. For brevity,
we omit the superscript M from the subsequent terms. In addition to 1. and 2. we define a
third property as follows:
e1. Y1(n) + Y4(n) = Y2(n) + Y3(n);
that is, property e: is property 1. with an equality replacing the inequality. We first establish
that if properties e and 2. are satisfied at time n, then properties 1. and 2. hold at time
n + 1. Let v = ¸ + ¹4 + M: be an upper bound on the total transition rate of the processes
Y1;:::;Y4. For n; such that e: and 2. hold, we define the following possible uniformized and
coupled transitions:
Arrival + balking: With probability ¸v we have a new order arriving into all four systems.
When a new order arrives, it balks system i with probability ¯(Yi(n)). This is done
as follows: Let Y(1)(n) ¸ Y(2)(n) ¸ Y(3)(n) ¸ Y(4)(n) be the order statistics for Yi(n),
i = 1;::;4: Respectively, refer to system (i) as the systems whose head-count is Y(i)(n).
Note that from properties e and 2; it follows that Y(1)(n) = Y1(n) and Y(4)(n) = Y4(n):
Now let ¯i = ¯(Y(i)(n)): From the monotonicity and concavity of ¯(¢) is follows that:
a. ¯1 ¸ ¯2 ¸ ¯3 ¸ ¯4;
b. ¯1 + ¯4 · ¯2 + ¯3:
Now, let U » Uniform(0;1): U will determine in which systems the order just arrived
will immediately balk according to the following rules:
i. If U · ¯4; then balk in all four systems.
ii. Else, if U · ¯2 + ¯3 ¡ 1; then balk from queues 1;(2) and (3):
iii. Else, if U · ¯3; then balk in queues (3) and 1 only.
iv. Else, if U · ¯1; then balk in queues (2) and 1 only.
v. Else, if U · ¯2 + ¯3 ¡ ¯4; balk in queue (2) only.
20
To verify that the balking occur according to the right probabilities, note that in systems
1;(3) and 4 the balking probabilities are trivially equal to the required probabilities. In
queue (2), if ¯2 + ¯3 ¡ ¯4 < 1 balking will occur with probability: ¯4 + (¯2 + ¯3 ¡ ¯4 ¡
¯3) = ¯2: Similarly, if ¯2 + ¯3 ¡ ¯4 ¸ 1; balking in this queue will occur with probability:
(¯2 + ¯3 ¡ 1) + (1 ¡ ¯3) = ¯2:
Service Completion: With probability ¹4v we have a service completion event. To deter-
mine which systems are going to indeed have service completions (as opposed to a
transition from a state to itself), let U vUniform(0;1).
a. If U < ¹1¹4 we have service completions from all systems for which Yi(n) > 0.
b. If ¹1¹4 · U < ¹2¹4 ; we have departures in systems 2 and 4 only, whenever the corre-
sponding queues are non-empty.
c. If ¹2¹4 · U < 1; we have departures in systems 3 and 4 only, whenever the corre-
sponding queue are non-empty.
It is easy to see, that system i has a service completion with probability ¹iv as long as
Yi(n) > 0 (recall that ¹1 + ¹4 = ¹2 + ¹3): Note that the reason why we do not simply
have a service completion from system i whenever U < ¹i¹4 ; is that in this case we may
have a service completion from system 4 only, which may violate property 1.
A Reneging Job (order cancellation) : Finally, with probability [´(Yi(n)) ^ M]=v we
have an order cancellation from system i. The coupling works as follows: let Y(1)(n) ¸
Y(2)(n) ¸ Y(3)(n) ¸ Y(4)(n) be the ordered statistics of Y1(n);:::;Y4(n); and let »(i) =
´M(Y(i)(n)) = minf´(Y(i)(n));Mg: Note that property e: and the convexity of ´M(¢)
imply that »(1) + »(4) · »(2) + »(3) (that is, the inequality with respect to the »i’s is
the opposite of property 1.) Let U v Uniform(0;1) be the random variable that
determines the reneging from all systems. Let m = maxfM;»(3) + »(2) ¡ »(4)g:
a. If U < »(4)m ; we will have one order cancellation from all the systems such that
Yi(n) > 0:
b. If »(4)m · U < »(3)m ; we have one order cancellation from each of the systems (3) and
(1) (provided that Y(i)(n) > 0; for i = 1;3):
21
c. If »(3)m · U < »(1)m , we have one order cancellation from each of the systems (2) and
(1) (provided that Y(i)(n) > 0; for i = 1;2):
d. If »(1)m · U < »(3)+»(2)¡»(4)m ; we have one order cancellation from system (2), provided
that Y(2)(n) > 0:
Note that given this setup, an order cancellation occurs in system (i) with probability
[´(Y(i)(n)) ^ M]=v:
We will now show that if properties e and 2. hold at time n, 1.-2. are satisfied at time
n + 1. We will go over the different types of events, to show that 1.-2. still hold at time
n + 1:
Arrival + balking: Since we have arrivals coming into all systems at the same time, prop-
erties 1:-2: will still hold at time n + 1, if no balking occurs. To verify that properties
1. and 2. hold at time n+1 in case of balking note that these can happen only if from
time n to n + 1 one of the following occurs:
I. The LHS of 1. stays the same, while the RHS of 1. increases by 1 or 2: This will
only occur when there is balking in both queues 1 and 4, which implies balking
in queues (2) and (3) as well.
II. The LHS of 1. increases by 1, while the RHS of 1. increases by 2: This change in
the LHS of 1. can only occur when the arrival to queue 4 does not balk, while
the arrival to queue 1 balks. However, in this case, at least one of the arrival to
queue (2) or (3) will balk.
III. Yi(n) = Y1(n) for some i 6= 1, and Y1 stays the same, while Yi increases by 1
(this will violate 2.): This would occur only if Y(2)(n) = Y1(n) and there will
be balking in queue 1 and not in queue (2). However, if Y(2)(n) = Y1(n); then
Y(3)(n) = Y4(n), and in particular ¯3 = ¯4: In this case, it is easily verified that
balking in queue 1 implies balking in queue (2) as well.
Service Completion: Here we have to make sure we are avoiding the following:
I. The LHS of 1. decreases by 1, while the RHS does not change:
II. The LHS of 1. decreases by 2, while the RHS decreases by 1 or does not change.
22
III. Yi = Y1 for some i 6= 1, and Y1 decreases by 1, while Yi does not change (hence
property 2. is violated).
Observe that none of these can happen because whenever Yi = 0 for either i = 2 or 3;
we have Y4 = 0: Moreover, if Yi = Y1; then if Y1 decreases, Yi will also decrease.
Order Cancellation: In this case, properties 1. - 2. will be violated if any of the above
I.-III. occur. We show that this cannot happen by going over the different values of
the uniform variable U. First note that here Y(1) = Y1 and Y(4) = Y4: Without loss of
generality, assume that Y(2) = Y2; and Y(3) = Y3; and omit the (¢) from the subscript.
Also, recall that »1 + »4 · »2 + »3:
a. If U < »4m; then Y4(n) > 0, which implies that Yi(n) > 0 for all i; which means that
all values of Yi(n) will be reduced by 1.
b. If »4m · U < »3m; then Y3(n) > Y4(n): This implies that Y1(n) > Y2(n) (from property
e1.), and therefore the fact that Y1(n) and Y3(n) are the only processes reduced by
1, will not violate 1.-2.
c. If »3m · U < »1m; then Y1(n) > Y3(n): This implies that Y2(n) > Y4(n) ¸ 0 (see
property e and therefore the fact that Y1(n) and Y2(n) are the only processes
reduced by 1, will not violate1.-2.
d. If »1m · U < »2+»3¡»4m ; then 1: ¡ 2: will clearly not be violated.
So far we have shown that if at time n properties e: and 2. hold, then at time n + 1
both properties 1 and 2 will hold. Suppose that at time n property 1. holds with a strict
inequality, that is:
Y1(n) + Y4(n) > Y2(n) + Y3(n):
In order to describe the transitions in this case, we first define the following transformation
of Y1(n) and Y4(n) : e1(n) = maxf0;Y2(n) + Y3(n) ¡ Y4(n)g and e4(n) = minfY2(n) +
Y3(n);Y4(n)g: It is easy to see that ei(n) · Yi(n) for i = 1;4. and that e1(n)+ e4(n) =
Y2(n) + Y3(n): That is, property e holds for the modified values of Yi(n): Let ei(n + 1);i =
1;2;3;4; be the values of these processes after one transition, that occurred according to the
above rules. In particular, we know that properties 1: and 2. hold for ei(n+1);i = 1;2;3;4.
Let Fi;x(y) = P¹=¹ifYi(n + 1) > y j Yi(n) = xg; then it is easy to verify that Fi;x(y) is
23
non-decreasing in x. In particular, for i = 1;4, let Yi(n + 1) = F¡1i;Yi(n)(Fi; x65Yi(n)(ei(n + 1)));
and for i = 2;3, simply let Yi(n + 1) = ei(n + 1): One can now easily verify that for all
i, Yi(n + 1) ¸ ei(n + 1); that properties 1. and 2. hold for Yi(n + 1);i = 1;::;4; and that
Yi(n + 1) has the right distribution (i.e. for all y, P¹=¹ifYi(n + 1) > yjYi(n)g = Fi;Yi(n)(y):
This completes the proof of the Proposition for the single server case.
It is left to prove the proposition for the general multiserver (S > 1) case. To extend
the above proof to the M/M/S system, the only case that needs to be treated is service
completions. We first establish the following relation:
If ¹1 + ¹4 = ¹2 + ¹3, Y1 + Y4 = Y2 + Y3 and Y1 is greater than maxfY2;Y3g then
¹1Y1 + ¹4Y4 · ¹2Y2 + ¹3Y3.
However, ¹4Y1 + ¹4Y4 = ¹4Y2 + ¹4Y3. Therefore, in order to prove the relation it is
sufficient to show: (¹1 ¡ ¹4)Y1 · (¹2 ¡ ¹4)Y2 + (¹3 ¡ ¹4)Y3. The last is true because
¹i ¡ ¹4 · 0, ¹1 ¡ ¹4 is equal to (¹2 ¡ ¹4) + (¹3 ¡ ¹4), and Y1 is greater than maxfY2;Y3g.
Once we have this relation in hand it follows that: ¹1 minfY1;Sg + ¹4 minfY4;Sg ·
¹2 minfY2;Sg + ¹3 minfY3;Sg.
To see this, notice that because Y1 and Y4 are more spread out than Y2 and Y3 and because
min is a concave function, minfY1;Sg+minfY4;Sg · minfY2;Sg+minfY3;Sg. (For a proof
assume that there are two random variables, the first of which takes values Y1 and Y4 with
probability 0.5 each, whereas the second takes the other two values with equal probability.
The random variables have the same expected value but one dominates the other in the
convex order.)
This observation and the earlier proved relation complete the proof that ¹1 minfY1;Sg +
¹4 minfY4;Sg · ¹2 minfY2;Sg + ¹3 minfY3;Sg.
Finally, this shows that we can couple the four systems such that the second and third
have more service completions on each sample path and that e and 2. hold at each service
completion.
currency1
Proof of Proposition 3: The proof follows the sample path approach. In particular, we
discretize time, and uniformize the transition rates in an analogous way to what was done in
the proof of Proposition 1. Specifically, we bound the reneging rate from above by M; and
after we prove the result for any M; we let M ! 1; to get the desired result. Given a value
of M; we show that we have sample-path sub-modularity for all n. More specifically, suppose
24
that the following three properties hold at time n = 0, for all ¸L < ¸H and ¹L < ¹H:
I. Y¸H;¹L(n) = maxfY¸;¹(n) ; ¸ = ¸L;¸H; ¹ = ¹L;¹Hg;
II. Y¸L;¹H (n) = minfY¸;¹(n) ; ¸ = ¸L;¸H; ¹ = ¹L;¹Hg;
III. Y¸H;¹H (n)¡ Y¸H;¹L(n) · Y¸L;¹H (n)¡ Y¸L;¹L(n);
then we show by induction that they hold for all n ¸ 0:
Suppose that S = 1, and let v = ¸H + ¹H + M. That is, v is the maximal transition
rate in all four systems given any state. Now suppose that I.-III. hold at time n, where III.
holds with an equality (we will call this property fI): In this case we have three types of
transitions:
Arrival + balking: With probability ¸Hv we have an arrival event. The coupling works as
follows: let U vUniform(0;1):
1. If U < ¸L¸
H
we have one arrival into each of the four systems.
2. If U ¸ ¸L¸
H
we have arrivals into the systems with ¸ = ¸H only.
Once it has been determined which systems will have new arrivals, these new arrivals all
balk together with probability ¯; and otherwise they join the queue.
Service Completion: With probability ¹Hv we have a service completion event. To deter-
mine which systems have a departure, let U vUniform(0;1):
1. If U < ¹L¹
H
we have a service completion for each one of the systems for which
Y¸;¹(n) > 0:
2. If U ¸ ¹L¹
H
we have a service completion for those systems with ¹ = ¹H only,
whenever Y¸;¹H (n) > 0:
Order Cancellation: With probability Mv we have an order cancellation event. Let ´M(y) =
minf´y;Mg be the reneging rate function. Let Y(i);i = 1;2;3;4 be a permuta-
tion of fY¸;¹(n); ¸ = ¸L;¸H;¹ = ¹L;¹Hg such that Y(1) ¸ Y(2) ¸ Y(3) ¸ Y(4):
Let »(i) = ´M(Y(i)): Note that I.,II, and f: and the concavity of ´M(¢) imply that
»(1) + »(4) · »(2) + »(3): Finally, let m = maxfM;»(2) + »(3) ¡ »(4)g. To determine which
systems have a service cancellation, let U vUniform(0;1):
25
1. If U < »(4)m ; we have a service cancellation from each one of the systems, provided
that the corresponding head-count is positive.
2. If »(4)m · U < »(3)m ; we have a service cancellation in systems (1) and (3), provided
that Y(i) > 0;i = 1;3:
3. If »(3)m · U < »(1)m ; we have a service cancellation in systems (1) and (2), provided
that Y(i) > 0;i = 1;2:
4. If »(1)m · U < »(2)+»(3)¡»(4)m ; we have a service cancellation is system (2), provided
that Y(2) > 0:
Verifying that if I:;II., and gI hold at time n, then I:;II. and III. hold at time
n + 1 is straightforward, and is analogous to proving Proposition 1. We omit the
details. If instead of gI, we have III at time n, proceed similarly to the proof of
the same proposition to validate the induction step. If S > 1 proceed similarly to the
general proof of Proposition 1, realizing that the only case to be concerned about is
the service completion. However, the service rates of the four systems being compared
can be ordered as ¹1;:::;¹4 as in the proof of Proposition 1. Therefore, this part of the
proof extends without modifications.
This completes the proof of the proposition. currency1
Proof of Lemma 1: Following the notation of the proof of Proposition 1, let 0 · ¹1 ·
¹2 · ¹3 · ¹4 be four service rates such that ¹1 + ¹4 = ¹2 + ¹3. Assume that the reneging
rate ´ is bounded above by ¹4. This is a weaker condition than the one stated in the Lemma,
but it turns out to be sufficient in establishing the its results.
Analogously to the proof of Proposition 1, let Y1;:::;Y4 be discretized and uniformized
versions of the head-count with service rates ¹1;:::;¹4, respectively, that satisfy properties:
1. Y1(n) + Y4(n) ¸ Y2(n) + Y3(n); a.s.
2. Y1(n) ¸ maxfY2(n);Y3(n);Y4(n)g; a.s.
at time n = 0. By induction, we wish to show that properties 1. and 2. hold for all
n ¸ 0.
The induction proof of 1. and 2. goes through by the simple construction explained next.
Note that arrivals, balking and service completion do not introduce a problem. For reneging,
26
one can transfer customers from system 1 to system 4 until one of two events happens: either
Y4 equals the minimum of Y2 and Y3, or Y4 equals S. In the first case, after the transfer Y1
will equal the maximum of Y2 and Y3. In the second case all systems will have S or more
customers. The transfer will not decrease the rate at which queues deplete in systems 1 and
4 due to the assumption on the reneging rate. Moreover, e: (or 1.) and 2. will continue to
hold. It thus follows that the induction proof goes through after this modification. In detail,
in the first case the two sets of systems will have equal reneging rate. In the second case,
(Y1 ¡S)+(Y4 ¡S) = (Y2 ¡S)+(Y3 ¡S). The reneging rates depend on these four quantities
and the earlier proof for Proposition 1 goes through.
Notice that if the condition ´ · ¹4 does not hold then the induction step will not work.
For example, if S = 1, then when Y1 = 2; Y2 = Y3 = 1; Y4 = 0, reneging can take place
only in the first system. Thus, 1. will get violated when there is a reneging. Similarly, if
¯ > 0 and S > 1, then the induction will not work either. For example, if S = 2, then when
Y1 = 2; Y2 = Y3 = 1; Y4 = 0, balking may only occur in system 1, and if it does occur
condition 1. will again be violated. Therefore, it appears that the conditions of the lemma
are not only sufficient but also necessary. currency1
Acknowledgments
This research was supported by the National Science Foundation under grant DMI-0239840.
27
References
Afeche, P. 2004, Incentive-compatible revenue management in queueing systems: optimal
strategic idleness and other delaying tactics, working paper. Kellogg School of Manage-
ment.
Armony, M. and M. Haviv. 2000. Price and delay competition between two service providers.
European Journal of Operational Research 147(1) 32-50.
Armony, M. and E. L. Plambeck. 2002. The impact of duplicate orders on demand estimation
and capacity investment. forthcoming in Management Science.
Baccelli, F. and Hebuterne G. 1981. On queues with impatient customers. In: F.J. Kylatra
(Ed.), Performance ’81. North-Holland Publishing Company, 159-179.
M.S. Bazaraa, H.D. Sherali, and C.M. Shetty. 1993. Nonlinear Programming: Theory and
Algorithms. 2nd edition. John Wiley & Sons, Inc.
Borst, S., Mandelbaum, A., Reiman M. and Zeltyn, S. 2005. Dimensioning call centers with
abandonment. In preparation.
Chen, L. and E.L. Plambeck. 2004. Dynamic inventory management with learning about
the demand distribution and substitution probability. Working Paper, Stanford Graduate
School of Business, Stanford, CA.
Cohen, M., P. Kleindorfer, and H. Lee. 1988. Service constrained (s,S) inventory systems
with priority demand classes and lost sales. Management Science 34 (4) 482-499.
Fridgeirsdottir, K. and S. Chiu. 2005 A note on convexity of the expected delay cost in
single server queues, forthcoming in Operations Research 53 (3).
Duenyas, I. 1995. Single facility due date setting with multiple customer classes Management
Science 41 608-619.
Duenyas, I. and W.J. Hopp. 1995. Quoting customer lead times Management Science 41
43-57.
Fairlie, R. 2004. How a custom PC can come with some very alien payment policies. Com-
puter Shopper, March 10.
Garnett O., Mandelbaum A. and Reiman M. 2002. Designing a Call Center with Impatient
Customers. Manufacturing and Service Operations Management, 4(3), 208-227.
28
Harrison and Zeevi. 2005. A method for staffing large call centers based on stochastic fluid
models. Manufacturing and Service Operations Management 7 (1) 20-36.
Ho, T.-H., S. Savin and C. Terwiesch. 2002. Managing demand and sales dynamics in new
product diffusion. Management Science, 48 (2) 187-206.
Hopp, W.J. and M.R. Sturgis. 2001. A simple and robust leadtime-quoting policy. Manu-
facturing and Service Operations Management 3 (4) 331-336.
Janakiraman, G. and R.O. Roundy. 2004. Lost-sales problems with stochastic leadtimes:
convexity results for base-stock policies. Operations Research. 52 (5) 795-803.
Johansen, S.G. and R.M. Hill. 2000. The (r,Q) control of a periodic-review inventory system
with continuous demand and lost sales. International Journal of Production Economics
68 279-286.
Johansen, S.G. and A. Thorstenson. 1993. Optimal and approximate (Q,r) inventory policies
with lost sales and gamma-distributed leadtimes. International Journal of Production
Economics 30-31 179-194.
Johansen, S.G. and A. Thorstenson. 1996. Optimal (r,Q) inventory policies with Poisson
demands and lost sales: discounted and undiscounted cases. International Journal of
Production Economics 46-47 359-371.
Kapuscinski, R. and S. Tayur. 2002. Reliable due date setting in a capacitated MTO system
with two customer classes. Michigan Business School Working Paper.
P. Keskinocak, R. Ravi, S. Tayur. 2001. Scheduling and reliable lead time quotation for
orders with availability intervals and lead time sensitive revenues. Management Science
47 (2) 264-279.
Kumar, S. and J. Swaminathan. 2003. Diffusion of innovations under supply constraints.
Operations Research 51 (6) 866-879.
Lederer, P.J. and L. Li. 1997. Pricing, production, scheduling and delivery-time competition.
Operations Research 45 (3) 407-420
Li, L. and Y.S. Lee. 1997. Pricing and delivery-time performance in a competitive environ-
ment. Management Science 40 (5) 633-646.
Mandelbaum A., Sakov A. and Zeltyn S. 2000. Empirical Analysis of a Call Center. Technical
Report.
29
Mandelbaum, A. and N. Shimkin. 2000. A model for rational abandonments from invisible
queues. Queueing Systems 36 (1-3) 1084-1134.
Mandelbaum A. and Zeltyn S. 1998. Estimating Characteristics of Queueing Networks Using
Transactional Data. Queueing Systems 29, 75-127.
Mendelson, H., S. Whang. 1990. Optimal incentive-compatible priority pricing for the
M/M/1 queue. Operations Research 38 (5) 870-883.
Moinzadeh, K. and S. Nahmias 1988. A continuous review model for an inventory system
with two supply modes. Management Science 6 761-773.
Nahmias, S. 1979. Simple approximations for a variety of dynamic leadtime lost-sales inven-
tory models. Operations Research 27 (5) 904-924.
Plambeck, E.L. 2004. Optimal leadtime differentiation via diffusion approximations. Oper-
ations Research 52 (2) 213-228.
Plambeck, E.L. 2004. Asymptotically optimal control for an assemble-to-order system with
capacitated component production and fixed transport cost. Working Paper, Stanford
Graduate School of Business, Stanford, CA.
Plambeck, E.L. and A.R. Ward. 2003. Optimal control of high-volume assemble-to-order
systems, Working Paper, Stanford Graduate School of Business, Stanford, CA.
Van Mieghem, J.A. 1995. Dynamic scheduling with convex delay costs: the generalized c¹
rule. Annals of Applied Probability 5 (3) 809-833.
Van Mieghem, J. 2000. Price and service discrimination in queueing systems: incentive
compatibility of Gc¹ scheduling. Management Science 46 (9) 1249-1267.
Ward, A.R. and P. Glynn. 2004. A diffusion approximation for a GI/GI/1 queue with
balking or reneging. Working Paper, School of Industrial and Systems Engineering,
Georgia Institute of Technology, Atlanta, GA.
Ward and Kumar. 2005. Asymptotically optimal admission control of a queue with impa-
tient customers. Working paper. School of Industrial and Systems Engineering, Georgia
Institute of Technology, Atlanta, GA.
Weber, R.R. 1983. A note on waiting times in single server queues. Operations Research 31
(5) 950-951.
Wein, L.M. 1991. Due date setting and priority sequencing in a multiclass M/G/1 queue.
30
Management Science 37 (7) 834-80.
Wein, L.M. and P. Chevalier. 1992. A broader view of the job-shop scheduling problem.
Management Science 38 (7) 1018-1033.
Zeltyn S. and Mandelbaum A. 2004. Call centers with impatient customers: many-server
asymptotics of the M/M/n+G queue. Working paper.
31