Load-balancing for multi-skilled servers with Bernoulli routing

Annals o Ope a ions Resea ch (2022) 312:949–971
h ps://doi.o g/10.1007/s10479-022-04532-7
ORIGINAL RESEARCH
Load-balancing o mul i-skilled se e s wi h Be noulli
ou ing
Fe nando Miguelez1·Josu Doncel2·Balak ishna J. P abhu3
Accep ed: 3 Janua y 2022 / Published online: 15 Janua y 2022
© The Au ho (s) 2022
Abs ac
We s udy he op imal Be noulli ou ing in a mul iclass queueing sys em wi h a dedica ed
se e o each class as well as a common (o mul i-skilled) se e ha can se e jobs o all
classes. Jobs o each class a i e acco ding o a Poisson p ocess. Each se e has a holding
cos pe cus ome and use he p ocesso sha ing discipline o se ice. The objec i e is o
minimize he weigh ed mean holding cos . Fi s , we p o ide condi ions unde which classes
send hei a ic only o hei dedica ed se e , only o he common se e , o o bo h. A ixed
poin algo i hm is gi en o he compu a ion o he op imal solu ion. We hen specialize o
wo classes and gi e explici exp essions o he op imal loads. Finally, we compa e he cos
o mul i-skilled se e wi h ha o only dedica ed o all common se e s. The heo e ical
esul s a e complemen ed by nume ical examples ha illus a e he a ious s uc u al esul s
as well as he con e gence o he ixed poin algo i hm.
Keywo ds Be noulli ou ing ·Pa allel-se e s ·Mul i-skilled se e s
1 In oduc ion
1.1 Mo i a ion
We in es iga e he pe o mance o a mul i-skilled queueing sys em o med by pa allel se e s
wi h P ocesso Sha ing (PS) queues. Jobs o di e en classes o cus ome s a i e o he sys em
ollowing a Poisson p ocess. The e is one dedica ed se e o each class o cus ome and one
mul i-skilled se e ha can execu e jobs o all classes. Fu he mo e, we assume ha jobs
a e assigned o he se e s acco ding o he Be noulli policy. Ou goal is o ind he op imal
load balancing so as o minimize he weigh ed mean numbe o jobs in he sys em.
The main applica ion o ou model comes om wi eless ne wo ks. Conside a egion
di ided in di e en sub egions. Each dedica ed se e models an an enna ha p o ides se -
BJosu Doncel
[email p o ec ed]
1Uni e sidad Publica de Na a a, Na a a, Spain
2Uni e si y o he Basque Coun y, UPV/EHU, Leioa, Spain
3LAAS-CNRS, Uni e si é de Toulouse, CNRS, Toulouse, F ance
123
950 Annals o Ope a ions Resea ch (2022) 312:949–971
ice o a unique sub egion and he mul i-skilled se e models a cen al an enna ha p o ides
se ice o all he sub egions. Using he esul s o his a icle, one can de e mine how he a ic
o each sub egion mus be sha ed be ween he an enna o ha egion and he cen al one in
o de o minimize he pe o mance o he sys em. This a chi ec u e has been p e iously con-
side ed by Taboada e al. (2017) in a di e en con ex whe e dedica ed se e s (o mic ocells
in hei model) can be swi ched on and o so as o minimize he weigh ed sum o he mean
delay and he mean powe consump ion in he sys em.
1.2 Rela ed wo k
Load balancing has been widely in es iga ed in di e en con ex s. In da a cen e s, o exam-
ple, a ious policies depending upon he in o ma ion a ailable o he dispa che ha e been
p oposed. In gene al, op imal policies o he ypical pe o mance measu es such as mean
p ocessing imes a e no easy o de e mine albei in some speci ic cases. Fo example, when
no in o ma ion on he s a e o he se e s is a ailable, he op imal Be noulli ou ing policy
was de e mined in Al man e al. (2011) o mono-skilled se e s only. Fo FCFS se e s, a
policy based on S u m sequences (Gaujal e al. 2006) a e known o be op imal. Wi h mo e
in o ma ion on he se e s a e, a numbe o heu is ics such as Join he Sho e o dqueues
(Mi zenmache 2001; V edenskaya e al. 1996) and Join he Sho es Queue (G aham 2000)
ha e been analyzed in he la ge se e asymp o ic case. In addi ion, he e a e a ious pull-
based policies such as Join he Idle Queue (Lu e al. 2011) ha a e known o wo k well in
p ac ice. Ano he impo an ou ing policy is he Size In e al Task Assignmen (Ha chol-
Bal e e al. 1999) whe e jobs o di e en sizes a e execu ed in di e en se e s and, he e o e,
he se ice equi emen o incoming asks need o be known. This policy has been u he
s udied in Feng e al. (2005) and he au ho in Ha chol-Bal e (2000) p esen ed a a ia ion
o his policy in which he size o jobs does no need o be known.
Load balancing has also been in es iga ed o balancing ene gy cos s in da a cen e s using
Ene gy Packe Ne wo ks model (Fou neau 2020), whe eas in Liu e al. (2015) i is conside ed
ha da a cen e s a e loca ed in di e en geog aphical zones. The abo e wo ks a e mos ly
conce ned wi h mono-skilled o homogeneous se e s.
In ne wo ks wi h mul i-skilled agen s o se e s, skill-based ou ing policies ha e been
p oposed and in es iga ed (Koole e al. 2003; Wallace and Whi 2005). These wo ks a e
mainly o ien ed owa ds call-cen e a chi ec u es wi h E lang-B o E lang-C ype o queues.
An illus a i e example is an o e low- ype policy, whe e each incoming call has a lis o
agen s o de ed by p io i y, wi h highes p io i y gi en o mono-skilled ones, and is ou ed o
he i s a ailable agen o his lis . I no agen is a ailable, he call can be queued o blocked
depending on he a chi ec u e. These ou ing policies a e usually di icul o analyze and
he ci ed wo ks a e in e es ed in app oxima ions o he a ious pe o mance measu es o a
gi en policy. In hese models, ob aining he op imal policy analy ically is no easy. We e e
o Chen e al. (2020) o a ecen su ey on mul i-skilled sys ems.
Mul i-skilled queues appea also in he analysis o edundancy sys ems (Ga dne e al.
2015; Bonald e al. 2017) in which incoming eques s can be sen simul aneously o a subse
o queues. We do no in es iga e he edundancy aspec .
The ne wo k opology we conside makes ou model di e en om Al man e al. (2011)
in which all se e s can execu e all ype o asks.
123
Annals o Ope a ions Resea ch (2022) 312:949–971 951
1.3 Con ibu ions
The main con ibu ions o he a icle a e summa ized as ollows:
•We p o ide a necessa y and su icien condi ion o he s abili y o he sys em.
•We show ha he op imiza ion p oblem in e ms o p obabili ies can be e o mula ed in
e ms o he loads o he se e s, which is a con ex p oblem wi h linea cons ain s. We
also show ha i he e a e ou ing p obabili ies ha sa is y he o iginal p oblem ( ha
we will call (PROB-OPT)), hen i is possible o ind loads ha sa is y he e o mula ed
p oblem ( ha we will call (LOAD-OPT)).
•We ully cha ac e ize he op imal loads on he se e s o wo classes o cus ome s. Fo
mo e han wo cus ome s, we p o ide in P oposi ion 2condi ions unde which each class
o a ic sa is ies one o he ollowing: (i) i sends all i s a ic o i s dedica ed se e ,
(ii) i sends all i s a ic o he mul i-skilled se e and (iii) i sha es i s a ic among he
mul i-skilled and i s dedica ed se e .
•Using he esul o P oposi ion 2, we p esen a ixed-poin algo i hm whose con e gence
ensu es ha he op imal loads on he se e s a e achie ed. This algo i hm s a s wi h an
ini ial condi ion o he se o se e s (acco ding o one o he h ee possible a ic sha ing
policies o P oposi ion 2) and i s ixed poin is gi en by he pa i ion o he se o se e s.
P o iding an analy ical p oo o his con e gence on he pa i ion o he se o se e s
seems o be an ex emely di icul ask. Howe e , we illus a e he con e gence o his
algo i hm using nume ical expe imen s.
•We compa e he pe o mance o ou model wi h he pe o mance o wo models. The
i s model consis s o a sys em whe e all he se e s a e mul i-skilled and we show he
exis ence o a swi ching cu e, i.e., when he a i al a e o one o he a ic inc eases,
he model whose pe o mance is be e changes. The second model consis s o a sys em
wi h no sha ing, ha is, all he se e s a e dedica ed o mono-skilled, and we p o ide
condi ions on he a i al a es such ha he pe o mance o he no-sha ing model is la ge
han he pe o mance o ou model.
•We del e in o he compa ison o he a o emen ioned models using nume ical expe imen s.
Fi s , we show he uniqueness o he swi ching cu e when we compa e ou model wi h
a sys em whe e all he se e s a e mul i-skilled. We also obse e ha , in a sys em o med
by se e s wi h equal capaci y and di e en (bu no ex emely la ge) holding cos s, he
egion whe e ou model ou pe o ms he all-sha ing sys em is e y la ge.
1.4 O ganiza ion
In he nex sec ion, we desc ibe he ne wo k model and de ine he op imiza ion p oblem.
Sec ion 3gi es he s abili y condi ion and p esen s an equi alen p oblem in e ms o loads
on he se e s. In Sec . 4, he main esul s on he s uc u e o he op imal policy a e p o ided
o he model unde conside a ion. We compa e in Sec . 5 he pe o mance o ou model
wi h he pe o mance o models wi h o he ne wo k opologies. We p esen ou nume ical
expe imen s in Sec . 6. Finally, we discuss ou main conclusions in Sec . 7.
123
952 Annals o Ope a ions Resea ch (2022) 312:949–971
Fig. 1 The model unde s udy in
his a icle
2 Model desc ip ion
2.1 No a ion
We conside a se e a m wi h P ocesso Sha ing (PS) queues and an inpu a ic o di e en
classes. Le K={1,2,...,C}be he se o classes. We assume ha jobs o class i∈K
a i e o he sys em acco ding o a Poisson p ocess and ha e gene ally dis ibu ed se ice
imes1.Le ηibe he a ic in ensi y o jobs o class i. The class o a job de ines he se o
se e s ha can be assigned o his job (Fig. 1).
We conside a sys em wi h C+1 se e s. Le S={0,1,...,C}be he se o se e s.
Fo a se e j∈S,wedeno eby j he capaci y o speed o Se e j(i.e., he amoun o
a ic ha can be se ed pe uni o ime) and by cji s holding cos . We deno e by Si he se
o se e s ha can execu e jobs o class iand, o A⊂K,SA=∪
i∈ASi.Fo j=1,...,C,
Se e jexecu es jobs o class j, i.e., hey a e dedica ed se e s. On he o he hand, Se e
0 execu es jobs o all he classes, i.e., i is a mul i-skilled se e .
Fo i=1,...,C,wedeno ebypi he p obabili y ha a class ijob is execu ed in i s
dedica ed se e , i.e., Se e i.Fo j=1,...,C, he load o Se e jis de ined as ollows
ρj(p)=ηjpj
j
,(1)
whe eas o Se e 0 as
ρ0(p)=j∈Kηj(1−pj)
0
.(2)
1Since ou goal is o analyze he mean numbe o jobs and, in a M/G/1-PS queue, he mean numbe o jobs
depends on he a i al a e and on he se ice ime equi emen s only h ough he in ensi y, we do no speci y
he a i al a e o each class
123
Annals o Ope a ions Resea ch (2022) 312:949–971 953
2.2 P oblem o mula ion
Fo a gi en ou ing s a egy p=(pi), he mean numbe o jobs o se e jis deno ed by
E[Nj(p)]. In his a icle, we aim o ind he ou ing ma ix ha minimizes he o al cos o
he sys em. Mo e speci ically, we analyze he ollowing op imiza ion p oblem:
min
p
j∈S
cjE[Nj(p)](PROB-OPT)
0≤pi≤1, o all i∈K;(3)
ηipi< i, o all i∈K;(4)

i∈K
ηi(1−pi)< 0.(5)
The i s cons ain ensu es ha pi’s a e p obabili ies. The second and hi d cons ain s
ensu e ha all he se e s a e s able, ha is, ha he o al incoming a ic in o a se e is
smalle han i s se ice capaci y.
3 P elimina y esul s
We i s s udy he exis ence o a easible solu ion o (PROB-OPT). This is he same as
cha ac e izing he condi ions unde which he sys em can be s abilized. In he ollowing
p oposi ion, we p o ide his esul .
P oposi ion 1 (S abili y) The sys em unde conside a ion can be s abilized i and only i
0+
i∈A
i>
i∈A
ηi,∀A⊂K.(6)
P oo See “Appendix A”. 
Since se e s a e M/G/1-PS queues, we know om Thm 3.8 and Thm 3.9 o Kelly (1979)
ha he p obabili y o being njobs in Se e iis ρn
i(1−ρi). The e o e, i ollows di ec ly
ha E[Nj(p)]= ρj
1−ρjand, as a consequence, we can e o mula e (PROB-OPT) in e ms o
he loads on he se e s as ollows:
min
æ
j∈S
cj
ρj
1−ρj
(LOAD-OPT)

i∈K
ηi= 0ρ0+
j∈K
jρj;(7)
0≤ρj<1, o all j∈S;(8)

i∈A
ηi≤ 0ρ0+
j∈A
jρj,∀A⊂K.(9)
We now show ha he op imiza ion p oblems we ha e conside ed so a a e ela ed. Mo e
p ecisely, we show ha , i he e a e ou ing p obabili ies ha sa is y (PROB-OPT), hen i is
possible o ind loads ha sa is y (LOAD-OPT).
123

954 Annals o Ope a ions Resea ch (2022) 312:949–971
Lemma 1 Le pbe a ou ing s a egy ha sa is ies (3)–(5). Then, o all j ∈S,ρj(p)also
sa is ies he cons ain s o (LOAD-OPT).
P oo Fi s , we obse e ha , i (3)-(5) a e sa is ied, using (1)and(2), i ollows ha 0 ≤
ρj<1 o all j∈S.
We now show ha i∈Kηi= 0ρ0+j∈K jρjin he ollowing way:
0ρ0+
j∈K
jρj=
i∈K
ηi(1−pi)+
i∈K
ηipi=
i∈K
ηi,
whe e he i s equali y is gi en using (1)and(2).
Finally, we ocus on he cons ain i∈Aηi≤ 0ρ0+j∈A jρj,∀A⊂K. Using again
(1)and(2), we ha e o all A⊂K ha
0ρ0+
j∈A
jρj=
i∈K
ηi(1−pi)+
i∈A
ηipi≥
i∈A
ηi(1−pi)+
i∈A
ηipi=
i∈A
ηi.
And he desi ed esul ollows. 
No e ha (LOAD-OPT) is a con ex p oblem wi h linea cons ain s and has an unique
solu ion as long as he s abili y condi ion in P oposi ion 1is e i ied. Mo eo e , om he
abo e lemma, he solu ion o (PROB-OPT) can be ob ained by op imizing di ec ly o e he
loads. Then, he op imal ou ing p obabili ies can be de e mined la e om (1), once he
op imal load on each se e is de e mined.
Rema k 1 Le us ema k ha we assume ha se e s a e M/G/1-PS queues. Howe e , he
esul s o his a icle a e also alid i we assume ha se e s a e M/M/1 queues wi h any
wo k-conse ing queueing discipline (no e ha he mean numbe o cus ome s o a se e j
in bo h cases is ρj/(1−ρj)).
4 Analysis o he solu ion o (LOAD-OPT)
Le δj=cj/ j
c0/ 0 o all j∈K.Wedeno ebyCb he se o classes ha ou e a ic o wo
se e s, by C0 he se o classes ha ou es all he a ic o Se e 0 and by Cd he se o
classes ha send all he a ic o i s dedica ed se e .
In he ollowing p oposi ion, we p esen he i s esul o his sec ion. I gi es he condi ions
unde which a class o a ic belongs o Cb,C0o Cd.
P oposi ion 2 Jobs o class i ou es a ic o Se e 0 i and only i
δi>1−ηi
i
1−ρ∗
0
,
and all he a ic o class i is ou ed o Se e 0 i and only i
δi≥1
1−ρ∗
0
,
whe e ρ∗
0is he op imal load a Se e 0and is gi en by
ρ∗
0=1− 0+j∈Cb j−j∈Cb∪C0ηj
0+j∈Cbδj j
.(10)
123
Annals o Ope a ions Resea ch (2022) 312:949–971 955
Besides, i j ∈Cd he op imal load o Se e j is ηj
j,i j ∈Cb he op imal load o Se e j
is
ρ∗
j=1−δj(1−ρ∗
0)(11)
and i j ∈C0 he op imal load o Se e j is ze o.
P oo See “Appendix B”. 
The abo e esul leads o his co olla y which gi es a simple su icien condi ion o de e -
mine when a gi en class will no send all i s a ic o he mul i-skilled se e .
Co olla y 1 Le j ∈S.I δj<1, hen j /∈C0.
P oo Since δj<1, we ha e ha he condi ion δj<1
1−ρ∗
0
is always sa is ied and his implies
ha j/∈C0acco ding o P oposi ion 2.
F om he abo e co olla y, i ollows ano he in e es ing p ope y ha says ha , i δj<1
o all j∈K, henC0=∅.
The nex esul gi es an o de ing which can help iden i y classes ha use bo h he dedica ed
and he mul i-skilled se e . This can be seen as a way o de e mine, o a gi en se o inpu
pa ame e s (a i al a e, se e speeds, holding cos s, e c.), he skills o which we need o
ain he mul i-skilled se e s in o de o he sys em o be op imal.
P oposi ion 3 Le δi≤δj.
(a) I i ∈C0, hen j ∈C0.
(b) I i ∈Cb∪C0and ηi
i≤ηj
j, hen j∈Cb∪C0.
P oo We i s show (a). We conside ha i∈C0.Sinceδj≥δi, i ollows ha δj≥δi≥
1
1−ρ∗
0
.
The e o e, om P oposi ion 2,j∈C0.
We now show (b). We conside ha i∈Cb∪C0.Since ηi
i≤ηj
jand δj≥δi, i ollows ha
δj≥δi≥1−ηi
i
1−ρ∗
0
≥
1−ηj
j
1−ρ∗
0
.
The e o e, om P oposi ion 2,j∈Cb∪C0.
We no e ha (b)o he abo e esul can be s a ed as ollows: i class j ou es all he a ic o
Se e j,classi ou es all i s a ic o Se e iwhen ηi
i≤ηj
jand δi≤δj. In he ollowing
esul , we show ha , unde simila condi ions, he se o classes ha send a ic o wo se e s
can ne e be {i,j}.
P oposi ion 4 I δi≤δj<1and ηi
i≤ηj
0+ j, henC
bcanno be {i,j}.
P oo We assume ha Cb={i,j}. Fo his case, i ollows om (10) ha
1
1−ρ∗
0
≥ 0+ jδj+ iδi
0+ j+ i−ηj−ηi
,
whe e he abo e inequali y is an equali y i C0=∅.
123
956 Annals o Ope a ions Resea ch (2022) 312:949–971
Since ηi
i≤ηj
0+ j,weha e o classi ha
δi>1−ηi
i
1−ρ∗
0
≥1−ηi
i 0+ jδj+ iδi
0+ j+ i−ηj−ηi
⇐⇒ δi( 0+ j+ i−ηj−ηi)
>1−ηi
i( 0+ jδj+ iδi)
⇐⇒ δi( 0+ j−ηj)>1−ηi
i( 0+ jδj)
⇐⇒ δi>1−ηi
i
1−ηj
0+ j
0+ jδj
0+ j
≥ 0+ jδj
0+ j
⇐⇒ δi>δ
j+ 0(1−δj)
0+ j
>δ
j,
which is in con adic ion wi h δi≤δj.
Le Tideno e he sojou n ime o jobs o class i.Wenowp o ideanin e es ing esul
ela ed o he sojou n ime o jobs.
P oposi ion 5 I δi≤δj. Then, ciE[Ti]≤cjE[Tj].
P oo We know ha he sojou n ime o jobs o class iand o class j ollow an exponen ial
dis ibu ion wi h a e 1
i(1−ρ∗
i)and 1
j(1−ρ∗
j) espec i ely. The e o e,
ciE(Ti)=ci
i(1−ρ∗
i)
=ci
iδi
1
1−ρ∗
0
=c0
0ci
i
1
1−ρ∗
0
≤c0
0cj
j
1
1−ρ∗
0
=cjE(Tj).
And he desi ed esul ollows. 
4.1 Cha a e iza ion o he solu ion o (LOAD-OPT)wi hC=2
We now ocus on he case C=2. Th oughou his a icle, we e e o his case as he M
model. Wi hou loss o gene ali y, we assume ha δ1≤δ2. The goal o his sec ion is o ully
cha ac e ize he solu ion o (LOAD-OPT) wi h C=2.
We i s no e ha , om P oposi ion 3, i can ne e be gi en he ollowing cases: (i)
C0={1}and Cd={2}and (ii) C0={1}and Cb={2}. Fo he emaining cases, we ha e
he ollowing op ions:
1. Cd={1,2}. In his case, each class sends all i s a ic o he dedica ed se e . The e o e,
ρ∗
i=ηi
i o i=1,2andρ∗
0=0. Acco ding o P oposi ion 2 his occu s when
δi≤1−ηi
i,i=1,2.
123
Annals o Ope a ions Resea ch (2022) 312:949–971 957
2. Cd={1}and Cb={2}. In his case, all he a ic o class 1 is sen o Se e 1 and
he a ic o class 2 is sen o Se e 0 and Se e 2. As a esul , ρ∗
1=η1
1and, om
(10)and(11) we ob ain ha ρ∗
2=1−δ2 0+ 2−η2
0+δ2 2and ρ∗
0=1− 0+ 2−η2
0+δ2 2. Acco ding o
P oposi ion 2, his case occu s when δ1≤1−η1
1
1−ρ∗
0
and 1
1−ρ∗
0
>δ
2>1−η2
2
1−ρ∗
0
, i.e.,
δ1≤1−η1
1 0+δ2 2
0+ 2−η2
and
0+δ2 2
0+ 2−η2
>δ
2>1−η2
2 0+δ2 2
0+ 2−η2
,
which simpli ying gi es
δ1≤1−η1
1 0+δ2 2
0+ 2−η2
and 1
1−η2
0
>δ
2>1−η2
2
.
3. Cd={1}and C0={2}. In his case, all he a ic o class 1 is sen o Se e 1 and he
a ic o class 2 is sen o Se e 0. As a esul , ρ∗
1=η1
1,ρ∗
0=η2
0and ρ∗
2=0. Acco ding
o P oposi ion 2, his case occu s when δ1≤1−η1
1
1−ρ∗
0
and δ2≥1
1−ρ∗
0
,i.e.
δ1≤1−η1
1
1−η2
0
and δ2≥1
1−η2
0
.
4. C0={1,2}. In his case, he a ic o bo h classes is sen o Se e 0. Hence, ρ∗
i=0 o
i=1,2 and om (10) ha ρ∗
0=1− 0−η1−η2
0=η1+η2
0.Acco ding o P oposi ion 2and
using ha δ1≤δ2, his case occu s when δ1≥1
1−ρ∗
0
,i.e.,
δ1≥ 0
0−η1−η2
.
5. Cb={1,2}. In his case, he a ic o class iis sen o Se e 0 and Se e i, o
i=1,2. F om (10)and(11), i esul s ha ρ∗
0=1− 0+ 1+ 2−η1−η2
0+δ1 1+δ2 2and, o i=1,2,
ρ∗
i=1−δi 0+ 1+ 2−η1−η2
0+δ1 1+δ2 2. Mo eo e , we conclude om P oposi ion 2 ha his occu s
when, o i=1,2, 1
1−ρ∗
0
>δ
i>1−ηi
i
1−ρ∗
0
, which using ha δ2≥δ1gi es
δ1>1−η1
1 0+δ1 1+δ2 2
0+ 1+ 2−η1−η2
and
0+δ1 1+δ2 2
0+ 1+ 2−η1−η2
>δ
2>1−η2
2 0+δ1 1+δ2 2
0+ 1+ 2−η1−η2
.
We simpli y he abo e exp essions and we ob ain
δ1>1−η1
1 0+δ2 2
0+ 2−η2
and
0+δ1 1
0+ 1−η1−η2
>δ
2>1−η2
2 0+δ1 1
0+ 1−η1
.
6. Cb={1}and Cd={2}. We obse e ha his case is symme ic o he case 2 (whe e
Cb={2}and Cd={1}) and using he same a gumen s, we ge he ollowing condi ions
1
1−η1
0
>δ
1>1−η1
1
and 1−η2
2δ2≤ 0+δ1 1
0+ 1−η1
.
123
964 Annals o Ope a ions Resea ch (2022) 312:949–971
Table 1 Pa ame e s o he sys em
conside ed in Sec . 6.3 j=0j=1j=2j=3j=4j=5
j25 34 38 39 13 27
cj5 10 11 6 86 14
ηj28 33 20 12 24
Fig. 6 Con e gence o he ixed-poin algo i hm p esen ed in Sec . 4.2. The x-axis ep esen s he i e a ions o
he algo i hm and he y-axis he load o each se e
whe eas in he bo om line he loads o Se e 3, Se e 4 and Se e 5. We obse e ha ,
when he algo i hm con e ges, he load o Se e 4 is ze o, which means ha , o his case,
ρ∗
4=0. We also see ha , o Se e 3, he ini ial load in he scena io ha is ep esen ed by
he solid line ( ha is, he scena io whe e all he classes send all he a ic o i s dedica ed
se e ) equals o he load when he algo i hm con e ges. This means ha , o class 3, we
ha e ha ρ∗
3=η3
3.
I is impo an o ema k ha , as we can also obse e in Fig. 6, he algo i hm con e ges
o he same alues o he h ee di e en ini ial pa i ions unde conside a ion. We ha e
also s a ed he sys em wi h o he ini ial pa i ions and he ob ained esul s con i med ha he
123

Annals o Ope a ions Resea ch (2022) 312:949–971 965
Fig. 7 Minimum and maximum numbe o i e a ions un il con e gence o sys ems o di e en size
algo i hm always con e ges. Ano he in e es ing p ope y o his algo i hm is ha he numbe
o i e a ions equi ed o each he con e gence is e y small. Indeed, when he ini ial pa i ion
o Kis such ha all he classes belong o Cd, he algo i hm con e ges a e 12 i e a ions.
Mo eo e , o he es o he cases, he algo i hm con e ges o a less numbe o i e a ions.
When he ini ial pa i ion o Kis such ha classes 1, 3 and 4 belong o Cdand classes 2 and
5 oCb, i con e ges a e 2 i e a ions and when he ini ial pa i ion o Kis such ha classes
1, 2, 3 and 4 belong o Cdandclass5 oCb, i con e ges a e 3 i e a ions.
We now p esen u he nume ical wo k we ha e pe o med o analyze he con e gence o
Algo i hm 1 o la ge sys ems. Fo his se o expe imen s, we conside ha he numbe o
dedica ed se e s, C, a ies om 10 o 200 wi h s ep 10. Fo each case we un ou algo i hm
10 imes whe e, in each un, he pa ame e s o he sys em a e andomly chosen (bu sa is ying
he s abili y condi ion); he esul s a e depic ed in Fig. 7, whe e he blue ba s ep esen he
minimum numbe o i e a ions equi ed o con e gence and he yellow ba s he di e ence
up o he maximum. The main conclusions o hese expe imen s a e wo old: i s , we obse e
ha he algo i hm con e ges in all he cases; and second, ha he numbe o i e a ions equi ed
o con e ge a ies be ween 2 and 6 in all he cases. This means ha he con e gence o his
algo i hm is e y as e en o la ge sys ems wi h 200 dedica ed se e s.
7 Conclusions
We s udy he op imal Be noulli ou ing in a sys em wi h Cdedica ed se e s and a single
mul i-skilled se e . We i s p o ide a necessa y and su icien condi ion o he s abili y o
he sys em. We hen e o mula e his p oblem as a op imiza ion p oblem in e ms o he loads
o he sys em and we show he equi alence o bo h p oblems. We p o ide s uc u al p ope ies
123
966 Annals o Ope a ions Resea ch (2022) 312:949–971
on he solu ion o he de i ed p oblem, which allows us o ully cha ac e ize he op imal loads
o he sys em when C=2 and also o p esen a ixed poin algo i hm whose con e gence
ensu e ha he op imal loads a e ob ained. We compa e he pe o mance o his sys em wi h
op imal loads wi h a sys em whe e all he se e s a e mul i-skilled and also wi h a sys em
whe e all he se e s a e dedica ed. Finally, we explo e nume ically he con e gence o he
ixed poin algo i hm and show ha , in all he conside ed cases, he algo i hm con e ges in
a e y ew numbe o s eps.
Fo u u e wo k, we a e in e es ed in gene alizing he esul s o his a icle o sys ems wi h
a mo e complex opology. Besides, we hink ha an in e es ing ex ension o he pe o mance
analysis o his wo k would be o conside o he popula load balancing policies such as
Powe o Two and Join he Sho es Queue.
Funding Open Access unding p o ided hanks o he CRUE-CSIC ag eemen wi h Sp inge Na u e.
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included in he
a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I ma e ial is
no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed by s a u o y
egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he copy igh holde .
To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
A P oo o P oposi ion 1
We i s show ha i he e exis s a subse A⊂Ksuch ha i∈Aηi> 0+i∈A i, hen
he sys em is no s able.
We know om (1)and(2) ha
0ρ0+
i∈A
iρi=
i∈K
ηi(1−pi)+
i∈A
ηipi
=
i∈A
ηi+
i∈K A
ηi(1−pi)
≥
i∈A
ηi
> 0+
i∈A
i.
The e o e, we ha e ob ained ha 0ρ0+i∈A iρi> 0+i∈A i, which equi es ha , a
leas , he load o one se e is la ge han one, i.e., ha he sys em is no s able.
Le >0 small. We now show ha , i (6) holds, hen he sys em is s able. Fo his pu pose,
we de ine he ollowing ou ing s a egy: o all i∈Ksuch ha ηi< i,pi=1−and o
all i∈Ksuch ha ηi≥ i,pi= i
ηi(1−). Fo his choice, i is clea ha ρj<1 o all
j∈K. We now ocus on Se e 0 and we aim o show ha

i∈K
ηi(1−pi)< 0.
123
Annals o Ope a ions Resea ch (2022) 312:949–971 967
We deno e by K∗ he se o classes such ha ηi≥ i. Hence, he abo e exp ession is
sa is ied i and only i

i∈K K∗
ηi+
i∈K∗
ηi(1−pi)< 0
Hence,

i∈K K∗
ηi+
i∈K∗
ηi1− i
ηi
(1−)< 0⇐⇒

i∈K K∗
ηi+
i∈K∗
(ηi− i(1−))< 0⇐⇒

i∈K K∗
ηi+
i∈K∗
(ηi− i+ i)< 0
We know om (6) ha i∈K∗(ηi− i)< 0and, he e o e, he abo e inequali y is sa is ied
i and only i
⎛
⎝
i∈K K∗
ηi+
i∈K∗
i⎞
⎠< 0−
i∈K∗
(ηi− i).
In o he wo ds, he desi ed esul ollows i we choose >0 such ha
< 0−i∈K∗(ηi− i)
i∈K K∗ηi+i∈K∗ i.
B P oo o P oposi ion 2
In he ollowing esul , we p o ide a p ope y ha will be use ul o show he esul o
P oposi ion 2.
Lemma 3 Le ˜
C⊆K. Then,

i∈˜
C
ηi= 0ρ0+
j∈˜
C
jρj⇐⇒ Cb∪C0⊆˜
C.
P oo To simpli y he no a ion, we w i e D=Cb∪C0.I D=∅, henρ0=0andρj=ηj/ j
o j=1,2,...,C, which implies clea ly ha i∈Aηi=j∈SAρj j o all A⊂K.
We now ocus on he case D=∅. We know ha
ρj<η
j/ j,∀j∈Dand ρj=ηj/ j,∀j∈K D.(14)
We now obse e ha K=D(K D)and he e o e om (7)

i∈D
ηi+
i∈K D
ηi= 0ρ0+
i∈D
iρi+
i∈K D
iρi.
F om ρj=ηj/ j,∀j∈K D, i ollows ha

i∈D
ηi+
i∈A
ηi= 0ρ0+
j∈D
jρj+
j∈A
jρj,∀A⊆K D.(15)
123
968 Annals o Ope a ions Resea ch (2022) 312:949–971
The e o e, o any ˜
C⊆Ksuch ha D⊆˜
C he cons ain (9) is sa is ied as an equali y.
Besides, we now show ha o any subse ha does no con ain D, he cons ain (9)is
sa is ied as an inequali y. Fo all B⊂D,(15) can be w i en as ollows:

i∈B
ηi+
i∈D B
ηi+
i∈A
ηi= 0ρ0+
j∈B
jρj+
j∈D B
jρj+
j∈A
jρj,∀A⊆K D,
which, by ρj<η
j/ j∀j∈D, gi es ha

i∈B
ηi+
i∈A
ηi= 0ρ0+
j∈B
jρj+
j∈D B
jρj−
i∈D B
ηi
+
j∈A
jρj
< 0ρ0+
j∈B
jρj+
j∈A
jρj,∀A⊆K D.
And he desi ed esul ollows. 
We now p o e he esul o P oposi ion 2.
P oo The Lag angian co esponding o (LOAD-OPT)is
L(ρ,ν,ζ,γ,ξ)=c0ρ0
1−ρ0
+
C

j=1
cjρj
1−ρj
+
C

j=0
νj(−ρj)+
C

j=0
ζj(ρj−1)
+γC

i=1
ηi− 0ρ0−
C

j=1
jρj
+
A⊂K
A=∅
ξA
i∈A
ηi− 0ρ0−
j∈A
jρj
Gi en ha he op imiza ion p oblem is con ex, ρ∗,ν∗,ζ∗,γ∗,ξ∗is a solu ion o (LOAD-
-OPT) i i sa is ies Ka ush-Kuhn-Tucke condi ions:
0≤ρ∗
j≤1,∀j=0,1,...,C(16)
c0
(1−ρ∗
0)2−ν∗
0+ζ∗
0− 0γ∗+
A⊂K
A=∅
ξ∗
A=0 (17)
cj
(1−ρ∗
j)2−ν∗
j+ζ∗
j− jγ∗+
A⊂K
j∈A
ξ∗
A=0,∀j=1,2,...,C(18)
ν∗
j≥0,ζ
∗
j≥0,γ
∗∈R,ξ
∗
A≥0,∀j=0,1,...,C,∀A⊂K,A=∅ (19)
ν∗
jρ∗
j=0,ζ
∗
j(ρ∗
j−1)=0,∀j=0,1,...,C(20)
C

i=1
ηi= 0ρ∗
0+
C

j=1
jρ∗
j(21)

i∈A
ηi≤ 0ρ∗
0+
j∈A
jρ∗
j,∀A⊂K,A=∅ (22)
123
Annals o Ope a ions Resea ch (2022) 312:949–971 969
ξ∗
A
i∈A
ηi− 0ρ∗
0−
j∈A
jρ∗
j=0,∀A⊂K,A=∅.(23)
We obse e ha he objec i e unc ion ends o in ini y when ρj→1, which implies ha
ρ∗
j<1,∀j=0,1,...,Cand, as a consequence o his and om (20), ζ∗
j=0,∀j=
0,1,...,C. Fu he mo e, om Lemma 3and (23), we conclude ha ∀A∈K ha does no
con ain Cb∪C0, i s mul iplie e i ies ha ξ∗
A=0, because o hose subse s he cons ain
(9) is sa is ied as an inequali y.
Fo Se e 0, we know ha ρ∗
0=0i C0∪Cb=∅and ρ0>0 o he wise. This clea ly
implies ha ν∗
0≥0i C0∪Cb=∅and ν∗
0=0 o he wise. Fo all j∈K, we know ha
ρ∗
j=ηj/ ji j∈Cd, whe eas ρ∗
j<η
j/ jo he wise. This clea ly implies ha ν∗
j=0
i j∈Cd. We also know ha ν∗
j=0i j∈Cbbecause, in his case, ρ∗
j>0, whe eas i
j∈C0,weha e ha ν∗
j≥0.
We i s p o e his esul when Cb∪C0=∅. Fo his case, he load o Se e 0 is ze o
and, hus, i is enough o show ha δj<1−ηj/ j.F om(17)and(18), we ge ha
c0−ν∗
0− 0γ∗+
A⊂K
A=∅
ξ∗
A=0(24)
cj
(1−ηj/ j)2− jγ∗+
A⊂K
j∈A
ξ∗
A=0,∀j=1,2,...,C.(25)
F om (24) and since ν∗
0≥0, i esul s ha
ν∗
0=c0− 0γ∗+
A⊂K
A=∅
ξ∗
A≥0⇐⇒ c0
0
≥γ∗+
A⊂K
A=∅
ξ∗
A,
F om (25), we ob ain ha
γ∗+
A⊂K
j∈A
ξ∗
A=cj
j
1
(1−ηj/ j)2,∀j=1,2,...,C.
The e o e,
cj
j
1
(1−ηj/ j)2=γ∗+
A⊂K
j∈A
ξ∗
A≤γ∗+
A⊂K
A=∅
ξ∗
A≤c0
0
,
which gi es he desi ed condi ion, i.e., δj≤1−ηj/ j,∀j=1,2,...,C.
We ocus on he case C0=∅o Cb=∅. We no e ha (17)and(18) can be w i en as
ollows:
c0
(1−ρ∗
0)2− 0γ∗+
A⊂K
Cb∪C0⊆A
ξ∗
A=0 (26)
cj−ν∗
j− jγ∗+
A⊂K
Cb∪C0⊆A
ξ∗
A=0,∀j∈C0(27)
cj
(1−ηj/ j)2− jγ∗+
A⊂K
Cb∪C0⊆A
j∈A
ξ∗
A=0,∀j∈Cd.(28)
123

970 Annals o Ope a ions Resea ch (2022) 312:949–971
cj
(1−ρ∗
j)2− jγ∗+
A⊂K
Cb∪C0⊆A
j∈A
ξ∗
A=0,∀j∈Cb.(29)
We aim o show ha , o all j∈C0,δj≥1
1−ρ∗
0
,and o all j∈Cb1
1−ρ∗
0
>δ
j>1−ηj/ j
1−ρ∗
0
.
Fo he i s condi ion, we obse e ha om (26)and(27), i ollows ha , o all j∈C0,
γ∗+
A⊂K
Cb⊆A
ξ∗
A=c0
0
1
(1−ρ∗
0)2=cj
j
−ν∗
j
j
,
which, using ha ν∗
j≥0, gi es ha
δj≥1
1−ρ∗
0
.
We now show he second condi ion, i.e., 1
1−ρ∗
0
>δ
j>1−ηj/ j
1−ρ∗
0
o all j∈Cb.F om(26)
and (29), i ollows ha , o all j∈Cb,
γ∗+
A⊂K
Cb∪C0⊆A
ξ∗
A=c0
0
1
(1−ρ∗
0)2=cj
j
1
(1−ρ∗
j)2(30)
⇐⇒ 0=cj
j
1
(1−ρ∗
j)2−c0
0
1
(1−ρ∗
0)2(31)
⇐⇒ δj=1−ρ∗
j
1−ρ∗
0
,(32)
which gi es ha
ρ∗
j=1−δj(1−ρ∗
0),
as desi ed.
Using he las exp ession and ha , o j∈Cb,0<ρ
∗
j<η
j/ j, he desi ed esul ollows,
i.e.,
1
1−ρ∗
0
>δ
j=1−ρ∗
j
1−ρ∗
0
>1−ηj/ j
1−ρ∗
0
.
To inish, we compu e he loads o all he se e s. Fi s , o j∈Cd,we ha e clea ly ha
ρ∗
j=ηj
j. Besides, we use ha o all j∈Cb,ρ∗
j=1−δj(1−ρ∗
0), and om he exp ession
(7), i ollows ha
C

i=1
ηi= 0ρ∗
0+
C

j=1
jρ∗
j⇐⇒
C

i=1
ηi= 0ρ∗
0+
j∈Cb
j(1−δj(1−ρ∗
0)) +
i∈Cd
ηi.
And ea anging bo h sides o he abo e exp ession, we ob ain ha
ρ∗
0=1− 0+j∈Cb j−i∈Cb∪C0ηi
0+j∈Cbδj j
.
123
Annals o Ope a ions Resea ch (2022) 312:949–971 971
And he desi ed esul ollows. 
Re e ences
Al man, E., Ayes a, U., & P abhu, B. J. (2011). Load balancing in p ocesso sha ing sys ems. Telecommuni-
ca ion Sys ems, 47(1–2), 35–48.
Bonald, T., Com e, C., & Ma hieu, F. (2017). Pe o mance o balanced ai ness in esou ce pools: A ecu si e
app oach. P oceedings o he ACM on Measu emen and Analysis o Compu ing Sys ems.h ps://doi.o g/
10.1145/3154500.
Chen, J., Do, J., & Shi, P. (2020). A su ey on skill-based ou ing wi h applica ions o se ice ope a ions
managemen . Queueing Sys ems, 96, 53–82.
Feng, H., Mis a, V., & Rubens ein, D. (2005). Op imal s a e- ee, size-awa e dispa ching o he e ogeneous
M/G/- ype sys ems. Pe o mance E alua ion, 62(1–4), 475–492.
Fou neau, J.-M. (2020). Modeling g een da a-cen e s and jobs balancing wi h ene gy packe ne wo ks and
in e up ed Poisson ene gy a i als. SN Compu e Science, 1(1), 28.
Ga dne , K., Zba sky, S., Do oudi, S., Ha chol-Bal e , M., & Hyy ia, E. (2015). Reducing la ency ia edun-
dan eques s: exac analysis. In P oceedings o he 2015 ACM SIGMETRICS In e na ional con e ence
on measu emen and modeling o compu e sys ems, SIGMETRICS ’15, Associa ion o Compu ing
Machine y, New Yo k, NY, USA (pp. 347–360).
Gaujal, B., Hyon, E., & Jean-Ma ie, A. (2006). Op imal ou ing in wo pa allel queues wi h exponen ial se ice
imes. Disc e e E en Dynamic Sys ems, 16(1), 71–107. h ps://doi.o g/10.1007/s10626-006-6179-3.
G aham, C. (2000). Chao ici y on pa h space o a queueing ne wo k wi h selec ion o he sho es queue among
se e al. Jou nal o Applied P obabili y, 37(1), 198–211. h ps://doi.o g/10.1239/jap/1014842277.
Ha chol-Bal e , M. (2000). Task assignmen wi h unknown du a ion. In P oceedings 20 h IEEE in e na ional
con e ence on dis ibu ed compu ing sys ems (pp. 214–224). IEEE.
Ha chol-Bal e , M., C o ella, M. E., & Mu a, C. D. (1999). On choosing a ask assignmen policy o a
dis ibu ed se e sys em. Jou nal o Pa allel and Dis ibu ed Compu ing, 59(2), 204–228.
Kelly, F. (1979). Re e sibili y and s ochas ic ne wo ks. Technical epo .
Koole, G., Po , A., & Talim, J. (2003). Rou ing heu is ics o mul i-skill call cen e s,2, 1813–1816.
Liu, Z., Lin, M., Wie man, A., Low, S., & And ew, L. L. H. (2015). G eening geog aphical load balancing.
IEEE/ACM T ansac ions on Ne wo king, 23(2), 657–671.
Lu, Y., Xie, Q., Klio , G., Gelle , A., La us, J. R., & G eenbe g, A. (2011). Join-idle-queue: A no el load
balancing algo i hm o dynamically scalable web se ices. Pe o mance E alua ion, 68(11), 1056–
1071.
Mi zenmache , M. (2001). The powe o wo choices in andomized load balancing. IEEE T ansac ions on
Pa allel and Dis ibu ed Sys ems, 12(10), 1094–1104.
Taboada, I., Aal o, S., Lassila, P., & Libe al, F. (2017). Delay and ene gy-awa e load balancing in ul a-dense
he e ogeneous 5G ne wo ks. T ansac ions on Eme ging Telecommunica ions Technologies, 28(9), e3170.
V edenskaya, N. D., Dob ushin, R. L., & Ka pele ich, F. I. (1996). Queueing sys em wi h selec ion o he
sho es o wo queues: An asymp o ic app oach. P oblems o In o ma ion T ansmission, 32(1), 15–27.
Wallace, R. B., & Whi , W. (2005). A s a ing algo i hm o call cen e s wi h skill-based Rou ing. Manu ac-
u ing & Se ice Ope a ions Managemen , 7(4), 276–294.
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps and
ins i u ional a ilia ions.
123