ON THE STEADY STATE PROBABILITIES
CONCERNED WITH TANDEM QUEUE
BYYoslRo TUMURA
1．Introduction． Let us consider；at丘rst， the two stage tandem queueing system・ M（Z）／M（Pt・）／1（。。）→M（Pt，）／1（N） shown in the fbllowi㎎丘gure： input rate λ 1st stage service waiti皿9 2nd stage service statlon roo血 statlon ⇒ rate μ1 一〇〇… ○○一number hmit
N Fig． 1 rate μ2 s ⇒ that is， customers arriving at random join immediatly another single queue after 丘nished the first stage service， where the service time in i−th station distribute a㏄ording to the exponential with the mean 1／μh（匡＝1，2）． And therfbre in the state when the second station is oocupied， we suppose that the customer must wait in the waiting room or in the 6rst station． As there is the limitation IV in the number of accomodation of the customers in the waiting room， a customer out of the lim三ta− tion∧「is in the state of occupying the 丘rst service station， that is to say， there occurs the state of blocking． A customer waiting in the first station after f桓ished the service is assumed as a member of the second queue． It has been proved［1］that the stability condition of the system is ρ＜γ（1十γ十… 十γN＋1）／（1十γ十… 十rN＋2）， （1．1）where
ρ＝λ／μ1 and γ＝μ2／μ1 However it is somewhat difficult to calculate in a common way the mean waiting time， mean nulnber of customers in queues fbr the system except in the case of lV＝0， that is， there is ng waiting room． In this paper we shall show some theorems concerning the tandem queueillg problems and bring hght why these problems have not been solved in the cases of IV＞0． Let．＠，ノ）be the． state in which the numbers of customers in the丘rst and the second queues are i and／respectively， and 」馬ゴbe the probabilities that the system be in the state（i，ノ）． Then we have f（）110wing equations fbr the steady state：［1］
2 Y．TUMURA
｛騰瓢…（一一 ’
ρPi＿1，0十rP 1＝＝（1十ρ）」PiO ’ ρ」Pi＿1， j＋1一トP，＋1， i十γPi，」＋2＝（1一トr十ρ）Pi，∫＋1 （ノ＝0， 1， … ，N） ρ・Pi＿1， N＋2十・Pi＋1， N＋1＝＝（γ十ρ）Pi，」V＋2 （i≧1）and
ΣP｝グ．−1，Pl」≧O It is㎞portant fbr the system evaluation that the values of Pii， Poo are obtai4ed． In the case where N＝0， we have i r（1＋r）一（1＋γ＋γ2） 几o＝− 1十γ十ρ γ However in the case where IV≧1， One may note that in the case of N≧1．the homogeneous without the restriction（L3）are indetem〔血late fbrm even in therefore f（）r given ・pbo equations （1．2）without （1．2） （1．3） esp㏄ially that of （1．4） we have not yet obtained the value．P』o． 1hlear equations （1．2） the ratio between pij， （1．3）can not be solved uniquely． At first sight this seems curious and to contradict the stab血ty Under（1．1）2．Co皿sideratio鵬on some Recurrence Equations． SupPose the simuhaneous
linear recurrence equations with variables of in丘nite llumber， but each equation co皿taining o皿1y五nite． number． We o丘en丘皿d equations of this type． In fact， the equations（1．2）』are those of this type． Let us◎onskler the equations： ・・ BIXk十B2Xk−1十… 十BbXl十Bk＋IXo＝P ． （2・1） ノ〔IXv＋．先十∠12xレ＋鳶＿1十… 十ノtkXY＋1十ノlk＋IXv＝0 （2．2） where the symbols・xv， xo， p，ん」Bi are denoted as the fbllows： Xp Xo・・・・… 一・・・・・・・・・・… P ’’”°”一一’°’’’’”r・’”… Ai（i＝1， … ， k十1） ・・・… Bi（’＝1，…k）………… B｝．1…………・…・…We assume that
rank（β1，…， rank（β1，… ， ．（mo≧1） AI is non singular． So we can select mo XOj＊， ．n dimensional vector 〃odimensional vector llon zero m dimensional◎onstant vector n×n．square Inatr1Xm×nmatr1X
m×no matnX， Bk）＝・・nk βみ＋1）＝rank（β1， … ， Bk．、s P）−nk＋n。一〃1。 （2．3） variables of xo， say xoi＊（ノ＝．1，…， Me）， such．that for given xy（v≧1）are uniquely determ血ed． Let mo be’the degr㏄of indetermination． One may rewrite the equations（2．1）and（2．2）by the fbllowing equations：where
ON THE STEADY STATE PROBABILrr】ES CONCERNED
Pyv＋1＝（］Yy ．（〃＝0， 1，2， … ） 0 ・・・… 0 ∠41θ・… OP＝
・ ． … ． ． ・ ・ ， ・ ・ Ak Ak−1−一…A1e−一
．4A＋1／1烏・…・、42 0．4鳶．1…．4300…OA鳶．x
（2．4） 3 yノー（x。k．、’，…，x（、＋、）鳶’）， ’． and Yoノ＝（xl，，…， xkt）is a sohltion of（2．1）， each element of which is the Hnear fbrm of x。ゴ＊（ノ＝1，2，…， Mo）． The homogeneous equations（2．1）and（2．2）， consequently（2．4）， can not be solved ulliquely， therefbre additional infbrmations are desirable． It is natural to assume the condition Yy．are bounded （2．7）or
limル＝0 （2．8） which are impHcity colltai皿ed in（L3）． Now we w血attempt to丘nd the collditions that the equations（2．1）and（2．2）assuming the corrdition（2．7）or（2．8）have unique solution． Letλ1， Z2，… ， Znh be the characteristic roots of the matrix P−1（∼assuming lλ、1≧lz、≧…≧12。k1， and sッbe the characteristic vector associated withλ“． Settillg up s’一（s、s2，…，s。k）， we have丘om（2．4） ． Yy＝」∫−11）λレSyo 、where 1）λindicates the diagonal matrix with the diagonal elementsλ． Now we will complete the proof of the fbllowing theorem： Lε〃1〃la 2．1． 7？ピequations（2．1） and（2．2）ha昭a boundedぷolutionぴand only るf theノ’ollowing areぷtatisfied （i） all characteristic roots㎡the〃latrix 」P−1（∼are not greater than uniリノin the abぷolute valueぷ， or （ii ） ｝vhen t／2ere exist α charactejド匡ぷtie roots greater ’乃α〃 〃nit）ノ in the abぷolute value， the conditions Sg Ye＝0 （ξ＝1，2，…，α） are satisfied． Proof Putting Z＝・ Sy。， S−1 ・・ T’一（t、，…， t。k）’，we have
y・一ア・Dλ〃2 where Dλ〃。桓dicates the diagonal matrix with the diagoanal elementsλyz． It wi皿 be suHlciellt to consider the fbllowing two possibiUties： ■4
Y．TUMURA
（i） thecaseoflλil＞1λ21and IRll＞1． For any su丘icient large〃 ぽ・・［t・・z・＋・（lf’ i”）］・ Si皿ceルis bounded， tendingッto infinity we have tii ＝O or z1＝0． On the other hand， if tj1＝O （ノ＝1，… ， k） Tlis singular， this is’a contradiction to the regularity of S． 】lence， z1＝0． 111the same ma皿er we have Zar＋1＝O for zl＝z2＝”…．＝zal＝Oalld 1λal＋11＞max（1，1λα・＋21）． （li）The case of lA，ト1λ21＝…＝1λβ1＞max（1，1，Zβ＋11）． If we assume zξキ0（ξ一1，2，…，β’；β’≦β）， the皿 β’ ルゴ＝Στぷ〃z‘＋Σti・iλivzi． i＝1 i≧β＋1 For the case ofβ’−1， we can prove as well as in the case of（i）． So we assume β，＞1． Putting ． λξ＝reiθξ 一 r＞max（1，1λβ＋1 D＝ro（say）， we have．fbr the large value of〃 ． ル’一〆・・〃・1［￡’・ξ・…〃・・ξ一θ・）＋・｛（÷）レ｝］or
隼・・ξ… ξ一…一・［（÷）］・ （…） Here we◎onsider、two parts， the part of rational number and the part of irrational， with regard to（θξ一θ1）／2π． Let a be the 1east common mUltiple of the denomina− tors in the first part． By takingり＝a，2α，…in（2．9）， we obtain Σ・ra・・’・ξ・・＋Σ・・…・・ξ・・・…eξ一・一・［（÷）］・ （・・1・） It is easily seen that each sum of the left hand side of（2．10） converge to 乞ero， sinceレ（θξ一θ1）are everyWhere dense in（0，2π）． Therefore we have Σ（ra・） t」’ gzξ ＝ O． Since T is llon singular， we have fbr the part of ratiollal zξ＝O． By the same argument we can prove also zξ＝Ofbr’狽??@part of irrationa1．ρ．E．D．We◎ould prove also
L卿〃la 2．2． The equa’ions （2．1）and（2．2） aぷsoeia’ed ｝ワ∬乃 （2．8） have a ∫01〃tion〃吻ue if and onlyぴωa〃C加蹴’eriぷtic rOO’5げP’ρare le∬吻η励砂∫肩ん
absolute切加θ， orθwん〃the1e exis’αcharac’eriぷ’匡cγoo’ぷZξ5〃c乃吻’IZξ1≧1， ’んcoη姻oηぷSg’y。−0（ξ一1，…，α）areぷa’isfied． From these two lemmas we have immediatlyON THE STEADY STATE PROBABILITIES CONCERNED
5 Le〃2〃la 2．3． The〃eceぷsar）ノandぷμがcjθπ’co〃ditio〃’hat the equatiO nぷ（2．1）α〃∂（2．2） associatedハ伊ith τ乃θ co〃4孜∫o〃 （2．7） have a u〃∫（7〃θ ぷolut匡oπ are the ／b〃bws： ザ’乃eγθ areαcharacterisガc roots AξげP−1ρsuchτ肋τ1λξ1＞1， the equations 5ξ勺？o ＝＝ O （1，2， … ，α） shOU〃beぷolved・U吻uely， whereぷξare the eharac’eriぷtic vectOrS corresponding’0λξ and Yo，＝（x1’，’”， Xkt） iぷ α solu’ion Oブ （2．1） ｝〃，∫〃ε〃 in τ乃ε 膓i〃ear プ∂r〃ls げ Xoj＊ ｛ノ＝1，2， 一・，〃lo）． ザwe eonsider the e4ua’ionぷ aぷsociated with ’乃θ condition （2．8）， ｝ve η2qア replace ’ん匡ηθσ〃alities lλξ1＞1 by lλξ1≧1． Re〃iark． The essential part of the condition（1．3）is．Plj≧0． So it is desirable to find the condition that the equations （2．1） should have a solution such that アPj≧0（ノ＝・1，…， nk；〃＝1，2，…）． We could prove easily that the necessary con− dition（not s面cient）is the、 same as that of Lemma 2．L 3．Two stage tandem queueiロg system． Now we shall apply the results伍the last s㏄tion to the two stage tandem queueing system． As the problem is to find the ratios between Pii， the first equatioll in（1．2），γPoi＝ρPoe， should be exduded as− suming Poe， consequently、Poi also， given． Challging the order of the equation（2．1） so as to satisfy the conditions（2．3）， we have three groups of equations： （1） （equations generatillg variables which can take arbitrary values） ・−1，・，…，［N；1］ ’ （a） （b） （c） （II） （a） （b） （c） （III） ・（a） （b） （c） ρPy＿1，0一トγ」P㌧1＝（1十ρ）P』o ρPy＿《＿1，2ぴ＿‘）＿1十Pレ＿i＋1、2（ジ＿‘ト2十γ」P』＿i，2（ン＿‘）＝（1十γ十ρ）Pレ＿ち2ぴ＿鈴＿1︷
ρPレ＿《＿1，2ぴ＿i）十Py＿i÷1，2（ッ＿5）＿1十γP㌧＿i，2（ン＿ど）＋1＝（1十γ十ρ）Pp＿i，2（ツ＿ξ｝ （i＝1，2， ・・．・， ソー1） P，，・・．2＋γP。，2戸（γ＋ρ）P。，2・．、︷
P1，2ッ＿1十γjPt），2レ＋1＝（γ十ρ）Po，2レ︸
ζ之鷲㌶ir）一
（Recin−ce eq・・…n・）・一［2V十1 2］＋！＋ノ・ノ＝−1・ ・q・・・・…緬ea・th・・e・・（1）（・）・・d（・）・…w・thv−［讐1］＋1 2，3，… ｝・qua・…ssame a・th・・e・・（1）（・）and（・）・…w・・h−［Nま1］＋1＋ノζ：㍍竃議鷲蒲＋・）一
6 Y．TUMURA
where［xコ．den・tes the largest int・ge・n・t gr・ate， than x． Fquati°ns（1）・・d（H）。・鵬・p・・d t・（2・1）・・d（m）t・（2．2）． Th・ 。q。ati。n，（1） 讐1］記・・…q・・…n・，・・d each S。・g。。。，a、es。n。 n。w。，b、吻・・・・・・…［ va「’“b’e・’S°th・d＝・f’・d就・面・a・i・n・・（・）・・eq・・1・・［N剖・V・1・…f the．va亘ab1・・i・σ）b血91gi・・n・th・equati・n・（II）and（IH）can』・・1。ed。。iq。。1y． So we have．働・em 3・1・Th・・9〃・卿（1・2）w鋤蜘’乃・・’W・’・吻，・5。b硫．、げ，ん
’脚卿・’・吻1ご㎎’sy・・erp』「N；1］←・・げ・励・・朋加・伽
F°「N＝°wh・・e・h・・e・・n・・血・岨…g…m・［N；1］一・，・・d・・w・ha・・a・
acorollary，⑭吻・Th・・9〃・伽・（1・2）…6・醜4卿u・ly in・乃…伽加’we．砧、ー
ﾑ
απ40ψぴ1V−0．
Using th・n・白ti・n i・th・previ・us s㏄ti・n， we can・e・・th・f。ll。晒。g、、 A， ＝＝ 一（1．＋ρ）r 1 0 0 100 00
fbr odd IV O …・＿＿．．． γ’”・・・・・・… 一（1十γ十ρ） 一… 一・ ． ■ ． ・ ■ ． 0 ・・0…… 1
000
一（1十γ十ρ）γ0
， A・〒D（ρ・一（1＋γ＋ρ），ρ，…，ρ，一（γ＋ρ））， A3f＝1）（0， ρ，0， ρ， … ， 0， ρ），and
P−・ρ一践㌦f A3二xA1 −xA2 determinant in（3．1）it is fb一
∼﹂01
の＋10
0
一 … ■■ ‥ 9■ 1■⋮00、O
oo⋮000
IA3． The characteristic equation of P−1ρis rewritten as 丘）reven」V O ・…・… 0 0 0γ……0 0 0
・・0 0 0 ． ． ． ■ ■ ■ ■ ■ ● ● ． ． ・ ． ． ． ・ ・ ． 0 ・・一（1十γ十ρ）γ 00・・…・r O γ
0 ・・・… 0 1 −（γ十ρ） ．…@， 0， ρ， 0） This equation has a root−1 independently ofρand und that aH elements ha鴨a common factor x十1， and （3・1）h・・a1・・・・・・…d・p・・d…1y・・…d・（ as saw皿丘om the structure of the matrix A3．・q…em・・…es・（・・1）…（・N＋・問）
have
1）（ρ・一（1＋γ＋ρ），ρ，…，ρ，一（1＋γ＋ρ），ρ） 1）（0， ρ， 0， ρ，蕊一（A、．W｝
A2
A、−xA、＝0・@ （3・1）
γ，．丘）radding all rows of the 岨・h迦1・・p・・・・…2＋［幻品・ρ〉・） As．41，．42 alld．43 are（N十3）×（1V十3） roots which depend onρandγ． Thus weON THE STEADY STATE PROBABILrrIES CONCERNED
7 TheOre〃13・ユ Theぷteadγぷ’a’eクrobabilities of’舵’｝vo 5tage・・ ta〃de〃1 ・q〃ε〃ε印9 sys’診〃2・励・w・i〃・鋤輌al・fu・・’わ祠’‥〆 ・quatlio…（・N＋・一閉）一・・
degree， which iぷ’〃ε砺c肪品 ‘‘加general，，． 1 Let us show examples whereγ＝1． ：．’ ．［EXAMPLE］
Characteristic roots，γ＝1 independent ofρ 9reater than l in abs． value N＝1，ρ＝0．3100
一 」V＝1，ρ＝0．5100
一 N＝3，ρ＝0．51000
一 一33．85456 一54．34343 一343．85622 − 4．59489 1ess than l in abs． valロe一1126
−．0687 −．0204 −．0124 一．3689 −．1506 −．0471 −．0275 一．2963 −．2008 −．0770 −．0442 −．0307 −．0249 A皿dwe have the ratios Pio：Poo， as fo皿ows： for N＝1， ρ＝0．3 PiO／Poo＝0．302 f（）rN＝1，ρ＝0．5 PiO／Poo ＝＝ O．509． 4・Three stage tandem queueing system・・p・・犠｛欝岨・m・…m鴛。器：ew・・…g…m3慧。謡・
＝＝＝＝＝＝〉 一〇〇… ○○一 一〇〇… ○○一 ＝＝＝＝＝＝〉・a・… a・…nUm暢Umit・a・・μ・nUm㌣Hmit輪μ・ ・
Fig． 2． Let us consider the three stage tandem queueing system as above， the servlce time inソーth service station distributes according to the exponential with the mean 1／μレ， having a waitillg、rooln of the number limitハイbetween the丘rst and the s㏄ond service stations and that of」V between the second alld the third． The stability condition of the system has been obtained by Mr． G． C， Hunt［1］ in the special case where．M＝1V＝O andμ1＝μ2＝μ3， and by Mdkino［2，3］in the general case． ヱ Let〃・iand／be the numbers of customers who are in service and waiting for the血rst・the s㏄co皿d and the third stage service respectively． Let P』ii be the steady state probab伍ties that the system be in the state（n， i，ノ）．8
Y．TUMURA
Then we have the fo皿owing equations： and those for n＝O， which are written by sides and the termsμ1 in the brackets of the right hand sides． Changing the order of equations as in the previous s㏄tion， we could have， in the same manner， the degree of indetermination： （M＋・）［N；1］＋M＋1・ λP．＿LO；O十Pt3PnO1＝（λ十μ1）Pneo ZPn−、，。，ゴ＋μ、P．，、， i．、＋μ・P，，・，∫．・一（Z＋μ・＋μ・）Pn・i （ノ＝1，2，‥・，ハ「十1） RP・一・，・， N・・＋μ・Pn，・， N・・一（Z＋μ・＋μ・）P・，・， N・2 、’ λPn＿1， i，0十μ1Pn＋1， i＿1，0十iU3Pn， i， O＝＝（λ十μ1十μ2）Pnio ZP．一・，i，・i＋μ・Pn・・，i・・，・j＋1・ip・， i・・，5−・＋X…P・，・i， i・・〒（λ＋μ・＋μ・＋μ・）P・・i （ノ＝1タ2，・・㌔N十1） ZP。一、， i． N．，＋Pt、p．．、， i−、， N．・＋μ・P。， i．・， N．・一（Z＋μ・＋μ・）P・， i． N・・ （∫＝1，2，…，M＋1） λPn＿1， M＋2，0十Ptlp．＋1， M＋90十lt3Pn， M＋2，1＝（λ十μ2）」Pn， M＋2，0 λP。一、，M．2，，＋μ、Pn．、， M．、， j＋μ3孔，□，∫．・一（λ＋μ・＋μ・）Pn， M・・2， i （ノー1，2，…，N） λP。一、，M．2， N．、＋μ、Pn．、． M．・． i−（Z＋μ2＋μ3）P．， M・・． N．・ omitting the first terms in the left hand Degree of indeterminationSlli−一一一M−一
コ リ う135
0 ︵∠4．6 0 12
34
1470
1
11瓦
210．04﹁
−八−
つ♪839V
1凸12
40102
P︶2Q／6 11︵∠
The order of the matrices．41， A2’and．43 are equal to（M十3）（N十3）−1， and the matrix P−1（∼has roots−1 and O（with the multiplicities M＋・＋（M十2）［N；2］＋［N；1］） independently ofλ，μ1，μ2 andμ3． It has also ・（M十3）（N＋・）一（M＋・）一（M＋・）［N；2］一［N；1］ （4・・） roots which depend oロλ，μ1，μ2 andμ3． These are roots of a polynominal in the degr㏄（4．2）which is‘‘in genera1”irreducible． Even in the simplest case of M＝N；0， we must solve the equation in 9−th degree． Thus， we have the same result as in the previous s㏄tion． 5．Approximate solutions↓The argument in the previous two sections indicate the method to solve the steady state probabilities in the tandem q血eUeing system．ON TH〔E STEADY STATE PROBABILITIES CONCERNED
rN・・［γ（1＋γ＋’”＋γ恒）一ρ（1＋γ＋…＋γN＋2）コ ー，壽・、［（1＋・＋…＋・…）＋・（1＋t＋……）コP・・ ＋1・［1＋・＋…＋・・一・コP・・＋…＋÷P・，・N… Noting the ratios、馬／Peo have been dete㎡ned uniqudy， we may assume蓋一｛㌫蕊丁3＋〃：‡差㌶
Putting（5．3）血（5．2）or（5．1）we have Theo昭〃5．1． ・f theぷ吻⑳ぷtate・pr・bability P。。元s・givenめ・the f・ll・wぷごP…N・≒1＋，＋．≦鵠諾夢二鵠蒜圭鵠年，）＋，。．、・
1｝zsρecial case判∼hereγ＝1， thθ〃IOre exact approxi〃m’ion iぷgiven／bアハr≧1α P・・…≒［（N＋2）一（N＋・）・コ／［（N＋・）＋（N＋1）・＋…＋…＋・…二（1一劉・…一（・」3＋13跳62N＋55）・…
一（・」5＋24N4＋271N3き劉N2＋4・672N＋2・952）・…］
（1一ρ）29
To calc司ate血e・’characteristic roots of a non symmetric matrix P・iC is， howevef， not so easy， even if a computeiC were．．used， since one root is rather large in the absoiute value and many roots assemble together near zero． So’the approximate expressions would be desirable． Two stage tandem queueillg system． Let ロ Fj一Σ・Pli， ■■0 乃being the values of the gellerat血g functions ち（z）of the st6ady state probab皿i− tles P｝j at z＝1． From the equationss（L2）， we get ち・・→F」一÷・・∫（ノー・，1，…，N＋1）・ From this relation andΣ乃＝1， we have 1㌔一1一ρ／γ （5．1）and
1 （5．2） （5．3） In’ん’WOぷ晦e tandem q〃euei噌鋼’θ〃π乃θ卿rOX’〃2α’e．expre∬ion （5．4） s／b〃bws： （5．5） “1＋、』．、ρ・・3＋N2＋鐸＋24・N・4＋N4＋22N3＋黙＋662N＋9°°・N・5’ Rθ〃iark・ The expression of the coe伍cients ofρN＋夕in the denominator of（5．5） does not hold if〃≧N十5， since the coe伍cients ofρ2（N＋2）＋・（〃≧1）need diMrent forms 伽mthose shown in（5．5）． For example， in． the case of IV＝O・；（5．5）’does not hold 品rthe sake of the te㎝ρ5． The general expression is too co血plicate． Therefore，10 Y．TUMURA if the more exact expression is llecessary it will be better to calculate for given IV． E・peci・Uy・wh・・th・・ize・f N i・，eq・・l t・0・1・and 2 w・hav・ f・・N−・P・・−11fi＋ile3pP（・h・・exp・・ss・・…exac・）
