OPTIMAL CONTROL OF FLEXIBLE SERVERS IN TWO TANDEM QUEUES WITH OPERATING COSTS

Dimitrios G. Pandelis

doi:10.1017/S0269964808000077

OPTIMAL CONTROL OF FLEXIBLE SERVERS IN TWO TANDEM QUEUES WITH OPERATING COSTS

Published online by Cambridge University Press: 18 December 2007

Dimitrios G. Pandelis

Show author details

Dimitrios G. Pandelis: Affiliation:
Department of Mechanical and Industrial EngineeringUniversity of Thessaly38334 Volos,Greece, E-mail: d_pandelis@mie.uth.gr

Article contents

Abstract
INTRODUCTION
CLEARING SYSTEMS
SYSTEMS WITH ARRIVALS
DISCUSSION
References

Rights & Permissions

Abstract

We consider two-stage tandem queuing systems with dedicated servers in each station and flexible servers that can serve in both stations. We assume exponential service times, linear holding costs, and operating costs incurred by the servers at rates proportional to their speeds. Under conditions that ensure the optimality of nonidling policies, we show that the optimal allocation of flexible servers is determined by a transition-monotone policy. Moreover, we present conditions under which the optimal policy can be explicitly determined.

Type: Research Article
Information: Probability in the Engineering and Informational Sciences , Volume 22 , Issue 1 , January 2008 , pp. 107 - 131

DOI: https://doi.org/10.1017/S0269964808000077 [Opens in a new window]
Copyright: Copyright © Cambridge University Press 2008

1. INTRODUCTION

We study the optimal dynamic assignment of flexible servers in two-stage tandem queuing systems, both without arrivals (clearing systems) and with arrivals. The problem we consider is motivated by applications in manufacturing systems where flexible resources (e.g., cross-trained workers, reconfigurable machines) are used to improve performance under varying demand and operating conditions. Narongwanich, Duenyas, and Birge [Reference Narongwanich, Duenyas and Birge16] considered the optimal allocation of capacity investments between dedicated and reconfigurable systems for firms that make products with random demands and introduced new generations of products in random future times. Hopp and Van Oyen [Reference Hopp and Van Oyen13] provide a framework for justifying workforce cross-training in an organization. They established the connection of cross-training to the organization's objectives and discussed methods of implementation appropriate for the specific application. Models of serial production systems with throughput maximization as the objective have been analyzed by Van Oyen, Gel, and Hopp [Reference Van Oyen, Gel and Hopp22], Andradottir, Ayhan, and Down [Reference Andradottir, Ayhan and Down4–Reference Andradottir, Ayhan and Down6], Gel, Hopp, and Van Oyen [Reference Gel, Hopp and Van Oyen10,Reference Gel, Hopp and Van Oyen11], Hopp, Tekin, and Van Oyen [Reference Hopp, Tekin and Van Oyen12], Iravani, Van Oyen, and Sims [Reference Iravani, Van Oyen and Sims15], and Ahn and Righter [Reference Ahn and Righter3]. These models include collaborative and noncollaborative work disciplines, open systems with external arrivals that are independent of the system state, closed systems (e.g., CONWIP systems where a departure triggers a new arrival), and various forms of cross-training (e.g., full, zone, or hierarchical cross-training).

There is also much research on the optimal use of flexible servers in tandem systems with holding costs. Because the mathematical models involved are quite complex, most results refer to two-stage systems and exponential service times. Rosberg, Varaiya, and Walrand [Reference Rosberg, Varaiya and Walrand19] considered a system with Poisson arrivals, a server with a constant service rate in the downstream station, and a server with a controllable service rate in the upstream station. They showed that the optimal service rate is nondecreasing in the length of the first queue and nonincreasing in the length of the second queue. Weber and Stidham [Reference Weber and Stidham23] considered a system of n stations with arrivals at each station, where, in addition to convex holding costs, servers incur operating costs that are convex functions of their service rates. They showed that the optimal policy is transition-monotone; that is, when a job leaves a queue, the optimal service rate in that queue is not increased and the optimal service rates in the other queues are not decreased. Duenyas, Gupta, and Olsen [Reference Duenyas, Gupta and Olsen7] and Iravani, Posner, and Buzacott [Reference Iravani, Posner and Buzacott14] characterized optimal policies for models of n and two-stage systems, respectively, with one flexible server and setup costs. Pandelis and Teneketzis [Reference Pandelis and Teneketzis18] studied two-stage clearing systems with multiple flexible servers where jobs join the second queue with probability p after completing service in the upstream station. They derived conditions under which the policy that gives priority to jobs in the upstream station is optimal for general service times. For a two-stage clearing system with two flexible servers, Ahn, Duenyas, and Zhang [Reference Ahn, Duenyas and Zhang2] provided necessary and sufficient conditions under which an exhaustive policy for the upstream or the downstream station is optimal. Similar results were obtained by Ahn, Duenyas, and Lewis [Reference Ahn, Duenyas and Lewis1] for the model with arrivals. The results of Ahn et al. [Reference Ahn, Duenyas and Zhang2] have been extended in two more directions. First, Schiefermayr and Weichbold [Reference Schiefermayr and Weichbold20] obtained the optimal policy for all values of holding costs and service times. Second, Weichbold and Schiefermayr [Reference Weichbold and Schiefermayr24] derived conditions for the optimality of exhaustive policies when jobs require the second stage of service with a certain probability.

With the exception of Rosberg et al. [Reference Rosberg, Varaiya and Walrand19] where there is a dedicated server in the downstream station, the aforementioned articles have assumed no dedicated capacity. Farrar [Reference Farrar8,Reference Farrar9] studied two versions of a clearing system with dedicated servers in both stations and one flexible server. In the constrained version, the flexible server can only work in the upstream station, whereas in the unconstrained version, the server can work in both stations. For both versions, he showed that the optimal policy is characterized by a switching curve; the flexible server is idled or assigned to the downstream station when the number of jobs there exceeds a certain threshold that depends on the number of jobs in the first queue. He also showed that the slope of the switching curve is greater than or equal to −1. Pandelis [Reference Pandelis17] showed the validity of the results obtained by Farrar [Reference Farrar8,Reference Farrar9] for the case when jobs might leave the system after completing service in the first station and specified subsets of the state space where the optimal policy can be explicitly determined. The same structure for the optimal policy was derived by Wu, Lewis, and Veatch [Reference Wu, Lewis and Veatch26] for a system with a number of flexible servers with the additional feature that all servers are subject to breakdowns. In their model, they assumed that processing requirements are the same in both stations, so actual processing times depend on the servers' speeds. Finally, Wu, Down, and Lewis [Reference Wu, Down and Lewis25] showed the optimality of a transition-monotone policy for the previous model with arrivals and no dedicated servers in the upstream station.

For clearing systems with no server breakdowns, we extend the results of Wu et al. [Reference Wu, Lewis and Veatch26] in two directions. First, we relax the assumption that the two stations are identical in terms of jobs' processing requirements. Second, we assume that all servers incur operating costs, different for each station, during the time they work. To the best of our knowledge, Weber and Stidham [Reference Weber and Stidham23] is the only previous work that has considered operating costs. Under the additional assumption that operating costs for flexible servers are proportional to their speeds, we get an equivalent problem with one flexible server. Depending on holding costs, operating costs, and service rates, there might be situations when it is optimal to idle the flexible server (e.g., when the number of jobs in the two stations is low enough to yield higher operating than potential holding costs). We derive a condition under which idling the flexible server is not optimal when there are jobs in the downstream station. For this instance of the problem, we show that when the flexible server has higher relative operating cost than the dedicated server in the same station, the optimal policy possesses the switching curve properties proven by Farrar [Reference Farrar8]. We also show for the case of no dedicated capacity in one of the two stations that it might be possible to determine the optimal policy explicitly. Specifically, the flexible server is always assigned to the station with no dedicated servers if the reduction in holding cost rate is larger in that station.

Assuming dedicated capacity in only one of the two stations, we obtain similar results for the problem with arrivals under the expected average cost criterion. After specifying the maximal arrival rate for which the problem has a solution and a condition for the optimality of nonidling policies, we show the following: (1) For dedicated capacity in the second stage only, the incentive to use the flexible server at the first stage is nonincreasing in the number of jobs at the second stage and (2) priority should be given to the station with no dedicated servers if the reduction in holding cost rate is larger and the operating cost is smaller there.

The article is organized as follows. In Section 2 the clearing model is formulated as a discrete-time Markov decision process and the structure of optimal nonidling policies is derived. The model with arrivals is analyzed in Section 3. Extensions are discussed as part of our concluding remarks in Section 4.

2. CLEARING SYSTEMS

We consider a tandem queuing system consisting of two stations. There is a number of jobs initially present in the system and no other external arrivals. Jobs that complete service in the upstream station (station 1) transfer to the downstream station (station 2) where they receive additional service and then leave the system. Every job in station i, i = 1, 2, requires an exponentially distributed amount of service with mean Y _i. There are dedicated servers, one for each station, working at speeds s _d1 and s _{d 2}; these servers are forced to work when there are jobs present in their corresponding station. There are also N additional servers that can serve in both stations; we assume that these servers can move from station to station instantaneously without any cost and work at speed s _i, i = 1, 2, …, N—the same for both stations. Let μ₁, μ₂ and μ_1i, μ_2i denote the processing rates for jobs served by the dedicated servers and flexible server i respectively at stations 1 and 2. We have

(1)

$\mu_1 = {s_{d1} \over Y_1}\comma \quad\quad \mu_2 = {s_{d2} \over Y_2}$

and

(2)

$\mu_{1i} = {s_i \over Y_1}\comma \quad\quad \mu_{2i} = {s_i \over Y_2}\comma \quad\quad i = 1\comma\; 2\comma \, \ldots\comma\; N.$

Each job in station i, i = 1, 2, incurs a linear holding cost at rate h _i. Moreover, dedicated servers incur linear operating costs at rates b ₁ and b ₂ during the time they work, whereas flexible servers incur costs at rates c _1i and c _2i, i = 1, 2, …, N, during the time they work in stations 1 and 2, respectively. Our objective is to determine an allocation strategy for the flexible servers that minimizes the total expected holding and operating costs until the system is cleared of all jobs. Allowing preemptions at times of service completions and assuming that work prior to completions is lost, we formulate the problem as a Markov decision process with state space {(x ₁, x ₂) : x ₁, x ₂ ≥ 0}, where x ₁ and x ₂ are the number of jobs in station 1 and station 2, respectively, including those in service. Starting from state (x ₁, x ₂), we let V(x ₁, x ₂) be the minimum total expected holding and operating cost incurred until the system empties, where V(0, 0) = 0. Let also M = {1, 2, … , N} be the set of flexible servers. To get an expression for the minimum cost function V(x ₁, x ₂), we minimize over all possible assignments of flexible servers to the two stations. After applying uniformization to convert the continuous-time problem to an equivalent discrete-time problem (see Serfozo [Reference Serfozo21]), we obtain dynamic programming equations (3)–(5), where terms V _F¹(x ₁, x ₂) and V _G²(x ₁, x ₂) correspond to machines in subsets F and G of M being assigned to stations 1 and 2, respectively. In deriving (3)–(5), we have assumed that the uniformization rate is μ₁ + μ₂ + ν₁ + ν₂ = 1, where ν₁ = ∑_iμ_1i and ν₂ = ∑_iμ_2i. We have also assumed that servers in the same station can collaborate to work on the same job, so that processing rates are additive. For x ₁, x ₂ ≥1, we have

(3)

$\eqalign{V\lpar x_1\comma\; x_2\rpar & = h_1 x_1 + h_2 x_2 + b_1 + b_2 + \mu_1 V\lpar x_1 - 1\comma\; x_2 + 1\rpar \cr & \quad + \mu_2 V\lpar x_1\comma\; x_2 - 1\rpar + \lpar \nu_1 + \nu_2\rpar V \lpar x_1\comma\; x_2\rpar \cr & \quad + \mathop{\min}\limits_{{F\comma G \subset M} \atop{F \cap G = \emptyset}} \lcub V_F^1 \lpar x_1\comma\; x_2\rpar + V_G^2 \lpar x_1\comma\; x_2\rpar \rcub \comma}$

(4)

$\eqalignno{V\lpar x_1\comma\; 0\rpar &= h_1 x_1 + b_1 + \mu_1 V\lpar x_1 - 1\comma\; 1\rpar \cr &\quad + \lpar \mu_2 + \nu_1 + \nu_2\rpar V\lpar x_1\comma\; 0\rpar + \mathop{\min \limits_{F \subset M}} \lcub V_F^1 \lpar x_1\comma\; 0\rpar \rcub \comma}$

(5)

$\eqalign{V\lpar 0\comma\; x_2\rpar & = h_2 x_2+b_2+\mu_2 V\lpar 0\comma\; x_2 - 1\rpar +\lpar \mu_1+\nu_1+\nu_2\rpar V\lpar 0\comma\; x_2\rpar \cr &\quad + \mathop{\min \limits_{G \subset M}} \lcub V_G^2 \lpar 0\comma\; x_2\rpar \rcub \comma }$

where

(6)

$V_F^1 \lpar x_1\comma\; x_2\rpar = c_{1F} + \mu_{1F} \lsqb V\lpar x_1 - 1\comma\; x_2 + 1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \comma$

(7)

$V_G^2 \lpar x_1\comma\; x_2\rpar = c_{2G}+\mu_{2G} \lsqb V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \comma$

and

(8)

$c_{1F} = \sum_{i \in F} c_{1i}\comma \quad\quad c_{2G} = \sum_{i \in G} c_{2i}\comma \quad\quad \mu_{1F} = \sum_{i \in F} \mu_{1i}\comma \quad\quad \mu_{2G} = \sum_{i \in G} \mu_{2i}.$

We assume that the following conditions hold.

(A1)
$\hskip -43pt{\eqalign{{c_{1i} \over s_i} &= \tilde{c}_1\comma \quad\quad {c_{2i} \over s_i}=\tilde{c}_2\comma \quad\quad i=1\comma\; 2\comma\, \ldots\comma\; N\comma\; \hbox{for some constants} \; \tilde{c}_1 \; \hbox{and} \; \tilde{c}_2.}}$
(A2)
${c_2 \over \nu_2} \leq {h_2+b_2 \over \mu_2}.$
(A3)
${c_1 \over \nu_1} \geq {b_1 \over \mu_1}\comma \quad\quad {c_2 \over \nu_2} \geq {b_2 \over \mu_2}$

Condition (A1) implies that operating costs incurred by flexible servers are proportional to their speeds. According to condition (A2), the mean operating cost for a job served in station 2 by the flexible server alone is no more than the corresponding mean holding and operating cost incurred during this job's service by the dedicated server alone. According to condition (A3), the operating cost per unit speed is greater for the flexible server compared to the dedicated server in the same station.

We show in the following proposition that under condition (A1), there exists an optimal policy that prescribes the same action for all flexible servers.

Proposition 1

Assume that condition (A1) holds. Then there exists an optimal policy that either idles all flexible servers or assigns them all to a single station.

Proof

Assuming F ≠ ∅ and m ∈ F and letting F _m = F − {m}, we obtain from condition (A1) and (1), (2), (6), and (8)

$\eqalign{V_F^1 \lpar x_1\comma\; x_2\rpar - V_{F_m }^1 \lpar x_1\comma\; x_2\rpar &=c_{1m}+\mu_{1m} \lsqb V\lpar x_1 - 1\comma\; x_2+1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \cr & =\mu_{1m} V_1 \lpar x_1\comma\; x_2\rpar \comma }$

where

$V_1 \lpar x_1\comma\; x_2\rpar =\tilde{c}_1 Y_1+V\lpar x_1 - 1\comma\; x_2+1\rpar - V\lpar x_1\comma\; x_2\rpar .$

Similarly, for G ≠ ∅, n ∈ G, and G _n = G − {n}, we obtain from condition (A1) and (1), (2), (7), and (8)

$\eqalign{V_G^2 \lpar x_1\comma\; x_2\rpar - V_{G_n }^2 \lpar x_1\comma\; x_2\rpar &=c_{2n}+\mu_{2n} \lsqb V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \cr & =\mu_{2n} V_2 \lpar x_1\comma\; x_2\rpar \comma }$

where

$V_2 \lpar x_1\comma\; x_2\rpar =\tilde{c}_2 Y_2+V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2\rpar .$

We have the following cases.

(i) V ₁(x ₁, x ₂) ≥ 0, V ₂(x ₁, x ₂) ≥ 0: It is optimal to idle all flexible servers.
(ii) V ₁(x ₁, x ₂) ≥ 0, V ₂(x ₁, x ₂) < 0: It is optimal to assign all flexible servers to station 2 when there is at least one job present there, otherwise idling is optimal.
(iii) V ₁(x ₁, x ₂) < 0, V ₂(x ₁, x ₂) ≥ 0: It is optimal to assign all flexible servers to station 1 when there is at least one job present there, otherwise idling is optimal.
(iv) V ₁(x ₁, x ₂) < 0, V ₂(x ₁, x ₂) < 0: Idling any flexible server is not optimal.

Therefore, it is optimal to either idle or use all flexible servers. It remains to show that when case (iv) holds, it is optimal to assign all servers to a single station. Let F and G be such that F xxx G = M and G ≠ ∅. For i ∈ G, we denote by F _i and G _i the sets of servers assigned to stations 1 and 2, respectively, after moving server i from station 2 to station 1 (i.e., F _i = F xxx {i}, G _i = G − {i}). From condition (A1) and (1), (2), and (6)–(8), we get

(9)

$\eqalignno{V_{F_i}^1 \lpar x_1\comma\; x_2\rpar &+V_{G_i}^2 \lpar x_1\comma\; x_2\rpar - \lsqb V_F^1 \lpar x_1\comma\; x_2\rpar +V_G^2 \lpar x_1\comma\; x_2\rpar \rsqb \cr &= c_{1i}+\mu_{1i} \lsqb V\lpar x_1 - 1\comma\; x_2+1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb - c_{2i} \cr &\quad - \mu_{2i} \lsqb V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \cr & = \mu_{2i} V_{12} \lpar x_1\comma\; x_2\rpar \comma\; & }$

where

$\eqalign{V_{12} \lpar x_1\comma\; x_2\rpar &=\lpar \tilde{c}_1 - \tilde{c}_2\rpar Y_2+{Y_2 \over Y_1}\lsqb V\lpar x_1 - 1\comma\; x_2+1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \cr &\quad - \lsqb V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb .}$

Equation (9) implies that when V ₁₂(x ₁, x ₂) ≥ 0, it is optimal to assign all flexible servers to station 2; otherwise, assign them to station 1.■

As a consequence of Proposition 1, replacing the N flexible servers with one server working at rates ν₁ and ν₂ and incurring operating costs at rates c ₁ and c ₂ given by c ₁ = ∑_ic _1i and c ₂ = ∑_ic _2i results in an equivalent problem. The optimality equations for this problem take the following form:

(10)

$\eqalignno{V\lpar x_1\comma\; x_2\rpar &=h_1 x_1+h_2 x_2+b_1+b_2+\mu_1 V\lpar x_1 - 1\comma\; x_2+1\rpar \cr &\quad +\mu_2 V\lpar x_1\comma\; x_2 - 1\rpar + \lpar \nu_1+\nu_2\rpar V\lpar x_1\comma\; x_2\rpar \cr &\quad +\min \!\lcub 0\comma\ V_M^1 \lpar x_1\comma\; x_2\rpar \comma\; V_M^2 \lpar x_1\comma\; x_2\rpar \rcub \comma\; & }$

(11)

$\eqalign{V\lpar x_1\comma\; 0\rpar &=h_1 x_1+b_1+\mu_1 V\lpar x_1 - 1\comma\; 1\rpar +\lpar \mu_2+\nu_1+\nu_2\rpar V\lpar x_1\comma\; 0\rpar \cr &\quad +\min\! \lcub 0\comma\; V_M^1 \lpar x_1\comma\; 0\rpar \rcub \comma }$

(12)

$\eqalignno{V\lpar 0\comma\; x_2\rpar &=h_2 x_2+b_2+\mu_2 V\lpar 0\comma\; x_2 - 1\rpar +\lpar \mu_1+\nu_1+\nu_2\rpar V\lpar 0\comma \ x_2\rpar \cr &\quad +\min \!\lcub 0\comma\; V_M^2 \lpar 0\comma\; x_2\rpar \rcub . &}$

Next, we show that, under condition (A2), idling the flexible server is not optimal when there is at least one job in station 2. Actually, condition (A2) is the condition under which it is optimal to use the flexible server when there are no jobs in station 1. To see this, note that when there are no jobs present at one of the two stations, we can derive the following expressions for the value function by conditioning on the time of the first service completion:

(13)

$V\lpar x_1\comma\; 0\rpar =\min \left\{{h_1 x_1+b_1 \over \mu_1}\comma\; {h_1 x_1+b_1+c_1 \over \mu_1+\nu_1}\right\}+V\lpar x_1 - 1\comma\; 1\rpar \comma\;$

(14)

$V\lpar 0\comma\; x_2\rpar =\min \left\{{h_2 x_2+b_2 \over \mu_2}\comma\; {h_2 x_2+b_2+c_2 \over \mu_2+\nu_2}\right\}+V\lpar 0\comma\; x_2 - 1\rpar .$

Therefore, when station 1 or station 2 is empty of jobs, idling the flexible server is optimal for x ₂ < X ₂ and x ₁ < X ₁, respectively, where

$X_2={c_2 \mu_2 - b_2 \nu_2 \over h_2 \nu_2}\comma \quad\quad X_1={c_1 \mu_1 - b_1 \nu_1 \over h_1 \nu_1}.$

Therefore, if condition (A2) holds, idling the flexible server is not optimal when x ₁ = 0. We show in Proposition 2 that this is also true for x ₁ > 0, provided that there are jobs in station 2. First, we need the following lemma (for the proof, see Appendix A).

Lemma 1

Assume that condition (A2) holds. Then, for x ₁, x ₂ ≥ 1,

$V\lpar x_1\comma\; x_2\rpar - V\lpar x_1\comma\; x_2 - 1\rpar \geq {h_2 x_2+b_2+c_2 \over \mu_2+\nu_2}.$

Proposition 2

Condition (A2) is a sufficient condition under which the optimal policy always uses the flexible server when there are jobs present in the downstream station.

Proof

Lemma 1 and condition (A2) yield

$\nu_2 \lsqb V\lpar x_1\comma\; x_2\rpar - V\lpar x_1\comma\; x_2 - 1\rpar \rsqb - c_2 \geq 0$

[i.e., V _M²(x ₁, x ₂) ≤ 0], which by (10) implies that for x ₁, x ₂ ≥ 1, the policy that assigns the flexible server to station 2 has no more cost than the one that idles the server. ■

Assuming condition (A2) holds and using (6)–(8), optimality equations (10)–(12) are reduced to the following. For x ₁, x ₂ ≥ 1,

(15)

$\eqalignno{V\lpar x_1\comma\; x_2\rpar &=h_1 x_1+h_2 x_2+b_1+b_2+\mu_1 V\lpar x_1 - 1\comma\; x_2+1\rpar \cr &\quad +\mu_2 V\lpar x_1\comma\; x_2 - 1\rpar + \min\! \lcub c_2+\nu_2 V\lpar x_1\comma\; x_2 - 1\rpar \cr &\quad +\nu_1 V\lpar x_1\comma\; x_2\rpar \comma\; c_1+\nu_1 V\lpar x_1 - 1\comma\; x_2+1\rpar +\nu_2 V\lpar x_1\comma\; x_2\rpar \rcub . & }$

For x ₂ = 0 or x ₁ = 0,

(16)

$\eqalignno{V\lpar x_1\comma\; 0\rpar &=h_1 x_1+b_1+\mu_1 V\lpar x_1 - 1\comma\; 1\rpar +\lpar \mu_2+\nu_2\rpar V\lpar x_1\comma\; 0\rpar \cr &\quad + \min\! \lcub \nu_1 V\lpar x_1\comma\; 0\rpar \comma\; c_1+\nu_1 V\lpar x_1 - 1\comma\; 1\rpar \rcub \comma &}$

(17)

$\eqalignno{V\lpar 0\comma\; x_2\rpar &=h_2 x_2+b_2+\mu_2 V\lpar 0\comma\; x_2 - 1\rpar +\lpar \mu_1 + \nu_1\rpar V\lpar 0\comma\; x_2\rpar \cr &\quad + \min \!\lcub c_2 + \nu_2 V\lpar 0\comma\; x_2 - 1\rpar \comma\; \nu_2 V\lpar 0\comma\; x_2\rpar \rcub .&}$

The first (resp. second) argument in the minimization terms corresponds to assigning the flexible server to station 2 (resp. station 1). When there are no jobs present in a station, assigning the additional server to that station is equivalent to idling. Although we have established that idling is not optimal when condition (A2) is true, we have left the corresponding term in (17) to facilitate subsequent analysis.

Based on (15)–(17), we define the decision function d(x ₁, x ₂) as follows:

$\eqalign{d\lpar x_1\comma\; x_2\rpar &=c_2 - c_1+\nu_2 \lsqb V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2\rpar \rsqb \cr &\quad + \nu_1 \lsqb V\lpar x_1\comma\; x_2\rpar - V\lpar x_1 - 1\comma\; x_2+1\rpar \rsqb \comma \quad\quad x_1\comma\; x_2 \geq 1\comma \cr d\lpar x_1\comma\; 0\rpar &=\nu_1 \lsqb V\lpar x_1\comma\; 0\rpar - V\lpar x_1 - 1\comma\; 1\rpar \rsqb - c_1\comma \quad\quad x_1 \geq 1\comma \cr d\lpar 0\comma\; x_2\rpar &=\nu_2 \lsqb V\lpar 0\comma\; x_2 - 1\rpar - V\lpar 0\comma\; x_2\rpar \rsqb +c_2\comma \quad\quad x_2 \geq 1.}$

The definition of the function d(x ₁, x ₂) implies that it is optimal to assign the flexible server to station 1 (resp. station 2) when d(x ₁, x ₂) > 0 (resp. d(x ₁, x ₂) ≤ 0); d(x ₁, x ₂) denotes the incentive to have the flexible server work in station 1 instead of station 2 in state (x ₁, x ₂).

Remark

We can explicitly determine d(x ₁, 0) and d(0, x ₂) using (13) and (14). We have

(18)

$d\lpar x_1\comma\; 0\rpar ={\nu_1 h_1 x_1+\nu_1 b_1 - \mu_1 c_1 \over \mu_1+\nu_1 {\bf 1}\lpar x_1 \geq X_1\rpar }\comma\;$

(19)

$\quad d\lpar 0\comma\; x_2\rpar =- {\nu_2\, h_2 x_2+\nu_2 b_2 - \mu_2 c_2 \over \mu_2+\nu_2}.$

It can be easily verified that condition (A2) yields d(0, x ₂) ≤ 0; that is, it does not pay to idle the flexible server. Also, d(x ₁, 0) ≤ 0 for x ₁ ≤ X ₁ and d(x ₁, 0) ≥ 0 for x ₁ ≥ X ₁.

Using optimality equations (15)–(17) and identities min(a, b) = b + (a − b)⁻ and min(a, b) = a − (a − b)⁺ for the first and second terms, respectively, of the differences appearing in the definition of d(x ₁, x ₂), we obtain the following recursive expressions for function d(x ₁, x ₂), x ₁, x ₂ ≥ 1:

(20)

$d\lpar x_1\comma\; x_2\rpar =f\lpar x_1\comma\; x_2\rpar +\nu_1 d\lpar x_1\comma\; x_2\rpar ^- +\nu_2 d\lpar x_1\comma\; x_2\rpar ^+\comma\;$

where

(21)

$\eqalignno{f\lpar x_1\comma\; x_2\rpar &=\nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2+\mu_1 d\lpar x_1 - 1\comma\; x_2+1\rpar +\mu_2 d\lpar x_1\comma\; x_2 - 1\rpar \cr &\quad + \nu_1 d\lpar x_1 - 1\comma\; x_2+1\rpar ^+ + \nu_2 d\lpar x_1\comma\; x_2 - 1\rpar ^- \cr &\quad + \lpar \nu_1 b_1 - \mu_1 c_1\rpar {\bf 1}\lpar x_1=1\rpar +\lpar \mu_2 c_2 - \nu_2 b_2\rpar {\bf 1}\lpar x_2=1\rpar . &}$

The expressions derived for d(x ₁, x ₂) provide an efficient way for the numerical computation of the optimal policy; starting with the values of d(x ₁, 0) and d(0, x ₂) obtained from (18) and (19), we can successively use (20) and (21) to compute d(x ₁, x ₂) for any x ₁, x ₂ ≥ 1. Furthermore, they provide the basis for proving qualitative properties of the optimal policy. Specifically, the optimal policy is characterized by a single switching curve (when the number of jobs present in the downstream station exceeds a certain threshold, it is optimal to assign the flexible server to that station), which is the main result of this section given in the following theorem.

Theorem 1

Assume conditions (A2) and (A3) are true. Then, for each x ₁ ≥ 1, there exists a positive integer t(x ₁) such that it is optimal to assign the flexible server to the downstream station only when x ₂ ≥ t(x ₁). Moreover, t(x ₁) = 1 for x ₁ ≤ X ₁, and the slope of t(x ₁) is greater than or equal to −1.

Remarks

We believe that the slope of the switching curve ia actually nonnegative and the lower bound of −1 is only the most we can prove. To verify our intuition, we used (18)–(21) to determine the optimal policy for several thousand cases, where, for each case, the parameter values were selected randomly. Not even one case exhibited a decreasing switching curve. On the other hand, condition (A3) is not just a technical condition needed for the proof. The following example illustrates that if condition (A3) is not satisfied, the existence of a single switching curve is not guaranteed.

Example

Consider a system with μ₁ = 0.2, μ₂ = 0.3, ν₁ = ν₂ = 0.25, h ₁ = 2, h ₂ = 1, b ₁ = 6, b ₂ = 10, c ₁ = 3, and c ₂ = 4. It is easy to verify that condition (A2) is satisfied, but not condition (A3). Using (18)–(21) to compute the decision function for x ₁ = 1, we get d(1, 0) = 3.1111, d(1, 1) = −0.1616, d(1, 2) = 0.0875, d(1, 3) = 0.1199, d(1, 4) = 0.0116, and d(1, 5) = −0.1529. We see that the optimal policy is switching between stations 1 and 2 three times, so it is not characterized by a single switching curve.

The proof of Theorem 1 requires the use of Lemmas 3–5, whose proofs are given in Appendix A. Lemma 2 is an auxiliary result.

Lemma 2

Assume A − B = g + λ(A ⁻ − B ⁻) + μ(A ⁺ − B ⁺) with 0 < λ< 1 and 0 < μ< 1. Then A − B and g have the same sign.

Proof

Assuming that A ≠ B, A ≤ B, and A ≥ B for g = 0, g > 0, and g < 0, respectively, we are led to contradictions.■

Lemma 3

For all x ₁ ≥ 1 and x ₂ ≥ 0,

$\hskip-145ptd\lpar x_1\comma\; x_2+1\rpar \lt d\lpar x_1\comma\; x_2\rpar .$

Lemma 4

For all x ₁ > 0,

$\hskip-165pt\mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1\comma\; x_2\rpar =- \infty.$

Lemma 5

For all x ₁, x ₂ ≥ 1,

$\hskip-60ptd\lpar x_1\comma\; x_2\rpar \gt 0 \Rightarrow d\lpar x_1\comma\; x_2\rpar \leq d\lpar x_1+1\comma\; x_2 - 1\rpar .$

Proof of Theorem 1

For x ₁ ≤ X ₁, we have d(x ₁, 0) ≤ 0, which implies that d(x ₁, x ₂) < 0 for all x ₂ ≥ 1 (Lemma 3). Therefore, t(x ₁) = 1, x ₁ ≤ X ₁. For x ₁ > X ₁, we have d(x ₁, 0) > 0, d(x ₁, x ₂) decreasing in x ₂ (Lemma 3), and d(x ₁, x ₂) < 0 for x ₂ sufficiently large (Lemma 4), so there exists an integer t(x ₁) such that d(x ₁, x ₂) ≤ 0 for x ₂ ≥ t(x ₁). Finally, by Lemma 5, we have for any x ₁, x ₂ ≥ 1,

$d\lpar x_1\comma\; x_2\rpar \gt 0 \Rightarrow d\lpar x_1+1\comma\; x_2 - 1\rpar \gt 0.$

Therefore, the slope of the switching curve t(x ₁) defined by the optimal policy is greater than or equal to −1.■

We end this section by considering systems with no dedicated capacity at the upstrean (resp. downstream) station. We show that the optimal policy assigns the flexible server to the upstream (resp. downstream) station when the reduction in holding cost rate resulting from the use of the flexible server is larger in that station.

Theorem 2

Let μ₁ = 0 and ν₁(h ₁ − h ₂) ≥ ν₂h ₂. Then it is optimal to assign the flexible server at station 1 for all x ₁ > 0.

Proof

We will show that d(x ₁, x ₂) ≥ 0 for x ₁ > 0. From (20) and (21), we have for x ₁, x ₂ ≥ 1,

$\eqalign{d\lpar x_1\comma\; x_2\rpar &=\nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2+\mu_2 d\lpar x_1\comma\; x_2 - 1\rpar \cr &\quad +\nu_1 d\lpar x_1 - 1\comma\; x_2+1\rpar ^+ + \nu_1 d\lpar x_1\comma\; x_2 - 1\rpar ^- \cr &\quad + \nu_1 b_1 {\bf 1}\lpar x_1=1\rpar +\lpar \mu_2 c_2 - \nu_2 b_2\rpar {\bf 1}\lpar x_2=1\rpar \cr &\quad +\nu_1 d\lpar x_1\comma\; x_2\rpar ^-+\nu_2 d\lpar x_1\comma\; x_2\rpar ^+.}$

We prove the result by induction on x ₂. We start the induction by noting that d(x ₁, 0) = h ₁x ₁ > 0. Then the induction step follows from condition (A3) and Lemma 2.■

Theorem 3

Let μ₂ = 0 and ν₁(h ₁ − h ₂) ≤ ν₂h ₂. Then it is optimal to assign the flexible server at station 2 for all x ₂ > 0.

Proof

We show d(x ₁, x ₂) ≤ 0 for x ₂ > 0 by induction on x ₁. We have d(0, x ₂) = −h ₂x ₂ < 0, and for x ₁, x ₂ ≥ 1,

$\eqalign{d\lpar x_1\comma\; x_2\rpar &=\nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2+\mu_1 d\lpar x_1 - 1\comma\; x_2+1\rpar \cr &\quad +\nu_1 d\lpar x_1 - 1\comma\; x_2+1\rpar ^++ \nu_2 d\lpar x_1\comma\; x_2 - 1\rpar ^- \cr &\quad +\lpar \nu_1 b_1 - \mu_1 c_1\rpar {\bf 1}\lpar x_1=1\rpar - \nu_2 b_2 {\bf 1}\lpar x_2=1\rpar \cr &\quad +\nu_1 d\lpar x_1\comma\; x_2\rpar ^-+\nu_2 d\lpar x_1\comma\; x_2\rpar ^+.}$

The result is proven by the induction hypothesis, condition (A3), and Lemma 2. ■

3. SYSTEMS WITH ARRIVALS

In this section we consider the previous model with Poisson arrivals of rate λ. We assume that condition (A1) holds and there are no operating costs for the dedicated servers (b ₁ = b ₂ = 0). Let β, 0 ≤ β ≤ 1, be a discount factor. We define by V _n,β^θ (x ₁, x ₂) and V _β^θ(x ₁, x ₂) the expected n-step discounted cost and the expected infinite horizon discounted cost, respectively, under policy θ starting at state (x ₁, x ₂). We also define the expected average cost under θ by

$J^\theta \lpar x_1\comma\; x_2\rpar =\mathop{\lim\sup}\limits_{n \to \infty} {V_{n\comma 1}^\theta \lpar x_1\comma\; x_2\rpar \over n}.$

Our objective is to characterize an allocation strategy for the flexible servers that minimizes the expected average cost. We were not able to do so for the general model with dedicated servers in both stations, but for special cases with a dedicated server in one of the two stations.

Assuming that the uniformization rate is λ + μ₁ + μ₂ + ν₁ + ν₂ = 1, we obtain optimality equations (22)–(24) for the three aforementioned problems. In deriving these equations we have taken into account condition (A1), under which the optimal policy prescribes the same action for all flexible servers, either idling them or assigning them to the same station (the proof is along the lines of that of Proposition 1).

(22)

$V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar =h_1 x_1+h_2 x_2+T_\beta V_{n - 1\comma \beta} \lpar x_1\comma\; x_2\rpar$

(23)

$V_\beta \lpar x_1\comma\; x_2\rpar =h_1 x_1+h_2 x_2+T_\beta V_\beta \lpar x_1\comma\; x_2\rpar$

(24)

$J+w\lpar x_1\comma\; x_2\rpar =h_1 x_1+h_2 x_2+T_1 w\lpar x_1\comma\; x_2\rpar \comma\;$

where the operator T _β is defined by

(25)

$\eqalignno{T_\beta V\lpar x_1\comma\; x_2\rpar &=\beta \lsqb \lambda V\lpar x_1+1\comma\; x_2\rpar +\mu_1 V\lpar x_1 - 1\comma\; x_2+1\rpar \cr &\quad +\mu_2 V\lpar x_1\comma\; x_2 - 1\rpar \rsqb \cr &\quad + \min \!\! \lcub \beta \lpar \nu_1+\nu_2\rpar V\lpar x_1\comma\; x_2\rpar \comma\; \cr &\qquad\qquad c_1 +\beta \lsqb \nu_1 V\lpar x_1 - 1\comma\ x_2 +1\rpar +\nu_2 V\lpar x_1\comma\; x_2\rpar \rsqb \comma\; \cr &\qquad\qquad\quad c_2+\beta \lsqb \nu_2 V\lpar x_1\comma\; x_2 - 1\rpar +\nu_1 V\lpar x_1\comma\; x_2\rpar \rsqb \rcub \comma &}$

(26)

$\eqalignno{T_\beta V\lpar x_1\comma\; 0\rpar &=\beta \lsqb \lambda V\lpar x_1+1\comma\; 0\rpar +\mu_1 V\lpar x_1 - 1\comma\; 1\rpar +\mu_2 V\lpar x_1\comma\; 0\rpar \rsqb \cr &\quad + \min \!\!\lcub \beta \lpar \nu_1+\nu_2\rpar V\lpar x_1\comma\; 0\rpar \comma \,\cr &\qquad\qquad c_1+\beta \lsqb \nu_1 V\lpar x_1 - 1\comma\; 1\rpar +\nu_2 V\lpar x_1\comma\; 0\rpar \rsqb \rcub \comma &}$

(27)

$\eqalignno{T_\beta V\lpar 0\comma\; x_2\rpar &=\beta \lsqb \lambda V\lpar 1\comma\; x_2\rpar +\mu_2 V\lpar 0\comma\; x_2 - 1\rpar +\mu_1 V\lpar 0\comma\; x_2\rpar \rsqb \cr &\quad + \min\!\! \lcub \beta \lpar \nu_1+\nu_2\rpar V\lpar 0\comma\; x_2\rpar \comma\;\cr &\qquad\qquad c_2+\beta \lsqb \nu_2 V\lpar 0\comma\; x_2 - 1\rpar +\nu_1 V\lpar 0\comma\; x_2\rpar \rsqb \rcub \comma & }$

(28)

$T_\beta V\lpar 0\comma\; 0\rpar =\beta \lsqb \lambda V\lpar 1\comma\; 0\rpar +\lpar \mu_1+\mu_2+\nu_1+\nu_2\rpar V\lpar 0\comma\; 0\rpar \rsqb .$

The solution of (22) gives the minimum expected n-step discounted cost (with V _0,β(x ₁, x ₂) = 0), whereas the solution of (23), if it exists, gives the minimum infinite horizon discounted cost. Finally, if a solution (J, w) of (24) exists and π is the policy that attains the minimum on its right-hand side, π is the optimal policy and J is the minimum average cost satisfying

$J=\mathop{\inf \limits_\theta} J^\theta \lpar x_1\comma\; x_2\rpar =J^\pi \lpar x_1\comma\; x_2\rpar \qquad \hbox{for all} \; x_1 \; \hbox{and} \; x_2.$

Propositions 3 and 4 make statements about the existence of solutions to (23) and (24), respectively, and their properties. For the proofs, we refer readers to Wu et al. [Reference Wu, Down and Lewis25], where analogous results are proven for the problem with holding costs and unreliable servers. The same arguments remain valid for our problem because linear operating costs make a finite contribution to the infinite horizon discounted cost and the average cost.

Proposition 3

For 0 < β < 1, ( 23) has a unique solution given by

$V_\beta \lpar x_1\comma\; x_2\rpar =\mathop{\lim\limits_{n \to \infty}} V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar .$

We define the maximal throughput Λ as the largest value of the arrival rate that is less than or equal to the average service rate at each station. The maximal throughput can be obtained from the solution of the linear program

$\matrix{\max &\Lambda \hfill \cr \hbox{s.t.} &\Lambda \leq \mu_i+\nu_i \delta_i\comma\; i=1\comma\; 2\comma\; \cr &\delta_1+\delta_2 \leq 1\comma\; \hfill \cr &\delta_1\comma\; \delta_2 \geq 0\comma \hfill }$

where δ₁ and δ₂ are the proportions of time the flexible server is assigned to the upstream and downstream station, respectively. It is straightforward to show that

$\Lambda= \left\{\matrix{\mu_1+\nu_1\hfill\qquad\qquad\qquad\qquad\hbox{if} \; \mu_1+\nu_1 \leq \mu_2\hfill\cr \mu_2+\nu_2\hfill \qquad\qquad\qquad\qquad\hbox{if} \; \mu_2+\nu_2 \leq \mu_1\hfill\cr \displaystyle{\mu_1 \nu_2+\nu_1 \mu_2+\nu_1 \nu_2 \over \nu_1+\nu_2} \hfill \ \hskip0.7pt \hbox{otherwise}.\hfill}\right.$

Proposition 4

For λ < Λ ( 24) has a solution (J, w), where J is given by lim_n→∞V _n,1 (x ₁, x ₂)/n. Moreover, for a fixed state (x ₁^*, x ₂^*), there exists a sequence β_l → 1 for which

$\mathop{\lim\limits_{l \to \infty}} \lsqb V_{\beta_l} \lpar x_1\comma\; x_2\rpar - V_{\beta_l} \lpar x^{\ast}_1\comma\; x_2^{\ast}\rpar \rsqb =w\lpar x_1\comma\; x_2\rpar .$

We prove that when the reduction in holding cost rate resulting from using the flexible server in the downstream station is larger than the corresponding operating cost, idling the flexible server is not optimal when there are jobs present there.

Proposition 5

Assume ν₂h ₂ > c ₂. Then idling the flexible server is not optimal for x ₂ > 0.

Proof

We start by showing that for β sufficiently close to 1, the result is true for the finite horizon problem, except for n = 1, in which case, idling the flexible server is optimal because there is nothing to be gained in terms of potential holding costs savings. In particular, we will show that the policy that assigns the flexible server to station 2 has no more cost than the one that idles the server, which by (25) and (27) implies that for n ≥ 1,

(29)

$\beta \nu_2 \lsqb V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar - V_{n\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar \rsqb \geq c_2.$

A sufficient condition for (29) to be true is

(30)

$V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar - V_{n\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar \geq h_2\comma\;$

because then (29) would be satisfied for β ≥ c ₂/ν₂h ₂. We prove (30) by induction on n. For n = 1, it is satisfied with equality. For n > 1, we have from (22),

$\eqalign{V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar &- V_{n\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar =h_2+T_\beta V_{n - 1\comma \beta} \lpar x_1\comma\; x_2\rpar \cr & - T_\beta V_{n - 1\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar .}$

Using (25)–(28) and the induction hypothesis, we get by a straightforward term-by-term comparison that T _βV _n−1,β(x ₁, x ₂) ≥ T _βV _n−1,β(x ₁, x ₂ − 1), which completes the induction. Letting n → ∞ in (29) and applying Proposition 3, we obtain for β ≥ c ₂/ν₂h ₂,

(31)

$\beta \nu_2 \lsqb V_\beta \lpar x_1\comma\; x_2\rpar - V_\beta \lpar x_1\comma\; x_2 - 1\rpar \rsqb \geq c_2.$

Applying now Proposition 4 to (31), we get

$\nu_2 \lsqb w\lpar x_1\comma\; x_2\rpar - w\lpar x_1\comma\; x_2 - 1\rpar \rsqb \geq c_2\comma$

which by (24), (25), and (27) proves the result for the average cost problem.■

To further characterize the policy that minimizes the average cost, we determine properties of the optimal policy for the finite horizon problem and then use Propositions 3 and 4 to show that the same properties are valid under the average cost criterion. We define decision function d _n,β(x ₁, x ₂) as in the previous section for clearing systems:

$\eqalign{d_{n\comma \beta} \lpar x_1\comma\; x_2\rpar &=c_2 - c_1+\beta \lcub \nu_2 \lsqb V_{n\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar - V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar \rsqb + \nu_1 \lsqb V_{n\comma \beta} \lpar x_1\comma\; x_2\rpar \cr &\qquad\qquad\qquad - V_{n\comma \beta} \lpar x_1 - 1\comma \ x_2+1\rpar \rsqb \rcub \comma\; \quad\quad x_1\comma\; x_2 \geq 1\comma \cr d_{n\comma \beta} \lpar x_1\comma\; 0\rpar &=\beta \nu_1 \lsqb V_{n\comma \beta} \lpar x_1\comma\; 0\rpar - V_{n\comma \beta} \lpar x_1 - 1\comma\; 1\rpar \rsqb - c_1\comma \quad\quad x_1 \geq 1\comma \cr d_{n\comma \beta} \lpar 0\comma\; x_2\rpar &=\beta \nu_2 \lsqb V_{n\comma \beta} \lpar 0\comma\; x_2 - 1\rpar - V_{n\comma \beta} \lpar 0\comma\; x_2\rpar \rsqb +c_2, \quad\quad x_2 \geq 1.}$

Under the assumption of Proposition 5, d _n,β(x ₁, x ₂), n ≥ 1, determines the optimal policy at stage n + 1; the flexible server is assigned to the upstream station if d _n,β(x ₁, x ₂) ≥ 0, and downstream otherwise. The following three lemmas characterize that optimal policy for large values of the discount factor when there is no dedicated capacity in one of the two stations. Their proofs can be found in Appendix B.

Lemma 6

Let μ₁ = 0, c ₂ < ν₂h ₂, and β ≥ β₁, where

$\matrix{&\beta_1 =\max \left\{\displaystyle{c_2 \over \nu_2 h_2}\comma\; {2c_1 - c_2 \over \nu_2 h_2 - \lpar \nu_1+\mu_2\rpar c_2+2c_1 - c_2}\right\} \quad if \, 2c_1\gt c_2{\it \comma} \cr &\beta_1 =\displaystyle{c_2 \over \nu_2 h_2}{\it \comma} \quad otherwise.\hfill}$

Then for n ≥ 1, x ₁ ≥ 1, and x ₂ ≥ 0,

$d_{n\comma \beta} \lpar x_1\comma\; x_2+1\rpar \leq d_{n\comma \beta} \lpar x_1\comma\; x_2\rpar .$

Lemma 7

Let μ₁ = 0, c ₁ ≤ c ₂ < ν₂h ₂ < ν₁(h ₁ − h ₂), and β ≥ β₂, where

$\beta_2=\max \left\{{c_2 \over \nu_2 h_2}\comma\; {c_2 - c_1 \over \nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2+c_2 - c_1}\right\}.$

Then for n ≥ 1, x ₁ ≥ 1, and x ₂ ≥ 0,

$d_{n\comma \beta} \lpar x_1\comma\; x_2\rpar \geq 0.$

Lemma 8

Let μ₂ = 0, c ₂ < ν₂h ₂, c ₂ ≤ c ₁, ν₁(h ₁ − h ₂) < ν₂h ₂, and β ≥ β₃, where

$\beta_3=\max \left\{{c_2 \over \nu_2 h_2}\comma\; {c_1 - c_2 \over \nu_2 h_2 - \nu_1 \lpar h_1 - h_2\rpar +c_1 - c_2}\right\}.$

Then for n ≥ 1, x ₁ ≥ 0, and x ₂ ≥ 1,

$d_{n\comma \beta} \lpar x_1\comma\; x_2\rpar \leq 0.$

When there is no dedicated server in station 1, Lemma 6 implies that the gain from having the flexible server work at station 1 is nonincreasing in the number of jobs in station 2. According to Lemma 7, it is always optimal to assign the flexible server at station 1 if the operating cost is smaller and the reduction in holding cost rate is larger in that station. By reversing these conditions, we show in Lemma 8 that the optimal policy always assigns the flexible server at station 2. Theorems 4–6 are the counterparts of Lemmas 6–8 for the average cost criterion.

Theorem 4

If μ₁ = 0 and c ₂ < ν₂h ₂, the incentive to use the flexible server at station 1 does not increase as the number of jobs in station 2 increases.

Proof

Applying successively Propositions 3 and 4 to the result of Lemma 6, we get

$\eqalign{c_2+\nu_2 \lsqb w\lpar x_1\comma\; 0\rpar &- w\lpar x_1\comma\; 1\rpar \rsqb +\nu_1 \lsqb w\lpar x_1\comma\; 1\rpar - w\lpar x_1 - 1\comma\; 2\rpar \rsqb \cr &\quad \leq \nu_1 \lsqb w\lpar x_1\comma\; 0\rpar - w\lpar x_1 - 1\comma\; 1\rpar \rsqb \comma }$

and for x ₂ ≥ 1,

$\eqalign{\nu_2 \lsqb w\lpar x_1\comma\; x_2\rpar &- w\lpar x_1\comma\; x_2+1\rpar \rsqb +\nu_1 \lsqb w\lpar x_1\comma\; x_2+1\rpar - w\lpar x_1 - 1\comma\; x_2+2\rpar \rsqb \cr &\quad \le \nu_2 \lsqb w\lpar x_1\comma\; x_2 - 1\rpar - w\lpar x_1\comma\; x_2\rpar \rsqb +\nu_1 \lsqb w\lpar x_1\comma\; x_2\rpar \cr &\quad - w\lpar x_1 - 1\comma\; x_2+1\rpar \rsqb \comma }$

which in view of (Reference Weichbold and Schiefermayr24)–(Reference Wu, Lewis and Veatch26) proves the statement of the theorem.■

Theorem 5

If μ₁ = 0 and c ₁ ≤ c ₂ < ν₂h ₂ < ν₁(h ₁ − h ₂), the optimal policy gives priority to the upstream station.

Theorem 6

If μ₂ = 0 and c ₂ < ν₂h ₂, c ₂ ≤ c ₁, ν₁(h ₁ − h ₂) < ν₂h ₂, the optimal policy gives priority to the downstream station.

The proofs of Theorems 5 and 6 are based on Lemmas 7 and 8, respectively, and are derived by identical arguments to that of Theorem 4.

4. DISCUSSION

We considered scheduling a number of flexible servers in a two-stage tandem queuing system with dedicated servers at each stage, where operating costs are incurred by the servers during the time they work. Assuming a collaborative work discipline and exponential service times, we showed that when operating cost rates due to flexible servers are proportional to their speeds, we get an equivalent problem with one flexible server. Furthermore, we identified conditions on holding costs, operating costs, and service times (see Propositions 2 and 5) under which there exist optimal nonidling policies for the flexible server when there are jobs in station 2. The analysis in the article focused on deriving properties of the optimal policy when the conditions that ensure the optimality of nonidling policies are satisfied.

For clearing systems, we showed that under condition (A2), allocating the flexible server to the downstream station becomes optimal as the number of jobs there increases. Moreover, the slope of the switching curve defined by the optimal policy is greater than or equal to −1. When condition (A2) is not satisfied, in which case idling is optimal for certain states of the problem, we have not been able to derive any structural properties of the optimal policy. Recall that when there are no jobs present in station 1 or 2, idling the flexible server is optimal when x ₂ < X ₂ and x ₁ < X ₁, respectively, where X ₁ and X ₂ have been defined in Section 2. We conjecture that when x ₂ ≥ X ₂, idling is not optimal for any number of jobs in station 1. We believe this is true for the following reason. If idling is not optimal when station 1 is empty, there must be no issue with high operating costs in station 2, which is a fact independent of jobs present in station 1. The reverse is not true, that is, when x ₁ ≥ X ₁, idling might be optimal when there are jobs in station 2. This is the case when holding and operating costs in station 2 are so large that it would not be beneficial to send jobs to station 2 (a process that would be facilitated by the use of the flexible server in station 1) or have the flexible server work in station 2.

For systems with arrivals, we showed the optimality of nonidling policies when the reduction in holding cost rate is larger than the operating cost in station 2. Moreover, we showed that the transition-monotonicity property of the optimal policy for clearing systems remains valid when there is no dedicated capacity in the upstream station. It is not clear whether or under what conditions this property holds for the general model as well. However, some numerical experimentation with the finite horizon problem seems to indicate that this might be the case.

APPENDIX A

PROOFS OF LEMMAS 1 AND 3–5

Proof of Lemma 1

Let V ^π_i(x ₁, x ₂), i = 0, 1, 2, be the expected cost of a policy that at state (x ₁, x ₂) idles the extra server, assigns it to station 1, or assigns it to station 2, respectively, and proceeds optimally after the first service completion. Therefore,

(A.1)

$\eqalignno{&V\lpar x_1\comma\; x_2\rpar - V\lpar x_1\comma\; x_2 - 1\rpar =\mathop{\min\limits_{i=0\comma\; 1\comma\; 2}} \lcub V^{\pi_i} \lpar x_1\comma\; x_2\rpar - V\lpar x_1\comma\; x_2 - 1\rpar \rcub \comma\; \cr &V\lpar x_1\comma\; x_2 - 1\rpar \leq V^{\pi_i } \lpar x_1\comma\; x_2 - 1\rpar \comma }$

implying that

(A.2)

$V\lpar x_1\comma\; x_2\rpar - V\lpar x_1\comma\; x_2 - 1\rpar \geq \mathop{\min\limits_{i=0\comma\; 1\comma\; 2}} \lcub V^{\pi_i} \lpar x_1\comma\; x_2\rpar - V^{\pi_i} \lpar x_1\comma\; x_2 - 1\rpar \rcub.$

For x ₁, x ₂ ≥ 1, by conditioning on the time of the first service completion, we derive the following expressions:

(A.3a)

$\eqalignno{V^{\pi_0} \lpar x_1\comma\; x_2\rpar &={h_1 x_1+h_2 x_2+b_1+b_2 \over \mu_1+\mu_2}+V\lpar x_1 - 1\comma\; x_2+1\rpar {\mu_1 \over \mu_1+\mu_2} \cr &\quad + V\lpar x_1\comma\; x_2 - 1\rpar {\mu_2 \over \mu_1+\mu_2}\comma}$

(A.3b)

$\eqalignno{V^{\pi_1} \lpar x_1\comma\; x_2\rpar &={h_1 x_1+h_2 x_2+b_1+b_2+c_1 \over \mu_1+\mu_2+\nu_1} +V\lpar x_1 - 1\comma\; x_2+1\rpar {\mu_1+\nu_1 \over \mu_1+\mu_2+\nu_1} \cr &\quad + V\lpar x_1\comma\; x_2 - 1\rpar {\mu_2 \over \mu_1+\mu_2+\nu_1}\comma\;}$

(A.3c)

$\eqalignno{V^{\pi_2} \lpar x_1\comma\; x_2\rpar &={h_1 x_1+h_2 x_2+b_1+b_2+c_2 \over \mu_1+\mu_2+\nu_2} +V\lpar x_1 - 1\comma\; x_2+1\rpar {\mu_1 \over \mu_1+\mu_2+\nu_2} \cr &\quad + V\lpar x_1\comma\; x_2 - 1\rpar {\mu_2+\nu_2 \over \mu_1+\mu_2+\nu_2}.}$

We will show that

(A.4)

$V^{\pi_i} \lpar x_1\comma\; 1\rpar - V\lpar x_1\comma\; 0\rpar \geq {h_2+b_2+c_2 \over \mu_2+\nu_2}\comma \enspace i=0\comma\; 1\comma\; 2\comma\;$

(A.5)

$V^{\pi_i} \lpar x_1\comma\; x_2\rpar - V^{\pi_i} \lpar x_1\comma\; x_2 - 1\rpar \geq {h_2 x_2+b_2+c_2 \over \mu_2+\nu_2}\comma\; \enspace i=0\comma\; 1\comma\; 2\comma\; x_2\gt 1\comma$

which by (A.1) and (A.2) suffice to prove the statement of the lemma. From (A.3a)–(A.3c), we have

(A.6a)

$V^{\pi_0} \lpar x_1\comma\; 1\rpar - V\lpar x_1\comma\; 0\rpar ={h_1 x_1+h_2+b_1+b_2 \over \mu_1+\mu_2} +\lsqb V\lpar x_1 - 1\comma\; 2\rpar - V\lpar x_1\comma\; 0\rpar \rsqb {\mu_1 \over \mu_1+\mu_2}\comma$

(A.6b)

$\eqalignno{V^{\pi_1} \lpar x_1\comma\; 1\rpar &- V\lpar x_1\comma\; 0\rpar ={h_1 x_1+h_2+b_1+b_2+c_1 \over \mu_1+\mu_2+\nu_1}\cr &\quad +\lsqb V\lpar x_1 - 1\comma\; 2\rpar - V\lpar x_1\comma\; 0\rpar \rsqb {\mu_1+\nu_1 \over \mu_1+\mu_2+\nu_1}\comma}$

(A.6c)

$\eqalignno{V^{\pi_2} \lpar x_1\comma\; 1\rpar &- V\lpar x_1\comma\; 0\rpar ={h_1 x_1+h_2+b_1+b_2+c_2 \over \mu_1+\mu_2+\nu_2}\cr &\quad +\lsqb V\lpar x_1 - 1\comma\; 2\rpar - V\lpar x_1\comma\; 0\rpar \rsqb {\mu_1 \over \mu_1+\mu_2+\nu_2}\comma}$

and for x ₂ > 1,

(A.7a)

$\eqalignno{V^{\pi_0} \lpar x_1\comma\; x_2\rpar - V^{\pi_0} \lpar x_1\comma\; x_2 - 1\rpar &={h_2 \over \mu_1+\mu_2}+\lsqb V\lpar x_1 - 1\comma\; x_2+1\rpar - V\lpar x_1 - 1\comma\; x_2\rpar \rsqb {\mu_1 \over \mu_1+\mu_2}\cr &\quad + \lsqb V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2 - 2\rpar \rsqb {\mu_2 \over \mu_1+\mu_2}\comma}$

(A.7b)

$\eqalignno{V^{\pi_1} \lpar x_1\comma\; x_2\rpar - V^{\pi_1} \lpar x_1\comma\; x_2 - 1\rpar &={h_2 \over \mu_1+\mu_2+\nu_1} +\lsqb V\lpar x_1 - 1\comma\; x_2+1\rpar \cr &\quad - V\lpar x_1 - 1\comma\; x_2\rpar \rsqb {\mu_1+\nu_1 \over \mu_1+\mu_2+\nu_1} + \lsqb V\lpar x_1\comma\; x_2 - 1\rpar\cr &\quad - V\lpar x_1\comma\; x_2 - 2\rpar \rsqb {\mu_2 \over \mu_1+\mu_2+\nu_1}\comma}$

(A.7c)

$\eqalignno{V^{\pi_2} \lpar x_1\comma\; x_2\rpar - V^{\pi_2 } \lpar x_1\comma\; x_2 - 1\rpar &={h_2 \over \mu_1+\mu_2+\nu_2} +\lsqb V\lpar x_1 - 1\comma\; x_2+1\rpar \cr &\quad - V\lpar x_1 - 1\comma\; x_2\rpar \rsqb {\mu_1 \over \mu_1+\mu_2+\nu_2} + \lsqb V\lpar x_1\comma\; x_2 - 1\rpar\cr &\quad - V\lpar x_1\comma\; x_2 - 2\rpar \rsqb {\mu_2+\nu_2 \over \mu_1+\mu_2+\nu_2}.}$

The proof of (A.4) and (A.5) is by means of induction on x ₁ and x ₂. First, we prove (A.4) for x ₁ = 1. From (13) and (14) and condition (A2), we get

(A.8a)

$\eqalignno{&V\lpar 0\comma\; 2\rpar - V\lpar 1\comma\; 0\rpar ={2 h_2+b_2+c_2 \over \mu_2+\nu_2} - \min \left\{{h_1+b_1 \over \mu_1}\comma\; {h_1+b_1+c_1 \over \mu_1+\nu_1}\right\}\Rightarrow \cr &V\lpar 0\comma\; 2\rpar - V\lpar 1\comma\; 0\rpar \geq {2 h_2+b_2+c_2 \over \mu_2+\nu_2} - {h_1+b_1 \over \mu_1}\comma}$

(A.8b)

$V\lpar 0\comma\; 2\rpar - V\lpar 1\comma\; 0\rpar \geq {2 h_2+b_2+c_2 \over \mu_2+\nu_2} - {h_1+b_1+c_1 \over \mu_1+\nu_1}.$

Substituting (A.8a) into (A.6a) and (A.6c), (A.8b) into (A.6b), and taking into account condition (A2) yields the result. To prove (A.5) for x ₁ = 1, we use induction on x ₂. From (14) and condition (A2), we get

(A.9)

$V\lpar 0\comma\; x_2+1\rpar - V\lpar 0\comma\; x_2\rpar ={h_2 \lpar x_2+1\rpar +b_2+c_2 \over \mu_2+\nu_2}.$

Applying the induction hypothesis (with the induction base, x ₂ = 2, having been established by the fact that the statement of the lemma has been proven to hold for x ₁ = x ₂ = 1) we also get

(A.10)

${V\lpar 1\comma\; x_2 - 1\rpar - V\lpar 1\comma\; x_2 - 2\rpar \geq {h_2 \lpar x_2 - 1\rpar +b_2+c_2 \over \mu_2+\nu_2}.}$

Then the result follows from (A.7a)–(A.7c), (A.9), and (A.10). Next we prove (A.4) and (A.5) for x ₁ > 1 by induction on x ₁. Starting with (A.4), we have from (13),

$\eqalign{V\lpar x_1 - 1\comma\; 2\rpar &- V\lpar x_1\comma\; 0\rpar =V\lpar x_1 - 1\comma\; 2\rpar \cr & \quad - \min \left\{{h_1 x_1+b_1 \over \mu_1}\comma\; {h_1 x_1+b_1+c_1 \over \mu_1+\nu_1}\right\}- V\lpar x_1 - 1\comma\; 1\rpar \cr &\quad \ge {2 h_2+b_2+c_2 \over \mu_2+\nu_2} - \min \left\{{h_1 x_1+b_1 \over \mu_1}\comma\; {h_1 x_1+b_1+c_1 \over \mu_1+\nu_1}\right\}\cr &\quad \Rightarrow V\lpar x_1 - 1\comma\; 2\rpar - V\lpar x_1\comma\; 0\rpar \geq {2 h_2+b_2+c_2 \over \mu_2+\nu_2} - {h_1 x_1+b_1 \over \mu_1}\comma \cr V\lpar x_1 - 1\comma\; 2\rpar &- V\lpar x_1\comma\; 0\rpar \geq {2 h_2+b_2+c_2 \over \mu_2+\nu_2} - {h_1 x_1+b_1+c_1 \over \mu_1+\nu_1}\comma }$

where the first inequality is a result of the induction hypothesis. The rest of the proof is identical to the one for x ₁ = 1 with h ₁ replaced by h ₁x ₁. Finally, we prove (A.5) by induction on x ₂. Applying the induction hypothesis, we get

$\eqalign{&V\lpar x_1 - 1\comma\; x_2+1\rpar - V\lpar x_1 - 1\comma\; x_2\rpar \geq {h_2 \lpar x_2+1\rpar +b_2+c_2 \over \mu_2+\nu_2}\comma \cr &V\lpar x_1\comma\; x_2 - 1\rpar - V\lpar x_1\comma\; x_2 - 2\rpar \geq {h_2 \lpar x_2 - 1\rpar +b_2+c_2 \over \mu_2+\nu_2}\comma }$

so the proof is essentially identical to the proof for x ₁ = 1.■

Proof of Lemma 3

The proof is by induction on x ₁. First, we prove the result for x ₁ = 1 by induction on x ₂. We establish the induction base by showing that d(1, 1) < d(1, 0).

Case 1

X ₁ > 1⇒d(1, 0) < 0.

From (21) and (18), we get

(A.11)

$\eqalign{f\lpar 1\comma\; 1\rpar &=-\nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar +\lpar \mu_1+\mu_2+\nu_2\rpar d\lpar 1\comma\; 0\rpar \cr &\quad +\mu_1 d\lpar 0\comma\; 2\rpar \lt 0\comma}$

because of condition (A2) and d(0, 2) < 0. Because f(1, 1) < 0, we get from (20) and Lemma 2 that d(1, 1) < 0, so by (20) and (A.11),

$d\lpar 1\comma\; 1\rpar ={f\lpar 1\comma \, 1\rpar \over 1 - \nu_1}={-\nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar +\mu_1 d\lpar 0\comma\; 2\rpar \over 1 - \nu_1} +d\lpar 1\comma\; 0\rpar \lt d\lpar 1\comma\; 0\rpar \comma$

where the inequality follows from condition (A2) and d(0, 2) < 0.

Case 2

X ₁ ≤ 1⇒d(1, 0) ≥ 0.

From (21) and (18), we get

(A.12)

$f\lpar 1\comma\; 1\rpar =- \nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar +\lpar \mu_1+\nu_1+\mu_2\rpar d\lpar 1\comma\; 0\rpar +\mu_1 d\lpar 0\comma\; 2\rpar$

The result is trivially true when f(1, 1) < 0 because in this case (20) and Lemma 2 imply that d(1, 1) < 0. In the case f(1, 1) ≥ 0, we get from (20) and Lemma 2 that d(1, 1) ≥ 0, which by (20) and (A.12) yields

$d\lpar 1\comma\; 1\rpar\, =\,\, {f\lpar 1\comma\; 1\rpar \over 1 - \nu_2}\,=\,{-\nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar +\mu_1 d\lpar 0\comma\; 2\rpar \over 1 - \nu_2} +d\lpar 1\comma\; 0\rpar \lt d\lpar 1\comma\; 0\rpar$

because of condition (A2) and d(0, 2) < 0.

The induction on x ₂ is completed by proving that the result holds for x ₂ = l + 1 provided that it holds for x ₂ = l. We have

(A.13)

$\eqalign{d\lpar 1\comma\; l+1\rpar - d\lpar 1\comma\; l+2\rpar &=f\lpar 1 \comma\; l+1\rpar - f\lpar 1\comma \;l+2\rpar + \nu_1 \lsqb d\lpar 1\comma\; l+1\rpar ^- \cr &\quad - d\lpar 1\comma\; l+2\rpar ^- \rsqb +\nu_2 \lsqb d\lpar 1\comma\; l+1\rpar ^+ - d\lpar 1\comma\; l+2\rpar ^+\rsqb .}$

Using the induction hypothesis, the fact that d(0, x ₂) is decreasing in x ₂ [(19)] and condition (A3), we get f(1, l + 1) − f(1, l + 2) > 0. Therefore, the result for x ₂ = l + 1 follows from (A.13) and Lemma 2. Next, we show that the result is true for x ₁ = k + 1 under the assumption that it is true for x ₁ = k and any x ₂. Again, we use induction on x ₂. To prove that d(k + 1, 1) < d(k + 1, 0), we consider two cases.

Case 1

k + 1 < X ₁⇒d(k + 1, 0) < 0, d(k, 0) < 0.

From (18) and the induction hypothesis, we have

(A.14)

$\nu_1 h_1=\lsqb d\lpar k+1\comma\; 0\rpar - d\lpar k\comma\; 0\rpar \rsqb \mu_1\comma\;$

(A.15)

$d\lpar k\comma\; 2\rpar \lt d\lpar k\comma\; 0\rpar \lt 0\comma\;$

respectively. Plugging (A.14) and (A.15) into (21), we get

(A.16)

$\eqalign{f\lpar k+1\comma\; 1\rpar &=- \nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar \cr &\quad + \lpar \mu_1+\mu_2+\nu_2\rpar d\lpar k+1\comma\; 0\rpar +\mu_1 \lsqb d\lpar k\comma\; 2\rpar - d\lpar k\comma\; 0\rpar \rsqb \lt 0\comma }$

because of condition (A2) and (A.15). Because f(k + 1, 1) < 0, we get from (20) and Lemma 2 that d(k + 1, 1) < 0, so from (20) and (A.16),

$\eqalign{d\lpar k+1\comma \ 1\rpar &={f\lpar k+1\comma\; 1\rpar \over 1 - \nu_1}\cr & ={ - \nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar +\mu_1 \lsqb d\lpar k\comma \ 2\rpar - d\lpar k\comma \ 0\rpar \rsqb \over 1 - \nu_1}\cr &\quad +d\lpar k+1\comma\; 0\rpar \lt d\lpar k+1\comma\; 0\rpar \comma }$

where the inequality follows from condition (A2) and (A.15).

Case 2

k + 1 ≥ X ₁⇒d(k + 1, 0) ≥ 0.

To prove that d(k + 1, 1) < d(k + 1, 0), we restrict attention to the case f(k + 1, 1) ≥ 0 as the case f(k + 1, 1) < 0 is trivial (f(k + 1, 1) < 0⇒d(k + 1, 1) < 0 ≤ d(k + 1, 0)). For f(k + 1, 1) ≥ 0, we have d(k + 1, 1) ≥ 0, and by (20),

(A.17)

$d\lpar k+1\comma\; 1\rpar ={f\lpar k+1\comma\; 1\rpar \over 1 - \nu_2}.$

In the case d(k, 0) ≥ 0, (18) yields

$\nu_1 h_1=\lsqb d\lpar k+1\comma\; 0\rpar - d\lpar k\comma\; 0\rpar \rsqb \lpar \mu_1+\nu_1\rpar.$

When d(k, 0) < 0, we have

(A.18a)

$\nu_1 h_1 = d\lpar k+1\comma\; 0\rpar \lpar \mu_1+\nu_1\rpar - d\lpar k\comma\; 0\rpar \mu_1.$

Then, we get from (A.17), (21), and (A.18a) and (A.18b)

$d\lpar k+1\comma\; 1\rpar = {\tilde{f}\lpar k+1\comma\; 1\rpar \over 1 - \nu_2}+d\lpar k+1\comma\; 0\rpar \comma$

where

$\eqalign{\tilde{f}\lpar k+1\comma\; 1\rpar &=- \nu_1 h_2 - \lpar \nu_2 h_2+\nu_2 b_2 - \mu_2 c_2\rpar +\mu_1 \lsqb d\lpar k\comma\; 2\rpar - d\lpar k\comma\; 0\rpar \rsqb \cr &\quad +\nu_1 \lsqb d\lpar k\comma\; 2\rpar ^+- d\lpar k\comma\; 0\rpar \rsqb {\bf1}\lpar d \lpar k \comma\ 0\rpar \ge0 \rpar .}$

The result follows from f˜(k + 1, 1) < 0, which is true because of condition (A2) and the induction hypothesis for x ₁(d(k, 2) < d(k, 0)). Finally, to prove the result for x ₂ = l + 1 assuming it is true for x ₂ = l, we obtain an equation analogous to (A.13) and use the induction hypotheses for x ₁ = k, x ₂ = l, and condition (A3).■

Proof of Lemma 4

The proof is by induction on x ₁. We begin by noting that lim_{x ₂}_→ ∞d (0, x ₂) = −∞ (see (19)). To complete the induction, we need to show that the result is true for x ₁ = x ₁^* under the assumption that it is true for x ₁ < x ₁^*.

Case 1

x ₁^* < X ₁⇒d(x ₁^*, 0) < 0, d(x ₁^* − 1, 0) < 0.

Because d(x ₁, x ₂) is a decreasing sequence in x ₂ (Lemma 3), we have d(x ₁^*, x ₂) < 0 and d(x ₁^* − 1, x ₂) < 0 for any x ₂, so (20) and (21) yield

$\eqalign{d\lpar x_1^{\ast}\comma\; x_2\rpar &=\nu_1 h_1 - \lpar \nu_1+\nu_2\rpar h_2+\mu_1 d\lpar x_1^{\ast} - 1\comma\; x_2+1\rpar +\mu_2 d\lpar x_1^{\ast}\comma\; x_2 - 1\rpar \cr &\quad + \nu_2 d\lpar x_1^{\ast}\comma\; x_2 - 1\rpar +\nu_1 d\lpar x_1^{\ast}\comma\; x_2\rpar + \lpar \nu_1 b_1 - \mu_1 c_1\rpar {\bf 1}\lpar x_1=1\rpar \cr &\quad +\lpar \mu_2 c_2 - \nu_2 b_2\rpar {\bf 1} \lpar x_2=1\rpar .}$

Taking limits on both sides and rearranging terms, we get

$\mu_1 \mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast}\comma\; x_2\rpar =C+\mu_1 \mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast} - 1\comma\; x_2\rpar \comma$

where C is a constant. The result is a consequence of the induction hypothesis.

Case 2

x ₁^* ≥ X ₁⇒d(x ₁^*, 0) ≥ 0.

We claim that d(x ₁^*, x ₂) < 0 for x ₂ sufficiently large; if this were not the case [i.e., if d(x ₁^*, x ₂) were bounded below by a nonnegative number], we would get from (20) and (21) that for x ₂ > 1,

Taking limits and using the induction hypothesis, we obtain

$\lpar \mu_1+\nu_1\rpar \mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast}\comma\; x_2\rpar =C+\mu_1 \mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast} - 1\comma\; x_2\rpar \comma$

which, by the induction hypothesis, yields

$\mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast}\comma\; x_2\rpar =- \infty\comma$

clearly a contradiction. Therefore, for x ₂ sufficiently large,

$\eqalign{d\lpar x_1^{\ast}\comma\; x_2\rpar &=\nu_1 h_1 - \lpar \nu_1+\nu_2\rpar h_2+\mu_1 d\lpar x_1^{\ast} - 1\comma\; x_2+1\rpar +\mu_2 d\lpar x_1^{\ast}\comma\; x_2 - 1\rpar \cr &\quad + \nu_2 d\lpar x_1^{\ast}\comma\; x_2 - 1\rpar +\nu_1 d\lpar x_1^{\ast}\comma\; x_2\rpar +\lpar \nu_1 b_1 - \mu_1 c_1\rpar {\bf 1}\lpar x_1^{\ast} =1\rpar \cr &\quad \Rightarrow \mu_1 \mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast}\comma\; x_2\rpar =C+\mu_1 \mathop{\lim\limits_{x_2 \to \infty}} d\lpar x_1^{\ast} - 1\comma\; x_2\rpar \comma }$

and lim_{x ₂}_→∞d(x ₁^*, x ₂) = −∞ follows from the induction hypothesis.■

Proof of Lemma 5

For each integer K ≥ 2, we introduce the function

$d_K \lpar x_1\rpar =d\lpar x_1\comma\; K - x_1\rpar \comma \enspace x_1=0\comma\; 1\comma\; \ldots\comma\; K.$

Therefore, we need to show that for all K ≥ 2,

$d_K \lpar x_1\rpar \gt 0 \Rightarrow d_K \lpar x_1\rpar \leq d_K \lpar x_1+1\rpar .$

Let

$\underline{K}=\min \lcub K\colon d_K \lpar x_1\rpar \gt 0 \; \hbox{for some} \; 1 \leq x_1 \leq K - 1\rcub$

and

$\!\!\!\!\!\!\!\! \overline{K}=\min \lcub K \geq \underline{K} \colon d_{K+1} \lpar x_1\rpar \leq 0\; \hbox{for all} \; x_1 \leq K\rcub .$

It suffices to prove the result for K ≤ K ≤ K, as the same arguments can be repeated for K > K. The proof is by induction on K (the inductive scheme is the one used by Wu et al. [Reference Wu, Lewis and Veatch26]). First, note that when d(x ₁ − 1, 1) > 0, it follows from Lemma 3 that d(x ₁ − 1, 0) > d(x ₁ − 1, 1) > 0, implying x ₁ − 1 > X ₁, which by (18) yields d(x ₁ − 1, 0) < d(x ₁, 0). Therefore,

(A.18b)

$d_{x_1} \lpar x_1 - 1\rpar \gt 0 \Rightarrow d_{x_1} \lpar x_1 - 1\rpar \lt d_{x_1} \lpar x_1\rpar.$

To start the induction, we prove the result for K = K. If K = 2, in which case d _K(K − 1) > 0, the result is a special case of (A.19). Consider now K > 2. Because d _K −1(x ₁) ≤ 0 for x ₁ ≤ K − 2, we have by Lemma 3 that d _K(x ₁) ≤ 0 for x ₁ ≤ K − 2. Therefore, d _K(K − 1) > 0 and it suffices to prove d _K(K − 1) ≤ d _K(K), which follows from (A.19).

To complete the induction, we assume that the result holds for K = k − 1, where K < k ≤ K, and prove it for K = k. Let x ₁^* = min{x ₁:d _k(x ₁) > 0}, so we need to show that d _k(x ₁^*) ≤ d _k(x ₁^* + 1) ≤ · · · ≤ d _k(k − 1) ≤ d _k(k). The last inequality has already been proven [(A.19)], so we only need to consider 1 ≤ x ₁^* ≤ k − 2. We start by proving the first inequality d _k(x ₁^*) ≤ d _k(x ₁^* + 1). From (20) and (21), we have

(A.20)

$\eqalign{d_k \lpar x_1^{\ast}\rpar - d_k \lpar x_1^{\ast} +1\rpar &=\mu_1 \lsqb d_k\lpar x_1^{\ast} - 1\rpar - d_k\lpar x_1^{\ast}\rpar \rsqb +\nu_1 \lsqb d_k\lpar x_1^{\ast} - 1\rpar ^+ -d_k \lpar x_1^{\ast}\rpar ^+\rsqb \cr &\quad + \mu_2 \lsqb d_{k - 1} \lpar x_1^{\ast}\rpar - d_{k - 1} \lpar x_1^{\ast} +1\rpar \rsqb +\nu_2 \lsqb d_{k - 1} \lpar x_1^{\ast}\rpar ^- - d_{k - 1} \lpar x_1^{\ast} +1\rpar ^- \rsqb \cr &\quad + \lpar \nu_1 b_1 - \mu_1 c_1\rpar {\bf 1}\lpar x_1^{\ast} =1\rpar - \lpar \mu_2 c_2 - \nu_2 b_2\rpar {\bf 1}\lpar x_1^{\ast} =k - 2\rpar \cr &\quad + \nu_1 \lsqb d_k \lpar x_1^{\ast}\rpar ^- - d_k \lpar x_1^{\ast} +1\rpar ^- \rsqb +\nu_2 \lsqb d_k \lpar x_1^{\ast}\rpar ^+ - d_k \lpar x_1^{\ast} +1\rpar ^+\rsqb .}$

By the definition of x ₁^* and Lemma 3, we get

(A.21)

$d_k \lpar x_1^{\ast} - 1\rpar \leq 0\lt d_k \lpar x_1^{\ast}\rpar \lt d_{k - 1} \lpar x_1^{\ast}\rpar .$

Because d _k−1(x ₁^*) > 0, we can apply the induction hypothesis to get d _k−1(x ₁^*) ≤ d _k−1(x ₁^* + 1), so from (A.20) and (A.21), condition (A3), and Lemma 2, we get d _k(x ₁^*) ≤ d _k(x ₁^* + 1). Having proven that d _k(x ₁^* + 1) > 0, we can show that d _k(x ₁^* + 1) ≤ d _k(x ₁^* + 2) ≤ · · · ≤ d _k(k − 1) by successive application of the same arguments.■

APPENDIX B

Proofs of Lemmas 6–8

Before we proceed to the proofs, we derive expressions for d _n,β(x ₁, x ₂). Because V _1,β(x ₁, x ₂) = h ₁x ₁ + h ₂x ₂, we get, for n = 1,

(B.1)

$d_{1\comma \beta} \lpar x_1\comma\; x_2\rpar =\lpar c_2 - c_1\rpar +\beta \lsqb \nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2\rsqb \comma\;$

(B.2)

$\hskip-53pt d_{1\comma \beta} \lpar x_1\comma\; 0\rpar = -c_1+\beta \nu_1 \lpar h_1 - h_2\rpar \comma\;$

(B.3)

$\hskip-90pt d_{1\comma \beta} \lpar 0\comma\; x_2\rpar =c_2 - \beta \nu_2 h_2.$

For n ≥ 2, we obtain the following recursive expressions from (22) and (25)–(28). For x ₁, x ₂ ≥ 1,

(B.4)

$\eqalignno{d_{n\comma \beta} \lpar x_1\comma\; x_2\rpar &=\lpar 1 - \beta\rpar \lpar c_1 - c_2\rpar +\beta \lsqb \nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2 - \mu_1 c_1 {\bf 1}\lpar x_1=1\rpar +\mu_2 c_2 {\bf 1} \lpar x_2=1\rpar \rsqb \cr &\quad + \beta \lsqb \lambda d_{n - 1\comma \beta} \lpar x_1+1\comma\; x_2\rpar +\mu_1 d_{n - 1\comma \beta} \lpar x_1 - 1\comma\; x_2+1\rpar +\mu_2 d_{n - 1\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar \cr &\quad + \nu_1 d_{n - 1\comma \beta} \lpar x_1 - 1\comma\; x_2+1\rpar ^+ + \nu_2 d_{n - 1\comma \beta} \lpar x_1\comma\; x_2 - 1\rpar ^- \cr &\quad + \nu_1 d_{n - 1\comma \beta} \lpar x_1\comma\; x_2\rpar ^-+\nu_2 d_{n - 1\comma \beta} \lpar x_1\comma\; x_2\rpar ^+\rsqb \comma}$

(B.5)

$\eqalignno{d_{n\comma \beta} \lpar x_1\comma\; 0\rpar &=- \lpar 1 - \beta\rpar c_1+\beta \lsqb \nu_1 \lpar h_1 - h_2\rpar - \nu_1 c_2 - \mu_1 c_1 {\bf 1}\lpar x_1=1\rpar - \mu_1 c_2 {\bf 1}\lpar x_1\gt 1\rpar \rsqb \cr &\quad + \beta \lsqb \lsqb \lpar \mu_2+\nu_2\rpar \beta \nu_1+\mu_1 \beta \nu_2 {\bf 1}\lpar x_1\gt 1\rpar \rsqb \lsqb V_{n - 1\comma \beta} \lpar x_1 - 1\comma\; 1\rpar - V_{n - 1\comma \beta} \lpar x_1 - 1\comma\; 0\rpar \rsqb \cr &\quad + \lambda d_{n - 1\comma \beta} \lpar x_1+1\comma\; 0\rpar +\mu_1 d_{n - 1\comma \beta} \lpar x_1 - 1\comma\; 1\rpar {\bf 1}\lpar x_1\gt 1\rpar +\lpar \mu_2+\nu_2\rpar d_{n - 1\comma \beta} \lpar x_1\comma\; 0\rpar \cr &\quad + \nu_1 d_{n - 1\comma \beta} \lpar x_1 - 1\comma\; 1\rpar ^+ + \nu_1 d_{n - 1\comma \beta} \lpar x_1\comma\; 0\rpar ^-\rsqb \comma}$

$\eqalign{d_{n\comma \beta} \lpar 0\comma\; x_2\rpar &=\lpar 1 - \beta\rpar c_2+\beta \lsqb - \nu_2 h_2+\lambda c_2+\mu_2 c_2 {\bf 1}\lpar x_2=1\rpar \rsqb \cr &\quad + \beta \lsqb \beta \lambda \nu_2 \lsqb V_{n - 1\comma \beta} \lpar 1\comma\; x_2 - 1\rpar - V_{n - 1\comma \beta} \lpar 1\comma\; x_2\rpar \rsqb +\lpar \mu_1+\nu_1\rpar d_{n - 1\comma \beta} \lpar 0\comma\; x_2\rpar \cr &\quad + \lsqb \mu_2 d_{n - 1\comma \beta} \lpar 0\comma\; x_2 - 1\rpar +\nu_2 d_{n - 1\comma \beta} \lpar 0\comma\; x_2 - 1\rpar ^- \rsqb {\bf 1}\lpar x_2\gt 1\rpar +\nu_2 d_{n - 1\comma \beta} \lpar 0\comma\; x_2\rpar ^+\rsqb .}$

The last equation is not needed for the proofs that follow, as we have already shown in Proposition 5 that d _n,β(0, x ₂) ≤ 0 for β ≥ c ₂/ν₂h ₂. However, we decided to include it in the article in order to have a complete set of expressions for d _n,β(x ₁, x ₂).

Proof of Lemma 6

The proof is by induction on n. For any x ₂ ≥ 1, we get from (B.1) and (B.2) that d _1,β(x ₁, x ₂) is constant for x ₂ ≥ 1 and

$d_{1\comma \beta} \lpar x_1\comma\; 0\rpar - d_{1\comma \beta} \lpar x_1\comma\; x_2\rpar =\beta \nu_2 h_2 - c_2\comma$

which is nonnegative because β ≥ β₁ ≥ c ₂/ν₂h ₂. Having established the induction base, we assume that the result holds for n = k and prove it for n = k + 1. Equations (B.4) and (B.5) and the fact that d _k,β(0, x ₂) ≤ 0 yield

$\eqalign{d_{k+1\comma \beta} \lpar x_1\comma\; 0\rpar - d_{k+1\comma \beta} \lpar x_1\comma\; 1\rpar &=- \lpar 1 - \beta\rpar \lpar 2c_1 - c_2\rpar +\beta \lsqb \nu_2 h_2 - \lpar \nu_1+\mu_2\rpar c_2 \rsqb \cr &\quad + \beta \lcub \lambda \lsqb d_{k\comma \beta} \lpar x_1+1\comma\; 0\rpar - d_{k\comma \beta} \lpar x_1+1\comma\; 1\rpar \rsqb \cr &\quad + \lpar \mu_2+\nu_2\rpar \beta \nu_1 \lsqb V_{k\comma \beta} \lpar x_1 - 1\comma\; 1\rpar - V_{k\comma \beta} \lpar x_1 - 1\comma\; 0\rpar \rsqb \cr &\quad + \nu_1 \lsqb d_{k\comma \beta} \lpar x_1 - 1\comma\; 1\rpar ^+- d_{k\comma \beta} \lpar x_1 - 1\comma\; 2\rpar ^+\rsqb {\bf 1} \lpar x_1\gt 1\rpar \cr &\quad +\nu_1 \lsqb d_{k\comma \beta} \lpar x_1\comma\; 0\rpar ^- - d_{k\comma \beta} \lpar x_1\comma\; 1\rpar ^- \rsqb \cr &\quad + \nu_2 \lsqb d_{k\comma \beta} \lpar x_1\comma\; 0\rpar - d_{k\comma \beta} \lpar x_1\comma\; 0\rpar ^- - d_{k\comma \beta} \lpar x_1\comma\; 1\rpar ^+\rsqb \rcub .}$

The combination of the first two terms of the right-hand side is nonnegative; it is positive when 2c ₁ ≤ c ₂ and nonnegative when 2c ₁ > c ₂ because

$\beta \geq \beta_1 \geq {2c_1 - c_2 \over \nu_2 h_2 - \lpar \nu_1+\mu_2\rpar c_2+2c_1 - c_2}.$

Noting that d _k,β(x ₁, 0) − d _k,β(x ₁, 0)⁻ = d _k,β(x ₁, 0)⁺, we get from the induction hypothesis and (30) that the remaining term is also nonnegative when β ≥ β₁. For x ₂ ≥ 1, d _k+1,β(x ₁, x ₂) − d _k+1,β(x ₁, x ₂ + 1) ≥ 0 follows in a straightforward manner from (B.4), d _k,β(0, x ₂) ≤ 0, and the induction hypothesis.■

Proof of Lemma 7

By induction on n. From (B.2), we get d _1,β(x ₁, 0) ≥ 0 because

$\beta \geq \beta_2 \geq {c_2 \over \nu_2h_2}\gt {c_1 \over \nu_1\lpar h_1 - h_2\rpar }$

and from (B.1), we get d _1,β(x ₁, x ₂) ≥ 0 for x ₂ ≥ 1. Assuming that d _k,β(x ₁, x ₂) ≥ 0, we use (B.5) and (B.4) to show that d _k+1,β(x ₁, x ₂) ≥ 0 for x ₂ = 0 and x ₂ ≥ 1, respectively. The sum of the first two terms of the right-hand side of (B.5) is nonnegative because

$\beta \geq \beta_2 \geq {c_2 \over \nu_2h_2}\gt {c_1 \over \nu_1 \lpar h_1 - h_2\rpar - \nu_1 c_2+c_1}.$

The last term is nonnegative by (30) and the induction hypothesis. Turning to (B.4), the sum of its first two terms is nonnegative because

$\beta \geq \beta_2 \geq {c_2 - c_1 \over \nu_1 \lpar h_1 - h_2\rpar - \nu_2 h_2+c_2 - c_1}\comma$

and the remaining term is nonnegative by the induction hypothesis.■

Proof of Lemma 8

The result has already been proven for x ₁ = 0 (proof of Proposition 5). For x ₁ > 0, we use induction on n. Equation (B.1) yields d _1,β(x ₁, x ₂) < 0. By applying the induction hypothesis to (B.4), we get d _n,β(x ₁, x ₂) ≤ 0 because■

$\beta \geq \beta_3 \geq {c_1 - c_2 \over \nu_2h_2 - \nu_1 \lpar h_1 - h_2\rpar +c_1 - c_2}.$

References

1.Ahn, H.S., Duenyas, I., & Lewis, M.E. (2002). The optimal control of a two-stage tandem queueing system with flexible servers. Probability in the Engineering and Informational Sciences 16: 453–469.CrossRef Google Scholar

2.Ahn, H.S., Duenyas, I., & Zhang, R. (1999). Optimal stochastic scheduling of a two-stage tandem queue with parallel servers. Advances in Applied Probability 31: 1095–1117.CrossRef Google Scholar

3.Ahn, H.S. & Righter, R. (2006). Dynamic load balancing with flexible workers. Advances in Applied Probability 38: 621–642.CrossRef Google Scholar

4.Andradottir, S., Ayhan, H., & Down, D.G. (2001). Server assignment policies for maximizing the steady-state throughput of finite queueing systems. Management Science 47: 1421–1439.CrossRef Google Scholar

5.Andradottir, S., Ayhan, H., & Down, D.G. (2003). Dynamic server allocation for queueing networks with flexible servers. Operations Research 51: 952–968.CrossRef Google Scholar

6.Andradottir, S., Ayhan, H., & Down, D.G. (2007). Compensating for failures with flexible servers. Operations Research 55: 753–768.CrossRef Google Scholar

7.Duenyas, I., Gupta, D., & Olsen, T. (1998). Control of a single server tandem queueing system with setups. Operations Research 46: 218–230.CrossRef Google Scholar

8.Farrar, T.M. (1992). Resource allocation in systems of queues. Ph.D. dissertation, Cambridge University, Cambridge.Google Scholar

9.Farrar, T.M. (1993). Optimal use of an extra server in a two station tandem queueing network. IEEE Transactions on Automatic Control 38: 1296–1299.CrossRef Google Scholar

10.Gel, E.S., Hopp, W.J., & Van Oyen, M.P. (2002). Factors affecting opportunity of worksharing as a dynamic load balancing mechanism. IIE Transactions 34: 847–863.CrossRef Google Scholar

11.Gel, E.S., Hopp, W.J., & Van Oyen, M.P. (2007). Hierarchical cross-training in work-in-process-constrained systems. IIE Transactions 39: 125–143.CrossRef Google Scholar

12.Hopp, W.J., Tekin, E., & Van Oyen, M.P. (2004). Benefits of skill-chaining in production lines with cross-trained workers. Management Science 50: 83–98.CrossRef Google Scholar

13.Hopp, W.J. & Van Oyen, M.P. (2004). Agile workforce evaluation: A framework for cross-training and coordination. IIE Transactions 36: 919–940.CrossRef Google Scholar

14.Iravani, S.M., Posner, M.J., & Buzacott, J.A. (1997). A two-stage tandem queue attended by a moving server with holding and switching costs. Queueing Systems 26: 203–228.CrossRef Google Scholar

15.Iravani, S.M., Van Oyen, M.P., & Sims, K.T. (2005). Structural flexibility: A new perspective on the design of manufacturing and service operations. Management Science 51: 151–166.CrossRef Google Scholar

16.Narongwanich, W., Duenyas, I., & Birge, J. (2003). Optimal portfolio of reconfigurable and dedicated capacity under uncertainty. http://users.iems.northwestern.edu/~jrbirge/Public/html/new.html Google Scholar

17.Pandelis, D.G. (2007). Optimal use of excess capacity in two interconnected queues. Mathematical Methods of Operations Research 65: 179–192.CrossRef Google Scholar

18.Pandelis, D.G. & Teneketzis, D. (1994). Optimal multiserver stochastic scheduling of two interconnected priority queues. Advances in Applied Probability 26: 258–279.CrossRef Google Scholar

19.Rosberg, Z., Varaiya, P., & Walrand, J. (1982). Optimal control of service in tandem queues. IEEE Transactions on Automatic Control 27: 600–609.CrossRef Google Scholar

20.Schiefermayr, K. & Weichbold, J. (2005). A complete solution for the optimal stochastic scheduling of a two-stage tandem queue with two flexible servers. Journal of Applied Probability 42: 778–796.CrossRef Google Scholar

21.Serfozo, R. (1978). An equivalence between continuous and discrete time Markov decision processes. Operations Research 27: 616–620.CrossRef Google Scholar

22.Van Oyen, M.P., Gel, E.S., & Hopp, W.J. (2001). Performance opportunity for workforce agility in collaborative and noncollaborative work systems. IIE Transactions 33: 761–777.CrossRef Google Scholar

23.Weber, R.R. & Stidham, S. (1987). Optimal control of service rates in networks of queues. Advances in Applied Probability 19: 202–218.CrossRef Google Scholar

24.Weichbold, J. & Schiefermayr, K. (2006). The optimal control of a general tandem queue. Probability in the Engineering and Informational Sciences 20: 307–327.CrossRef Google Scholar

25.Wu, C.H., Down, D.G., & Lewis, M.E. (2007). Heuristics for allocation of reconfigurable resources in a serial line with reliability considerations. IEEE Transactions (In Press).Google Scholar

26.Wu, C.H., Lewis, M.E., & Veatch, M. (2006). Dynamic allocation of reconfigurable resources in a two-stage tandem queueing system with reliability considerations. IEEE Transactions on Automatic Control 51: 309–314.CrossRef Google Scholar

Article contents

OPTIMAL CONTROL OF FLEXIBLE SERVERS IN TWO TANDEM QUEUES WITH OPERATING COSTS

Abstract

1. INTRODUCTION

2. CLEARING SYSTEMS

Proposition 1

Proof

Lemma 1

Proposition 2

Proof

Remark

Theorem 1

Remarks

Example

Lemma 2

Proof

Lemma 3

Lemma 4

Lemma 5

Proof of Theorem 1

Theorem 2

Proof

Theorem 3

Proof

3. SYSTEMS WITH ARRIVALS

Proposition 3

Proposition 4

Proposition 5

Proof

Lemma 6

Lemma 7

Lemma 8

Theorem 4

Proof

Theorem 5

Theorem 6

4. DISCUSSION

APPENDIX A

PROOFS OF LEMMAS 1 AND 3–5

Proof of Lemma 1

Proof of Lemma 3

Case 1

Case 2

Case 1

Case 2

Proof of Lemma 4

Case 1

Case 2

Proof of Lemma 5

APPENDIX B

Proofs of Lemmas 6–8

Proof of Lemma 6

Proof of Lemma 7

Proof of Lemma 8

References

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests