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

कतारबद्ध सिद्धांत में, संभाव्यता के गणितीय सिद्धांत के भीतर एक अनुशासन, औसत मूल्य विश्लेषण (एमवीए) अपेक्षित मूल्य कतार लंबाई की गणना के लिए एक पुनरावर्ती तकनीक है, क्यूइंग नोड्स पर प्रतीक्षा समय और कतारों की एक बंद वियोज्य प्रणाली के लिए संतुलन में थ्रूपुट। पहली अनुमानित तकनीकों को श्वित्ज़र द्वारा स्वतंत्र रूप से प्रकाशित किया गया थाऔर बार्ड, बाद में 1980 में प्रकाशित Lavenberg और Reiser द्वारा एक सटीक संस्करण द्वारा पीछा किया गया। यह आगमन प्रमेय पर आधारित है, जिसमें कहा गया है कि जब एम-ग्राहक बंद प्रणाली में एक ग्राहक एक सेवा सुविधा पर आता है तो वह शेष प्रणाली को एम − 1 ग्राहकों के साथ एक प्रणाली के लिए संतुलन स्थिति में देखता है।

समस्या सेटअप

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

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

अब L लिखिए_i(एन) कतार में ग्राहक की औसत संख्या के लिए जब सिस्टम में कुल एन ग्राहक होते हैं (इसमें कतार में वर्तमान में सेवा की जा रही नौकरी शामिल है) और डब्ल्यू_j(एन) एक ग्राहक द्वारा कतार में बिताए गए औसत समय के लिए जब सिस्टम में कुल एन ग्राहक होते हैं। m ग्राहकों वाले सिस्टम के थ्रुपुट को λ से निरूपित करें_m.

एल्गोरिथम

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

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

एम = 1,..., एम के लिए दोहराएँ:

1. के = 1, ..., के लिए आगमन प्रमेय का उपयोग करके प्रत्येक नोड पर प्रतीक्षा समय की गणना करें

$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)$

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

स्यूडोकोड

set L_k(m) = M/K

repeat until convergence:

$\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}}}$

मल्टीक्लास नेटवर्क

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

प्रतीक्षा समय डब्ल्यू_k,r कतार k पर कक्षा-आर नौकरियों द्वारा अनुभव अभी भी आगमन प्रमेय के सामान्यीकरण का उपयोग करके नोड 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})$ आर वर्गों के लिए ग्राहक आबादी का एक वेक्टर है और $1_{r}$ के r-वें तत्व से एक घटाता है $\mathbb {m}$, ये मानते हुए $m_{r}\geq 1$.

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

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

एक्सटेंशन

माध्य मान विश्लेषण एल्गोरिथम को PEPA मॉडल के एक वर्ग पर लागू किया गया है जो कतारबद्ध नेटवर्क और एक प्रमुख वितरण केंद्र के प्रदर्शन का वर्णन करता है।

सॉफ्टवेयर

• 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.