Optimal Server Assignment in Queues with Flexible Servers and Abandonments

1. Introduction

We consider a Markovian system of two tandem stations, a finite buffer of size B between the stations, and two servers. Suppose there is an infinite supply of raw materials in front of the first station, infinite storage space after the second station, and the system is operating under manufacturing blocking. The servers are flexible in that they are crosstrained and allowed to switch between stations with negligible travel time. We assume that each server can work on only one job at a time and that if both servers are assigned to the same station, they work together on one job. The jobs waiting in line to be processed by the second station (i.e., after being processed by the first station) may abandon the system (without receiving service at the second station) after an exponential amount of time with rate $\theta >0$. The service rate of server i = 1, 2 at station j = 1, 2 is denoted by μ_ij. When two servers work together on a job, their service rates are assumed to be additive. The service requirements for the jobs at the two stations are independently and exponentially distributed, and without loss of generality, we assume the mean service requirement of each job at each station is one. For example, such a queueing system can be used to model a manufacturing system producing time-sensitive goods (such as food items, pharmaceutical products, etc.) (as an example, see Aazami and Saidi-Mehrabad 2021).

For the queueing system described, our objective is to determine the dynamic server assignment policy that maximizes the long-run average throughput. The trade-off between assigning servers to station 1 versus station 2 is that one may either risk losing jobs that have been already processed at station 1 or not take advantage of the servers’ abilities at the station that they are most effective at. By dynamic assignment, we mean that servers are allocated to stations according to the state of the underlying system. We use Π to denote the set of all dynamic server assignment policies and $D_{\pi }(t)$ to denote the number of departures from the tandem line (after completing service at station 2) under policy $\pi \in \mathrm{\Pi }$ by time $t\ge 0$. Define $g^{\pi }={\mathrm{lim\hspace{0.17em}}\sup }_{t\to \infty }E[D_{\pi }(t)]/t$ as the long-run average throughput under policy π. Our objective is to solve the optimization problem

and identify the optimal throughput $g^{*}$ and the optimal policy ${\pi }^{*}$ such that $g^{{\pi }^{*}}=g^{*}$. For simplicity, set ${\mathrm{\Sigma }}_j={\sum }_{i=1}^2{\mu }_{ij}$ for $j\in \{1,2\}$. For any j, ${\mathrm{\Sigma }}_j=0$ would imply the throughput of the tandem line will always be zero and any server assignment policy is optimal. Similarly, for each server $i\in \{1,2\},\hspace{0.17em}{\sum }_{j=1}^2{\mu }_{ij}=0$ would imply the server will always be idle, and we can simply exclude the server from the system, in which case one can easily show that the expedite policy (that assigns all servers to the same job until completion) would be optimal. To avoid trivial cases, we assume ${\mathrm{\Sigma }}_j>0$ for all j = 1, 2 and ${\sum }_{j=1}^2{\mu }_{ij}>0$ for all i = 1, 2.

The rest of the paper is organized as follows. In Section 2, we discuss the relevant literature. Section 3 describes the Markov decision process problem that will be used to determine the optimal assignment of the servers. In Section 4, we present our optimal server allocation policy. Finally, Section 5 discusses the properties of the optimal policy. Proofs of some technical results are given in the appendix.

2. Literature Review

Tandem queues with flexible server(s) have drawn a lot of attention in the queueing theory literature. Many authors have considered the dynamic allocation of flexible server(s) to the stations in order to maximize various performance measures. In the interest of space, rather than presenting the entire body of literature in this area, we will mention only some sample papers. In one of the earliest papers in the area, Iravani et al. (1997) considered a two-station tandem queue with a single flexible server. Andradóttir et al. (2001) is the first paper that focused on throughput maximization in tandem queues where the number of servers is equal to the number of stations and the servers are heterogenous. Ahn et al. (2002) considered minimizing the holding cost in a two-station and two-server setting with homogeneous servers. In a more recent paper, Işik et al. (2016) focused on tandem lines with equal numbers of servers and stations where servers do not collaborate. van Leeuwen and Núñez-Queija (2017) investigated a Markovian tandem queueing model, in which service to the first queue is provided in batches, but rather than determining the assignment of servers, they focused on choosing the batch sizes so as to minimize a linear cost function of the mean queue lengths.

On the other hand, queueing systems with customer abandonments arise in many applications, such as manufacturing systems, call centers, hospital emergency rooms, etc. As a result, queues with abandonments have been of interest for a long time (see, for example, Barrer 1957, Ancker and Gafarian 1963, and Baccelli et al. 1984 for earlier works and Jouini and Dallery 2007, Boxma et al. 2011, Brandt and Brandt 2013, Das et al. 2013, Fralix 2013, and Moyal 2013 for more recent results). However, abandonment is a difficult phenomenon to analyze exactly. Because of the interest in call centers, many authors have considered asymptotic analysis of parallel queues with abandonments (see, for example, Whitt 2006 and Dai and He 2013) as well as the determination of asymptotically optimal staffing decisions in parallel queues with abandonments (see, for example, Dai and Tezcan 2008, Atar et al. 2010, Puha and Ward 2019, and Long et al. 2020).

There are a handful of papers that focus on obtaining exact optimal server assignment policies in parallel queues with abandonments. Koole and Pot (2011) consider an inbound call center with a fixed reward per call and communication and agent costs. In the presence of abandonments, they maximize the profit by controlling the number of lines and the number of agents. Down et al. (2011) consider the optimal dynamic assignment of a single server in a two-class service system with abandonments. They formulate the problem as a continuous-time Markov decision process to obtain partial results. Ansari et al. (2019) study a multiclass queueing system with a single server and customer abandonment. They show that the optimal scheduling policy of the server (to minimize the long-run average customer abandonment cost) is a static priority policy. They then derive conditions under which the asymptotically optimal policy of Atar et al. (2010) is optimal in this setting. On the other hand, Batt and Terwiesch (2015) provide an empirical study of parallel queues with impatient customers in the context of an emergency department.

However, the literature on the analysis and control of tandem queues with customer abandonments is scarce. Toward this end, Ayhan (2022) draws attention to this void in the literature, identifies a class of tandem queueing systems with customers abandonments for which exact analysis and control could be possible, and lists some of the open problems in this area that might be of interest to the queueing community. Armony et al. (2017) use fluid and diffusion approximations to determine the allocation of nurses in a tandem queue with abandonments that arises in a healthcare setting. Kim et al. (2013) derive the Laplace–Stieltjes transform of the sojourn time distribution in a tandem queue with Markovian arrivals and customer abandonments that can model a call center with interactive voice response. Reed and Yechiali (2013) study a two-station tandem queue with deadlines and retrials (i.e., when the deadline of a job expires, it is fed back to the end of the line rather than abandoning) and derive its stability condition. To the best of our knowledge, there are only four papers that provide exact analysis of tandem queues with flexible servers and abandonments. We review these next.

Wang et al. (2019) consider a Markovian queuing system of two stations in tandem where the first station has infinite buffer capacity and the second station has finite buffer capacity. Customers can get impatient and leave while waiting for service at the first or second station. Furthermore, they can also balk if there is no place available in the buffer of the second station when they complete service at the first station. The authors develop a recursive algorithm to compute the throughput of such systems and then, use their methodology to compute the system throughput under various staffing strategies. Zayas-Cabán et al. (2016) consider a similar Markovian system but with infinite buffer capacity at both stations. The objective is to determine the dynamic allocation of multiple homogenous servers at the two stations in order to maximize the discounted infinite-horizon expected reward and long-run average reward. The main novelty of their paper is to analyze the continuous-time problem directly because uniformization is not possible because of infinite buffer sizes and abandonments. They provide some sufficient conditions that guarantee that simple priority policies are optimal. In a follow-up paper, Zayas-Cabán et al. (2019) consider emergency departments with two stages where the patients can abandon without being treated in the second stage. They introduce threshold policies that prioritize the second stage unless the number of patients in the first stage exceeds the threshold and provide heuristics on how to choose the threshold. In a recent paper, Yu et al. (2023) consider a two-stage service system with two types of servers, namely subordinates who perform the first-stage service and supervisors who have their own responsibilities in addition to collaborating with the subordinates on the second-stage service. Rewards are earned when first- or second-stage service is completed and when supervisors finish one of their own responsibilities. Costs are incurred when impatient customers abandon without completing the second-stage service. They determine how the supervisors should distribute their time between their joint work with the subordinates and their own responsibilities to maximize the long-run average reward.

We now explain the positioning of this work relative to other papers (i.e., Zayas-Cabán et al. 2016, 2019; Wang et al. 2019; Yu et al. 2023) that also provide exact analysis of tandem systems with flexible servers and abandonments. In particular, unlike Zayas-Cabán et al. (2016, 2019) and Wang et al. (2019), we completely characterize the server allocation policy that maximizes the long-run average throughput for the two-station and two-server tandem network with abandonments described in Section 1. Furthermore, we allow the servers to be heterogenous in that their service rates not only depend on the station but also, depend on the server. Finally, unlike Yu et al. (2023), we consider the optimal allocation of all heterogenous servers, whereas Yu et al. (2023) focuses on dynamic assignment of one server type in a different setting.

3. Problem Formulation

For all $\pi \in \mathrm{\Pi }$ and $t\ge 0$, let $X^{\pi }(t)$ denote the number of jobs that have been processed at station 1 but are either waiting to be processed or being processed by station 2 at time t, where $X^{\pi }(t)\in S=\{0,1,\dots ,B+2\}$. From now on, we assume that Π is the set of all Markovian stationary deterministic policies corresponding to the state space S. For any given $\pi \in \mathrm{\Pi },\hspace{0.17em}\{X^{\pi }(t):t\ge 0\}$ is clearly a birth-death process with state space S. Because $B<\infty$ and the sum of all transition rates out of each state $s\in S$ is bounded by ${\sum }_{i=1}^2{\max }_{1\le j\le 2}{\mu }_{ij}+(B+2)\theta <+\infty$, $\{X^{\pi }(t)\}$ is uniformizable with a finite uniformization constant q. Thus, the continuous-time optimization Problem (1) can be translated into a discrete-time Markov decision problem by uniformization (i.e., modeling the state transitions at the event times of a Poisson process with rate q) (see, for example, Andradóttir et al. 2001). Note that q must satisfy ${\sum }_{i=1}^2{\max }_{1\le j\le 2}{\mu }_{ij}+(B+2)\theta \le q<\infty$, and the chosen value of q has no impact on our results.

We next provide a formal description of the discrete-time Markov decision process problem. As mentioned, the state space is $S=\{0,1,\dots ,B+2\}$, and we define the action space $A≔\{a_{{\sigma }_1{\sigma }_2}:{\sigma }_i\in \{0,1,2\},\forall i=1,2\}$, where ${\sigma }_i=j\in \{1,2\}$ means that server i is assigned to station j and ${\sigma }_i=0$ means server i is idle.

We next specify for all $s\in S$ and $a\in A$, r(s, a) and $p(j|s,a)$, which are the immediate reward and the probability of going to state j in one step when action a is chosen in state s when action a is chosen in state s, which is. We have for all $a\in A$,

and for all $s=1,\dots ,B+2$,

Finally, for all $s=1,\dots ,B+2$,

Furthermore,

andwhere in the interest of space, we omitted $p(j|s,a_{01}),\hspace{0.17em}p(j|s,a_{02})$, and $p(j|s,a_{21})$ because they are similar to $p(j|s,a_{10}),\hspace{0.17em}p(j|s,a_{20})$, and $p(j|s,a_{12})$, respectively, with the roles of servers 1 and 2 switched.

Note that because of the abandonments, the Markov decision process problem is unichain, and hence, the long-run average reward optimality equations for all $s=0,\dots ,B+2$ are given as

where g is the long-run average throughput and h is the bias vector (see sections 8.2.1 and 8.4.1 in Puterman 1994). Furthermore, we know from theorem 8.4.5 in Puterman (1994) that there exists an optimal Markovian stationary policy ${\pi }^{*}$. Note that a Markovian deterministic decision rule $d:S\to A$ specifies which action $d(s)\in A$ to choose in each state $s\in S$. Thus, a stationary policy π can be defined using the corresponding decision rule d and will be denoted as $\pi =d^{\infty }$.

4. Optimal Server Assignment Policy

In this section, we completely characterize the dynamic server assignment policy that maximizes the long-run average throughput. Without loss of generality, we number the servers such that ${\mu }_{11}{\mu }_{22}\ge {\mu }_{21}{\mu }_{12}$. From our assumptions in Section 1, this means that ${\mu }_{11}>0$ and ${\mu }_{22}>0$. For $n=1,\dots ,B+2$, define the decision rule d_n as follows:

Note that ${(d_1)}^{\infty }$ is the expedite policy, whereas ${(d_{B+2})}^{\infty }$ is the optimal policy when there are no abandonments (as shown in Andradóttir et al. 2001). On the other hand, ${(d_n)}^{\infty }$, for $1<n<B+2$, is equivalent to the optimal policy of systems without abandonments with a buffer size of n – 2.

We next state the main result of the paper, which completely characterizes the optimal server assignment policy. Note that the uniqueness of the optimal policy is subject to the interpretation that two actions could be equivalent if the service rate of a server at a particular station is zero.

Theorem 4.1.

When the servers are numbered such that ${\mu }_{11}{\mu }_{22}\ge {\mu }_{21}{\mu }_{12}$, the policy ${(d_N)}^{\infty }$ is optimal with throughput $g^{*}=g_N$ where N and g_n (for $n=1,\dots ,B+2$) are defined in (8) and (2), respectively. Furthermore, this is the unique optimal policy in the class of Markovian stationary deterministic policies when $\tau (N)>0$, where $\tau (n)$ (for $n=1,\dots ,B+2$) is defined in (4) and (5).

We next define the terminology used in the statement of Theorem 4.1 and provide several results that will be used in its proof. One can easily compute the long-run average throughput g_n under policy ${(d_n)}^{\infty }$, for $n=1,\dots ,B+2$, as

wherewithand the convention that summation over an empty set is zero and the multiplication over an empty set is one. We then characterizeand for $n=2,\dots ,B+2$,where $g_0=0$,and for $n=2,\dots ,B+2,$

Thus, the sign of $\tau (n)$ is the same as the sign of $g_n-g_{n-1}$ for $1\le n\le B+2$. The next proposition provides a useful property of the $\tau (·)$ function.

Proposition 4.1.

For $n\in \{2,\dots ,B+2\}$, if $\tau (n)\ge 0$, then $\tau (k)\ge 0$ for all $1\le k\le n-1$. Similarly, if $\tau (n)\le 0$, then $\tau (k)\le 0$ for all $n+1\le k\le B+2$.

Proof.

For $n\ge 2$, we have

$$\tau (n+1)=[{\mu }_{22}+(n-1)\theta ]\tau (n)-{\mu }_{12}\theta \epsilon (n-1),$$(6)

where for $n\ge 1$,

$$\begin{array}{ll}\epsilon (n)\hfill & =[f(1,n)+{\mathrm{\Sigma }}_1\alpha (n)][n(n-1){\theta }^2+(2n-1){\mu }_{22}\theta +{\mu }_{11}{\mu }_{12}]+{\mathrm{\Sigma }}_1{\mu }_{22}^2\alpha (n)\hfill \\ \hfill & +f(1,n)[{\mu }_{22}\theta +{\mu }_{22}{\mathrm{\Sigma }}_2+{\mu }_{11}{\mu }_{22}]+{\mathrm{\Sigma }}_1{\mu }_{11}^{n-1}[n\theta +{\mu }_{11}+{\mu }_{22}].\hfill \end{array}$$(7)

The relationship in (6) with some algebra follows from the equalities

$$\begin{array}{ll}f(k,n+1)=[{\mu }_{22}+(n-1)\theta ]f(k,n)\hfill & =[{\mu }_{22}+(n-1)\theta ][{\mu }_{22}+(n-2)\theta ]f(k,n-1) \text{and}\hfill \\ \alpha (n+1)=[{\mu }_{22}+(n-1)\theta ]\alpha (n)+{\mu }_{11}^{n-1}\hfill & =[{\mu }_{22}+(n-1)\theta ][{\mu }_{22}+(n-2)\theta ]\alpha (n-1)+\hfill \\ \hfill & [{\mu }_{22}+(n-1)\theta ]{\mu }_{11}^{n-2}+{\mu }_{11}^{n-1},\hfill \end{array}$$

with $n\ge 2$ and $k=1,\dots ,n-1$.

Because $\epsilon (n)>0$, we have $\tau (n)\ge 0$ if $\tau (n+1)\ge 0$. Note that if n = 1, the assertion still holds because $\tau (1)={\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2>0$. Similarly, if $\tau (n)\le 0$, then $\tau (n+1)\le 0$. $\square$

We then define

Note that Proposition 4.1 implies that $g_N\ge g_{N-1}\ge \cdots \ge g_1$ and $g_N>g_{N+1}\ge \cdots \ge g_{B+2}$. It also follows from (6) that $N=B+2$ when ${\mu }_{12}=0$. This makes sense because when ${\mu }_{12}=0,\hspace{0.17em}{a}_{12}=a_{22}$.

Before proving the theorem, we will present several properties of the bias vector h_N under policy ${(d_N)}^{\infty }$. Let $P_{d_N}$ be the $(B+2)\times (B+2)$-dimensional transition probability matrix corresponding to the decision rule d_N, and let $r_{d_N}$ be the $(B+2)$-dimensional reward vector corresponding to d_N, with $r_{d_N}(s)$ denoting the reward earned in state s under decision rule d_N, for all $s\in S$ (see Section 3). Then,

and

Because the Markov decision process problem is unichain, we employ the unichain policy iteration algorithm (see section 8.6.1 in Puterman 1994) and find a scalar g_N and a vector h_N solving

with $h_N(0)=0$. Note that e is a column vector of ones and I is the identity matrix. Furthermore, g_N is the unique scalar that satisfies (9), whereas h_N is unique and equal to the true bias vector plus a constant multiple of the vector e. In the next two lemmas, we provide some properties of the bias vector h_N that will be useful in the proof of Theorem 4.1. The proofs of these lemmas are given in the appendix.

Lemma 4.1.

We have

$$h_N(1)=\frac{g_{N}q}{{\mathrm{\Sigma }}_1},$$(10)

and for $s=2,\dots ,N$,

$$h_N(s)-h_N(s-1)=q\left[{\displaystyle \sum _{i=0}^{s-2}\frac{g_N-{\mu }_{22}}{{\mu }_{11}^{i+1}}}{\displaystyle \prod _{j=s-i-1}^{s-2}({\mu }_{22}+j\theta )}+\frac{g_N}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}f(1,s)\right],$$(11)

with the convention that product over an empty set is one and for $s=N,\dots ,B+2$,

$$h_N(s)-h_N(s-1)=\frac{q}{{\mathrm{\Sigma }}_2+(s-1)\theta }[{\mathrm{\Sigma }}_2-g_N].$$(12)

The next lemma provides closed-form expressions for the differences in (11) and (12). Note that because $h_N(0)=0$, (10), (13), and (14) show that, for all $s=1,\dots ,B+2,\hspace{0.17em}{h}_N(s)-h_N(s-1)\ge 0$.

Lemma 4.2.

For $s=2,\dots ,N$,

$$h_N(s)-h_N(s-1)=\frac{q}{\mathrm{\Delta }(N)}[{\mu }_{11}^{N-s}{\mu }_{12}{\mathrm{\Sigma }}_1\alpha (s)+[{\mathrm{\Sigma }}_2+(N-1)\theta ]{\mu }_{22}{\displaystyle \sum _{k=s+1}^N{\mu }_{11}^{k-s-1}}f(k,N)f(1,s)+{\mu }_{11}^{N-s}{\mathrm{\Sigma }}_{2}f(1,s)],$$(13)

with the convention that summation over an empty set is zero and for $s=N,\dots ,B+2$,

$$h_N(s)-h_N(s-1)=q[{\mathrm{\Sigma }}_2+(N-1)\theta ]\frac{{\mathrm{\Sigma }}_1{\mu }_{12}\alpha (N)+{\mathrm{\Sigma }}_{2}f(1,N)}{[{\mathrm{\Sigma }}_2+(s-1)\theta ]\mathrm{\Delta }(N)}.$$(14)

Proof of Theorem 4.1.

We use policy iteration for unichain models (see section 8.6.1 in Puterman 1994) to prove the optimality of ${(d_N)}^{\infty }$. In particular, we set the initial decision rule ν₀ of the policy iteration algorithm equal to d_N and then, show that the decision rule ν₁ computed as

$${\nu }_1(s)\in \arg \underset{a\in A_s}{\max }\left\{r(s,a)+{\displaystyle \sum _{j\in S}p}(j|s,a)h_N(j)\right\},\forall s\in S,$$

is equal to $d_N(s)$ for all $s\in S$. Toward this end, for all $s\in S$ and $a\in A_s$, we will compute the differences

$$\mathrm{\Gamma }(s,a)=r(s,d_N(s))+{\displaystyle \sum _{j\in S}p}(j|s,d_N(s))h_N(j)-(r(s,a)+{\displaystyle \sum _{j\in S}p}(j|s,a)h_N(j))$$

and show that the differences are nonnegative.

For s = 0, we have $d_N(s)=a_{11}$. Then, (10) yields

$$\mathrm{\Gamma }(0,a_{12})=\frac{{\mathrm{\Sigma }}_1}{q}{h}_N(1)-\frac{{\mu }_{11}}{q}{h}_N(1)=\frac{{\mu }_{21}}{q}{h}_N(1)=\frac{{\mu }_{21}}{{\mathrm{\Sigma }}_1}{g}_N\ge 0.$$

Note that $\mathrm{\Gamma }(0,a_{12})=0$ if and only if ${\mu }_{21}=0$, in which case actions a₁₁ and a₁₂ are the same. Similarly, for $a=a_{21}$,

$$\mathrm{\Gamma }(0,a_{21})=\frac{{\mathrm{\Sigma }}_1}{q}{h}_N(1)-\frac{{\mu }_{21}}{q}{h}_N(1)=\frac{{\mu }_{11}}{q}{h}_N(1)=\frac{{\mu }_{11}}{{\mathrm{\Sigma }}_1}{g}_N>0.$$

Finally, when $a=a_{22},\hspace{0.17em}\mathrm{\Gamma }(0,a_{22})=\frac{{\mathrm{\Sigma }}_1}{q}{h}_N(1)=g_N>0$. Because in state s = 0, $a_{12}=a_{10},\hspace{0.17em}{a}_{21}=a_{01}$, and $a_{22}=a_{02}=a_{20}=a_{00}$, we have shown that for all $a\in A\setminus \{a_{11}\},\hspace{0.17em}\mathrm{\Gamma }(0,a)\ge 0$. In the interest of space, for the rest of the proof, we do not specify the differences for idling actions that are all nonnegative (in particular, the differences are strictly positive as long as the actions are not equivalent).

Next, we consider $s=1,\dots ,N-1$ for which $d_N(s)=a_{12}$. For $a=a_{22}$,

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{22})\hfill & ={\mu }_{22}-{\mathrm{\Sigma }}_2+\frac{{\mathrm{\Sigma }}_2-{\mu }_{22}}{q}[h_N(s)-h_N(s-1)]+\frac{{\mu }_{11}}{q}[h_N(s+1)-h_N(s)]\hfill \\ \hfill & ={\mu }_{22}-{\mathrm{\Sigma }}_2+\frac{{\mathrm{\Sigma }}_2-{\mu }_{22}}{q}[h_N(s)-h_N(s-1)]+g_N-{\mu }_{22}+\frac{{\mu }_{22}+(s-1)\theta }{q}[h_N(s)-h_N(s-1)]\hfill \\ \hfill & =g_N-{\mathrm{\Sigma }}_2+\frac{{\mathrm{\Sigma }}_2+(s-1)\theta }{q}[h_N(s)-h_N(s-1)],\hfill \end{array}$$

where the second equality follows from (A.3). Now, (11) yields

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{22})\hfill & =g_N\left(1+\frac{{\mathrm{\Sigma }}_2+(s-1)\theta }{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}f(1,s)+[{\mathrm{\Sigma }}_2+(s-1)\theta ]{\displaystyle \sum _{i=0}^{s-2}\frac{1}{{\mu }_{11}^{i+1}}}{\displaystyle \prod _{j=s-1-i}^{s-2}({\mu }_{22}+j\theta )}\right)\hfill \\ \hfill & -\left({\mathrm{\Sigma }}_2+{\mu }_{22}[{\mathrm{\Sigma }}_2+(s-1)\theta ]{\displaystyle \sum _{i=0}^{s-2}\frac{1}{{\mu }_{11}^{i+1}}}{\displaystyle \prod _{j=s-1-i}^{s-2}({\mu }_{22}+j\theta )}\right)\hfill \\ \hfill & =g_N\left(\frac{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}+[{\mathrm{\Sigma }}_2+(s-1)\theta ][f(1,s)+{\mathrm{\Sigma }}_1\alpha (s)]}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}\right)\hfill \\ \hfill & -\frac{{\mathrm{\Sigma }}_2{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}+[{\mathrm{\Sigma }}_2+(s-1)\theta ]{\mathrm{\Sigma }}_1{\mu }_{22}\alpha (s)}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}\hfill \\ \hfill & \ge g_{s+1}\left(\frac{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}+[{\mathrm{\Sigma }}_2+(s-1)\theta ][f(1,s)+{\mathrm{\Sigma }}_1\alpha (s)]}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}\right)\hfill \\ \hfill & -\frac{{\mathrm{\Sigma }}_2{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}+[{\mathrm{\Sigma }}_2+(s-1)\theta ]{\mathrm{\Sigma }}_1{\mu }_{22}\alpha (s)}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}\hfill \\ \hfill & =\frac{\beta (s+1)}{\mathrm{\Delta }(s+1)}\times \frac{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}+[{\mathrm{\Sigma }}_2+(s-1)\theta ][f(1,s)+{\mathrm{\Sigma }}_1\alpha (s)]}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}\hfill \\ \hfill & -\frac{{\mathrm{\Sigma }}_2{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}+[{\mathrm{\Sigma }}_2+(s-1)\theta ]{\mathrm{\Sigma }}_1{\mu }_{22}\alpha (s)}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}}\times \frac{\mathrm{\Delta }(s+1)}{\mathrm{\Delta }(s+1)}\hfill \\ \hfill & =\frac{\beta (s+1)\mathrm{\Delta }(s)-\beta (s)\mathrm{\Delta }(s+1)}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}\mathrm{\Delta }(s+1)}=\frac{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}\tau (s+1)}{{\mathrm{\Sigma }}_1{\mu }_{11}^{s-1}\mathrm{\Delta }(s+1)}=\frac{\tau (s+1)}{\mathrm{\Delta }(s+1)}\ge 0,\hfill \end{array}$$

where the second equality follows from a change of variables with some algebra, the first inequality follows from the definition of N and Proposition 4.1, the second to last equality follows from (3), and the second inequality follows the definition of N and Proposition 4.1. Note that it follows from (6) that $\tau (s+1)=0$ if and only if $\tau (N)=0$ and $s=N-1$. We next consider $a=a_{21}$ for which

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{21})\hfill & ={\mu }_{22}-{\mathrm{\Sigma }}_2+\frac{{\mathrm{\Sigma }}_2-{\mu }_{22}}{q}[h_N(s)-h_N(s-1)]+\frac{{\mu }_{11}}{q}[h_N(s+1)-h_N(s)]\hfill \\ \hfill & +{\mu }_{22}+\frac{{\mathrm{\Sigma }}_1-{\mu }_{11}}{q}[h_N(s)-h_N(s+1)]+\frac{{\mu }_{22}}{q}[h_N(s-1)-h_N(s)]\hfill \\ \hfill & =\mathrm{\Gamma }(s,a_{22})+\mathrm{\Gamma }\prime (s,a_{21}),\hfill \end{array}$$

where we denote the expression in the second line as $\mathrm{\Gamma }\prime (s,a_{21})$. Because $\mathrm{\Gamma }(s,a_{22})\ge 0$, it suffices to show that $\mathrm{\Gamma }\prime (s,a_{21})\ge 0$. From (A.3), we have

$$\begin{array}{ll}\mathrm{\Gamma }\prime (s,a_{21})\hfill & =\frac{{\mathrm{\Sigma }}_1{\mu }_{22}+({\mu }_{11}-{\mathrm{\Sigma }}_1)g_N}{{\mu }_{11}}+\frac{-{\mathrm{\Sigma }}_1{\mu }_{22}+({\mu }_{11}-{\mathrm{\Sigma }}_1)(s-1)\theta }{q{\mu }_{11}}[h_N(s)-h_N(s-1)]\hfill \\ \hfill & =\frac{{\mathrm{\Sigma }}_1{\mu }_{22}+({\mu }_{11}-{\mathrm{\Sigma }}_1)g_N}{{\mu }_{11}}+\frac{-{\mathrm{\Sigma }}_1{\mu }_{22}+({\mu }_{11}-{\mathrm{\Sigma }}_1)(s-1)\theta }{\mathrm{\Delta }(N){\mu }_{11}}[{\mu }_{11}^{N-s}({\mathrm{\Sigma }}_2-{\mu }_{22}){\mathrm{\Sigma }}_1\alpha (s)\hfill \\ \hfill & +[{\mathrm{\Sigma }}_2+(N-1)\theta ]{\mu }_{22}{\displaystyle \sum _{k=s+1}^N{\mu }_{11}^{k-s-1}}f(k,N)f(1,s)+{\mu }_{11}^{N-s}{\mathrm{\Sigma }}_{2}f(1,s)],\hfill \end{array}$$

where the second equality follows from (13). Plugging in the closed-form Expression (2) of g_N and combining the terms with similar coefficients, with some algebra, we can write ${\mu }_{11}\mathrm{\Delta }(N)\mathrm{\Gamma }\prime (s,a_{21})$ as the following sum:

$$({\mathrm{\Sigma }}_1{\mu }_{22}+{\mu }_{11}{\mathrm{\Sigma }}_2-{\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2)({\mathrm{\Sigma }}_1{\mu }_{11}^{N-1}+(s-1)\theta {\mu }_{11}^{N-s}{\mathrm{\Sigma }}_1\alpha (s))+$$(15)

$${\mu }_{22}[{\mathrm{\Sigma }}_2+(N-1)\theta ]{\mathrm{\Sigma }}_1{\displaystyle \sum _{k=s+1}^N{\mu }_{11}^{k-s-1}}[f(k-s,N)-f(k,N)f(1,s+1)]+$$(16)

$${\mu }_{22}[{\mathrm{\Sigma }}_2+(N-1)\theta ]{\mu }_{11}(s-1)\theta {\displaystyle \sum _{k=s+1}^{N}f}(k,N)f(1,s)+$$(17)

$${\mu }_{11}^{N-s}{\mathrm{\Sigma }}_1{\mu }_{22}\left[{\mathrm{\Sigma }}_2{\mu }_{11}{\displaystyle \sum _{k=2}^s{\mu }_{11}^{k-2}}f(k+N-s,N)+{\mathrm{\Sigma }}_1({\mu }_{22}-{\mathrm{\Sigma }}_2)\alpha (s)\right]+$$(18)

$${\mu }_{11}^{N-s+1}{\mathrm{\Sigma }}_1{\mu }_{22}\left[(N-1)\theta {\displaystyle \sum _{k=2}^s{\mu }_{11}^{k-2}}f(k+N-s,N)-(s-1)\theta \alpha (s)\right]+$$(19)

$${\mu }_{11}^{N-s}f(1,s)\theta [{\mathrm{\Sigma }}_2({\mu }_{11}-{\mathrm{\Sigma }}_1)(s-1)+{\mathrm{\Sigma }}_1{\mu }_{22}(N-1)]+$$(20)

$${\mu }_{22}{\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2{\mu }_{11}^{N-1}[f(N+1-s,N)-f(1,s)].$$(21)

In order to prove that $\mathrm{\Gamma }\prime (s,a_{21})\ge 0$, we will show that the expressions in (15)–(21) are nonnegative. Note that

$${\mathrm{\Sigma }}_1{\mu }_{22}+{\mu }_{11}{\mathrm{\Sigma }}_2-{\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2={\mu }_{11}{\mu }_{22}-{\mu }_{21}{\mu }_{12}\ge 0,$$(22)

which implies that (15) is nonnegative. Similarly, for $s+1\le k\le N$, we have

$$f(k-s,N)-f(1,s+1)f(k,N)=f(k-s,k)f(k,N)-f(1,s+1)f(k,N)\ge 0,$$

where the inequality follows from the fact $f(k-s,k)\ge f(1,s+1)$. Thus, the expression in (16) is nonnegative. Clearly, (17) is nonnegative. Note that

$$\begin{array}{ll}\hfill & {\mathrm{\Sigma }}_2{\mu }_{11}{\displaystyle \sum _{k=2}^s{\mu }_{11}^{k-2}}f(k+N-s,N)+{\mathrm{\Sigma }}_1({\mu }_{22}-{\mathrm{\Sigma }}_2)\alpha (s)\hfill \\ \hfill & \ge {\mathrm{\Sigma }}_2{\mu }_{11}{\displaystyle \sum _{k=2}^s{\mu }_{11}^{k-2}}f(k,s)+{\mathrm{\Sigma }}_1({\mu }_{22}-{\mathrm{\Sigma }}_2)\alpha (s)\hfill \\ \hfill & ={\mathrm{\Sigma }}_2{\mu }_{11}\alpha (s)+{\mathrm{\Sigma }}_1({\mu }_{22}-{\mathrm{\Sigma }}_2)\alpha (s)\hfill \\ \hfill & =({\mathrm{\Sigma }}_1{\mu }_{22}+{\mu }_{11}{\mathrm{\Sigma }}_2-{\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2)\alpha (s)\ge 0,\hfill \end{array}$$

where the last inequality follows from (22). This shows that (18) is nonnegative. Similarly, the nonnegativity of (19) follows because ${\sum }_{k=2}^s{\mu }_{11}^{k-2}f(k+N-s,N)\ge \alpha (s)$ for $s\le N-1$. Note that

$${\mathrm{\Sigma }}_2({\mu }_{11}-{\mathrm{\Sigma }}_1)(s-1)+{\mathrm{\Sigma }}_1{\mu }_{22}(N-1)\ge (s-1)[{\mathrm{\Sigma }}_2({\mu }_{11}-{\mathrm{\Sigma }}_1)+{\mathrm{\Sigma }}_1{\mu }_{22}]\ge 0,$$(23)

where the last inequality follows from (22), which implies that (20) is nonnegative. Finally, $f(N+1-s,N)-f(1,s)\ge 0$ for $s=1,\dots ,N-1$, and hence, (21) is also nonnegative. This shows that $\mathrm{\Gamma }\prime (s,a_{21})>0$. Note that we cannot have $\mathrm{\Gamma }\prime (s,a_{21})=0$ because this would require s = N in (23), which is not possible because we are considering the case $s=1,\dots ,N-1$. Thus, $\mathrm{\Gamma }(s,a_{21})=\mathrm{\Gamma }(s,a_{22})+\mathrm{\Gamma }\prime (s,a_{21})>0$. We next consider $\mathrm{\Gamma }(s,a_{11})$ for $s=1,\dots ,N-1$. We have

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{11})\hfill & ={\mu }_{22}+\frac{{\mathrm{\Sigma }}_1-{\mu }_{11}}{q}[h_N(s)-h_N(s+1)]+\frac{{\mu }_{22}-\theta }{q}[h_N(s-1)-h_N(s))]\hfill \\ \hfill & =\mathrm{\Gamma }\prime (s,a_{12})+\frac{\theta }{q}[h_N(s)-h_N(s-1)]>0,\hfill \end{array}$$

where the inequality follows because $\mathrm{\Gamma }\prime (s,a_{12})>0$, and we have from Lemma 4.1 that $\frac{\theta }{q}[h_N(s)-h_N(s-1)]>0$. Thus, we have for all $a\in A$ and $s=1,\dots ,N-1,\hspace{0.17em}\mathrm{\Gamma }(s,a_{12})\ge 0$.

Next, we consider $s=N,\dots ,B+2$ for which $d_N(s)=a_{22}$. For $a=a_{12}$,

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{12})\hfill & ={\mu }_{12}+\frac{{\mu }_{12}}{q}[h_N(s-1)-h_N(s)]+\frac{{\mu }_{11}}{q}[h_N(s)-h_N(s+1)]\hfill \\ \hfill & ={\mu }_{12}+\frac{{\mu }_{12}}{{\mathrm{\Sigma }}_2+(s-1)\theta }(g_N-{\mathrm{\Sigma }}_2)+\frac{{\mu }_{11}}{{\mathrm{\Sigma }}_2+s\theta }(g_N-{\mathrm{\Sigma }}_2),\hfill \end{array}$$

where the second equality follows from (12). In particular, for s = N,

$$\begin{array}{ll}\mathrm{\Gamma }(N,a_{12})\hfill & ={\mu }_{12}+\frac{{\mu }_{12}}{{\mathrm{\Sigma }}_2+(N-1)\theta }(g_N-{\mathrm{\Sigma }}_2)+\frac{{\mu }_{11}}{{\mathrm{\Sigma }}_2+N\theta }(g_N-{\mathrm{\Sigma }}_2)\hfill \\ \hfill & =-\frac{\tau (N+1)}{({\mathrm{\Sigma }}_2+N\theta )\mathrm{\Delta }(N)}>0,\hfill \end{array}$$

where the second equality follows because

$$g_N-{\mathrm{\Sigma }}_2=\frac{-[{\mathrm{\Sigma }}_2+(N-1)\theta ]({\mathrm{\Sigma }}_{2}f(1,N)+{\mathrm{\Sigma }}_1{\mu }_{12}\alpha (N))}{\mathrm{\Delta }(N)}$$(24)

and the inequality follows from the definition of N. Furthermore, for $s=N,\dots ,B$,

$$\begin{array}{lll}\hfill & \hfill & \mathrm{\Gamma }(s+1,a_{12})-\mathrm{\Gamma }(s,a_{12})=(g_N-{\mathrm{\Sigma }}_2)\left[{\mu }_{12}\left(\frac{1}{{\mathrm{\Sigma }}_2+s\theta }-\frac{1}{{\mathrm{\Sigma }}_2+(s-1)\theta }\right)+{\mu }_{11}\left(\frac{1}{{\mathrm{\Sigma }}_2+(s+1)\theta }-\frac{1}{{\mathrm{\Sigma }}_2+s\theta }\right)\right]>0,\hfill \end{array}$$

where the inequality follows because $g_N-{\mathrm{\Sigma }}_2<0$ as shown in (24). Similarly,

$$\mathrm{\Gamma }(B+2,a_{12})-\mathrm{\Gamma }(B+1,a_{12})=(g_N-{\mathrm{\Sigma }}_2)\left[{\mu }_{12}\left(\frac{1}{{\mathrm{\Sigma }}_2+(B+1)\theta }-\frac{1}{{\mathrm{\Sigma }}_2+B\theta }\right)-\frac{{\mu }_{11}}{{\mathrm{\Sigma }}_2+(B+1)\theta }\right]>0.$$

Hence, $\mathrm{\Gamma }(s,a_{12})>0$ for all $s=N,\dots ,B+2$. Next, we consider $\mathrm{\Gamma }(s,a_{21})$ for $s=N,\dots ,B+2$. We have for $s=N,\dots ,B+1$,

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{21})\hfill & ={\mu }_{22}+\frac{{\mu }_{22}}{q}[h_N(s-1)-h_N(s)]+\frac{{\mu }_{21}}{q}[h_N(s)-h_N(s+1)]\hfill \\ \hfill & ={\mu }_{22}+\frac{{\mu }_{22}}{{\mathrm{\Sigma }}_2+(s-1)\theta }(g_N-{\mathrm{\Sigma }}_2)+\frac{{\mu }_{21}}{{\mathrm{\Sigma }}_2+s\theta }(g_N-{\mathrm{\Sigma }}_2).\hfill \end{array}$$

Thus,

$$\begin{array}{ll}\mathrm{\Gamma }(N,a_{21})\hfill & ={\mu }_{22}+\frac{{\mu }_{22}}{{\mathrm{\Sigma }}_2+(N-1)\theta }(g_N-{\mathrm{\Sigma }}_2)+\frac{{\mu }_{21}}{{\mathrm{\Sigma }}_2+N\theta }(g_N-{\mathrm{\Sigma }}_2)\hfill \\ \hfill & =\frac{({\mathrm{\Sigma }}_2+N\theta )(N-1){\mu }_{22}\theta f(1,N)+{\mathrm{\Sigma }}_1{\mu }_{22}\theta (({\mathrm{\Sigma }}_2+N\theta )(N-2)\alpha (N)+f(1,N))}{({\mathrm{\Sigma }}_2+N\theta )\mathrm{\Delta }(N)}+\hfill \\ \hfill & +({\mathrm{\Sigma }}_1{\mu }_{22}+{\mu }_{11}{\mathrm{\Sigma }}_2-{\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2)[{\mathrm{\Sigma }}_2+(N-1)\theta ]\frac{f(1,N)+{\mathrm{\Sigma }}_1\alpha (N)}{({\mathrm{\Sigma }}_2+N\theta )\mathrm{\Delta }(N)}>0,\hfill \end{array}$$

where the inequality follows from (22). Furthermore,

$$\begin{array}{lll}\hfill & \hfill & \mathrm{\Gamma }(s+1,a_{21})-\mathrm{\Gamma }(s,a_{21})=(g_N-{\mathrm{\Sigma }}_2)\left[{\mu }_{21}\left(\frac{1}{{\mathrm{\Sigma }}_2+(s+1)\theta }-\frac{1}{{\mathrm{\Sigma }}_2+s\theta }\right)+{\mu }_{22}\left(\frac{1}{{\mathrm{\Sigma }}_2+s\theta }-\frac{1}{{\mathrm{\Sigma }}_2+(s-1)\theta }\right)\right]>0,\hfill \end{array}$$

where the inequality follows because $g_N-{\mathrm{\Sigma }}_2<0$. Note that

$$\begin{array}{ll}\mathrm{\Gamma }(B+2,a_{21})\hfill & ={\mu }_{22}+\frac{{\mu }_{22}}{q}[h_N(B+1)-h_N(B+2)]\hfill \\ \hfill & ={\mu }_{22}+\frac{{\mu }_{22}}{{\mathrm{\Sigma }}_2+(B+1)\theta }(g_N-{\mathrm{\Sigma }}_2)\hfill \\ \hfill & =\frac{{\mu }_{22}(g_N+(B+1)\theta )}{{\mathrm{\Sigma }}_2+(B+1)\theta }>0.\hfill \end{array}$$

Thus, $\mathrm{\Gamma }(s,a_{21})>0$ for all $s=N,\dots ,B+2$. Finally, for $s=N,\dots ,B+2$,

$$\begin{array}{ll}\mathrm{\Gamma }(s,a_{11})\hfill & ={\mathrm{\Sigma }}_2+\frac{{\mathrm{\Sigma }}_2}{q}[h_N(s-1)-h_N(s)]+\frac{{\mathrm{\Sigma }}_1}{q}[h_N(s)-h_N(s+1)]+\frac{\theta }{q}[h_N(s)-h_N(s-1)]\hfill \\ \hfill & =\mathrm{\Gamma }(s,a_{12})+\mathrm{\Gamma }(s,a_{21})+\frac{\theta }{q}[h_N(s)-h_N(s-1)])>0.\hfill \end{array}$$

This proves the optimality of ${(d_N)}^{\infty }$ (see theorem 8.6.6 in Puterman 1994). Because $\mathrm{\Gamma }(s,a)>0$ for all $s=0,\dots ,B+2$, $a\in A\setminus \{d_N(s)\}$ when $\tau (N)>0$, and a and $d_N(s)$ are not equivalent, the uniqueness of the optimal policy follows from proposition 8.5.10 in Puterman 1994. $\square$

5. Properties of the Optimal Policy

Theorem 4.1 demonstrates that as in the optimal server assignment policy without abandonments (characterized in Andradóttir et al. 2001), the primary assignment of the servers to the stations is determined by maximizing the product of the service rates. Furthermore, as in Andradóttir et al. (2001), the servers work together at station 1 only when there is no work to be done at station 2. However, unlike the optimal policy without abandonments, servers work together at station 2 as long as there are N or more customers in the system where $N\le B+2$. Thus, the optimal policy does not necessarily use the entire buffer space. Hence, Theorem 4.1 suggests that there is a trade-off between using servers where they are effective (i.e., by letting N be large) and avoiding abandonments (i.e., by choosing N small). Theorem 4.1 also indicates that in the presence of abandonments, the buffer allocation should be done accordingly as one can incur unnecessary costs by assigning buffer space, which will not be needed. We now identify conditions under which n = 1 (so that the expedite policy is optimal).

Remark 5.1.

It is easy to see that n = 1 if and only if ${\mu }_{12}>0$ and $\theta >\frac{{\mathrm{\Sigma }}_2({\mu }_{11}{\mu }_{22}-{\mu }_{21}{\mu }_{12})}{{\mathrm{\Sigma }}_1{\mu }_{12}}$. This follows because $\tau (1)>0$, and from (5), we have

$$\tau (2)={\mathrm{\Sigma }}_2({\mu }_{11}{\mu }_{22}-{\mu }_{21}{\mu }_{12})-\theta {\mathrm{\Sigma }}_1{\mu }_{12},$$(25)

which is negative when ${\mu }_{12}>0$ and $\theta >\frac{{\mathrm{\Sigma }}_2({\mu }_{11}{\mu }_{22}-{\mu }_{21}{\mu }_{12})}{{\mathrm{\Sigma }}_1{\mu }_{12}}$. It then immediately follows that n = 1 when ${\mu }_{11}{\mu }_{22}={\mu }_{21}{\mu }_{12}$ (because ${\mu }_{11}{\mu }_{22}>0$ under our assumptions).

It follows from Remark 5.1 and Theorem 4.1 that ${(d_1)}^{\infty }$ (i.e., the expedite policy) is the unique optimal policy when ${\mu }_{11}{\mu }_{22}={\mu }_{21}{\mu }_{12}$ for any $\theta >0$. Thus, when there are abandonments, the optimal policy utilizes no buffer space. This is different from the case when θ = 0. Indeed, we know from Andradóttir et al. (2001) that when there are no abandonments and ${\mu }_{11}{\mu }_{22}={\mu }_{21}{\mu }_{12},\hspace{0.17em}{(d_1)}^{\infty }$ is an optimal policy, but it is not unique. In fact, in this case, ${(d_{B+2})}^{\infty }$ is also optimal. Continuing in this vein, the next corollary (which follows from Remark 5.1 and Theorem 4.1) shows that ${(d_1)}^{\infty }$ (i.e., the expedite policy) is the unique optimal policy when the servers are generalists (i.e., ${\mu }_{ij}={\mu }_i{\gamma }_j$ for i = 1, 2 and j = 1, 2; observe that $\tau (1)$ is always positive).

Corollary 5.1.

Suppose that ${\mu }_{ij}={\mu }_i{\gamma }_j$ for i = 1, 2 and j = 1, 2. Then, ${(d_1)}^{\infty }$ is the unique optimal policy.

Note that when the servers are generalists, they are equally effective at both stations. As a result, there is no trade-off between using the servers at stations that they are effective at versus avoiding abandonments. Thus, the optimal policy avoids abandonments completely and utilizes no buffer space.

The next proposition implies that for large-enough B, there exists $N<B+2$ as long as ${\mu }_{12}>0$.

Proposition 5.1.

We have for $\theta >0$ and ${\mu }_{12}>0$,

$$\underset{n\to \infty }{\lim }\tau (n)=-\infty .$$

Proof.

Note that combining similar terms, with some algebra the expression of $\tau (n)$ given in (5) can be written as

$$\begin{array}{ll}\tau (n)\hfill & =[{\mathrm{\Sigma }}_2+(n-1)\theta ][{\mu }_{12}{\mu }_{22}f(1,n-1)+{\mu }_{22}f(1,n)-{\mathrm{\Sigma }}_1{\mu }_{12}\alpha (n)-{\mathrm{\Sigma }}_{2}f(1,n)]\hfill \\ \hfill & +[{\mathrm{\Sigma }}_2+(n-2)\theta ]{\mu }_{11}[{\mathrm{\Sigma }}_1{\mu }_{12}\alpha (n-1)+{\mathrm{\Sigma }}_{2}f(1,n-1)]\hfill \\ \hfill & =-[{\mathrm{\Sigma }}_2+(n-1)\theta ][{\mu }_{12}f(1,n-1)(n-2)\theta +{\mathrm{\Sigma }}_1{\mu }_{12}\alpha (n)]\hfill \\ \hfill & +[{\mathrm{\Sigma }}_2+(n-2)\theta ]{\mu }_{11}[{\mathrm{\Sigma }}_1{\mu }_{12}\alpha (n-1)+{\mathrm{\Sigma }}_{2}f(1,n-1)]\hfill \\ \hfill & =[{\mathrm{\Sigma }}_2+(n-2)\theta ][{\mathrm{\Sigma }}_1{\mu }_{12}\left({\displaystyle \sum _{k=2}^{n-1}{\mu }_{11}^{k-1}}[f(k,n-1)-f(k+1,n)]-f(2,n)\right)\hfill \\ \hfill & -f(1,n-1)((n-2)\theta {\mu }_{12}-{\mu }_{11}{\mathrm{\Sigma }}_2)]-{\mu }_{12}\theta [{\mathrm{\Sigma }}_1\alpha (n)+(n-2)\theta f(1,n-1)],\hfill \end{array}$$(26)

for $n\ge 2$. The result then follows because $f(k,n-1)<f(k+1,n)$ for $k=2,\dots ,n-1$ and both $(n-2)\theta {\mu }_{12}$ and f(2, n) tend to infinity as n gets large. $\square$

Remark 5.2.

Note that N is nondecreasing in the buffer size B. This immediately follows from the fact that $\tau (n)$ does not depend on B (see Equations (4) and (5)). Furthermore, we have from Proposition 5.1 that if ${\mu }_{12}>0$, then N will remain the same after some finite B.

In the next proposition, we characterize how N changes with respect to the abandonment rate θ and the four service rates ${\mu }_{22},{\mu }_{11},{\mu }_{12}$, and μ₂₁. In what follows, increasing means nondecreasing, and decreasing means nonincreasing.

Proposition 5.2.

We have

1. N is decreasing in θ,

2. N is increasing in μ₂₂,

3. N is either increasing or is first increasing and then decreasing in μ₁₁,

4. N is decreasing in μ₁₂, and

5. N is decreasing in μ₂₁.

Proof.

First assume that ${\mu }_{12}=0$. Then, $N=B+2$, and (i)–(iii) and (v) hold trivially. Moreover, (iv) also holds because N cannot be larger than B + 2. For the rest of the proof, we assume that ${\mu }_{12}>0$. Furthermore, with a slight abuse of notation, in this proof, we will have g_n, τ, and ε not only as functions of n but also, the corresponding rate considered in each case.

1. We have from Remark 5.1 that n = 1 if ${\mu }_{11}{\mu }_{22}={\mu }_{21}{\mu }_{12}$. Thus, the result holds for this case, and we assume that ${\mu }_{11}{\mu }_{22}-{\mu }_{21}{\mu }_{12}>0$ for the rest of the proof. Note that it follows from (6) and (25) that, for $n\ge 2$,

   $$\tau (n,0)={\mu }_{22}^{n-2}\tau (2,0)={\mu }_{22}^{n-2}{\mathrm{\Sigma }}_2({\mu }_{11}{\mu }_{22}-{\mu }_{21}{\mu }_{12})>0.$$(27)

   Furthermore, it follows from (6), (7), and (25) that ${\lim }_{\theta \to \infty }\tau (n,\theta )=-\infty$ (because the largest power ${\theta }^{n-1}$ has a negative coefficient). Thus, for each $n\ge 2,\hspace{0.17em}\tau (n,\theta )$ has a positive root. We will show that $\tau (n,\theta )$ has a single positive root $\theta (n)$.

   We start by showing that g_n is nonincreasing in θ for all $n\ge 1$. Note that g₁ does not depend on θ and hence, is constant in θ. Now, assume that systems I and II are both operating under ${(d_n)}^{\infty }$ for $n\ge 2$ but that system I has a higher abandonment rate $\theta \prime$ than system II. Consider sample paths of both systems starting in the same state and generated using (the same) independent Poisson processes with rates ${\mu }_{11}+{\mu }_{21},\hspace{0.17em}{\mu }_{12}+{\mu }_{22},\hspace{0.17em}(n-1)\theta \prime$, and thinning. As time evolves, the number of customers in system II will be always greater than or equal to the number of customers in system I because of the higher abandonment rate of system I. In particular, when both systems are in the same state, every abandonment from (service completion at station 1 in) system II is associated with a simultaneous abandonment from (service completion at station 1 in) system I. Moreover, every service completion at station 2 in system I is accompanied by a simultaneous service completion at station 2 in system II. This shows that more customers complete service at station 2 in system II and that g_n is nonincreasing in θ.

   Now, suppose that $\tau (n,\theta )$ has two roots $0<{\theta }^1(n)<{\theta }^2(n)$. Then, $\tau (n,{\theta }^1(n))=\tau (n,{\theta }^2(n))=0$, which implies that $g_n({\theta }^1(n))=g_{n-1}({\theta }^1(n))$ and $g_n({\theta }^2(n))=g_{n-1}({\theta }^2(n))$. Again, consider two systems but now, with arbitrary abandonment rate θ: system I operating under ${(d_n)}^{\infty }$ and system II operating under ${(d_{n-1})}^{\infty }$. Assume that both systems start at an arbitrary state $s\le n-1$, and consider their sample paths generated using (the same) independent Poisson processes with rates ${\mu }_{11}+{\mu }_{21},\hspace{0.17em}{\mu }_{12}+{\mu }_{22},\hspace{0.17em}(n-1)\theta$, and thinning. Then, both systems will evolve the same until state n – 1 is reached. If there is an abandonment in state n – 1, both systems experience the abandonment, but it is possible that in state n – 1, system I (but not system II) can transition to state n because of a service completion at station 1 or system II (but not necessarily system I) will transition to state n – 2 because of a service completion at station 2. If this happens, then from this point onward, the number of customers in system I will dominate the number of customers in system II. Because the number of customers in system I is always greater than or equal to the number of customers in system II, all abandonments in system II will be experienced in system I as well. However, when the two systems are not in the same state, there may be abandonments in system I that do not occur in system II. Some of these additional abandonments in system I may be replaced by additional service completions at station 1 in system I but not in system II (if both systems are in state n ‒ 1); others may not be replaced. Because all service completions at station 1 lead to either abandonments or service completions at station 2, this implies that as θ increases, $g_n(\theta )$ decreases at least as rapidly as $g_{n-1}(\theta )$. So, if $g_n({\theta }^1(n))=g_{n-1}({\theta }^1(n))$, then $g_n({\theta }^2(n))\le g_{n-1}({\theta }^2(n))$. Furthermore, the inequality must be strict because otherwise, we would have $g_n(\theta )=g_{n-1}(\theta )$ for all ${\theta }^1(n)\le \theta \le {\theta }^2(n)$, which would imply that $\tau (n,\theta )=0$ for all ${\theta }^1(n)\le \theta \le {\theta }^2(n)$. This is not possible because $\tau (n,\theta )$ can have at most n – 1 roots as it is a polynomial of order n – 1 in θ. Hence, there is a single $\theta (n)>0$ such that $\tau (n,\theta (n))=0$.

   We then have from (6) and (7) that

   $$\tau (n+1,\theta (n))=[{\mu }_{22}+(n-1)\theta (n)]\tau (n,\theta (n))-{\mu }_{12}\theta (n)\epsilon (n-1,\theta (n))<0,$$
   which together with (27), implies that $\theta (n+1)<\theta (n)$. Thus,
   $$N=\{\begin{array}{ll}B+2\hfill & \text{if} \theta \le \theta (B+2),\hfill \\ n\in \{2,\dots ,B+1\}\hfill & \text{if} \theta (n+1)<\theta \le \theta (n),\hfill \\ 1\hfill & \text{for} \theta >\theta (2),\hfill \end{array}$$
   and the result follows.

2. The proof is similar to the proof of part (i) and is given in the appendix.

3. Note that ${\mu }_{11}\ge \frac{{\mu }_{21}{\mu }_{12}}{{\mu }_{22}}$, and it immediately follows from (6) and (7) that if for some ${\mu }_{11}\ge \frac{{\mu }_{21}{\mu }_{12}}{{\mu }_{22}},\hspace{0.17em}\tau (n,{\mu }_{11})\le 0$, and then, $\tau (n+1,{\mu }_{11})<0$. From (25), observe that

   $$\tau (2,{\mu }_{11})={\mu }_{11}({\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12})-{\mu }_{21}{\mu }_{12}({\mathrm{\Sigma }}_2+\theta ).$$(28)

   Then, n = 1 if ${\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12}<0$, n = 1 if ${\mu }_{21}>0$ and ${\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12}=0$, and n = 2 if ${\mu }_{21}=0$ and ${\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12}=0$. Thus, the result holds when ${\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12}\le 0$.

   Now, suppose that ${\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12}>0$. It follows from (6), (7), and (25) that $\tau (n,\frac{{\mu }_{21}{\mu }_{12}}{{\mu }_{22}})<0$ for all $n\ge 2$ because when ${\mu }_{11}=\frac{{\mu }_{21}{\mu }_{12}}{{\mu }_{22}}$, we have $\tau (2,\frac{{\mu }_{21}{\mu }_{12}}{{\mu }_{22}})=-\theta {\mathrm{\Sigma }}_1{\mu }_{12}<0$ (because ${\mu }_{12}>0$). Furthermore, ${\lim }_{{\mu }_{11}\to \infty }\tau (2,{\mu }_{11})=\infty$ (from (28)) and ${\lim }_{{\mu }_{11}\to \infty }\tau (n,{\mu }_{11})=-\infty$ for all $n\ge 3$ (because (6), (7), and (28) imply that the highest-power ${({\mu }_{11})}^{n-1}$ has a negative coefficient). It follows from (25) and (28) that $\tau (2,{\mu }_{11})$ has a single root ${\mu }_{11}(2)$ greater than $\frac{{\mu }_{21}{\mu }_{12}}{{\mu }_{22}}$. Finally, one can immediately see from (26) that for $n\ge 3,\hspace{0.17em}\frac{{\partial }^2\tau (n,{\mu }_{11})}{\partial {({\mu }_{11})}^2}<0$, and hence, $\tau (n,{\mu }_{11})$ is a concave function of μ₁₁. We can then conclude that for $n\ge 3,\hspace{0.17em}\tau (n,{\mu }_{11})$ has two roots, a single root, or no roots. Note that it follows from (6) and (7) that if $\tau (n,{\mu }_{11})$ has a single root or no roots, then $\tau (n+1,{\mu }_{11})$ has no roots. First, assume that there exists $3\le n\le B+2$ such that $\tau (n,{\mu }_{11})$ has two roots, and let $n^{*}$ be the largest such n. Then, $\tau (n,{\mu }_{11})$ for $3\le n<n^{*}$ must all have two roots. We consider two cases.

   1. $n^{*}\le B+1$, and $\tau (n^{*}+1,{\mu }_{11})$ has a single root. Let ${\mu }_{11}^1(n)$ and ${\mu }_{11}^2(n)$ be the two roots of $\tau (n,{\mu }_{11})$ for $3\le n\le n^{*}$ and ${\mu }_{11}(n^{*}+1)$ be the root of $\tau (n^{*}+1,{\mu }_{11})$. Then, these roots should satisfy ${\mu }_{11}(2)<{\mu }_{11}^1(3)<{\mu }_{11}^1(4)<\cdots <{\mu }_{11}^1(n^{*})<{\mu }_{11}(n^{*}+1)<{\mu }_{11}^2(n^{*})<{\mu }_{11}^2(n^{*}-1)<\cdots <{\mu }_{11}^2(3)$ because from (6) and (7), we have $\tau (n,{\mu }_{11})\le 0$, which implies that $\tau (n+1,{\mu }_{11})<0$ and $\tau (n,{\mu }_{11})$ is concave in μ₁₁. We will have n = 1 if ${\mu }_{11}<{\mu }_{11}(2)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge 2$; n = 2 if ${\mu }_{11}(2)\le {\mu }_{11}<{\mu }_{11}^1(3)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge 3$; n = 3 if ${\mu }_{11}^1(3)\le {\mu }_{11}<{\mu }_{11}^1(4)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge 4$; $\dots$ ; $N=n^{*}$ if ${\mu }_{11}^1(n^{*})\le {\mu }_{11}<{\mu }_{11}(n^{*}+1)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge n^{*}+1$; $N=n^{*}+1$ if ${\mu }_{11}={\mu }_{11}(n^{*}+1)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge n^{*}+1$; $N=n^{*}$ if ${\mu }_{11}(n^{*}+1)<{\mu }_{11}\le {\mu }_{11}^2(n^{*})$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge n^{*}+1$; $\dots$ ; n = 3 if ${\mu }_{11}^2(4)<{\mu }_{11}\le {\mu }_{11}^2(3)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge 4$; and n = 2 if ${\mu }_{11}>{\mu }_{11}^2(3)$ because $\tau (n,{\mu }_{11})<0$ for all $n\ge 3$. Thus, in this case, N is first nondecreasing and then nonincreasing in μ₁₁.

   2. $n^{*}=B+2$, or $\tau (n^{*}+1,{\mu }_{11})$ has no roots. Using the argument in (a), one can conclude that N will be first nondecreasing and then nonincreasing in μ₁₁ but in this case, will never attain $n^{*}+1$.

      On the other hand, if there is no $3\le n\le B+2$ such that $\tau (n,{\mu }_{11})$ has two roots, we also consider two cases.

   3. $\tau (3,{\mu }_{11})$ has one root. Then, we will have ${\mu }_{11}(2)<{\mu }_{11}(3)$, and n = 1 if ${\mu }_{11}<{\mu }_{11}(2)$; n = 2 if ${\mu }_{11}(2)\le {\mu }_{11}<{\mu }_{11}(3)$; n = 3 if ${\mu }_{11}={\mu }_{11}(3)$; and n = 2 if ${\mu }_{11}>{\mu }_{11}(3)$. Thus, N is again first nondecreasing and then nonincreasing in μ₁₁.

   4. $\tau (3,n)$ has no roots. Then, n = 1 if ${\mu }_{11}<{\mu }_{11}(2)$ and n = 2 if ${\mu }_{11}>{\mu }_{11}(2)$. Hence, in this case, N is nondecreasing in μ₁₁.

   This concludes the proof that when ${\mathrm{\Sigma }}_2{\mu }_{22}-\theta {\mu }_{12}>0$, N is either nondecreasing or is first nondecreasing and then nonincreasing in μ₁₁.

4. Proofs are given in the appendix. $\square$

As expected, Proposition 5.2(i) shows that as the abandonment rate θ increases, the optimal policy utilizes smaller buffer space in order to avoid abandonments. On the other hand, we have from Proposition 5.2(ii) that as the service rate μ₂₂ of the server at the second station increases, the optimal policy uses a larger buffer space and takes advantage of the effectiveness of the server at station 2. Moreover, Proposition 5.2(iii) indicates that when μ₁₁ is sufficiently large, the jobs accumulate quickly in the buffer, and the optimal policy uses a smaller buffer capacity as the service rate μ₁₁ at the first station increases. However, for small μ₁₁, it is possible that the optimal policy may utilize the specialty of the servers and that the optimal (utilized) buffer capacity may increase as μ₁₁ increases. As an example, consider a system with ${\mu }_{12}=1,{\mu }_{21}=1,{\mu }_{22}=8$, and θ = 4. It is easy to verify that when ${\mu }_{11}=3$, n = 4; when ${\mu }_{11}=4$, n = 5; and when ${\mu }_{11}=30$, n = 4. Thus, N first increases and then decreases as μ₁₁ increases. Proposition 5.2(iv) shows that the optimal (utilized) buffer capacity decreases as the service rate μ₁₂ of the first server at the second station increases (provided that it is less than or equal to $\frac{{\mu }_{11}{\mu }_{22}}{{\mu }_{21}}$). Similarly, Proposition 5.2(v) indicates that if the service rate μ₂₁ of the second server at the first station increases (provided that it is less than or equal to $\frac{{\mu }_{11}{\mu }_{22}}{{\mu }_{12}}$), then the optimal policy uses a smaller buffer space. These results are reasonable because as the service rates μ₁₂, μ₂₁ increase, the servers become less specialized, and hence, the optimal policy shifts emphasis from utilizing server specialty toward reducing abandonments.