Admission Policies in Loss Queueing Models with Heterogeneous Arrivals

0025-1909/98/4403/0311$05.00 Copy igh q 1998, Ins i u e o Ope a ions Resea ch and he Managemen Sciences M ANAGEMENT S CIENCE /Vol. 44, No. 3, Ma ch 1998 311 3b24 0011 Mp 311 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 Admission Policies in Loss Queueing Models wi h He e ogeneous A i als E. Ca izosa j E. Conde j M. Mun˜oz-Ma´ quez Facul ad de Ma ema´ icas, Uni e sidad de Se illa, Ta ia s/n, 41012 Se illa, Spain Facul ad de Ma ema´ icas, Uni e sidad de Se illa, Ta ia s/n, 41012 Se illa, Spain Depa amen o de Ma ema´ icas, Uni e sidad de Ca´diz, Sac amen o 82, Escuela Poli e´cnica de Ca´diz, 11002 Ca´diz, Spain I n hispape weconside alosssys emwhe e hea i alscanbeclassi iedin odi e en g oups acco ding o hei a i al a e and expec ed se ice ime. While he s anda dadmissionpolicy consis s o ejec ing only hose cus ome s who a i e when all se e s a e busy, we add ess he p oblem o inding he op imal s a ic admission policy (wi h espec oa gi en ewa ds uc u e) when cus ome s can be disc imina ed acco ding o he g oup hey belong o, hus cus ome s o some g oups migh be au oma ically ejec ed (e en i some se e s emain idle) in o de o enhance he global e iciency o he sys em. The op imali y o a c m - ule is shown, om which ini e- ime algo i hms o he one- and wo-se e cases a e de i ed. (Algo i hms;Mul ichannel Queues;Nonlinea P og amming;Op imiza ion) 1. In oduc ion Mo i a ed by eal-wo ld applica ions, he e hasbeenan inc easing in e es in he op imal design and con ol o queueing models (see, e.g., C abill e al. 1977, Ha el 1990, Hillie and Liebe man 1990, Mendelson and Whang 1990, Viscolani 1993, Wal and 1988, Zipkin 1986, and he e e ences he ein), whe e he se o pa- ame e s ha op imize a ce ain pe o mance measu e is sough . In hese p oblems, he con ollable pa ame- e s a e usually he numbe o se e s, he a i al and se ice a e, and he capaci y o he sys em. Finding he op imal alues o he con ollablepa am- e e s is usually educed o sol ing a ma hema ical p o- g am, whe e he con ollable pa ame e s play he ole o decision a iables, and he objec i e unc ion o be op imized is he pe o mance measu e. The de e mi- na ion o such op imal pa ame e s p o ides ope a ion ules ha op imize he pe o mance o he sys em. In his pape we add ess a design p oblem o a loss sys em wi h he e ogeneous a i als, whe e i is sough he op imal co e age wi h espec o a gi en cos s uc- u e: any accep ed ( espec i ely, ejec ed) cus ome in- duces a cos o disu ili y ( espec i ely, ˆ), wi h õ ˆ, and he pe o mance measu e is he expec ed disu ili y pe uni ime. A di ec applica ion o his model appea s when one has a queueing sys em wi h hie a chical se ice acili- ies: a p ima y and a back-up acili y. Suppose ha he na u e o he se ice is such ha no queue is allowed a he p ima y acili y; hence, any cus ome inding he p ima y acili y busy mus be e ou ed and se ed a a highe cos by he back-up sys em. Then, minimizing he o e all cos does no mean alloca ing o he p ima y acili y all he cus ome s inding some o i s se e s a ailable, bu inding an op imal alloca ion ule. This si ua ion appea s, e.g., when one in oduces mobile eme gency uni s o se e a ce ain communi y, whe e one has di e en poin s, ep esen ing popula ed a eas ( owns, . . .); acco ding o hei own ea u es, eacha ea has i s own a i al a e and se ice ime, ela ed wi h he dis ance om he home loca ion o he se e s o he a ea (Chiu and La son 1985). Any call inding all he uni s busy is se ed by an exogenous sys em (a a highe cos ). Since se ice imes a e dependen o a el imes, i should be in ui i ely ob ious ha he op imi- za ion o he sys em pe o mance—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, Ma ch 1998 3b24 0011 Mp 312 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 he expec ed numbe o calls se ed—would imply o se e jus hose cus ome s close enough o he acili y, condemning he ou lie s o be sys ema ically se ed by he exogenous se e . Applica ions o his app oach o Compu e Science can be ound in Xu e al. (1992). See also Mille (1969) o ano he ejec ion model in loss sys ems. In spi e o hei p ac ical in e es , hese ejec ionspol- icies ha e no been ex ensi ely conside ed in he li e - a u e (some excep ions a e Ba a 1988, Lippman and Ross 1971), mainly due o he ma hema ical di icul ies inhe en o such models. Needless o say also ha a much ha de o analyze dynamic con ol o he sys em, aking in o accoun he numbe o busy se e s and hei emainingp ocessing imeis o ou pe o mas a ic policy, which decides whe he o accep o no acco d- ing o jus he g oup he cus ome belongs o and he exis ence o idle se e s. Ne e heless, he e a e si ua- ions whe e ob aining in eal ime he in o ma ion needed by dynamic ules is so cos ly o di icul ha one can use a s a ic model as an app oxima ion o he much less ac able dynamic models. The es o he pape is o ganized as ollows. In §2 he model is o mally in oduced, and some p ope ies o he co esponding ma hema ical p og am a e dis- cussed. Sec ion 3 is de o ed o he s a emen o op i- mali y condi ions and localiza ion esul s on he op i- mal solu ion, which a e used in §4 o design esolu ion p ocedu es. The pape ends p esen ing some conclu- sions and ex ensions in §5. 2. The Model Le J Å {1,2,...,n} ep esen n ypes o cus ome s e- ques ing se ice o a sys em consis ing o a ini e num- be co iden ical se e s. Cus ome s o ype i(he ea e called i-cus ome s) a i e ollowing a Poisson p ocess wi h a e l i ú 0, he a i al p ocesses o he di e en g oups being independen . The du a ion o each i- cus ome se ice is modelled as a andom a iable wi h means i (0 õ s i õ` ). No queueis allowed, whichmeans ha an a i al ha inds he cse e s busy is e e ed o a back-up se ice sys em. In addi ion, anyi-cus ome ha a i es when a leas one acili y is idle is accep ed (and i s se ice s a s immedia ely) wi h p obabili y x i , and is ejec ed ( e ou ed) wi h p obabili y 1 0 x i , he x i ’s being con ollable a iables. Any accep ed ( espec- i ely, los ) i-cus ome induces a cos o he sys em o i ( espec i ely, ˆ i ) mone a y uni s, whe e i õ ˆ i . Unde he assump ions abo e, he goal is o de e - mine he alue o x Å (x 1 ,...,x n ) ha minimizes he expec ed cos pe uni ime. Ob iously, gi en x √ [0, 1] n , his sys em beha es as an M/G/c/csys em wi h a i al a e l (x) and mean se ice ime s(x) gi en by n l (x) Ål x, ∑ ii iÅ1 n l x ii s(x) Å s, ∑ i l (x) iÅ1 wi h he con en ion ha s(x) Å 0i l (x) Å 0. Le Å ( 1 ,..., n ) deno e he ec o o loads o e ed by he di e en g oups o cus ome s, i.e., Ål s,i Å 1,2,...,n. iii Then, he ac ion o ime ha a leas one ou o he c se e s is idle is gi en by C c ( · x), whe e u · deno es he usual scala p oduc in R n and C c ( ) is he ac ion o ime ha an M/G/c/csys em wi h o e ed load has a leas one se e idle, (see Klein ock 1975), i.e., c01k ( /k! kÅ0 C ( ) Å . cck ( /k! kÅ0 The expec ed numbe o i-cus ome s pe uni ime ha en e in o he sys em is gi en by l i x i C c ( · x), and he expec ed numbe o ejec ed i-cus ome s pe uni ime equals l i (1 0 x i ) /l i x i (1 0C c ( · x)) Ål i (1 0 x i C c ( · x)). Hence, he expec ed o al cos pe uni ime is gi en by nn C ( · x) l x /l P (1 0 x C ( · x)). (2.1) ∑∑ ciiiiiic iÅ1iÅ1 Fo each i Å 1,2,...,n, de ine he ejec ion su cha ge D i as he di e ence be ween he indi idual cos o e- jec ed and accep ed i-cus ome s, i.e., DÅ P 0 . iii In e ms o hese pa ame e s, he main esul o he pape —Theo em 3.4—s a es ha he op imal policy is ac m - ule, since i disc imina es g oups acco ding o he a ios ( D i )/s i , i.e., cus ome s a e so ed acco ding o a CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models M ANAGEMENT S CIENCE /Vol. 44, No. 3, Ma ch 1998 313 3b24 0011 Mp 313 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 Figu e 1 F Is No Conca e single measu e: he ejec ion su cha ge pe uni se ice ime. Since (2.1) u ns ou o be nn l P 0C ( · x) lD x, ∑∑ ii c i i i iÅ1iÅ1 de e mining he ec o xminimizing he expec ed cos pe uni ime is equi alen osol ing he ollowingmax- imiza ion p oblem n max C ( · x) lD x, ∑ ciii iÅ1 n s. . x √ [0, 1] . To simpli y he no a ion, we i s ans o m he cos s uc u e in o an equi alen one by making he wo ol- lowing assump ions. A SSUMPTION A1. We assume ha DÅ 1 ∀ i Å 1,...,n. (A1) i Assump ion A1 supposes no loss o gene ali y. In- deed, i A1 did no hold, one could de ine o each i Å 1,2,...,n HlÅlD , iii I s Å s/ D ,. (2.2) iii HDÅ 1 i Then, i is easily seen ha he sys em wi hpa ame e s gi es o all x √ [0, 1] n he same alue o he Hl , I s, HD ii i pe o mance measu e as he o iginal sys em. A SSUMPTION A2. We assume ha s õ s õ··· õ s. (A2) 12 n Assump ion A2 supposes no loss o gene ali y. In- deed, i s i Å s j o some i,j,i x j, we can cons uc an equi alen sys em wi h n 0 1 ypes o cus ome s, whe e g oups iand ja e mixed in one g oup wi h a i al a e l i /l j and mean se ice ime s i Å s j , and, a e ela- belling he g oups, i necessa y, he Assump ion A2 is e i ied. He ea e , unless explici ely men ioned, we assume ha Assump ions A1 and A2 hold, and s ess ha his is done jus o no a ional con enience; i hey do no hold, one can always ans o m he o iginal pa ame e s using (2.2) and so ing he se ice imes. Unde such assump ions, he ma hema ical p og am o in e es is max F(x) Å ( l· x) C ( · x), c n s. . x √ [0, 1] , (P) whe e lÅ ( l 1 ,..., l n ). As Fis con inuous and he easible se is compac , he maximum o (P) is a ained a some x* √ [0, 1] n . The case n Å 1 (homogeneous a i als) is s aigh o - wa d: F(x) gi es hen he h oughpu o an M/G/c/c sys em wi h expec ed se ice ime s 1 and a i al a e l 1 x 1 , which is conca e (see Ha el 1990) and ob iously inc easing in x 1 . Hence, he op imal solu ion is , * x Å 1 1 which co esponds o he policy o ejec ing only hose cus ome s who ind he cse e s busy. Un o una ely, hese p ope ies do no ex end o he case n ú 1 and con a y o mos models encoun e ed in he li e a u e (G assman 1983, Ha el 1990, Ha el and Zipkin 1987, Viscolani 1993, Yao and Shan ikuma 1987, Zipkin 1986 among o he s), Fis no conca e, see Figu e 1. This, a leas a i s glance, makes he op imiza ion p ocess mo e di icul . In spi e o i s lack o conca i y, Fenjoys in e es ing ma hema ical p ope ies (in ac some gene alized con- CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 314 M ANAGEMENT S CIENCE /Vol. 44, No. 3, Ma ch 1998 3b24 0011 Mp 314 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 ca i y), as shown in Theo em 2.1). We ecall ha a di - e en iable unc ion gon a con ex se Sis said o be pseudoconca e i Ç g(x) · (y 0 x) ú 0 whene e x,y √ S,g(y) ú g(x). See, e.g., A iel e al. (1988) o Ma os (1977) o u he p ope ies on pseudoconca e unc ions. T HEOREM 2.1. F is pseudoconca e. The p oo can be ound in he appendix. See also Ba os and F enk (1995) o ano he ‘‘ ac a- ble’’ queueing model wi h nonconca e objec i e unc- ion. 3. Op imali y Condi ions The pu pose o his sec ion is o s a e op imali y con- di ions o p oblem (P). Exp essing Fas in (7.1), we see ha (P)isanonlinea ac ional p og am wi h con ex ea- sible egion ( he n-cube [0, 1] n ) and pseudoconca e ob- jec i e unc ion (Theo em 2.1). The pseudoconca i y o Fenables he s a emen o op imali y condi ions in e ms o he g adien Ç Fo F(see, e.g., Co olla y 7.49 o Ma os 1977). Mo e p ecisely, i we deno e by D(x) he se o easible di ec ions a x √ [0, 1] n , hen n x √ [0, 1] is an op imal solu ion o (P)(3.1) i Ç F(x) · d ° 0 ∀ d √ D(x). The g adien o Fis easily ob ained, Ç F(x) ÅlC ( · x) c (3.2) n / ( l· x) C* ( · x) ∀ x √ [0, 1] . c We will combine (3.1) and (3.2) abo e o ob ain op- imali y condi ions. Fi s we show ha no in e io poin xcan be op imal. L EMMA 3.1. Suppose ha x Å (x 1 ,...,x n )is an op imal solu ion o (P), and 0 õ x k õ 1. Then, 0C ( · x) c s Å . k ( l· x) C* ( · x) c P ROOF . Le e k be he ec o wi h 1 a he k h coo - dina e and ze os e e ywhe e else. As 0 õ x k õ 1, bo h e k and 0 e k a e easible di ec ions, which, by (3.1), im- plies ha k Ç F(x) · e Å 0 By (3.2), he esul ollows. h The nex lemma shows ha any op imal policy is de- e minis ic excep o a mos one class o cus ome s. L EMMA 3.2. I x is an op imal solu ion o (P), hen x has a mos one ac ional componen . The p oo is s aigh o wa d by he lemma abo e and Assump ion A2. h This esul leads o an in e es ing consequence abou he geome ical s uc u e o he se o op imal solu ions, s a ed in he heo em below. T HEOREM 3.1. The se o op imal solu ions o (P)is a closed (possibly degene a e)segmen con ained in an edge o [0, 1] n . P ROOF . As, by Theo em 2.1, Fis pseudoconca e, i is con inuous and quasiconca e (see Theo em 7.28 o Ma os 1977). Hence, he se So op imal solu ions o (P) is a closed con ex se . Fu he mo e, Sis con ained in an edge o [0, 1] n . Indeed, else, he e would exis x 1 , x 2 √ Sno con ained in he same edge. By con exi y o Sand he quasiconca i y o F, he whole segmen wi h endpoin s x 1 and x 2 would consis o op imal solu ions. Then he e would exis an op imal solu ion wi h a leas wo ac ional componen s, which, by Lemma 3.2, is a con adic ion. Hence, he esul holds. h C OROLLARY 3.1. I c ú 1, hen he se o op imal solu- ions o (P)is a single on. See he appendix o he p oo . R EMARK 3.1. I c ú 1, he co olla y abo e shows ha he e exis s a unique op imal solu ion. Howe e , i c Å 1, (P) migh ha e mul iple op imal solu ions. As a simple example, ake n Å 2, l 1 Ål 2 Å 1, s 1 Å 1, s 2 Å 2. Then, i is easily checked ha he se o op imal solu- ions o (P) is he closed segmen wi h endpoin s (1, 0) and (1, 1). In ac , i will be shown in §4 ha , o c Å 1, he se o op imal policies consis s o ei he one non an- domized policy o he se o mix u es o wo non an- domized policies. By he heo em abo e, any op imal solu ion x o (P) mus be ei he a e ex o a poin on an edge o [0, 1] n , hus he sea ch o op imal solu ions o (P) is educed o he 0- and one-dimensional aces o he 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, Ma ch 1998 315 3b24 0011 Mp 315 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 Figu e 2 The Se a ([0, n ]) when n Å 3 We s a e below he co esponding op imali y condi- ions. De ine, o each x √ [0, 1] n he se s I(x) and J(x) as I(x) Å {i:x Å 0}, J(x) Å {i:x Å 1}. ii T HEOREM 3.2. (op imali y condi ions a a e ex) Le x x 0be a e ex o [0,1] n .Then,x is an op imalsolu ion o (P)i 0C ( · x) c min s ¢¢ max s. (3.3) ii ( l· x) C* ( · x) i√I(x)i√J(x) c The p oo can be ound in he appendix. T HEOREM 3.3. (op imali y condi ions on edges). Le x √ [0, 1] n be such ha 0 õ x k õ 1 o some k,and x i √ {0, 1} ∀ i x k.Then,x is an op imal solu ion o (P)i 0C ( · x) c min s ú s Åú max s. (3.4) ik i ( l· x) C* ( · x) i√I(x)i√J(x) c The p oo o his heo em uns pa allel o ha o he heo em abo e, jus aking in o accoun Lemma 3.1 and Assump ion A2. h R EMARK 3.2. Al hough he condi ions (3.3) and (3.4) ha e been ob ained unde Assump ions A1 and A2, hey lead o a meaning ul in e p e a ion in e ms o he o iginalse ing:I is op imal o se eonly hosecus om- e s whose ejec ion su cha ge pe uni se ice ime is high enough. The esul s s a ed so a sugges anaı¨ ep ocedu e o sol ing (P): E alua e he 2 n e ices o [0, 1] n , and sol e he n2 n01 one-dimensional nonlinea ac ional p o- g ams ob ained by op imizing Fon each edge. How- e e , we can go much u he ; as shown below, nei he all he e ices no all he edges a e ue candida es o con ain op imal solu ions. Fo his pu pose, le i ,i Å 0,...,nbe he ec o wi h 1 a he i s icoo dina es and 0 e e ywhe e else. Le a :[0,n] [0, 1] n be he na u al pa ame iza ion o he pa h h ough 0 , 1 ,..., n (see Figu e 2 o an illus a- ion o a when n Å 3). The nex heo em shows ha any op imal solu ion mus be con ained in he pa h a ([0, n]), i.e., since, by Assump ion A2, he se ice imes a e gi en in inc eas- ing o de , he op imal policy belongs o he class o c m ules. T HEOREM 3.4. I x is an op imal solu ion o (P), hen he e exis s some ,0 õ ° n such ha x Åa ( ). P ROOF . By Lemma 3.2, xhas a mos one ac ional componen , hus ei he (3.3) o (3.4) apply. Hence, A2 implies ha i x Å 0, hen x Å 0 ∀ j ú i ij , (3.5) J i x ú 0, hen x Å 1 ∀ j õ i ij hus x Åa ( ) o some . h R EMARK 3.3. The c m - ule op imali y is no longe ue when one es ic s he se o policies o non andomized ones, i.e., when, ins ead o sol ing (P) one wan s o sol e i s {0, 1}- e sion (P NR ) max F(x), n s. . x √ {0, 1} . (P NR ) Fo ins ance, i we ake 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, i is easily seen ha he op imal solu ion o (P NR ) is he ec o x* Å (1, 0, 1), which is no in he pa h { a ( ): √ [0, 3]}. The heo em abo e shows ha (P)isequi alen o he one-dimensional p oblem (P ˜) ˜ max F( ) Å F( a ( )), (s. . √ [0, n]. (P ˜) As a ( · ) is no di e en iable a in ege poin s, F ˜migh no be di e en iable, bu i emains di ec ionally di e - en iable. CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 316 M ANAGEMENT S CIENCE /Vol. 44, No. 3, Ma ch 1998 3b24 0011 Mp 316 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 Figu e 3 The F ˜ Co esponding o F o Figu e 1 Wha does no seem so in ui i e is he ac ha F ˜( · ) is also unimodal. As an example, Figu e 3 shows he F ˜ co esponding o he unc ion Fo Figu e 1. In ac , as he nex heo em shows, F ˜( · ) is a di ec ion- ally di e en iable (al hough non-di e en iable) semilo- cally pseudoconca e unc ion on [0, n], i.e., ˜˜˜ F * ( ;s– ) ú 0 whene e F(s) ú F( ), s, √ [0, n] whe e F ˜ * ( ;s– ) s ands o he di ec ional de i a i e o F ˜a in he di ec ion s– . See Kaul and Kau (1982) o u he esul s on his concep . T HEOREM 3.5. F ˜( · )is semilocally pseudoconca e on [0, n]. Fo he p oo , see he appendix. 4. Finding an Op imal Rejec ion Policy In he sec ion abo e we ha e shown ha inding an op imal policy is equi alen o sol ing he one- dimensional p oblem (P ˜), ˜ max F( ) Å F( a ( )), s. . √ [0, n]. (P ˜) Fu he mo e, by Theo em 3.5 he objec i e unc ionis semilocally pseudoconca e, which enables he esolu- ion (up o a p especi ied accu acy e )o (P ˜) by a a ie y o well-known me hods (see, e.g., Chap e 8 o Baza aa and She y 1979). An illus a ion is gi en in he nex example. E XAMPLE 4.1. Conside a sys em wi h c Å 3 se e s and n Å 8 classes o cus ome s. The i-cus ome s a i e ollowing a Poisson p ocess wi h a i al a e l i Å 1 and ha e expec ed se ice ime s i Å i 3 /10, i Å 1,...,8. The g aph o F ˜is plo ed in Figu e 4, and Figu e 5 ep esen s he po ion boxed in Figu e 4. No e ha F ˜ a ains i s maximum a a nonin ege poin , i.e., op i- mali y is a ained a a andomized ejec ion policy. In o de o sol e (P ˜), we ha e chosen he golden sec- ion me hod (see, e.g., Baza aa and She y 1979). Fo a p especi ied accu acy o eÅ 0.001 we needed 18 i e a- ions; he esul s a e 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, Ma ch 1998 317 3b24 0011 Mp 317 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 Figu e 4 The G aph o F ˜ Hence, we ake as solu ion he poin * Å 2.18013, which gi es F ˜( *) Å 1.92477, and co esponds o he ol- lowing policy: when an a i ing i-cus ome inds a leas one se e idle, i is ejec ed by he sys em wi h p obabili y 0 i i Å 1, 2; wi h p obabili y 3– * Å 0.81987 i i Å 3 and wi h p obabili y 1 i i ú 3. h The me hodology abo e applies o any alue o c. Howe e , when c ° 2, he unc ions Fand F ˜ha e a much simple shape, which enables us o sol e exac ly he p oblem (P ˜) and also (P) in ini e ime. We explo e i s he single-se e case, i.e., c Å 1. Then, (P) akes he o m max F(x) Å ( l· x)/(1 / · x), n s. . x √ [0, 1] . (P) This implies ha (P) becomes a linea ac ional p o- g am, hus he objec i e unc ion Fis no only pseudo- conca e bu pseudomono onic. See, e.g., A iel e al. (1988) o Ma os (1977) o u he p ope ies on his class o unc ions. The single-se e assump ion enables o s eng hen o ease some o he esul s ob ained in p e ious sec- ions. Fo ins ance, we know om §3 ha he se So op imal solu ions o (P) migh no be a single on, bu is con ainedin an edgeo [0, 1] n .Thepseudomono onici y o Fimplies ha Smus equal he con ex hull o he op imal e ices. Hence, Smus ha e one o he wo ollowing o ms: 1. The single on { a (k)} o some k √ {1,2,...,n}. 2. The closed segmen wi h endpoin s{ a (k)}and{ a (k / 1)} o some k √ {1,2,...,n 0 1}. In o he wo ds, he e always exis s some ksuch ha he non andomized policy consis ing o au oma ically ejec ing all he i-cus ome s (i ú k) and se ing e e y i-cus ome (i Å 1,2,...,k) who inds idle se e s is op imal. Hence, in CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models 318 M ANAGEMENT S CIENCE /Vol. 44, No. 3, Ma ch 1998 3b24 0011 Mp 318 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 Figu e 5 F ˜ A ains I s Maximum a a Nonin ege Poin Table 1 Sol ing by he Golden Sec ion Me hod ( H P ) I e a . Accu acy Op imal In e al 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) o de o ind an op imal policy we can es ic ou a en ion o he se { a (1), a (2), ..., a (n)} as candida e poin s (i.e., { a (1), a (2), ..., a (n)} is a ini e domina ing se , see Hooke e al. 1991), which sugges s he ollowing app oach: E al- ua e Fa a (i) o all i, and ake as op imal solu ion he a (i*) gi ing he highes alue o F. This simple algo i hm uns in O(n 2 ) ime, which is accep able o mode a e alues o n.I nis so la ge ha e en an O(n 2 ) compu ing ime should be conside ed as p ohibi i e, mo e sub le p ocedu es can be used. In- deed, as shown in Hansen e al. (1991), i is possible o use bina y sea ch echniques o ob ain an o e all com- plexi y o O(n) ime and space. We examine now he case c Å 2. I is a he easy o ind he in ege ksuch ha he op imal solu ion o (P ˜) ei he is ko belongs o he open in e al (k,k / 1). Indeed, such conclusion can be ob ained a e checking he op imali y condi ions a e ices and pe o ming some i e a ions o , o ins ance, a bina y-sea ch p oce- du e. I kis op imal o (P ˜), hen a (k) is op imal o (P). On he con a y, i he op imal solu ion is * √ (k,k / 1), hen, by he semilocal pseudoconca i y o F ˜, *is he unique oo in (k,k / 1) o he nonlinea equa ion ˜ F * ( ) Å 0. (4.1) By (7.5), i is easily seen ha when c Å 2, (4.1) can be w i en in he o m Q( ) Å 0, whe e Qis a polynomium o deg eeno g ea e han3.Hence, heop imalsolu ion o (P ˜) is he unique oo o Qin (k,k / 1), which, as is well-known, can be ob ained exac ly. 5. Conclusions In his pape we ha e add essed a design p oblem as- socia ed wi h a loss model wi h he e ogeneousa i als, whe e he decision a iables ep esen he p obabili y CARRIZOSA, CONDE, AND MUN ˜OZ-MA ´RQUEZ Admission Policies in Loss Queueing Models M ANAGEMENT S CIENCE /Vol. 44, No. 3, Ma ch 1998 319 3b24 0011 Mp 319 Monday Ma 09 09:37 AM Man Sci (Janua y) 0011 ha a cus ome o each class is ejec ed by he sys em when he inds some se e s idle. A e imposing a cos s uc u e on he model, he sea ch o a cos -op imal policy is educed o sol ing a nonlinea ma hema ical p og am. The objec i e unc- ion o he p oblem add essed may no be conca e; ne - e heless, we s a e some p ope ies o he p oblem (op- imali y o a c m - ule) ha enable us o educe he op imiza ion o sol ing an equi alen unimodal one- dimensionalp oblem o whichse e alwell-known es- olu ion echniques can be applied. Finally, we ha e shown ha an op imal policy o he wo-se e case can be ound as a oo o a polynomial unc ion o deg ee 3, whils he one-se e case leads o a linea ac ional p og am wi h a simple s uc u e, which can be sol ed in O(n 2 ) ime by s aigh o wa d echniques, and in linea ime by bina y sea ch. Ex ensions o hese esul s o sys ems go e ned by dynamic s a e-dependen policies, o o M/G/1/ ` sys- ems a e in e es ing ques ions which emain open. 1 1 The esea ch o he au ho s is pa ially suppo ed by Spanish DGI- CYT g an PB93-0927. This suppo is g a e ully acknowledged. Appendix L EMMA 7.1. The unc ion 1/ C c ( · )is con ex on [0, ` ). Mo eo e ,i c ú 1 hen 1/ C c ( · )is s ic ly con ex on [0, ` ). P ROOF . The case c Å 1 is s aigh o wa d (1/ C 1 ( ) Å 1 / ), so we conside only he case c ú 1. As ck ( /k! kÅ0 1/ C ( ) ÅÅ 1 / (1 0C ( )), cc01 c01k ( /k!c kÅ0 and he unc ion ° C c01 ( ) is conca e (see, e.g., Co olla y 1o Ha el 1990), i ollows ha 1/ C c ( · ) is con ex. In o de o check ha i is also s ic ly con ex, obse e ha , o he wise, 1/ C c ( · ) should be a poly- nomial o deg ee a mos one in some nondegene a e in e al I, i.e., he e would exis a , b such ha ck ( /k! kÅ0 Åa /b∀ √ I. c01k ( /k! kÅ0 Equa ing coe icien s, one would ob ain aÅ 0 Å 1/c, which is a con adic ion. h P ROOF OF T HEOREM 2.1. Obse e ha l· x F(x) Å . (7.1) 1/ C ( · x) c By Lemma 7.1, he unc ion ° 1/ C c ( ) is con ex. Hence, i s com- posi ion wi h he linea unc ion x ° · xis con ex. Hence, Fis he quo ien o a nonnega i e linea and a posi i e con ex unc ion, hus Fis pseudoconca e, as asse ed. h P ROOF OF C OROLLARY 3.1. Suppose, on he con a y, ha (P) has a leas wo di e en op imal solu ions x,y. Then, by he heo em abo e, bo h xand ybelong o he same edge o [0, 1] n . Wi hin he in e al Io endpoin s x,y, one deduces om Theo em 5.17 o A iel e al. (1988) and ou Lemma 7.1 ha Fis s ic ly pseu- doconca e on I, which is a con adic ion wi h he simul aneous op i- mali y o xand y. h P ROOF OF T HEOREM 3.2. Fi s , obse e ha C c ( ) is s ic lydec eas- ing in (see Ha el 1990), i.e., C* ( ) õ 0 ∀ . (7.2) c De ine, o each i Å 1,...,n, he ec o e i as in he p oo o Lemma 3.1. Ob iously ii D(x) Å cone({e:i √ I(x)} < { 0 e:i √ J(x)}), (7.3) whe e cone (A) ep esen s he cone gene a ed by he elemen s o A. Hence, by (3.1), (3.2), and (7.3), i ollows ha xis op imal i lC ( · x) / ( l· x) C* ( · x) ° 0 ∀ i √ I(x), ic c i 5 lC ( · x) / ( l· x) C* ( · x) ¢ 0 ∀ i √ J(x), ic c i which, by (7.2), u ns ou o be equi alen o (3.3). h P ROOF OF T HEOREM 3.5. Fo each k Å 1,...,nle he ec o e k be de ined as in he p oo o Lemma 3.1. We will jus show ha F ˜( · )is semilocally pseudoconca e a nonin ege poin s √ [0, n], namely, ˜ s, √ [0, n], s x ,F * ( ;s 0 ) ° 0(7.4) ˜ implies H F(s) ° F( ). The p oo o in ege poin s is comple ely analogous and will no be gi en he e. Hence, we assume ha √ [0, n] is no in ege , hus he e exis s k √ {0,1,...,n 0 1} such ha k õ õ k / 1. Wi hin he in e al [k,k / 1] he unc ion F ˜ akes he o m ˜ F(s) Ål/l (s 0 k) ∑ ik SD iõk ·C / (s 0 k) ∀ s √ [k,k / 1]. ∑ cik SD iõk Hence, F ˜is di e en iable a , and k H F * ( ) ÅÇ F( a ( )) · e ÅlC ( ·a ( )) / ( l·a ( )) C* ( ·a ( )) . (7.5) kc c k Hence, one has H F * ( ) ° 0 i C ( ·a ( )) / ( l·a ( )) C* ( ·a ( )) s ° 0. cck Since, by (7.2) and A2,