제품형태솔루션

Product-form solution

확률론에서, 제품 형태 해법은 다른 요소들에 걸친 측정의 산물로써 구성 요소들의 수집을 위한 측정 기준을 작성할 수 있는 별개의 하위 구성 요소들을 가진 시스템의 일부 측정 기준을 결정하기 위한 해법의 특히 효율적인 형태이다.대문자 Pi 표기법을 사용하여 제품 형태 해는 대수적 형식을 갖는다.

여기서 B는 어떤 상수입니다.이 형식의 해법은 큰 값 n에 대해 평가하는 데 계산적으로 저렴하기 때문에 흥미롭다.큐잉 네트워크의 이러한 솔루션은 멀티프로그래밍된 시간 공유 컴퓨터 시스템의 모델에서 성능 메트릭을 찾는 데 중요합니다.

평형 분포

마르코프 사슬의 평형 분포에 대한 첫 번째 제품 형태 솔루션이 발견되었다.일반적으로 두 개 이상의 독립적인 하위 구성요소로 구성된 모델은 독립성의 정의에 따라 제품 형태의 솔루션을 제시합니다.처음에 이 용어는 서브컴포넌트가 개별 큐가 되는 큐잉네트워크에서 사용되었습니다.예를 들어, 잭슨의 정리는 개별 [1]큐의 평형 분포의 산물로서 개방 큐잉 네트워크의 공동 평형 분포를 제공한다.BCMP 네트워크를 중심으로 수많은 확장이 이루어진 후 로컬 밸런스가 제품 형태의 [2][3]솔루션의 요건이라고 생각되었습니다.

Gelenbe의 G-network 모델은 이것이 사실이 아님을 보여주는 첫 번째 모델이다.그는 스파이킹 행동과 같은 점 과정을 가진 생물학적 뉴런을 모델링할 필요성에 자극받아 G-Networks의 선구자를 소개했는데, 이를 무작위 뉴럴 [4]네트워크라고 부른다.그는 다른 고객을 파괴하거나 제거할 수 있는 "부정 고객"을 도입함으로써 제품 형태 네트워크 [5]제품군을 일반화했습니다.그 후, 이것은 Gelenbe의 「트리거」에 의해서, 몇개의 스텝으로 한층 더 확대되었습니다.이 「트리거」는, 다른 고객을 다른 큐로부터 [6]다른 큐로 이동시키는 힘을 가지는 고객입니다.또한 제품 형태를 이끈 또 다른 새로운 형태의 고객은 겔렌베의 "배치 제거"[7]였습니다.이는 Erol Gelenbe 및 Jean-Michel Fourneau에 의해 더욱 확장되었습니다.이러한 유형의 장애 복구는 큐가 빈 상태에 이르렀을 때(예를 들어 장애를 나타냄), 큐 길이를 다시 점프하거나 정상 상태의 분포로 "리셋"하여 복구 작업을 나타낼 수 있습니다.G-Networks의 모든 이전 유형의 고객은 여러 클래스를 포함하여 동일한 네트워크 내에 존재할 수 있으며, 모두 함께 제품 폼 솔루션을 제공하므로 [8]이전까지 고려되었던 되돌릴 수 없는 네트워크를 훨씬 뛰어넘을 수 있습니다.

제품 형태의 솔루션은 때때로 "스테이션을 평형에서 독립적"[9]이라고 표현됩니다.제품 양식 솔루션은 벌크 [10]큐의 네트워크에도 존재합니다.

그렇듯 해리슨과 RJ윌리엄스는"사실상 모든 성공적으로 클래식 사려고 줄 서 있는 네트워크 이론에 분석이 된 모델의 모델들이 소위product-form 고정 유통을 보내고 있어"[9]더 최근에,product-form 솔루션 마르코프 과정 algebras과 확률(예를 들어 무선 조정 항공표적 PEPA[11][12]에)배양 수록되어 있습니다.nets.[13][14]마틴 파인버그의 결손 제로 정리는 화학 반응 네트워크가 생성물 형태의 [15]정상 분포를 나타낼 수 있는 충분한 조건을 제공한다.

Gelenbe의 연구는 또한 제품 형태 G-Networks를 사용하여 스파이킹 랜덤 신경망을 모델링할 수 있으며, 나아가 그러한 네트워크는 유계되고 연속적인 실질 가치 [16][17]함수에 근사적으로 사용될 수 있다는 것을 보여준다.

체류 시간 분포

product 폼이라는 용어는 사이클 큐잉시스템에서의 체류시간 분포를 나타내기 위해서도 사용되고 있습니다.여기서 M노드에서의 작업에 의해 소비된 시간은 [18]각 노드에서 소비된 시간의 곱으로 지정됩니다.1957년에 라이히는 [19]2개의 M/M/1 큐의 결과를 보여주었고, 나중에 이것을 n개의 M/M/1 큐로 동시에[20] 확장하여 잭슨 네트워크의 [21]추월 프리 패스에 적용하는 것으로 나타났습니다.Walrand와 Varaiya는 추월하지 않는 것(고객이 네트워크를 통해 다른 경로를 통해 다른 고객을 추월할 수 없는 것)이 결과를 [21]유지하기 위한 필수 조건일 수 있다고 제안합니다.Mitrani는 추월로 몇 가지 간단한 네트워크에 정확한 솔루션을 제공하고 있으며, 이러한 네트워크 중 어느 것도 제품 형태의 체류 시간 [22]분포를 나타내지 않음을 보여줍니다.

폐쇄형 네트워크의 경우 Chow는 2개의 서비스 [23]노드를 유지하는 결과를 보여주었습니다.이 노드는 나중에 큐의 사이클로[24] 일반화되어 Gordon-Newell [25][26]네트워크에서 경로를 추월하지 않는 것으로 나타났습니다.

내선번호

  • 대략적인 제품 형태 솔루션은 독립적 한계 분포를 가정하여 계산되며,[27][28] 이는 일부 조건에서 정상 분포에 대한 근사치를 제공할 수 있다.
  • 반제품 형태의 솔루션은 용어가 글로벌 상태 공간에 대한 함수 의존성이 제한적인 제품으로서 분포가 작성될 수 있는 솔루션이며,[29] 이는 대략적으로 추정할 수 있습니다.
  • 준제품 형태 솔루션은 다음 중 하나입니다.
    • 한계 밀도의 산물이 아닌 한계 밀도의 산물인 해법은 제품 유형의[30] 방식으로 분포를 기술한다.
    • 과도 모멘트를 [31]근사화할 수 있는 과도 확률 분포에 대한 근사 형식.

레퍼런스

  1. ^ Jackson, James R. (1963). "Jobshop-like queueing systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.10.1.131.
  2. ^ Boucherie, Richard J.; van Dijk, N. M. (1994). "Local balance in queueing networks with positive and negative customers". Annals of Operations Research. 48 (5): 463–492. doi:10.1007/BF02033315. hdl:1871/12327. S2CID 15599820.
  3. ^ Chandy, K. Mani; Howard, J. H., Jr; Towsley, D. F. (1977). "Product form and local balance in queueing networks". Journal of the ACM. 24 (2): 250–263. doi:10.1145/322003.322009. S2CID 6218474.
  4. ^ Gelenbe, Erol (1989). "Random Neural Networks with Negative and Positive Signals and Product Form Solution". Neural Computation. 1 (4): 502–510. doi:10.1162/neco.1989.1.4.502. S2CID 207737442.
  5. ^ Gelenbe, Erol (1991). "Product-form queueing networks with negative and positive customers". Journal of Applied Probability. 28 (3): 656–663. doi:10.2307/3214499. JSTOR 3214499.
  6. ^ Gelenbe, Erol (1993). "G-networks with triggered customer movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781.
  7. ^ Gelenbe, Erol (1993). "G-Networks with triggered customer movement". Probability in the Engineering and Informational Sciences. 7 (3): 335–342. doi:10.1017/S0269964800002953.
  8. ^ Gelenbe, Erol; Fourneau, Jean-Michel (2002). "G-Networks with resets". Performance Evaluation. 49 (1): 179–191. doi:10.1016/S0166-5316(02)00127-X.
  9. ^ a b Harrison, J. M.; Williams, R. J. (1992). "Brownian models of feedforward queueing networks: quasireversibility and product-form solutions". Annals of Applied Probability. 2 (2): 263–293. CiteSeerX 10.1.1.56.1572. doi:10.1214/aoap/1177005704.
  10. ^ Henderson, W.; Taylor, P. G. (1990). "Product form in networks of queues with batch arrivals and batch services". Queueing Systems. 6: 71–87. doi:10.1007/BF02411466. S2CID 30949152.
  11. ^ Hillston, J.; Thomas, N. (1999). "Product form solution for a class of PEPA models" (PDF). Performance Evaluation. 35 (3–4): 171–192. doi:10.1016/S0166-5316(99)00005-X. hdl:20.500.11820/13c57018-5854-4f34-a4c9-833262a71b7c.
  12. ^ Harrison, P. G. (2003). "Turning back time in Markovian process algebra". Theoretical Computer Science. 290 (3): 1947–2013. doi:10.1016/S0304-3975(02)00375-4. Archived from the original on 2006-10-15. Retrieved 2015-08-29.
  13. ^ Marin, A.; Balsamo, S.; Harrison, P. G. (2012). "Analysis of stochastic Petri nets with signals". Performance Evaluation. 69 (11): 551–572. doi:10.1016/j.peva.2012.06.003. hdl:10044/1/14180.
  14. ^ Mairesse, J.; Nguyen, H. T. (2009). "Deficiency Zero Petri Nets and Product Form". Applications and Theory of Petri Nets. Lecture Notes in Computer Science. Vol. 5606. p. 103. CiteSeerX 10.1.1.745.1585. doi:10.1007/978-3-642-02424-5_8. ISBN 978-3-642-02423-8.
  15. ^ Anderson, D. F.; Craciun, G.; Kurtz, T. G. (2010). "Product-Form Stationary Distributions for Deficiency Zero Chemical Reaction Networks". Bulletin of Mathematical Biology. 72 (8): 1947–1970. arXiv:0803.3042. doi:10.1007/s11538-010-9517-4. PMID 20306147. S2CID 2204856.
  16. ^ Gelenbe, Erol (1993). "Learning in the recurrent random neural network". Neural Computation. 5 (1): 154–164. doi:10.1162/neco.1993.5.1.154. S2CID 38667978.
  17. ^ Gelenbe, Erol; Mao, Zhi-Hong; Li, Yan-Da (1991). "Function approximation with the random neural network". IEEE Transactions on Neural Networks. 10 (1): 3–9. CiteSeerX 10.1.1.46.7710. doi:10.1109/72.737488. PMID 18252498.
  18. ^ Boxma, O. J.; Kelly, F. P.; Konheim, A. G. (January 1984). "The Product Form for Sojourn Time Distributions in Cyclic Exponential Queues". Journal of the ACM. 31 (1): 128–133. doi:10.1145/2422.322419. S2CID 6770615.
  19. ^ Reich, Edgar (1957). "Waiting Times when Queues are in Tandem". The Annals of Mathematical Statistics. 28 (3): 768–773. doi:10.1214/aoms/1177706889.
  20. ^ Reich, E. (1963). "Note on Queues in Tandem". The Annals of Mathematical Statistics. 34: 338–341. doi:10.1214/aoms/1177704275.
  21. ^ a b Walrand, J.; Varaiya, P. (1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. JSTOR 1426753.
  22. ^ Mitrani, I. (1985). "Response Time Problems in Communication Networks". Journal of the Royal Statistical Society. Series B (Methodological). 47 (3): 396–406. doi:10.1111/j.2517-6161.1985.tb01368.x. JSTOR 2345774.
  23. ^ Chow, We-Min (April 1980). "The Cycle Time Distribution of Exponential Cyclic Queues". Journal of the ACM. 27 (2): 281–286. doi:10.1145/322186.322193. S2CID 14084475.
  24. ^ Schassberger, R.; Daduna, H. (1983). "The Time for a Round Trip in a Cycle of Exponential Queues". Journal of the ACM. 30: 146–150. doi:10.1145/322358.322369. S2CID 33401212.
  25. ^ Daduna, H. (1982). "Passage Times for Overtake-Free Paths in Gordon-Newell Networks". Advances in Applied Probability. 14 (3): 672–686. doi:10.2307/1426680. JSTOR 1426680.
  26. ^ Kelly, F. P.; Pollett, P. K. (1983). "Sojourn Times in Closed Queueing Networks". Advances in Applied Probability. 15 (3): 638–656. doi:10.2307/1426623. JSTOR 1426623.
  27. ^ Baynat, B.; Dallery, Y. (1993). "A unified view of product-form approximation techniques for general closed queueing networks". Performance Evaluation. 18 (3): 205–224. doi:10.1016/0166-5316(93)90017-O.
  28. ^ Dallery, Y.; Cao, X. R. (1992). "Operational analysis of stochastic closed queueing networks". Performance Evaluation. 14: 43–61. doi:10.1016/0166-5316(92)90019-D.
  29. ^ Thomas, Nigel; Harrison, Peter G. (2010). "State-Dependent Rates and Semi-Product-Form via the Reversed Process". Computer Performance Engineering. Lecture Notes in Computer Science. Vol. 6342. p. 207. doi:10.1007/978-3-642-15784-4_14. ISBN 978-3-642-15783-7.
  30. ^ Debicki, K.; Dieker, A. B.; Rolski, T. (2007). "Quasi-Product Forms for Levy-Driven Fluid Networks". Mathematics of Operations Research. 32 (3): 629–647. arXiv:math/0512119. doi:10.1287/moor.1070.0259. S2CID 16150704.
  31. ^ Angius, A.; Horváth, A. S.; Wolf, V. (2013). "Approximate Transient Analysis of Queuing Networks by Quasi Product Forms". Analytical and Stochastic Modeling Techniques and Applications. Lecture Notes in Computer Science. Vol. 7984. p. 22. doi:10.1007/978-3-642-39408-9_3. ISBN 978-3-642-39407-2.