Admission Policies in Loss Queueing Models with Heterogeneous Arrivals

0025-1909/98/4403/0311$05.00 Copyright q 1998, Institute for Operations Research and the Management Sciences M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 311 3b24 0011 Mp 311 Monday Mar 09 09:37 AM Man Sci (January) 0011 Admission Policies in Loss Queueing Models with Heterogeneous Arrivals E. Carrizosa j E. Conde j M. Mun˜oz-Ma´rquez Facultad de Matema´ticas, Universidad de Sevilla, Tarfia s/n, 41012 Sevilla, Spain Facultad de Matema´ticas, Universidad de Sevilla, Tarfia s/n, 41012 Sevilla, Spain Departamento de Matema´ticas, Universidad de Ca´diz, Sacramento 82, Escuela Polite´cnica de Ca´diz, 11002 Ca´diz, Spain I nthispaperweconsideralosssystemwherethearrivalscanbeclassifiedintodifferentgroups according to their arrival rate and expected service time. While the standardadmissionpolicy consists of rejecting only those customers who arrive when all servers are busy, we address the problem of finding the optimal static admission policy (with respect toa givenrewardstructure) when customers can be discriminated according to the group they belong to, thus customers of some groups might be automatically rejected (even if some servers remain idle) in order to enhance the global efficiency of the system. The optimality of a c m -rule is shown, from which finite-time algorithms for the one- and two-server cases are derived. (Algorithms;Multichannel Queues;Nonlinear Programming;Optimization) 1. Introduction Motivated by real-world applications, there hasbeenan increasing interest in the optimal design and control of queueing models (see, e.g., Crabill et al. 1977, Harel 1990, Hillier and Lieberman 1990, Mendelson and Whang 1990, Viscolani 1993, Walrand 1988, Zipkin 1986, and the references therein), where the set of parameters that optimize a certain performance measure is sought. In these problems, the controllable parameters are usually the number of servers, the arrival and service rate, and the capacity of the system. Finding the optimal values of the controllableparameters is usually reduced to solving a mathematical program, where the controllable parameters play the role of decision variables, and the objective function to be optimized is the performance measure. The determination of such optimal parameters provides operation rules that optimize the performance of the system. In this paper we address a design problem for a loss system with heterogeneous arrivals, where it is sought the optimal coverage with respect to a given cost structure: any accepted (respectively, rejected) customer induces a cost or disutility r(respectively, rˆ), with r õ rˆ, and the performance measure is the expected disutility per unit time. A direct application of this model appears when one has a queueing system with hierarchical service facilities: a primary and a back-up facility. Suppose that the nature of the service is such that no queue is allowed at the primary facility; hence, any customer finding the primary facility busy must be rerouted and served at a higher cost by the back-up system. Then, minimizing the overall cost does not mean allocating to the primary facility all the customers finding some of its servers available, but finding an optimal allocation rule. This situation appears, e.g., when one introduces mobile emergency units to serve a certain community, where one has different points, representing populated areas (towns, . . .); according to their own features, eacharea has its own arrival rate and service time, related with the distance from the home location of the servers tothe area (Chiu and Larson 1985). Any call finding all the units busy is served by an exogenous system (at a higher cost). Since service times are dependent oftravel times, it should be intuitively obvious that the optimization of the system performance—e.g., by maximizing CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 312 M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 3b24 0011 Mp 312 Monday Mar 09 09:37 AM Man Sci (January) 0011 the expected number of calls served—would imply to serve just those customers close enough to the facility, condemning the outliers to be systematically served by the exogenous server. Applications of this approach to Computer Science can be found in Xu et al. (1992). See also Miller (1969) for another rejection model in loss systems. In spite of their practical interest, these rejectionspolicies have not been extensively considered in the literature (some exceptions are Batta 1988, Lippman and Ross 1971), mainly due to the mathematical difficulties inherent to such models. Needless to say also that a much harder to analyze dynamic control of the system, taking into account the number of busy servers and theirremainingprocessing timeis to outperformastatic policy, which decides whether to accept or not according to just the group the customer belongs to and the existence of idle servers. Nevertheless, there are situations where obtaining in real time the information needed by dynamic rules is so costly or difficult that one can use a static model as an approximation to the much less tractable dynamic models. The rest of the paper is organized as follows. In §2 the model is formally introduced, and some properties of the corresponding mathematical program are discussed. Section 3 is devoted to the statement of optimality conditions and localization results on the optimal solution, which are used in §4 to design resolution procedures. The paper ends presenting some conclusions and extensions in §5. 2. The Model Let J Å {1,2,...,n} represent ntypes of customers requesting service of a system consisting of a finite number cof identical servers. Customers of type i(hereafter called i-customers) arrive following a Poisson process with rate l i ú 0, the arrival processes of the different groups being independent. The duration of each icustomer service is modelled as a random variable with means i (0 õ s i õ` ). No queueis allowed, whichmeans that an arrival that finds the cservers busy is referred to a back-up service system. In addition, anyi-customer that arrives when at least one facility is idle is accepted (and its service starts immediately) with probability x i , and is rejected (rerouted) with probability 1 0 x i , the x i ’s being controllable variables. Any accepted (respectively, lost) i-customer induces a cost to the system of r i (respectively, rˆ i ) monetary units, where r i õ rˆ i . Under the assumptions above, the goal is to determine the value of x Å (x 1 ,...,x n ) that minimizes the expected cost per unit time. Obviously, given x √ [0, 1] n , this system behaves as an M/G/c/csystem with arrival rate l (x) and mean service time s(x) given by n l (x) Ål x, ∑ ii iÅ1 n l x ii s(x) Å s, ∑ i l (x) iÅ1 with the convention that s(x) Å 0if l (x) Å 0. Let rÅ ( r 1 ,..., r n ) denote the vector of loads offered by the different groups of customers, i.e., rÅl s,i Å 1,2,...,n. iii Then, the fraction of time that at least one out of the c servers is idle is given by C c ( r· x), where u · vdenotes the usual scalar product in R n and C c (t) is the fraction of time that an M/G/c/csystem with offered loadthas at least one server idle, (see Kleinrock 1975), i.e., c01k ( t/k! kÅ0 C (t) Å . cck ( t/k! kÅ0 The expected number of i-customers per unit time that enter into the system is given by l i x i C c ( r· x), and the expected number of rejected i-customers per unit time equals l i (1 0 x i ) /l i x i (1 0C c ( r· x)) Ål i (1 0 x i C c ( r· x)). Hence, the expected total cost per unit time is given by nn C ( r· x) l rx /l P r(1 0 x C ( r· x)). (2.1) ∑∑ ciiiiiic iÅ1iÅ1 For each i Å 1,2,...,n, define the rejection surcharge D i as the difference between the individual cost of rejected and accepted i-customers, i.e., DÅ P r 0 r. iii In terms of these parameters, the main result of the paper—Theorem 3.4—states that the optimal policy is ac m -rule, since it discriminates groups according to the ratios ( D i )/s i , i.e., customers are sorted according to a CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 313 3b24 0011 Mp 313 Monday Mar 09 09:37 AM Man Sci (January) 0011 Figure 1 F Is Not Concave single measure: the rejection surcharge per unit service time. Since (2.1) turns out to be nn l P r 0C ( r· x) lD x, ∑∑ ii c i i i iÅ1iÅ1 determining the vector xminimizing the expected cost perunittime is equivalenttosolvingthefollowingmaximization problem n max C ( r· x) lD x, ∑ ciii iÅ1 n s.t. x √ [0, 1] . To simplify the notation, we first transform the cost structure into an equivalent one by making the two following assumptions. A SSUMPTION A1. We assume that DÅ 1 ∀ i Å 1,...,n. (A1) i Assumption A1 supposes no loss of generality. Indeed, if A1 did not hold, one could define for each i Å 1,2,...,n HlÅlD , iii I s Å s/ D ,. (2.2) iii HDÅ 1 i Then, it is easily seen that the system withparameters gives for all x √ [0, 1] n the same value of the Hl , I s, HD ii i performance measure as the original system. A SSUMPTION A2. We assume that s õ s õ··· õ s. (A2) 12 n Assumption A2 supposes no loss of generality. Indeed, if s i Å s j for some i,j,i x j, we can construct an equivalent system with n 0 1 types of customers, where groups iand jare mixed in one group with arrival rate l i /l j and mean service time s i Å s j , and, after relabelling the groups, if necessary, the Assumption A2 is verified. Hereafter, unless explicitely mentioned, we assume that Assumptions A1 and A2 hold, and stress that this is done just for notational convenience; if they do not hold, one can always transform the original parameters using (2.2) and sorting the service times. Under such assumptions, the mathematical program of interest is max F(x) Å ( l· x) C ( r· x), c n s.t. x √ [0, 1] , (P) where lÅ ( l 1 ,..., l n ). As Fis continuous and the feasible set is compact, the maximum of (P) is attained at some x* √ [0, 1] n . The case n Å 1 (homogeneous arrivals) is straightforward: F(x) gives then the throughput of an M/G/c/c system with expected service time s 1 and arrival rate l 1 x 1 , which is concave (see Harel 1990) and obviously increasing in x 1 . Hence, the optimal solution is , * x Å 1 1 which corresponds to the policy of rejecting only those customers who find the cservers busy. Unfortunately, these properties do not extend to the case n ú 1 and contrary to most models encountered in the literature (Grassman 1983, Harel 1990, Harel and Zipkin 1987, Viscolani 1993, Yao and Shantikumar1987, Zipkin 1986 among others), Fis not concave, see Figure 1. This, at least at first glance, makes the optimization process more difficult. In spite of its lack of concavity, Fenjoys interesting mathematical properties (in fact some generalized con- CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 314 M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 3b24 0011 Mp 314 Monday Mar 09 09:37 AM Man Sci (January) 0011 cavity), as shown in Theorem 2.1). We recall that a differentiable function gon a convex set Sis said to be pseudoconcave iff Ç g(x) · (y 0 x) ú 0 whenever x,y √ S,g(y) ú g(x). See, e.g., Avriel et al. (1988) or Martos (1977) forfurther properties on pseudoconcave functions. T HEOREM 2.1. F is pseudoconcave. The proof can be found in the appendix. See also Barros and Frenk (1995) for another ‘‘tractable’’ queueing model with nonconcave objective function. 3. Optimality Conditions The purpose of this section is to state optimality conditions for problem (P). Expressing Fas in (7.1), we see that (P)isanonlinear fractional program with convex feasible region (the n-cube [0, 1] n ) and pseudoconcave objective function (Theorem 2.1). The pseudoconcavity of Fenables the statement of optimality conditions in terms of the gradient Ç Fof F(see, e.g., Corollary 7.49 of Martos 1977). More precisely, if we denote by D(x) the set of feasible directions at x √ [0, 1] n , then n x √ [0, 1] is an optimal solution to (P)(3.1) iff Ç F(x) · d ° 0 ∀ d √ D(x). The gradient of Fis easily obtained, Ç F(x) ÅlC ( r· x) c (3.2) n / ( l· x) C* ( r· x) r∀ x √ [0, 1] . c We will combine (3.1) and (3.2) above to obtain optimality conditions. First we show that no interior point xcan be optimal. L EMMA 3.1. Suppose that x Å (x 1 ,...,x n )is an optimal solution to (P), and 0 õ x k õ 1. Then, 0C ( r· x) c s Å . k ( l· x) C* ( r· x) c P ROOF . Let e k be the vector with 1 at the kth coordinate and zeros everywhere else. As 0 õ x k õ 1, both e k and 0 e k are feasible directions, which, by (3.1), implies that k Ç F(x) · e Å 0 By (3.2), the result follows. h The next lemma shows that any optimal policy is deterministic except for at most one class of customers. L EMMA 3.2. If x is an optimal solution to (P), then x has at most one fractional component. The proof is straightforward by the lemma above and Assumption A2. h This result leads to an interesting consequence about the geometrical structure of the set of optimal solutions, stated in the theorem below. T HEOREM 3.1. The set of optimal solutions to (P)is a closed (possibly degenerate)segment contained in an edge of [0, 1] n . P ROOF . As, by Theorem 2.1, Fis pseudoconcave, it is continuous and quasiconcave (see Theorem 7.28 of Martos 1977). Hence, the set Sof optimal solutions to (P) is a closed convex set. Furthermore, Sis contained in an edge of [0, 1] n . Indeed, else, there would exist x 1 , x 2 √ Snot contained in the same edge. By convexity of Sand the quasiconcavity of F, the whole segment with endpoints x 1 and x 2 would consist of optimal solutions. Then there would exist an optimal solution with atleast two fractional components, which, by Lemma 3.2, is a contradiction. Hence, the result holds. h C OROLLARY 3.1. If c ú 1,then the set of optimal solutions to (P)is a singleton. See the appendix for the proof. R EMARK 3.1. If c ú 1, the corollary above shows that there exists a unique optimal solution. However, if c Å 1, (P) might have multiple optimal solutions. As a simple example, take n Å 2, l 1 Ål 2 Å 1, s 1 Å 1, s 2 Å 2. Then, it is easily checked that the set of optimal solutions to (P) is the closed segment with endpoints (1, 0) and (1, 1). In fact, it will be shown in §4 that, for c Å 1, the set of optimal policies consists of either one nonrandomized policy or the set of mixtures of two nonrandomized policies. By the theorem above, any optimal solution xto (P) must be either a vertex or a point on an edge of [0, 1] n , thus the search of optimal solutions to (P) is reduced to the 0- and one-dimensional faces of the n-cube [0, 1] n . CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 315 3b24 0011 Mp 315 Monday Mar 09 09:37 AM Man Sci (January) 0011 Figure 2 The Set a ([0, n ]) when n Å 3 We state below the corresponding optimality conditions. Define, for each x √ [0, 1] n the sets I(x) and J(x) as I(x) Å {i:x Å 0}, J(x) Å {i:x Å 1}. ii T HEOREM 3.2. (optimality conditions at a vertex) Let x x 0be a vertex of [0,1] n .Then,x is an optimalsolution to (P)iff 0C ( r· x) c min s ¢¢ max s. (3.3) ii ( l· x) C* ( r· x) i√I(x)i√J(x) c The proof can be found in the appendix. T HEOREM 3.3. (optimality conditions on edges). Let x √ [0, 1] n be such that 0 õ x k õ 1for some k,and x i √ {0, 1} ∀ i x k.Then,x is an optimal solution to (P)iff 0C ( r· x) c min s ú s Åú max s. (3.4) ik i ( l· x) C* ( r· x) i√I(x)i√J(x) c The proof of this theorem runs parallel to that of the theorem above, just taking into account Lemma 3.1 and Assumption A2. h R EMARK 3.2. Although the conditions (3.3) and (3.4) have been obtained under Assumptions A1 and A2, they lead to a meaningful interpretation in terms of the originalsetting:Itis optimal to serveonlythosecustomers whose rejection surcharge per unit service time is high enough. The results stated so far suggest anaı¨veprocedurefor solving (P): Evaluate the 2 n vertices of [0, 1] n , and solve the n2 n01 one-dimensional nonlinear fractional programs obtained by optimizing Fon each edge. However, we can go much further; as shown below, neither all the vertices nor all the edges are true candidates to contain optimal solutions. For this purpose, let v i ,i Å 0,...,nbe the vector with 1 at the first icoordinates and 0 everywhere else. Let a :[0,n] r [0, 1] n be the natural parametrization of the path through v 0 ,v 1 ,...,v n (see Figure 2 for an illustration of a when n Å 3). The next theorem shows that any optimal solution must be contained in the path a ([0, n]), i.e., since, by Assumption A2, the service times are given in increasing order, the optimal policy belongs to the class of c m rules. T HEOREM 3.4. If x is an optimal solution to (P), then there exists some t,0 õ t ° n such that x Åa (t). P ROOF . By Lemma 3.2, xhas at most one fractional component, thus either (3.3) or (3.4) apply. Hence, A2 implies that if x Å 0, then x Å 0 ∀ j ú i ij , (3.5) J if x ú 0, then x Å 1 ∀ j õ i ij thus x Åa (t) for some t. h R EMARK 3.3. The c m -rule optimality is no longer true when one restricts the set of policies to nonrandomized ones, i.e., when, instead of solving (P) one wants to solve its {0, 1}-version (P NR ) max F(x), n s.t. x √ {0, 1} . (P NR ) For instance, if we take c Å 2, n Å 3, l 1 Å 1, s 1 Å 1, l 2 Å 10, s 2 Å 2.5, l 3 Å 0.5, s 3 Å 0.75, it is easily seen that the optimal solution to (P NR ) is the vector x* Å (1, 0, 1), which is not in the path { a (t):t √ [0, 3]}. The theorem above shows that (P)isequivalenttothe one-dimensional problem (P ˜) ˜ max F(t) Å F( a (t)), (s.t. t √ [0, n]. (P ˜) As a ( · ) is not differentiable at integer points, F ˜might not be differentiable, but it remains directionally differentiable. CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 316 M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 3b24 0011 Mp 316 Monday Mar 09 09:37 AM Man Sci (January) 0011 Figure 3 The F ˜ Corresponding to F of Figure 1 What does not seem so intuitive is the fact that F ˜( · ) is also unimodal. As an example, Figure 3 shows the F ˜ corresponding to the function Fof Figure 1. In fact, as the next theorem shows, F ˜( · ) is a directionally differentiable (although non-differentiable) semilocally pseudoconcave function on [0, n], i.e., ˜˜˜ F * (t;s–t) ú 0 whenever F(s) ú F(t), s,t √ [0, n] where F ˜ * (t;s–t) stands for the directional derivative of F ˜at tin the direction s–t. See Kaul and Kaur (1982) for further results on this concept. T HEOREM 3.5. F ˜( · )is semilocally pseudoconcave on [0, n]. For the proof, see the appendix. 4. Finding an Optimal Rejection Policy In the section above we have shown that finding an optimal policy is equivalent to solving the onedimensional problem (P ˜), ˜ max F(t) Å F( a (t)), s.t. t √ [0, n]. (P ˜) Furthermore, by Theorem 3.5 the objective functionis semilocally pseudoconcave, which enables the resolution (up to a prespecified accuracy e )of(P ˜) by a variety of well-known methods (see, e.g., Chapter 8 of Bazaraa and Shetty 1979). An illustration is given in the next example. E XAMPLE 4.1. Consider a system with c Å 3 servers and n Å 8 classes of customers. The i-customers arrive following a Poisson process with arrival rate l i Å 1 and have expected service time s i Å i 3 /10, i Å 1,...,8. The graph of F ˜is plotted in Figure 4, and Figure 5 represents the portion boxed in Figure 4. Note that F ˜ attains its maximum at a noninteger point, i.e., optimality is attained at a randomized rejection policy. In order to solve (P ˜), we have chosen the golden section method (see, e.g., Bazaraa and Shetty 1979). For a prespecified accuracy of eÅ 0.001 we needed 18 iterations; the results are shown in Table 1. CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 317 3b24 0011 Mp 317 Monday Mar 09 09:37 AM Man Sci (January) 0011 Figure 4 The Graph of F ˜ Hence, we take as solution the point t* Å 2.18013, which gives F ˜(t*) Å 1.92477, and corresponds to the following policy: when an arriving i-customer finds at least one server idle, it is rejected by the system with probability 0 if i Å 1, 2; with probability 3–t* Å 0.81987 if i Å 3 and with probability 1 if i ú 3. h The methodology above applies for any value of c. However, when c ° 2, the functions Fand F ˜have a much simpler shape, which enables us to solve exactly the problem (P ˜) and also (P) in finite time. We explore first the single-server case, i.e., c Å 1. Then, (P) takes the form max F(x) Å ( l· x)/(1 /r· x), n s.t. x √ [0, 1] . (P) This implies that (P) becomes a linear fractional program, thus the objective function Fis not only pseudoconcave but pseudomonotonic. See, e.g., Avriel et al. (1988) or Martos (1977) for further properties on this class of functions. The single-server assumption enables to strengthen or ease some of the results obtained in previous sections. For instance, we know from §3 that the set Sof optimal solutions to (P) might not be a singleton, but is containedin an edgeof[0, 1] n .Thepseudomonotonicity of Fimplies that Smust equal the convex hull of the optimal vertices. Hence, Smust have one of the two following forms: 1. The singleton { a (k)} for some k √ {1,2,...,n}. 2. The closed segment with endpoints{ a (k)}and{ a (k / 1)} for some k √ {1,2,...,n 0 1}. In other words, there always exists some ksuch that the nonrandomized policy consisting of automatically rejecting all the i-customers (i ú k) and serving every i-customer (i Å 1,2,...,k) who finds idle servers is optimal. Hence, in CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 318 M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 3b24 0011 Mp 318 Monday Mar 09 09:37 AM Man Sci (January) 0011 Figure 5 F ˜ Attains Its Maximum at a Noninteger Point Table 1 Solving by the Golden Section Method ( H P ) Iterat. Accuracy Optimal Interval 1 3.05573 (0.00000, 4.94427) 2 1.88854 (0.00000, 3.05573) 3 1.16718 (1.16718, 3.05573) 4 0.72136 (1.88854, 3.05573) 5 0.44582 (1.88854, 2.60990) ··· ··· 16 0.00224 (2.17719, 2.18082) 17 0.00138 (2.17858, 2.18082) 18 0.00086 (2.17943, 2.18082) order to find an optimal policy we can restrictourattention to the set { a (1), a (2), ..., a (n)} as candidate points (i.e., { a (1), a (2), ..., a (n)} is a finite dominating set, see Hooker et al. 1991), which suggests the following approach: Evaluate Fat a (i) for all i, and take as optimal solution the a (i*) giving the highest value of F. This simple algorithm runs in O(n 2 ) time, which is acceptable for moderate values of n.Ifnis so large that even an O(n 2 ) computing time should be considered as prohibitive, more subtle procedures can be used. Indeed, as shown in Hansen et al. (1991), it is possible to use binary search techniques to obtain an overall complexity of O(n) time and space. We examine now the case c Å 2. It is rather easy to find the integer ksuch that the optimal solution to (P ˜) either is kor belongs to the open interval (k,k / 1). Indeed, such conclusion can be obtained after checking the optimality conditions at vertices and performing some iterations of, for instance, a binary-search procedure. If kis optimal to (P ˜), then a (k) is optimal to (P). On the contrary, if the optimal solution is t* √ (k,k / 1), then, by the semilocal pseudoconcavity of F ˜,t*is the unique root in (k,k / 1) of the nonlinear equation ˜ F * (t) Å 0. (4.1) By (7.5), it is easily seen that when c Å 2, (4.1) can be written in the form Q(t) Å 0, where Qis a polynomium ofdegreenotgreaterthan3.Hence,theoptimalsolution to (P ˜) is the unique root of Qin (k,k / 1), which, as is well-known, can be obtained exactly. 5. Conclusions In this paper we have addressed a design problem associated with a loss model with heterogeneousarrivals, where the decision variables represent the probability CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models M ANAGEMENT S CIENCE /Vol. 44, No. 3, March 1998 319 3b24 0011 Mp 319 Monday Mar 09 09:37 AM Man Sci (January) 0011 that a customer of each class is rejected by the system when he finds some servers idle. After imposing a cost structure on the model, the search of a cost-optimal policy is reduced to solving a nonlinear mathematical program. The objective function of the problem addressed may not be concave; nevertheless, we state some properties of the problem (optimality of a c m -rule) that enable us to reduce the optimization to solving an equivalent unimodal onedimensionalproblemforwhichseveralwell-knownres- olution techniques can be applied. Finally, we have shown that an optimal policy forthe two-server case can be found as a root of a polynomial function of degree 3, whilst the one-server case leads to a linear fractional program with a simple structure, which can be solved in O(n 2 ) time by straightforward techniques, and in linear time by binary search. Extensions of these results to systems governed by dynamic state-dependent policies, or to M/G/1/ ` systems are interesting questions which remain open. 1 1 The research of the authors is partially supported by Spanish DGICYT grant PB93-0927. This support is gratefully acknowledged. Appendix L EMMA 7.1. The function 1/ C c ( · )is convex on [0, ` ). Moreover,if c ú 1then 1/ C c ( · )is strictly convex on [0, ` ). P ROOF . The case c Å 1 is straightforward (1/ C 1 (t) Å 1 / t), so we consider only the case c ú 1. As ck ( t/k!t kÅ0 1/ C (t) ÅÅ 1 / (1 0C (t)), cc01 c01k ( t/k!c kÅ0 and the function t ° t C c01 (t) is concave (see, e.g., Corollary 1ofHarel 1990), it follows that 1/ C c ( · ) is convex. In order to check that it is also strictly convex, observe that, otherwise, 1/ C c ( · ) should be a polynomial of degree at most one in some nondegenerate interval I, i.e., there would exist a , b such that ck ( t/k! kÅ0 Åa t /b∀ t √ I. c01k ( t/k! kÅ0 Equating coefficients, one would obtain aÅ 0 Å 1/c, which is a contradiction. h P ROOF OF T HEOREM 2.1. Observe that l· x F(x) Å . (7.1) 1/ C ( r· x) c By Lemma 7.1, the function t ° 1/ C c (t) is convex. Hence, its composition with the linear function x °r· xis convex. Hence, Fis the quotient of a nonnegative linear and a positive convex function, thus Fis pseudoconcave, as asserted. h P ROOF OF C OROLLARY 3.1. Suppose, on the contrary, that (P) has at least two different optimal solutions x,y. Then, by the theorem above, both xand ybelong to the same edge of [0, 1] n . Within the interval Iof endpoints x,y, one deduces from Theorem 5.17 of Avriel et al. (1988) and our Lemma 7.1 that Fis strictly pseudoconcave on I, which is a contradiction with the simultaneous optimality of xand y. h P ROOF OF T HEOREM 3.2. First, observe that C c (t) is strictlydecreasing in t(see Harel 1990), i.e., C* (t) õ 0 ∀ t. (7.2) c Define, for each i Å 1,...,n, the vector e i as in the proof of Lemma 3.1. Obviously ii D(x) Å cone({e:i √ I(x)} < { 0 e:i √ J(x)}), (7.3) where cone (A) represents the cone generated by the elements of A. Hence, by (3.1), (3.2), and (7.3), it follows that xis optimal iff lC ( r· x) / ( l· x) C* ( r· x) r° 0 ∀ i √ I(x), ic c i 5 lC ( r· x) / ( l· x) C* ( r· x) r¢ 0 ∀ i √ J(x), ic c i which, by (7.2), turns out to be equivalent to (3.3). h P ROOF OF T HEOREM 3.5. For each k Å 1,...,nlet the vector e k be defined as in the proof of Lemma 3.1. We will just show that F ˜( · )is semilocally pseudoconcave at noninteger points t √ [0, n], namely, ˜ s,t √ [0, n], s x t,F * (t;s 0 t) ° 0(7.4) ˜ implies H F(s) ° F(t). The proof for integer points tis completely analogous and will not be given here. Hence, we assume that t √ [0, n] is not integer, thus there exists k √ {0,1,...,n 0 1} such that k õ t õ k / 1. Within the interval [k,k / 1] the function F ˜takes the form ˜ F(s) Ål/l (s 0 k) ∑ ik SD iõk ·Cr/r (s 0 k) ∀ s √ [k,k / 1]. ∑ cik SD iõk Hence, F ˜is differentiable at t, and k H F * (t) ÅÇ F( a (t)) · e ÅlC ( r·a (t)) / ( l·a (t)) C* ( r·a (t)) r . (7.5) kc c k Hence, one has H F * (t) ° 0 iff C ( r·a (t)) / ( l·a (t)) C* ( r·a (t)) s ° 0. cck Since, by (7.2) and A2,