ในทฤษฎีคิว ซึ่ง เป็นสาขาหนึ่งใน ทฤษฎีความน่าจะเป็นทางคณิตศาสตร์อัลกอริทึมของ Buzen (หรือ อัลกอริทึมการสังเคราะห์ ) เป็นอัลกอริทึมสำหรับการคำนวณค่าคงที่การทำให้เป็นมาตรฐาน G( N ) ในทฤษฎีบท Gordon–Newellวิธีนี้ได้รับการเสนอครั้งแรกโดยJeffrey P. Buzenในวิทยานิพนธ์ปริญญาเอกของเขาในปี 1971 ^{[ 1 ]}และต่อมาได้รับการตีพิมพ์ในวารสารที่ได้รับการตรวจสอบโดยผู้ทรงคุณวุฒิในปี 1973 ^{[ 2 ]}การคำนวณ G( N ) เป็นสิ่งจำเป็นในการคำนวณการกระจายความน่าจะ เป็นแบบคงที่ ของเครือข่ายคิวปิด^{[ 3 ]}

การคำนวณค่าคงที่มาตรฐานแบบง่ายๆ จำเป็นต้องแจงนับสถานะทั้งหมด สำหรับเครือข่ายปิดที่มีลูกค้าหมุนเวียนN ราย และสิ่งอำนวยความสะดวกด้านบริการ Mแห่ง G( N ) คือผลรวมของแต่ละเทอม โดยแต่ละเทอมประกอบด้วย ปัจจัย M ตัวที่ยกกำลังซึ่งผลรวมคือNอัลกอริทึมของ Buzen คำนวณ G( N ) โดยใช้การคูณเพียงNM ครั้งและ การบวก เพียง NM ครั้งการปรับปรุงครั้งสำคัญนี้เปิดประตูสู่การประยุกต์ใช้ทฤษฎีบท Gordon-Newell กับแบบจำลองของระบบคอมพิวเตอร์ในโลกแห่งความเป็นจริง เช่นเดียวกับระบบการผลิตที่ยืดหยุ่นและกรณีอื่นๆ ที่อาจเกิดคอขวดและคิวขึ้นภายในเครือข่ายของสิ่งอำนวยความสะดวกด้านบริการที่เชื่อมต่อกัน^{[ 4 ]}ค่าของ G(1), G(2) ... G( N -1) ซึ่งสามารถใช้ในการคำนวณปริมาณสำคัญอื่นๆ ที่น่าสนใจ จะถูกคำนวณเป็นผลพลอยได้จากอัลกอริทึม ${\displaystyle {\tbinom {N+M-1}{M-1}}}$

พิจารณาเครือข่ายคิวปิดที่มีศูนย์บริการM แห่ง และลูกค้าหมุนเวียน Nราย สมมติว่าเวลาให้บริการของลูกค้าที่ศูนย์บริการiกำหนดโดย ตัวแปรสุ่ม ที่มีการแจกแจงแบบ เอกซ์โพเนนเชียล โดยมีพารามิเตอร์μ _iและหลังจากเสร็จสิ้นการบริการที่ศูนย์บริการi ^แล้วลูกค้าจะไปยังศูนย์บริการj ต่อไป ด้วยความน่าจะเป็นp _ij [ ^{3 ]}

ให้เป็นความน่าจะเป็นสภาวะคงที่ที่จำนวนลูกค้า ณ สถานที่ให้บริการiเท่ากับn _i สำหรับi = 1, 2, ... , M จากทฤษฎีบทของกอร์ดอน-นิวเวลล์ จะได้ ว่า ${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}}$${\displaystyle \left(X_{1}\right)^{n_{1}}}$${\displaystyle \left(X_{2}\right)^{n_{2}}}$....${\displaystyle \left(X_{M}\right)^{n_{M}}}$

ผลลัพธ์นี้มักเขียนในรูปแบบที่กระชับกว่าได้ดังนี้

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^{n_{i}}}$

ค่าของX _iถูกกำหนดโดยการแก้สมการ

${\displaystyle \mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\quad {\text{ สำหรับ }}j=1,\ldots ,M.}$

G ( N ) คือค่าคงที่มาตรฐานที่เลือกไว้เพื่อให้ผลรวมของค่าทั้งหมดของเท่ากับ 1 อัลกอริทึมของ Buzen แสดงถึงขั้นตอนที่มีประสิทธิภาพแรกในการคำนวณ G( N ) ^{[ 2 ] [ 4 ]}${\displaystyle {\tbinom {N+M-1}{M-1}}}$${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$

พจน์แต่ละพจน์ที่ต้องนำมาบวกกันเพื่อคำนวณ G( N ) ล้วนมีรูปแบบดังต่อไปนี้:

${\displaystyle \left(X_{1}\right)^{n_{1}}}$${\displaystyle \left(X_{2}\right)^{n_{2}}}$.... โปรดสังเกตว่าชุดพจน์เหล่านี้สามารถแบ่งออกเป็นสองกลุ่ม กลุ่มแรกประกอบด้วยพจน์ทั้งหมดที่มีเลขชี้กำลังมากกว่าหรือเท่ากับ 1 ซึ่งหมายความว่าสามารถดึงตัวประกอบ 1 ที่ยกกำลัง 1 ออกจากแต่ละพจน์เหล่านี้ได้   ${\displaystyle \left(X_{M}\right)^{n_{M}}}$${\displaystyle \left(X_{M}\right)}$${\displaystyle \left(X_{M}\right)}$

หลังจากแยกตัวประกอบแล้วผลลัพธ์ที่น่าประหลาดใจก็ปรากฏขึ้น: เงื่อนไขที่แก้ไขในกลุ่มแรกนั้นเหมือนกับเงื่อนไขที่ใช้ในการคำนวณค่าคงที่มาตรฐานสำหรับเครือข่ายเดียวกันโดยที่ลูกค้าหนึ่งรายถูกลบออกไป ดังนั้น ผลรวมของเงื่อนไขในกลุ่มแรกจึงสามารถเขียนได้เป็น “ X _M คูณ G( N -1)” ความเข้าใจนี้เป็นพื้นฐานสำหรับการพัฒนาอัลกอริทึม^{[ 4 ]}${\displaystyle \left(X_{M}\right)}$  

ต่อไปให้พิจารณากลุ่มที่สอง เลขชี้กำลังของX _M สำหรับทุกพจน์ในกลุ่มนี้เป็นศูนย์ ส่งผลให้สถานบริการM หายไปจากทุกพจน์ในกลุ่มนี้อย่างมีประสิทธิภาพ (เนื่องจากในทุกกรณีจะลดลงเหลือเพียงปัจจัย 1) ทำให้จำนวนลูกค้าทั้งหมดที่สถานบริการที่เหลือM - 1 แห่ง เท่ากับNกลุ่มที่สองนี้ประกอบด้วยการจัดเรียงที่เป็นไปได้ทั้งหมดของลูกค้า N รายนี้

เพื่อแสดงแนวคิดนี้อย่างแม่นยำ สมมติว่าX ₁ , X ₂ , … X _M ได้รับมาแล้วสำหรับเครือข่ายที่กำหนดซึ่งมี สิ่งอำนวยความสะดวกด้านบริการ M แห่ง สำหรับn ≤ Nและ m ≤ M ใดๆ ให้กำหนด g( n,m ) เป็นค่าคงที่การทำให้เป็นมาตรฐานสำหรับเครือข่ายที่มีลูกค้าn ราย สิ่งอำนวยความสะดวกด้านบริการ m แห่ง (1,2, … m ) และค่าของ   X ₁ , X ₂ , … X _m  ที่ตรงกับ สมาชิก m ตัวแรก ของลำดับดั้งเดิมX ₁ , X ₂ , … X _M

จากนิยามนี้ ผลรวมของพจน์ในกลุ่มที่สองสามารถเขียนได้เป็น g( N , M -1)

นอกจากนี้ยังสามารถสรุปได้ทันทีว่า “ X _M คูณ G( N -1)” ซึ่งเป็นผลรวมของพจน์ในกลุ่มแรก สามารถเขียนใหม่ได้เป็น “ X _M คูณ g( N -1, M )”  

นอกจากนี้ ค่าคงที่การทำให้เป็นมาตรฐาน G( N ) ในทฤษฎีบท Gordon-Newell สามารถเขียนใหม่ได้เป็น g( N , M )

เนื่องจาก G( N ) เท่ากับผลรวมของพจน์ในกลุ่มแรกและกลุ่มที่สอง

G( N ) = g( N , M ) = X _M g( N -1, M ) + g( N , M -1)

ความ สัมพันธ์   เวียนเกิดเดียวกันนี้ปรากฏให้เห็นอย่างชัดเจนสำหรับค่าn ใดๆ ที่ อยู่ระหว่าง 1 ถึงNและสำหรับค่าm ใดๆ ที่ อยู่ระหว่าง 1 ถึงM

สิ่งนี้หมายความว่า g( n,m ) = X _m g( n -1, m ) + g( n,m -1) อัลกอริทึมของ Buzen เป็นเพียงการประยุกต์ใช้ความสัมพันธ์เวียนเกิดพื้นฐานนี้ซ้ำๆ พร้อมกับเงื่อนไขขอบเขตต่อไปนี้

g(0, m ) = 1 สำหรับm = 1, 2, … M

g( n ,1) = ( X _i ) ⁿสำหรับn = 0, 1, … N

ทฤษฎีบทกอร์ดอน-นิวเวลล์ช่วยให้นักวิเคราะห์สามารถกำหนดความน่าจะเป็นคงที่ที่เกี่ยวข้องกับแต่ละสถานะของเครือข่ายคิวปิดได้ จากนั้นต้องนำความน่าจะเป็นแต่ละค่าเหล่านี้มารวมกันเพื่อประเมินความน่าจะเป็นที่สำคัญอื่นๆ ตัวอย่างเช่น P( n _i ≥ k ) ซึ่งเป็นความน่าจะเป็นที่จำนวนลูกค้าทั้งหมดที่ศูนย์บริการiมากกว่าหรือเท่ากับkจะต้องนำมาบวกกันสำหรับค่าn _i ≥ k ทั้งหมด และสำหรับแต่ละค่าn _i ดังกล่าว จะต้องนำมาบวก กันสำหรับวิธีการกระจายลูกค้าที่เหลือN – n _iไปยังศูนย์บริการอีกM -1 แห่งในเครือข่าย ทั้งหมดด้วย

ความน่าจะเป็นส่วนย่อยเหล่านี้จำนวนมากสามารถคำนวณได้โดยใช้ความพยายามเพิ่มเติมเพียงเล็กน้อย เห็นได้ชัดเจนในกรณีของ P( n _i ≥ k) เห็นได้ชัดว่าX _iต้องยกกำลังkหรือสูงกว่าในทุกสถานะที่จำนวนลูกค้าที่ศูนย์บริการiมากกว่าหรือเท่ากับkดังนั้นX _i ^kสามารถแยกตัวประกอบออกจากความน่าจะเป็นเหล่านี้ได้ เหลือเพียงชุดความน่าจะเป็นที่ปรับเปลี่ยนแล้วซึ่งผลรวมเท่ากับ G( N -k)/G( N ) ข้อสังเกตนี้ให้ผลลัพธ์ที่เรียบง่ายและมีประสิทธิภาพสูงดังต่อไปนี้:

P( n _i ≥ k ) = ( X _i ) ^k G( N - k )/G( N )

จากนั้นจึงสามารถใช้ความสัมพันธ์นี้ในการคำนวณการแจกแจงส่วนเพิ่มและจำนวนลูกค้า ที่คาดหวัง ณ สถานที่ให้บริการแต่ละแห่งได้

${\displaystyle \mathbb {P} (n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(Nk)-X_{i}G(Nk-1)]\quad {\text{ สำหรับ }}k=0,1,\ldots ,N-1,}$

${\displaystyle \mathbb {P} (n_{i}=N)={\frac {X_{i}^{N}}{G(N)}}.}$

จำนวนลูกค้าที่คาดว่าจะใช้บริการที่สถานบริการiกำหนดโดย

${\displaystyle \mathbb {E} (n_{i})=\sum _{k=1}^{N}X_{i}^{k}{\frac {G(Nk)}{G(N)}}.}$

ลักษณะเฉพาะของปริมาณที่น่าสนใจในแง่ของ G( n ) เหล่านี้เกิดจาก Buzen เช่นกัน^{[ 2 ]}

จะถือว่าค่าX _mได้ถูกคำนวณโดยการแก้สมการที่เกี่ยวข้องแล้ว และพร้อมใช้งานเป็นข้อมูลป้อนเข้าสำหรับรูทีนของเรา แม้ว่า g( n,m ) โดยหลักการแล้วจะเป็นเมทริกซ์สองมิติ แต่สามารถคำนวณได้ทีละคอลัมน์ โดยเริ่มจากด้านบนของคอลัมน์ซ้ายสุดและไล่ลงมาจนถึงด้านล่างของแต่ละคอลัมน์ก่อนที่จะไปยังคอลัมน์ถัดไปทางด้านขวา รูทีนนี้ใช้เวกเตอร์คอลัมน์เดียวCเพื่อแสดงคอลัมน์ปัจจุบันของ g

ลูปแรกในอัลกอริทึมด้านล่างจะกำหนดค่าเริ่มต้นให้กับเวกเตอร์คอลัมน์ C[n] โดยที่ C[0] = 1 และ C(n) = 0 สำหรับ n≥1 โปรดสังเกตว่า C[0] ยังคงเท่ากับ 1 ตลอดการวนซ้ำครั้งต่อๆ ไป  

ในลูปที่สอง ค่า C(n) ที่ต่อเนื่องกันแต่ละค่าสำหรับ n≥1 จะถูกกำหนดให้เท่ากับค่า g( n,m) ที่สอดคล้องกัน เมื่ออัลกอริทึมดำเนินการลงไปตามคอลัมน์ m ซึ่งทำได้โดยการกำหนดค่า C(n) ที่ต่อเนื่องกันแต่ละค่าให้เท่ากับ:

g( n,m-1 ) บวกX _m คูณ g( n-1,m )  

โปรดทราบว่า g( n,m-1 ) คือค่าก่อนหน้าของ C(n) และ g( n-1,m ) คือค่าปัจจุบันของ C(n-1)

C [ 0 ] := 1 สำหรับn := 1 ก้าวที่1 จนกระทั่งN ทำC [ n ] := 0 ;สำหรับm := 1 ก้าวที่1 จนถึงM ทำซ้ำสำหรับn := 1 ก้าวที่1 จนถึงN ทำซ้ำC [ n ] := C [ n ] + X [ m ] * C [ n - 1 ] ;

เมื่อเสร็จสิ้น ค่าสุดท้ายของ C[n] จะสอดคล้องกับคอลัมน์Mในเมทริกซ์ g( n,m ) ดังนั้นจึงแสดงถึงค่าที่ต้องการ G (0), G (1), ... , G (N ⁾ [ ^{2 ]}