부젠 알고리즘

Buzen's algorithm

큐잉 이론에서, 확률의 수학적 이론 내의 한 분야인 부젠 알고리즘은 고든-뉴엘 정리에서의 정규화 상수 G(N)를 계산하는 알고리즘이다.이 방법은 1973년 [1]Jeffrey P. Buzen에 의해 처음 제안되었다.폐쇄 큐잉 네트워크의 [2]정상 확률 분포를 계산하려면 G(N) 계산이 필요합니다.

정규화 상수의 순진한 계산을 수행하려면 모든 상태를 열거해야 합니다.N개의 작업과 M 상태가 있는 시스템의 경우 (+ - M - ) {개의 조합이 있습니다Buzen의 알고리즘은 "총 NM 곱셈과 NM 덧셈을 사용하여 G(1), G(2), ..., G(N)를 계산한다."이는 대폭적인 개선으로 훨씬 더 [1]큰 네트워크에서 계산을 수행할 수 있습니다.

문제 셋업

M개의 서비스 시설과 N개의 순환 고객을 가진 폐쇄형 큐잉 네트워크를 고려합니다.고객의 수가 ith 시설에서 시간 t에 있는 것처럼 ∑ 나는 갈1M와 나는 N{\displaystyle\scriptstyle \sum_{i=1}^{M}n_{나는}=N원을 제시한}. 우리는 ith 시설의 고객을 위해 이 서비스를 시간 변수 μi을 가진 기하 급수적으로 분산된 확률 변수에 의해 완성 후는 땅이 주어진 것이라고 생각합니다 ni(t)을 써라.rvice at the ith facility에서 고객은ij 확률 [2]p로 j번째 facility로 진행됩니다.

고든-뉴엘 정리로부터 이 모델의 평형 분포는 다음과 같다.

여기서 X는i 풀어서 찾을 수 있다.

G(N)는 위의 확률을 합한 1로 선택한 [1]정규화 상수입니다.

부젠의 알고리즘은 G(N)[1]를 계산하는 효율적인 방법입니다.

알고리즘 설명

N개의 순환 고객 및 M개의 서비스 스테이션이 있는 폐쇄 큐잉 네트워크의 정규화 정수를 g(N,M)로 적습니다.알고리즘은 X에i 대해 위의 관계를 풀고 시작 조건을[1] 설정하는 것으로 시작합니다.

반복[1] 관계

값의 격자를 계산하는 데 사용됩니다.요구된 값 G(N) = g([1]N,M).

한계 분포, 예상 고객 수

Buzen의 알고리즘을 사용하여 계산된 계수 g(n,m)는 또한 각 노드의 한계 분포와 예상 고객 수를 계산하는 데 사용할 수 있다.

시설 i의 예상 고객 수

실행

X는m 관련 방정식을 풀어서 계산되었으며 우리의 루틴에 입력으로 사용할 수 있다고 가정할 것이다.g는 원칙적으로 2차원 매트릭스이지만 맨 왼쪽 열부터 열별로 계산할 수 있다.이 루틴에서는 g의 현재 열을 나타내기 위해 단일 열 벡터 C를 사용합니다.

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는 원하는 값 G(0), G(1)~G(N)를 포함한다.[1]

레퍼런스

  1. ^ a b c d e f g h Buzen, J. P. (1973). "Computational algorithms for closed queueing networks with exponential servers" (PDF). Communications of the ACM. 16 (9): 527–531. doi:10.1145/362342.362345. S2CID 10702.
  2. ^ a b Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557.