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,