Buzen's algorithm: Difference between revisions

Revision as of 17:25, 7 February 2022

Revision as of 19:58, 22 May 2023

Line 1:

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], '''Buzen's algorithm''' (or '''convolution algorithm''') is an algorithm for calculating the [[normalization constant]] G(''N'') in the [[Gordon–Newell theorem]]. This method was first proposed by [[Jeffrey P. Buzen]] in his 1971 PhD dissertation<ref name=":0">{{Cite book |last=Defense Technical Information Center |url=http://archive.org/details/DTIC_AD0731575 |title=DTIC AD0731575: Queueing Network Models of Multiprogramming |date=1971-08-01 |language=english}}</ref> and subsequently published in a refereed journal in 1973.<ref name="buzen-1973">{{Cite journal | last1 = Buzen | first1 = J. P. | author-link = Jeffrey P. Buzen| title = Computational algorithms for closed queueing networks with exponential servers | doi = 10.1145/362342.362345 | url = http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf| journal = Communications of the ACM | volume = 16 | issue = 9 | pages = 527–531 | year = 1973 | s2cid = 10702 }}</ref> Computing G(''N'') is required to compute the stationary [[probability distribution]] of a closed queueing network.<ref name="gn">{{Cite journal | last1 = Gordon | first1 = W. J. | last2 = Newell | first2 = G. F. | author-link2 = Gordon F. Newell| doi = 10.1287/opre.15.2.254 | jstor = 168557| title = Closed Queuing Systems with Exponential Servers | journal = [[Operations Research (journal)|Operations Research]]| volume = 15 | issue = 2 | pages = 254 | year = 1967 }}</ref>

Performing a naïve computation of the normalising constant requires enumeration of all states. For a systemclosed network with ''N'' circulating jobs and ''M'' statesservice therecenters, areG(N) is the sum of <math>\tbinom{N+M-1}{M-1}</math> combinationsindividual terms. Buzen's algorithm "computes G(1), G(2), ..., G(''N'') using a total of ''NM'' multiplications and ''NM'' additions." This is a significant improvement and allows for computations to be performed with much larger networks.<ref name="buzen-1973" /> The values of G(1), G(2) ... G(N-1), which can be used to express other quantities of interest,<ref name=":0" /> are also computed as by-products.

==Problem setup==

Line 17:

==Algorithm description==

Write g(''N'',''M'') for the normalisingnormalizing constant of a closed queueing network with ''N'' circulating customers and ''M'' service stations. The algorithm starts by noting solving the above relations for the ''X''_''i'' and then setting starting conditions<ref name="buzen-1973" />

::<math>g(0, m) = 1 \text{ for }m=1,2,\cdots,M</math>

::<math>g(n, 1) = (X_1)^n \text{ for }n=0,1,\cdots,N.</math>