IIE Transactions (2000) 32, 881±890
Strongly asymptotically optimal design and control of production and service systems J. GEORGE SHANTHIKUMAR1 and SUSAN H. XU2 1
Department of Industrial Engineering and Operations Research and Walter A. Hass School of Business, University of California at Berkeley, Berkeley, CA 94720, USA E-mail:
[email protected] 2 Department of Management Science and Information Systems, College of Business Administration, The Pennsylvania State University, University Park, PA 16802, USA E-mail:
[email protected] Received January 1998 and accepted November 1999
In this paper we consider production and service systems that can be modeled as single or multiple stage queueing networks. We provide a formal de®nition of strong asymptotic optimality in the context of design and control of such queueing systems. We describe a simple approach to obtain strongly asymptotically optimal design and control policies for these systems. We illustrate our approach through some examples. In particular we obtain a strongly asymptotically optimal workload allocation for a multiple center service system modeled by the open Jackson network. The objective here is to minimize the expected total holding cost. A simple counter example shows that the much celebrated balanced workload allocation is not even asymptotically optimal for minimizing the expected number of jobs in the system. We show that an index policy is strongly asymptotically optimal for the scheduling control problem in a single stage (G=GI=1) service system. We also obtain a strongly asymptotically optimal allocation of classes of customers to a multiple center service system. This allocation agrees with the traditional wisdom of forming service stations to process similar tasks that reduce ¯uctuations in processing times. Suggestions for further work on this topic are summarized as well.
1. Introduction It is often dicult to obtain easily computable exact results for the performance measures of queueing models of real production and service systems. It is a common practice to devise approximations for the performance measures of such queueing systems (Bitran and Dasu, 1992; Buzacott and Shanthikumar, 1993; Harrison and Nyguen, 1993; Whitt, 1994). These approximations are then used to design (Bitran and Morabito, 1996; Buzacott and Shanthikumar, 1992) or used to develop control policies (Wein, 1990). While these approaches provide an ecient way to resolve practical issues, the goodness of these approximations, except for numerical veri®cation, often remains open. The purpose of this paper is: (i) to de®ne a notion of strong asymptotic optimality that could be used in some of these cases to measure the goodness of approximations (actually the resulting design or control policy); (ii) to provide a simple approach to obtain a strongly asymptotically optimal design or control policy; and (iii) to illustrate this approach through some examples. Suppose C
x; h is the performance measure of a queueing system, where x,
x 2 X is the design vari0740-817X
Ó
2000 ``IIE''
able(s) or the control policy (such as the number of servers at dierent service centers in a production or service system and/or the workload allocated there or the scheduling control policy) and h,
h 2 H is a system parameter (such as the customer arrival rate to the service system and/or the population size of a closed queueing netwrok). Let x
h be an optimal value of x that maximizes C
x; h. If our approximation results in a ^
h, we are interested in evaluating the degree solution x x
h; h. As of suboptimality ^ d
h C
x
h; h ÿ C
^ pointed out at the beginning of the paper, it is customary only to evaluate this numerically. But in cases, where it is possible to identify a h such that C
x
h; h ! 1 as h ! h (such as the utilization of a server going to one, or the population size in a closed system going to in®nity), one is often interested in showing that ^ d
h ! 0 as h ! h :
1 C
x
h; h ^
h is an asymptotically If this is achieved we say that x optimal design or control policy in h. Such an approach is common in heavy trac analysis (Kushner and Rama-
882
Shanthikumar and Xu
chandran, 1989; Seshadri, 1993). But even when this is achieved we may have ^ d
h ! 1 as h ! h : Therefore just showing (1) alone is not sucient to verify ^
h is a good design or a good control policy. that x Suppose we can show that there exists a ®nite constant K independent of h such that ^ d
h K; h 2 H and as h ! h :
2
If the above can be veri®ed, we will say that the design or the control policy
^ x
h is strongly asymptotically optimal in h. Better yet, if in addition to (2) we can show that ^ d
h ! 0
as h ! h ;
we will say that the design or the control policy is asymptotically exact in h. We can easily establish these properties by working with some upper (Cu
x; h) and lower (Cl
x; h) bounds for C
x; h. Suppose the upper bound Cu
x; h is selected ^
h. Then such that it is maximized by x ^ x
h; h ÿ Cl
^ x
h; h : ^s
h: d
h Cu
^ If ^s
h is bounded for all values of h 2 H and as h ! h , then we have strong asymptotic optimality. If, in addition, ^s
h ! 0 as h ! h , then we have an asymptotically exact design or control policy. In case we are interested in ^
h to the minimization of C
x
h; h, we will want x minimize the lower bound Cl
x; h. The organization of this paper is as follows: in Section 2, we obtain a strongly asymptotically optimal workload allocation (with respect to the customer arrival rate) for a multiple center service facility modelled by an open Jackson queueing network. We show that the balanced workload allocation is not even asymptotically optimal in minimizing the number of customers in such a service system. It is shown in Section 3 that the cl rule is a strongly asymptotically optimal scheduling control policy for the multiple class single stage service system (with respect to the customer arrival rate). A strongly asymptotically optimal allocation of classes of customers to a multiple center service system is addressed in Section 4. Suggestions for further work on this topic are summarized in Section 5.
2. Optimal workload allocation in a multiple center service system Consider a multiple center service system modelled by an open Jackson queueing network with m stations, with si parallel servers at station i, i 1; 2; . . . ; m. Customers arrive at the network according to a Poisson process with rate k. Each customer brings an average of W units of work which needs to be allocated among the m stations. Workload allocation in queueing systems, in various forms, has been considered by several authors (Bitran and
Morabito, 1996; Buzacott and Shanthikumar, 1992, 1993; Chen et al., 1995; Mohanty and Cassandras, 1993; Ni and Hwang, 1985; Seshadri and Pinedo, 2000; Shanthikumar, 1997; Tantawi and Towsley, 1985; Wein, 1989; Yao and Shanthikumar, 1987). Let the holding cost rate of each customer at station i be hi , i 1; 2; . . . ; m. We wish to allocate this total workload (of W units) among the m stations so that the long-run average holding cost of the system is minimized. We say that wi units of workload is allocated to station i if the average processing time of a customer by a server at station i is wi , or equivalently, the processing time of a customer at station i is exponentially distributed with rate 1=wi , i 1; 2; . . . ; m. Our objective is to minimize the expected total holding cost of the system: m X kwi
3 hi EN ; si ; min si i1 subject to m X
wi W ;
4
i1
where EN
q; s is the expected number of customers at an M=M=s queueing system with Poisson arrivals, exponentially distributed service times and s servers with server utilization q. EN
q; s is given by Buzacott and Shanthikumar (1993) as ( )
sqs q PfN
q; s 0g;
5 EN
q; s sq s
1 ÿ q2 where
" PfN
q; s 0g
#ÿ1
sqs : k! s!
1 ÿ q
sÿ1 X
sqk k0
6
First we will ®nd upper and lower bounds for EN
q; s that we can use to ®nd a strongly asymptotically optimal workload allocation. It is easily veri®ed that EN
q; 1 EN
q; s EN
q; 1 s ÿ 1;
7
where EN
q; 1
q : 1ÿq
8
Indeed, the leftmost term of (7) is the expected number of customers in an M=M=1 system, with the single server serving a customer s times as fast as a server in the M=M=s queue. The rightmost term of (7) is the expected number of customers in an M=M=s system with server utilization q, except that the s servers will service customers only if there are at least s customers available. The busy servers will halt their service as soon as the number of customers reduces to s ÿ 1 and resume their service immediately after a new customer arrives. Intuitively, the inserted idleness of servers under this rule causes more
Strongly asymptotically optimal control of queues
883
customers to remain in the system, and consequently, it provides an upper bound for EN
q; s. Observe that the number of customers in this system is the number of customer in an M=M=1 system with server utilization q plus s ÿ 1 customers. The
s ÿ 1 customers are those that are always present in the system, whereas q represents the fraction of time the (aggregated) server is busy. Hence the rightmost term of (7). Note that the bounds in (7) may be shown to hold in a sample path sense. Observe that the upper and lower bounds for the objective function are then given by X m m m X X qi kwi qi hi hi EN ; si hi K; 1 ÿ qi si 1 ÿ qi i1 i1 i1
9
P where K m i1 hi
si ÿ 1. Since the dierence K between the upper and lower bounds is bounded and is independent of the arrival rate k it is easily seen that the workload allocation that minimizes the lower bound is a strongly asymptotically optimal workload P allocation for (3) and (4) as k ! S=W , where S m i1 si is the total number of servers in the system (see Theorem 1 below and Section 1). The following lemma gives the allocation of workload that minimizes the lower bound for the total holding cost in the network. Lemma 1. The workload allocation p si S hi si ^i ÿ ÿ W Pn p ; i 1; 2; . . . ; m;
10 w k k hj sj j1 minimizes the lower bound for the average total holding cost n m m X X X qi kwi hi EN
qi ; 1 hi hi ;
11 1 ÿ qi si ÿ kwi i1 i1 i1 P subject to the condition m i1 wi W , and wi < si =k; i 1; 2; . . . ; m. Proof. From (11) one sees that " # m d X hi si k hi EN
qi ; 1 ; dwi i1
si ÿ wi k2
is greater than zero. Therefore, the objective function in (11) is separable and strictly convex and by the Karush± Kuhn±Tucker condition there exists a constant g such that " # m d X hi si k hi EN
qi ; 1 dwi i1 ^ i k2
si ÿ w ^ w w i
g; ^ i we get Solving for w
i 1; 2; . . . ; m:
13
s hi si : gk
14
Summing (14) over its index and using the fact that Pm ^ i W , one ®nds that i1 w s m m n X X si X hi si ^i w ÿ :
15 W k i1 gk i1 i1 This implies that
Pm 1
si =k ÿ W p : p Pi1 m g
hi si =k i1
16
Substitute (16) into (14) and one obtains (10).
j
Before we proceed, let us look at the capacity of the system. Recall that the capacity of the system is de®ned as the minimum value of k such that for any arrival rate k larger than this value the number of customers in the network will grow without limit. For a given k, the ca^ i , i 1; 2; . . . ; m, is pacity of our system under allocation w si : min 1im w ^i ^ i , i 1; 2; . . . ; m, given in (10), is a Since allocation w function of k, it is clear that the capacity of our system varies as k changes. Also, (10) implies that to ensure stability, k cannot exceed S=W , which is the limiting ca^ i , i 1; 2; . . . ; m. Further, this pacity under allocation w allocation approaches Wsi S
17 as k ! ; i 1; 2; . . . ; m: W S Note that under this allocation, all stations reach their capacities simultaneously as k approaches the capacity of the network. Next we show the strong asymptotic optimality of the above allocation. ^i ! w
Theorem 1. The allocation given by (10) is strongly asymptotically optimal in heavy trac. Speci®cally, let wi , i 1; 2; . . . ; m, be the optimal allocation and let
i 1; 2; . . . ; m;
12
i
si ^i ÿ w k
^i q then 0
m X i1
and Pm
i1
m X
^i k w ; si
qi
hi EN
^ qi ; si ÿ
wi k ; si
m X i1
hi EN
qi ; si
hi
si ÿ 1 < 1;
18
i1
P hi EN
^ q ;s ÿ m i1 hi EN
qi ; si Pmi i !0 i1 hi EN
qi ; si
as k !
S : W
19
884
Shanthikumar and Xu 3. Optimal scheduling control in single stage service systems
Proof. From (9) one sees that m m X X hi EN
^ qi ; si ÿ hi EN
qi ; si 0 i1
m X i1 m X
i1
hi EN
^ qi ; 1
si ÿ 1 ÿ
m X i1
EN
qi ; 1
hi
si ÿ 1;
20
i1
^ i , i 1; 2; . . . ; m, where the last expression holds because w minimizes the lower (and upper) bound to the average total holding cost of the system. This proves (18). Now (19) follows immediately from (18) and the fact that the denominator of (19) approaches in®nity as k ! S=W : j It is often advocated that the workload in all the centers of a service facility should be balanced to minimize the average number of customers in the system. The balanced workload allocation is wbi
W =Ssi ; i 1; 2; . . . ; m. It is easily noted that for hi 1; i 1; 2; . . . ; m, we have ^ i ! wbi as k ! S=W . It is therefore tempting to speculate w that the balanced workload allocation is also strongly asymptotically optimal. Consider the following two station example. Let m 2, s1 1, s2 9 and W 10. Then wb1 1 and wb2 9: For an arrival rate k (k < 1) we have qb1 k and qb2 k. Hence from (9) we have k :
21 1ÿk Consider the following allocation (given in (10)) that minimizes the lower bound. 1ÿk 1ÿk ^ 2
k 9 1:5 ^ 1
k 1 ÿ 1:5 and w : w k k C
wb ; k EN
qb1 ; 1 EN
qb2 ; 9 2
Hence from (9) we have q2 ; 9 C
^ w
k; k EN
^ q1 ; 1 EN
^ k 1 ÿ 8: 2 1 ÿ k 2:5
1 ÿ k
ai supfESi ÿ xjSi > xg < 1; x0
22
23
Clearly, as k ! 1 we have db
k ! 1. Hence the balanced workload allocation is not strongly asymptotically optimal. Indeed one sees (from (22) and (23)) that db
k ! 0:25 as k ! 1: C
W
k; k That is, the balanced workload allocation is not even asymptotically optimal.
i 1; 2; . . . ; r:
24
The holding cost rate of class i customers is denoted by ci . Without loss of generality let ci li ci1 li1 ;
i 1; 2; . . . ; r;
25
where cr1 lr1 0. We consider the class U of all work-conserving, nonanticipative and nonpreemptive scheduling control policies. De®nition 1. A scheduling control policy is work-conserving and nonanticipative, if no server is allowed to be idle when there are customers waiting to be served, and the control is only allowed to make use of past history and the current state of the system. Neither can an admissible control aect the arrival processes or the service requirements of the customers. Otherwise we propose no further restrictions on the system. We aim at ®nding a scheduling control policy in U that minimizes the long-run average total holding cost of the system ( ) r X ci ENi
u ; u 2 U ;
26 min u2U
From (21) and (22) one sees that db
k : C
wb ; k ÿ C
w
k; k; C
wb ; k ÿ C
^ w
k; k 1 ÿ 8: 2:5
1 ÿ k
Consider a service system that has a single server that serves r classes of customers. Class i customers arrive to the system according to a point process, with the timeaverage arrival rate ki , i 1; 2; . . . ; r. The service times of class i customers form an i:i:d: sequence of random variables, identically distributed as Si , where ESi 1=li , i 1; 2; . . . ; r. We assume that the expected remaining service time of a class i customer, with any attained service x, x 0, is ®nite:
i1
where ENi
u is the time-average number of class i customers in the system under policy u. Optimal scheduling control policies, when we have Poisson arrivals, have been investigated by several authors, for example Wol (1970), Bertsimas (1995), Shanthikumar and Yao (1992) and references there in. Let qi ki =li be the fraction of time that the Pserver services class i customers, i 1; 2; . . . ; r; q : ri1 qi < 1. Since in a stable system every customer is eventually served, qi is invarant under any scheduling control policy. Let Vi
u be the time-average remaining workload of class i customers under u, i 1; 2; . . . ; r. Then EVi
u
1 ESi2 ;
ENi
u ÿ qi qi li 2ESi
Multiplying both sides by li yields
27
Strongly asymptotically optimal control of queues li EVi
u ENi
u ÿ qi ki
ESi2 : 2ESi
28
ENi
u li EVi
u qi ÿ ki
ESi2 : 2ESi
29
Hence
Substituting (29) into (26) gives us ( ) r X ci ENi
u min u2U
i1
(
min u2U
r X i1
ci li EVi
u
r X i1
u2U
ci ki ESi2 ci qi ÿ 2ESi
) :
30
i1
using a decomposition argument similar to that in Doshi (1985), it can be shown that X EVi
uT b
T aT b
T aE :
35 i2T
Now let ucl be the policy which assigns HOL priority to class i customers over class i 1 customers, i 1; 2; . . . ; r. That is, the priority is assigned to classes in a decreasing order of ci li . The next theorem shows that the cl rule is strongly asymptotically optimal. Theorem 2. The scheduling control policy ucl is strongly asymptotically optimal under heavy trac. Speci®cally, r r X X ci li EVi
ucl ÿ ci li EVi
u c1 l1 aE < 1; 0 i1
ji
i1
j r X X
cj lj ÿ cj1 lj1 EVi
u:
i1
36
32
i1
j1
Note that the last expression is obtained by interchanging the order of summations. Let E f1; 2; . . . ; rg be the set of all classes of customers, T be a subset of E, and T E ÿ T . For simplicity, we say a customer is a T -customer (T-customer) if its customer class belongs to the set T (T). Let b
T be the time-average remaining workload when T -customers have preemptive priority over T-customers. Observe that this quantity is invariant under all scheduling rules within the class of customers in T and T. Using sample path arguments it can be veri®ed that X EVi
u b
T ; u 2 U :
33
and Pr
P
u ÿ ri1 ci li EVi
u i1 ci li EV Pi r cl i1 ci li EVi
u
Because cj lj cj1 lj1 (see (25)), one sees from (32) that the objective function has a lower bound r r X X ci li EVi
u
cj lj ÿ cj1 lj1 b
1; 2; . . . ; j; j1
Indeed, the lower bound is independent of the control policy u. Hence we need to ®nd an upper bound and a control policy for which the upper bound is close to this lower bound. We shall do this next. Let us now consider the class of Head-Of-the-Line (HOL) priority policies, UHOL , where each class is as-
0
as q ! 1:
37
Proof. From (32) we obtain r r X X ci li EVi
ucl ÿ ci li EVi
u 0 i1
i1
j r X X
cj lj ÿ cj1 lj1 EVi
ucl i1
j1
ÿ
i2T
i1
34
i2T
It will prove convenient to rewrite the objective function as follows: " # r r r X X X ci li EVi
u EVi
u
cj lj ÿ cj1 lj1 i1
signed a ®xed, nonpreemptive priority. Let uT 2 UHOL be any admissible policy which gives T -customers the headof-the-line priority over T-customers. Since no preemptions are allowed under uT , those arriving T -customers who ®nd a T-customer on service have to wait until the T-customer completes its service. Because the expected remaining service time of the T-customer cannot exceed aT , where aT : maxfai g;
Notice that the last summation on the right-hand side (RHS) of (30) is independent of u, thus our objective is achieved by determining u , the optimal scheduling control policy, such that ( ) r r X X ci li EVi
u : min ci li EVi
u :
31 i1
885
r X
j X
j1
i1
cj lj ÿ cj1 lj1
EVi
u
r X j1
ÿ
cj lj ÿ cj1 lj1 b
1; . . . ; j aE
r X
cj lj ÿ cj1 lj1 b
1; . . . ; j j1
c1 l1 aE ;
38
where in the second inequality we used (33) and (35), respectively. This proves (36). Since b
1; . . . ; r ! 1 as q ! 1, the denominator of (37) approaches in®nity in heavy trac. Then (37) follows from (36). j
886
Shanthikumar and Xu
4. Allocation of customer classes to multiple service centers The allocation of dierent classes of customers to dierent servers (or service centers/stations) in a service facility is one of the fundamental design problems. It is a traditional wisdom that forming service stations to process similar items and to reduce wide ¯uctuations in processing requirements is desirable. In this section, we will formulate a queueing model to address this design issue and show that an allocation algorithm that agrees with this traditional wisdom is indeed strongly asymptotically optimal. Consider a single-stage queueing system that has s servers (or stations) of equal capabilities. Customers arrive at the system according to a renewal stream with inter-arrival times fAn ; n 1; 2; . . .g with ®nite mean 1=k and squared coecient of variation (scv) Ca2 . The probability that aPnew arrival belongs to class j is qj , j 1; 2; . . . ; r, rj1 qj 1. Upon arrival, the class of the customer is identi®ed. Then a P class j customer is routed to server i with probability hij , si1 hij 1, j 1; 2; . . . ; r. Let H fhij ; i 1; . . . ; s; j 1; . . . ; rg. The generic processing time of a class j customer is Sj , j 1; 2; . . . ; r, with ®nite mean 1=lj and scv CS2j . Let kj qj k be the arrival rate of class j customers to the system and kij hij kj the rate of class j customers routed to station i. Suppose that the service discipline at each station is First-Come FirstServed (FCFS). We require that the allocation is equitable to all s stations. That is, the average workload allocated to each station is identical. Therefore, our problem is min H
s X
ENi
H;
i1
subject to s X
hij 1; j 1; 2; . . . ; r;
i1 r X
kij ESj q; i 1; 2; . . . ; s;
Let T and T be a partition of those 2n classes, with cardinalities jT j and jTj, respectively. We wish to group these classes into two sets T and T such that jT j n jTj and classes in T are assigned to station 1 and classes in T are assigned to station 2. The problem is then minfEN1
T EN2
Tg;
41 T
where EN1
T (EN2
T) is the expected number of customers in station 1 (station 2) under allocation T (T). Without loss of generality we assume that the classes are ordered so that ES1 ES2 ESr : Then, from (40), k1 k2 kr :
43
We also assume that the service times of dierent classes satisfy the following agreeability condition for the mean remaining service times ES12 ES22 ESr2 : 2ES1 2ES2 2ESr
44
In other words, we require that if the mean service time of a class is smaller than that of another class, then the same relationship holds with respect to the mean remaining service time. Then from (40) and (44) one has k1 ES12 k2 ES22 kr ESr2 :
45
Next we derive the expression for EN1
T . Since the service discipline is FCFS, we can aggregate all classes in T into a single customer class, say class T -customers, and ®nd the means and scv's of inter-arrival times and service times of class T -customers. Let fAn ; n 1; 2; . . .g be the sequence of i:i:d: inter-arrival times with the same distribution as A and let ZT be an independentPgeometric random variable on f1; 2; . . .g with mean 1=
j2T kj =k. Then the arrival process to station 1 is a renewal process with the generic inter-arrival time AT given by AT
39
d
ZT X
An :
46
n1
j1
where ENP i
H is the number of customers in station i, q
k=s rj1 qj ESj is the workload per unit time routed to each station. The problem of allocating multiple classes of customers in a multiple cell system with Poisson arrival process has been studied by Buzacott and Shanthikumar (1993). The approach adopted here is similar to theirs. We ®rst consider a simpli®ed version of the problem whose solution will lead to a solution to the preceding problem. Suppose that we have two stations (s 2) and r 2n classes, for some n 1; 2; . . . ; so that qs q
40 kj ESj constant ; j 1; 2; . . . ; r: r n
42
The mean and scv of AT , denoted by 1=kT and Ca2
T , are 1 1 : EAT P ; kT j2T kj and Ca2
T
kT :
Ca2 ÿ 1 1; k
47
respectively. The mean service time of a class T -customer is X kj 1 1 q ;
48 lT kT k l j2T T j
Strongly asymptotically optimal control of queues P where q
1=2 rj1
kj =lj , and the last equality of (48) is due to (40). Note that the fraction of time that station 1 is busy is kT =lT q. The scv of the service time of the class T -customer is found to be P X kj ESj2 kT j2T kj ESj2 2 2 CS
T
lT ÿ1 ÿ 1: kT q2 j2T
49 With the above notation, it is known, see Equation 3.112 of Buzacott and Shanthikumar (1993), that EN1
T
Ca2
T
2
1 ÿ 2q q 2
1 ÿ q
CS2
T
and l 2CS2 Ca2 2a 2b 1;
50
where IT maxfA^T ÿ WT ; 0g;
51
and WT is the stationary sojourn time of a T -customer. Similarly, C 2
T Cs2
T 1 q
1 qCS2
T ÿ EN2
T a 2
1 ÿ q 2 2 2 kTEIT :
52 2EIT The proof of the next lemma can be found in Shanthikumar and Xu (1997). Lemma 2. Let T be a subset of f1; 2; . . . ; rg and jT j n. aT : supfkT EAT ÿ xjAT > xg and x ( ) E
AT ÿ x2 jAT > x : bT : sup kT 2EAT ÿ xjAT > x x
57
CS2 maxfCS2
T g;
58
T
a maxfaT g;
59
b maxfbT g:
60
T T
Then
53
61
Proof. Substituting (47)±(49) into (50) we obtain P
Ca2 ÿ 1kT =k
1=q2
kT j2T kj ESj2 EN1
T 2
1 ÿ q 1 q
1 qCS2
T kT EIT2 :
62 ÿ ÿ 2 2 2EIT Similarly, we can obtain the expression for EN2
T. Thus the total number of customers in the system under the partition
T ; T is EN1
T EN2
T
Ca2 ÿ 1
1=q2
kT
P j2T
P
kj ESj2
kT
2 j2T kj ESj
2
1 ÿ q
1 q
CS2
T CS2
T kT EIT2 kT EIT2 ÿ
1 q ÿ ÿ : 2 2EIT 2EIT
63 Lemma 3 is the immediate consequence of Lemma 2 and Equations (58)±(60). j Consider the lower bound EN1
T EN2
T N^1
T N^2
T ÿ l
Ca2 ÿ 1
1=q2
kT
P j2T
kj ESj2
kT
P
2 j2T kj ESj
2
1 ÿ q
Then kT EIT2 kT 2
Ca ÿ 1 2aT 2bT 2: EIT k
u 2;
N^1
T N^2
T ÿ l EN1
T EN2
T N^1
T N^2
T u:
C 2
T Cs2
T 1 q
1 qCS2
T ÿ a 2
1 ÿ q 2 2 kT EIT2 ; 2EIT
and
where
1
kT EIT2 q; ÿ 2EIT
887
ÿ l:
64
54
The next lemma gives the bounds for EN1
T EN2
T. Lemma 3. Let T be a subset of f1; 2; . . . ; rg and jT j n. Let P
Ca2 ÿ 1
kT =k
1=q2
kT j2T kj ESj2 ;
55 N^1
T 2
1 ÿ q P
Ca2 ÿ 1
kT=k
1=q2
kT j2T kj ESj2 ^ ;
56 N2
T 2
1 ÿ q
Let T 0 f1; 2; . . . ; ng and T0 fn 1; n 2; . . . ; 2ng. By (43), kT kk ESk2 kTkl ESl2 kT 0 minfkk ESk2 ; kl ESl2 g kT0 maxfkk ESk2 ; kl ESl2 g; it is immediate from (45) that P P kT j2T kj ESj2 kT j2T kj ESj2
kT 0
2
1 ÿ q P 2 2 j2T 0 kj ESj kT0 j2T0 kj ESj
P
2
1 ÿ q
:
65
888
Shanthikumar and Xu
Because Ca2 ÿ 1 and q are ®xed in (64), we see that allocation
T 0 ; T0 minimizes the lower bound for the number of customers in the system. The next theorem, under the conditions of (42) and (44), addresses the strong optimality of
T 0 ; T0 . Its proof is similar to its counterpart in Sections 2 and 3 and hence is omitted. Theorem 3. Let
T ; T be the optimal grouping that minimizes Equation (41). The grouping
T 0 ; T0 is strongly asymptotically optimal under heavy trac in the sense that 0
EN1
T 0 EN2
T0 ÿ
EN1
T EN2
T l u < 1;
66
and EN1
T 0 EN2
T0 ÿ EN1
T EN2
T !0 EN1
T EN2
T as k ! l:
67
Now consider our original problem of probabilistic routing of multiple classes of customers to two stations. We assume that (42) and (44) still hold. Suppose qj are rationals, where qj kj ESj , j 1; 2; . . . ; r. It implies that q is an integer, there exists a q^ > 0 such that nj qj =^ j 1; 2; . . . ; r. For some integer m 1, let us divide each class j into 2m nj arti®cial classes, each new class with arrival rate kj =
2m nj and the same service time distribution as class j customers. Then the workload of each arti®cial class P is q^=2m. With the new classi®cation we have totally 2m rj1 nj customer classes, each new class with an equitable workload rate of q^=2m. Using the previous result, of thePclasses is f1; 2; . . . ; P P the optimal grouping m rj1 nj g and fm rj1 nj 1; 2m rj1 nj g: Let ( ) l r X X nj m nj ; l 1; . . . ; r :
68 k min l : 2m j1
j1
Then k corresponds to the class whose customers are split probabilistically between the two stations, where the rates of going to station i, i 1; 2, are P P
m rj1 nj ÿ 2m kÿ1 q j1 nj ^ ; kk1 2mESk
69 kk2 kk ÿ kk1 : Then, the original classes f1; 2; . . . ; kg with allocation rate fk1 ; . . . ; kkÿ1 ; kk1 g are routed to station 1, and the original classes fk; . . . ; rg with allocation rate fkk2 ; kk1 ; . . . ; kr g q, we can rewrite are routed to station 2. Because nj qj =^ (68) as ( ) l X qj q; l 1; . . . ; r ;
70 k min l : 2 j1
kk1
q=2 ÿ
Pkÿ1 j1
ESk
qj
and kk2 kk ÿ kk1 :
71
Observe that this optimal grouping is independent of m. Because the workload rate of each arti®cial class q^=2m ! 0 as m ! 1, the class grouping problem becomes the same as the probabilistic routing problem. Hence the independence of the solution of the grouping problem to the value of m implies that this solution is strongly asymptotically optimal to the probabilistic routing problem as well. Finally, using pairwise application of this result to s stations, one concludes: Theorem 4. The following allocation is strongly asymptotically optimal: For l l; 2; . . . ; s, classes fil ; . . . ; il1 g should be allocated to station l with corresponding probabilities
kl;il =kl ; 1; . . . ; 1; kl;il1 , where i1 1, ( ) k X qj lq; k 1; . . . ; r
72 il1 min k : kl;il1
lq ÿ
Pil1
j1 qj
ESil1
j1
and kl1;il1 kil1 ÿ kl;il1 :
73
In words, Theorem 4 says that the strongly asymptotically routing has the property that the classes with similar processing times are routed to the same station. Hence our solution supports the traditional wisdom of forming stations to process similar items and to reduce wide ¯uctuations in processing requirement. Remarks 1. If the arrival process is Poisson (Ca2 1, then the approximate routing probabilities are indeed optimal (see Buzacott and Shanthikumar, 1993, Section 10.6.1). 2. In this section we assumed that the class of a customer is identi®able upon its arrival. If the class is not observable at the time of the customer arrival, then we can generalize Shanthikumar and Xu's approach as follows: As in the previous model we assume that customers arrive at the system according to a renewal process with that a new ®nite mean 1=k and scv Ca2 . The probability Pr q customer belongs to class j is qj , j1 j 1. The system has s heterogeneous stations (i.e., we do not require all stations to be identical). The processing time of a class j customer at station i has ®nite mean 1=lij and scv CS2ij , i 1; 2; . . . ; s, j 1; 2; . . . ; r. The holding cost rate of station i is ci per unit time (i.e., the holding cost of a customer depends on which station it is served, but is independent of its class). The service discipline at all stations is FCFS. We are interested inP ®nding the s routing probabilities hi , i 1; 2; . . . ; s, i1 hi 1,
Strongly asymptotically optimal control of queues that minimize the average total holding cost of the system: ( ) s X ci ENi
hi ; min h1 ;...;hs
i1
subject to s X
hi 1;
i1
where ENi
hi is the long-run average number of customers in station i, i 1; . . . ; s. Since one cannot observe customer classes and the service discipline is FCFS, we can aggregate all customers into a single class. Then the service time of a customer routed to station i has mean r X 1 1 : qj ; li l ij j1
i 1; . . . ; s;
74
and scv CS2i : l2i
r X qj j1
l2ij
1 CS2ij ÿ 1;
i 1; 2; . . . ; s;
75
respectively. With the aggregated single class, the problem reduces to the model studied by Shanthikumar and Xu (1977). We present the following result without proof. Theorem 5. Let fh1 ; . . . ; hs g be the optimal routing probabilities for a given k. The routing probabilities given by p l lÿk ci Ki h^i i ÿ Ps p ; i 1; 2; . . . ; s;
76 k k cj Kj j1 are strongly asymptotically optimal under heavy trac conditions. Speci®cally, s s X X ci ENi
h^i ÿ ci ENi
hi c; for all k < l; 0 i1
i1
77 and Ps
Ps ^ i
hi ÿ i1 ci EN i1 ci ENi
hi Ps i1 ci ENi
hi
! 0 as k ! l;
78
where c is a ®nite constant, and Ki
Ca2 ÿ 1l2i
CS2i 1kli ;
i 1; 2; . . . ; s:
79
5. Concluding remarks In this paper we have de®ned a notion of strong asymptotic optimality in the design and control of production and service systems modelled by single and multiple stage
889 queueing networks. Some examples are presented to illustrate an approach to obtain strongly asymptotically optimal design and control policies for such systems. Some other problems that are worth considering are 1. Workload allocation for service facilities modelled by the generalized Jackson queueing network (Wein, 1989). 2. Scheduling control of a single stage service system with customer feedback (Bertsekas, 1995; Klimov, 1974). 3. Scheduling control of service facilities modelled by the generalized Jackson queueing networks (Wein, 1990). In all these problems, the system parameter of interest is the external customer arrival rate (k). It will be of interest to look at examples where other system parameters could be utilized. We will next discuss such a case. Consider a service system modelled by the closed Jackson queueing network with m stations, with si parallel servers at station i, i 1; 2; . . . ; m. There are n customers in the system circulating through these stations. Each customer requires an average of W units of work to be performed on these m stations during one cycle. We wish to allocate this total workload among the m stations so that the throughput of the system is maximized. Suppose we have allocated wi units of work to station i, i 1; 2; . . . ; m: Then the processing time of a customer at station i is exponentially distributed with mean wi , i 1; 2; . . . ; m. Let N
q; s be a generic random variable representing the stationary number of customers at a single stage (M=M=s) queueing system with a Poisson arrival process, exponentially distributed service times and s servers with server utilization q, (q < 1). Then the throughput of the system is P Pf m i1 N
kwi =si ; si n ÿ 1g P ;
80 TH
w; s; n k Pf m i1 N
kwi =si ; si ng where k is any positive value chosen such that kwi < si ; i 1; 2; . . . ; m: It is now well known that when si c; i 1; 2; . . . ; m; a balanced workload allocation (wi W =m; i 1; 2; . . . ; m) will maximize the throughput (Shanthikumar, 1987). However, when the number of servers are not the same at all stations such a balanced workload allocation, though often advocated in practise, is not optimal (Buzacott and Shanthikumar, 1993). In an asymptotic sense (as n ! 1) it is easily veri®ed that TH
w; s; n ! minfsi =wi ; i 1; 2; . . . ; mg and that a balanced workload maximize the throughput. Since the throughput is ®nite, this does not con®rm, in our setting, that the balanced workload is asymptotically exact (see Section 1 for its de®nition). For this we need to choose an objective function that is strictly monotone in throughput and should approach in®nity as n ! 1. A natural choice
890
Shanthikumar and Xu
is nTH
w; s; n (essentially this will give us the rate of convergence ). Our objective is to maximize nTH
w; s; n for each given n. Consider a closed queueing network that serves a customer at every station i if and only if at least si customers are there, i 1; 2; . . . ; m. The throughput of such a network will be that of a closed queueing network with a single server with a service rate si =wi at station i; i P1; 2 . . . ; m and n m ÿ S customers, where S m i1 si . Using sample path arguments it can be seen that this is a lower bound to the throughput of our system. That is TH
w1 =s1 ; w2 =s2 ; . . . ; wm =sm ; 1; n m ÿ S TH
w; s; n: Now consider a closed queueing network where all servers at any station can serve customers at the full rate as long as at least one customer is there. This system provides an upper bound for the throughput. That is TH
w1 =s1 ; w2 =s2 ; . . . ; wm =sm ; 1; n TH
w; s; n: Details of these and other bounds can be found in Shanthikumar and Yao (1988). It will be of interest to see whether these bounds can be used to: (i) obtain a strong asymptotically optimal workload allocation; and (ii) to study the goodness of balanced workload allocation for closed Jackson queueing networks.
Acknowledgement The authors thank Professor Rhonda Righter for her helpful comments on an earlier version of this paper. The authors also thank the anonymous referee for his or her careful review of the paper and useful comments.
References Bertsimas, D. (1995) The achievable region method in the optimal control of queueing systems: formulations, bounds and policies. Queueing Systems: Theory and Applications, 21, 337±389. Bitran, G.R. and Dasu, S. (1992) A review of open queueing network models of manufacturing systems. Queueing Systems: Theory and Applications, 12, 95±134. Bitran, G.R. and Morabito, R. (1996) Open queueing networks: optimization and performance evaluation models for discrete manufacturing systems. Production and Operations Management, 5, 163±193. Buzacott, J.A. and Shanthikumar, J.G. (1992) Design of manufacturing systems using queueing models. Queueing Systems: Theory and Applications, 12, 135±214. Buzacott, J.A. and Shanthikumar, J.G. (1993) Stochastic Models of Manufacturing Systems, Prentice Hall, Englewood Clis, NJ.
Chen, L.T., Rotem, D. and Seshadri, S. (1995) Declustering databases on heterogeneous disk systems, in Proceedings, 21st VLDP Conference, pp. 110±121. Doshi, B. (1985) Queueing systems with vacations ± a survey. Queueing Systems: Theory and Applications, 1, 29±66. Harrison, J.M. and Nguyen, V. (1993) Brownian models of multiclass queueing networks: current status and open problems. Queueing Systems: Theory and Applications, 13, 5±40. Klimov, G.P. (1974) Time-sharing service systems. Theory Probability Applications, 19, 558±576. Kushner, H.J. and Ramachandran, K.M. (1989) Optimal and approximately optimal control policies for queues in heavy trac. SIAM Journal on Control and Optimization, 27, 1293±1318. Mohanty, B. and Cassandras, C.G. (1993) Asymptotic analysis of the eect of arrival model uncertainties in some optimal routing problems. Journal of Optimization Theory and Applications, 77. Ni, L.M. and Hwang, H. (1985) Optimal load balancing in a multiprocessor with many job classes. IEEE Transaction on Software Engineering, SE-11, 491±496. Pinedo, M. and Seshadri, S. (2000) Optimal allocation of resources in a job shop environment. IIE Transactions on Operations Engineering, (in press). Seshadri, S. (1993) Stochastic models of semiconductor fabs. Ph.D. thesis, Walter A. Haas School of Business, University of California, Berkeley, CA, 94720. Shanthikumar, J.G. (1987) Stochastic majorization of random variables with proportional equilibrium rates. Advances in Applied Probability, 19, 854±872. Shanthikumar, J.G. and Xu, S.H. (1997) Asymptotically optimal routing and service rate allocation in a multi-server queueing system. Operations Research, 45, 464±469. Shanthikumar, J.G. and Yao, D.D. (1988) Throughput bounds for closed queueing networks with queue-dependent service rates. Performance Evaluations, 9, 69±78. Shanthikumar, J.G. and Yao, D.D. (1992) Multiclass queueing systems: polymatroidal structure and optimal scheduling control. Operations Research, 40, S293±S299. Tantawi, A.N. and Towsley, D. (1985) Optimal static load balancing in distributed computer system. Journal of ACM, 32, 445±465. Wein, L.M. (1989) Capacity allocation in generalized Jackson networks. Operations Research Letters, 8, 143±146. Wein, L.M. (1990) Scheduling networks of queues: heavy trac analysis of a multistation network with controllable inputs. Operations Research, 40, S312±S334. Whitt, W. (1994) Towards better multi-class parametric decomposition approximations for open queueing networks. Annals of Operations Research, 48, 221±248. Wol, R.W. (1970) Work-conserving priorities. Journal of Applied Probability, 7, 327±337. Yao, D.D. and Shanthikumar, J.G. (1987) The optimal input rates to a system of manufacturing cells. INFOR, 25, 57±65.
Biographies J. George Shanthikumar is a Professor in the Department of Industrial Engineering and Operations Research at the University of California at Berkeley. Susan H. Xu is a Professor in the Department of Management Science and Information Systems at the Pennsylvania State University. Both authors research interests are in stochastic modeling and applications.