औसत मूल्य विश्लेषण

कतार सिद्धांत में, प्रायिकता के गणितीय सिद्धांत के अंदर एक विषय, माध्य मान विश्लेषण (मीन वैल्यू एनालिसिस, एमवीए) पुनरावृत्तिमूलक तकनीक है जो संवृत वियोज्य प्रणाली के लिए संतुष्टि में आपेक्षिक कतार लंबाई, कतार पर प्रतीक्षा समय और प्रवाह की गणना करने के लिए उपयोगी होती है। सर्वप्रथम प्रायिकता तकनीकों को स्विटजर और बार्ड ने स्वतंत्र रूप से प्रकाशित किया गया था, बाद में 1980 में लेवेनबर्ग और रीज़र द्वारा एक यथार्थ संस्करण प्रकाशित किया गया।

यह एराइवल सिद्धांत पर आधारित है, इस सिद्धांत के अनुसार, M-ग्राहक संवृत प्रणाली में किसी सेवा सुविधा पर आगमन करने पर वह देखता है कि M - 1 ग्राहकों के साथ संगठित प्रणाली की साम्य स्थिति में शेष अंश है।

समस्या व्यवस्थापन

किसी संवृत प्रणाली के कतारबद्ध तंत्र पर विचार करें जिसमें K M/M/1 कतारें होती हैं और सिस्टम में M ग्राहक संचार करते हैं। मान लीजिए कि ग्राहक एक-दूसरे से अस्पष्ट होते हैं, इसलिए नेटवर्क के पास ग्राहकों का एक ही वर्ग होता है। प्रत्येक नोड पर औसत कतार की लंबाई और प्रतीक्षा समय गणना करने के लिए हम 0 ग्राहकों के नेटवर्क के साथ पुनरावृत्त एल्गोरिदम का उपयोग करते हैं।

नोड i पर सेवा दर के लिए μ_i को लिखें और ग्राहक रूटिंग मैट्रिक्स के लिए P को लिखें, जहां तत्व p_ij उन प्रायिकता को दर्शाता है जो ग्राहक को नोड i पर सेवा समाप्त करने के बाद नोड j पर सेवा के लिए जाने की प्रायिकता होती है। एल्गोरिदम का उपयोग करने के लिए हम पहले विज़िट अनुपात पंक्ति सदिश v की गणना करते हैं, किसी सदिश जिसके लिए v = v P होता है।

अब प्रणाली में कुल n ग्राहक होने पर कतार i में ग्राहकों की औसत संख्या के लिए L_i(n) लिखें (इसमें कतार i में सेवा की नौकरी भी सम्मिलित है) और प्रणाली में कुल n ग्राहक होने पर कतार i में ग्राहक द्वारा व्यतीत समय के लिए W_j(n) लिखें। m ग्राहकों के साथ प्रणली की प्रवाह क्षमता को λ_m से दर्शाएँ।

कलन विधि

कलन विधि अकार्य तंत्र (शून्य ग्राहकों) से आरम्भ होती है, फिर प्रत्येक पुनरावृत्ति में ग्राहकों की संख्या को 1 बढ़ाता है जब तक प्रणाली में आवश्यक संख्या (M) के ग्राहक न हो जाएं।

प्रारंभ करने के लिए, के लिए L_k(0) = 0 व्यवस्थित करें, k = 1,...,K। (यह निर्धारित करता है कि शून्य ग्राहकों वाली प्रणाली में सभी नोडों पर औसत कतार लंबाई को शून्य पर सेट किया जाता है।)

m = 1,...,M के लिए पुनरुक्ति:

1. k = 1, ... K के लिए, एराइवल प्रमेय का उपयोग करके प्रत्येक नोड पर प्रतीक्षा समय की गणना करता है

$W_{k}(m)={\frac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.$

2. अतः तत्पश्चात लिटिल के नियम का उपयोग करके प्रणाली प्रवाह क्षमता की गणना करें

$\lambda _{m}={\frac {m}{\sum _{k=1}^{K}W_{k}(m)v_{k}}}.$

3. अंतिम रूप में, प्रत्येक कतार के लिए लिटिल के नियम का उपयोग करके कतार की औसत लंबाई गणना करें, k = 1, ..., K के लिए।

$L_{k}(m)=v_{k}\lambda _{m}W_{k}(m).$

पुनरावृति समाप्त करें।

बार्ड-श्विट्जर विधि

बार्ड-श्वित्जर सन्निकटन का अनुमान है कि नोड k पर नौकरियों की औसत संख्या होगी

$L_{k}(m-1)\approx {\frac {m-1}{m}}L_{k}(m)$

जो एक रेखीय प्रक्षेप है। उपरोक्त सूत्रों से, यह सन्निकटन निश्चित-बिंदु संबंध उत्पन्न करता है जिसे संख्यानुसार हल किया जा सकता है। यह पुनरावृत्त दृष्टिकोण प्रायः अनुमानित एमवीए (एएमवीए) के नाम से जाना जाता है और यह सामान्यतः एमवीए के पुनरावर्ती दृष्टिकोण से तीव्र होता है।

स्यूडोकोड

set L_k(m) = M/K

कन्वर्जेन्स तक पुनरावृत्ति करें:

$\lambda _{m}={\frac {m}{\sum _{k=1}^{K}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}v_{k}}}$

$L_{k}(m)=v_{k}\lambda _{m}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}$

बहुवर्गीय तंत्र

बहुवर्गीय तंत्र की स्थिति में, ग्राहकों के R श्रेणियों के साथ, प्रत्येक कतार k में प्रति नौकरी श्रेणी r=1,...,R के लिए विभिन्न सेवा दर μ_k,r हो सकती हैं, हालांकि बहुवर्गी वाली स्थिति में पहले आए पहले सेवाधारित स्टेशनों की स्थिति में बीसीएमपी सिद्धांत की मान्यताओं के कारण कुछ प्रतिबंध होते हैं।

कतार k पर वर्ग-r नौकरियों द्वारा अनुभवित प्रतीक्षा समय W_k,r को प्रतिकूलता करके नोड k पर कुल औसत कतार-लंबाई के साथ संबंधित किया जा सकता है, एराइवल सिद्धांत के एक सारांश का उपयोग करके।

$W_{k,r}(\mathbb {m} )={\frac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.$

जहाँ $\mathbb {m} =(m_{1},\ldots ,m_{R})$ ग्राहक जनसंख्या का एक सदिश है जो R वर्गों के लिए है, और $1_{r}$ $\mathbb {m}$ के r-वें तत्व से एक घटाता है, $m_{r}\geq 1$ की मान्यताओं के अनुमान के साथ।

एकल ग्राहक वर्ग वाले तंत्र के लिए एमवीए कलन विधि बहुत तीव्र है और ग्राहकों की संख्या और कतारों की संख्या के साथ रैखिक रूप से समय लगता है। हालाँकि, बहुवर्गी मॉडल में गुणन और परिवर्धन की संख्या और एमवीए के लिए भंडारण आवश्यकताओं में ग्राहक वर्गों की संख्या के साथ तीव्रता से वृद्धि होती है। वास्तव में, कलन विधि 3-4 ग्राहक वर्गों के लिए अच्छी तरह से कार्य करता है, हालांकि यह सामान्यतः मॉडल के कार्यान्वयन और संरचना पर निर्भर करता है। उदाहरण के लिए, ट्री-एमवीए विधि बड़े मॉडल के लिए स्केल कर सकती है यदि रूटिंग मैट्रिक्स विरल है।

औसत निष्पादन मेट्रिक्स के लिए यथार्थ मान बड़े मॉडलों में मोमेंट्स की विधि का उपयोग करके प्राप्त किया जा सकता है, जिसके लिए लॉग-द्विघात समय की आवश्यकता होती है। मोमेंट्स की विधि ग्राहकों के 10 वर्गों तक या कभी-कभी बड़े के साथ अभ्यास मॉडल में हल कर सकती है, जो यथार्थ एमवीए के माध्यम से सामान्यतः पहुंच योग्य नहीं होती हैं। हालांकि यह तकनीक एराइवल प्रमेय का उपयोग नहीं करती है और कतारबद्ध तंत्र के लिए किसी स्थिति की प्रायिकताओं के सामान्यीकरण स्थिरांक को सम्मिलित करते हुए रैखिक समीकरणों की प्रणाली को हल करने पर निर्भर करती है।

अनुमानित एमवीए (एएमवीए) एल्गोरिदम, जैसे कि बार्ड-श्विट्जर विधि, इसके बजाय वैकल्पिक समाधान तकनीक प्रदान करते हैं जो बहुवर्गी तंत्र पर भी कम जटिलता प्रदान करती है और सामान्यतः अत्यधिक यथार्थ परिणाम प्रदान करती है।

संतति

माध्य मान विश्लेषण कलन विधि कतारबद्ध तंत्र और प्रमुख वितरण केंद्र के प्रदर्शन का वर्णन करने वाले पीईपीए मॉडल के किसी वर्ग पर लागू किया गया है।

सॉफ्टवेयर

• JMVA, जावा (प्रोग्रामिंग भाषा) में लिखा गया एक टूल जो एमवीए को लागू करता है।
• [1], जीएनयू ऑक्टेव के लिए एक पुस्तकालय जिसमें एमवीए सम्मिलित है।
• Line, एक MATLAB टूलबॉक्स जिसमें यथार्थ और अनुमानित एमवीए एल्गोरिदम सम्मिलित हैं।

यह भी देखें

• कतारबद्ध सिद्धांत

बाहरी संबंध

• J. Virtamo: Queuing networks. Handout from Helsinki Tech gives good overview of Jackson's Theorem and MVA.
• Simon Lam: A simple derivation of the MVA algorithm. Shows relationship between Buzen's algorithm and MVA.