जैक्सन नेटवर्क: Difference between revisions
From Vigyanwiki
No edit summary |
(→प्रमेय) |
||
| Line 5: | Line 5: | ||
अग्रानुक्रम पंक्तियां (पंक्तियां की परिमित श्रृंखला जहां प्रत्येक ग्राहक को प्रत्येक पंक्ति में क्रम से जाना चाहिए) और चक्रीय नेटवर्क (पंक्तियां का लूप जहां प्रत्येक ग्राहक को क्रम में प्रत्येक पंक्ति में जाना चाहिए) के लिए आर.आर.पी. जैक्सन द्वारा पूर्व उत्पाद-रूप समाधान पाया गया था।<ref>{{cite journal|title=Book review: Queueing networks and product forms: a systems approach|first=R. R. P.|last=Jackson|doi=10.1093/imaman/6.4.382|year=1995|volume=6|pages=382–384|journal=IMA Journal of Management Mathematics|issue=4}}</ref> | अग्रानुक्रम पंक्तियां (पंक्तियां की परिमित श्रृंखला जहां प्रत्येक ग्राहक को प्रत्येक पंक्ति में क्रम से जाना चाहिए) और चक्रीय नेटवर्क (पंक्तियां का लूप जहां प्रत्येक ग्राहक को क्रम में प्रत्येक पंक्ति में जाना चाहिए) के लिए आर.आर.पी. जैक्सन द्वारा पूर्व उत्पाद-रूप समाधान पाया गया था।<ref>{{cite journal|title=Book review: Queueing networks and product forms: a systems approach|first=R. R. P.|last=Jackson|doi=10.1093/imaman/6.4.382|year=1995|volume=6|pages=382–384|journal=IMA Journal of Management Mathematics|issue=4}}</ref> | ||
जैक्सन नेटवर्क में कई नोड्स होते हैं, जहां प्रत्येक नोड पंक्ति का प्रतिनिधित्व करता है जिसमें सेवा दर दोनों नोड-निर्भर हो सकती है (विभिन्न नोड्स में अलग-अलग सेवा दरें होती हैं) और | जैक्सन नेटवर्क में कई नोड्स होते हैं, जहां प्रत्येक नोड पंक्ति का प्रतिनिधित्व करता है जिसमें सेवा दर दोनों नोड-निर्भर हो सकती है (विभिन्न नोड्स में अलग-अलग सेवा दरें होती हैं) और स्थिति-निर्भर (पंक्ति की लंबाई के आधार पर सेवा दरें बदलती हैं)। निश्चित रूटिंग मैट्रिक्स के बाद नौकरियां नोड्स के बीच यात्रा करती हैं। प्रत्येक नोड पर सभी नौकरियां एक ही वर्ग से संबंधित हैं और नौकरियां समान सेवा-समय वितरण और समान रूटिंग तंत्र का पालन करती हैं। फलस्वरूप, नौकरियों की सेवा में प्राथमिकता की कोई धारणा नहीं है: प्रत्येक नोड पर सभी नौकरियां पहले आओ, पहले पाओ के आधार पर दी जाती हैं। | ||
जैक्सन नेटवर्क जहां नौकरियों की सीमित आबादी एक बंद नेटवर्क के आसपास घूमती है, वहां गॉर्डन-नेवेल प्रमेय द्वारा वर्णित उत्पाद-रूप समाधान भी है।<ref>{{Cite journal | last1 = Gordon | first1 = W. J. | last2 = Newell | first2 = G. F. | author-link2 = Gordon F. Newell| doi = 10.1287/opre.15.2.254 | jstor = 168557| title = एक्सपोनेंशियल सर्वर के साथ क्लोज्ड क्यूइंग सिस्टम| journal = [[Operations Research (journal)|Operations Research]]| volume = 15 | issue = 2 | pages = 254 | year = 1967 }}</ref> | जैक्सन नेटवर्क जहां नौकरियों की सीमित आबादी एक बंद नेटवर्क के आसपास घूमती है, वहां गॉर्डन-नेवेल प्रमेय द्वारा वर्णित उत्पाद-रूप समाधान भी है।<ref>{{Cite journal | last1 = Gordon | first1 = W. J. | last2 = Newell | first2 = G. F. | author-link2 = Gordon F. Newell| doi = 10.1287/opre.15.2.254 | jstor = 168557| title = एक्सपोनेंशियल सर्वर के साथ क्लोज्ड क्यूइंग सिस्टम| journal = [[Operations Research (journal)|Operations Research]]| volume = 15 | issue = 2 | pages = 254 | year = 1967 }}</ref> | ||
| Line 19: | Line 19: | ||
== प्रमेय == | == प्रमेय == | ||
एम एम/एम/1 पंक्तियां के खुले जैक्सन नेटवर्क में जहां उपयोग होता है <math>\rho_i</math> प्रत्येक पंक्ति में 1 से कम है, संतुलन | एम एम/एम/1 पंक्तियां के खुले जैक्सन नेटवर्क में जहां उपयोग होता है <math>\rho_i</math> प्रत्येक पंक्ति में 1 से कम है, संतुलन स्थिति संभाव्यता वितरण मौजूद है और स्थिति के लिए <math>\scriptstyle{(k_1,k_2,\ldots,k_m)}</math> व्यक्तिगत पंक्ति संतुलन वितरण के उत्पाद द्वारा दिया जाता है | ||
:<math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i) = \prod_{i=1}^{m} [\rho_i^{k_i} (1-\rho_i)].</math> | :<math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i) = \prod_{i=1}^{m} [\rho_i^{k_i} (1-\rho_i)].</math> | ||
परिणाम <math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i)</math> ''c<sub>i</sub>'' सर्वर के साथ एम/एम/सी मॉडल के लिए भी है <math>i^\text{th}</math> | परिणाम <math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i)</math> ''c<sub>i</sub>'' सर्वर के साथ एम/एम/सी मॉडल स्टेशनों के लिए भी है <math>i^\text{th}</math> स्टेशन, उपयोग की आवश्यकता के साथ <math>\rho_i < c_i</math>. | ||
== परिभाषा == | == परिभाषा == | ||
खुले नेटवर्क में, दर के साथ पॉइसन प्रक्रिया के बाद नौकरियां बाहर से आती हैं <math>\alpha>0</math>। प्रत्येक आगमन को संभावना के साथ स्वतंत्र रूप से नोड j पर रूट किया जाता है <math>p_{0j}\ge0</math> और <math>\sum_{j=1}^J p_{0j}=1</math>. नोड I पर सेवा पूर्ण होने पर, कार्य संभाव्यता के साथ दूसरे नोड j पर जा सकता है <math>p_{ij}</math> या संभाव्यता के साथ नेटवर्क छोड़ दें <math>p_{i0}=1-\sum_{j=1}^J p_{ij}</math>. | |||
इसलिए हमारे पास नोड i के लिए समग्र आगमन दर है, <math>\lambda_i</math>, बाहरी आगमन और आंतरिक संक्रमण दोनों सहित: | इसलिए हमारे पास नोड i, के लिए समग्र आगमन दर है, <math>\lambda_i</math>, बाहरी आगमन और आंतरिक संक्रमण दोनों सहित: | ||
:<math> \lambda_i =\alpha p_{0i} + \sum_{j=1}^J \lambda_j p_{ji}, i=1,\ldots,J. \qquad (1)</math> | :<math> \lambda_i =\alpha p_{0i} + \sum_{j=1}^J \lambda_j p_{ji}, i=1,\ldots,J. \qquad (1)</math> | ||
(चूंकि प्रत्येक नोड पर उपयोग 1 से कम है, और हम संतुलन वितरण | (चूंकि प्रत्येक नोड पर उपयोग 1 से कम है, और हम संतुलन वितरण अर्थात लंबे समय तक चलने वाले औसत व्यवहार को देख रहे हैं, j से i में संक्रमण की दर j पर आगमन दर के अंश से बंधी है और हम सेवा दर की उपेक्षा करते हैं <math>\mu_j</math> ऊपरोक्त में।) | ||
परिभाषित करना <math> a=(\alpha p_{0i})_{i=1}^J</math>, तो हम हल कर सकते हैं <math> \lambda=(I-P^T)^{-1}a</math>. | परिभाषित करना <math> a=(\alpha p_{0i})_{i=1}^J</math>, तो हम हल कर सकते हैं <math> \lambda=(I-P^T)^{-1}a</math>. | ||
पॉसों प्रक्रिया के बाद सभी कार्य प्रत्येक नोड को छोड़ देते हैं, और परिभाषित करते हैं <math> \mu_i(x_i) </math> जब वहाँ नोड | पॉसों प्रक्रिया के बाद सभी कार्य प्रत्येक नोड को छोड़ देते हैं, और परिभाषित करते हैं <math> \mu_i(x_i) </math> जब वहाँ नोड i की सेवा दर के रूप में <math> x_i </math> नोड i पर कार्य। | ||
होने देना <math>X_i(t)</math> नोड i पर समय t पर नौकरियों की संख्या को | होने देना <math>X_i(t)</math> नोड i पर समय t पर नौकरियों की संख्या को दर्शाता है, और <math> \mathbf{X}=(X_i)_{i=1}^J</math>. फिर का संतुलन वितरण <math>\mathbf{X}</math>, <math>\pi(\mathbf{x})=P(\mathbf{X}=\mathbf{x})</math> संतुलन समीकरणों की निम्नलिखित प्रणाली द्वारा निर्धारित किया जाता है: | ||
:<math> | :<math> | ||
| Line 47: | Line 47: | ||
=== प्रमेय === | === प्रमेय === | ||
मान लीजिए स्वतंत्र | मान लीजिए स्वतंत्र अनियमित चर का एक वेक्टर <math> (Y_1,\ldots,Y_J)</math> प्रत्येक के साथ <math> Y_i</math> संभाव्यता द्रव्यमान कार्य के रूप में | ||
:<math> P(Y_i=n)=p(Y_i=0)\cdot \frac{\lambda_i^n}{M_i(n)}, \quad (3)</math> | :<math> P(Y_i=n)=p(Y_i=0)\cdot \frac{\lambda_i^n}{M_i(n)}, \quad (3)</math> | ||
| Line 57: | Line 57: | ||
{{hidden begin | {{hidden begin | ||
|toggle = left | |toggle = left | ||
|title = | |title = प्रमाण | ||
|titlestyle= font-size:12pt | |titlestyle= font-size:12pt | ||
}} | }} | ||
| Line 76: | Line 76: | ||
{{hidden end}} | {{hidden end}} | ||
यह प्रमेय प्रत्येक नोड की | यह प्रमेय प्रत्येक नोड की स्थिति-निर्भर सेवा दर की अनुमति देकर ऊपर दिखाए गए को बढ़ाता है। के वितरण से संबंधित है <math>\mathbf{X}</math> स्वतंत्र चर के एक सदिश द्वारा <math> \mathbf{Y} </math>। | ||
=== उदाहरण === | === उदाहरण === | ||
| Line 125: | Line 125: | ||
:<math> \pi(1,1,1)=\frac{5}{6}\cdot\frac{2.5}{15}\cdot\frac{11}{16}\cdot\frac{3.75}{12}\cdot\frac{7}{8}\cdot\frac{1.25}{10}\approx 0.00326</math> | :<math> \pi(1,1,1)=\frac{5}{6}\cdot\frac{2.5}{15}\cdot\frac{11}{16}\cdot\frac{3.75}{12}\cdot\frac{7}{8}\cdot\frac{1.25}{10}\approx 0.00326</math> | ||
चूंकि यहां सेवा दर | चूंकि यहां सेवा दर स्थिति पर निर्भर नहीं करती है, इसलिए <math> Y_i</math> बस एक [[ज्यामितीय वितरण]] का अनुसरण करते हैं। | ||
== सामान्यीकृत जैक्सन नेटवर्क == | == सामान्यीकृत जैक्सन नेटवर्क == | ||
'''सामान्यीकृत''' जैक्सन नेटवर्क [[नवीनीकरण प्रक्रिया]] की अनुमति देता है, जिसके लिए पोइसन प्रक्रियाओं की आवश्यकता नहीं होती है, और स्वतंत्र, समान रूप से गैर-घातीय सेवा समय वितरित किया जाता है। सामान्य तौर पर, इस नेटवर्क में उत्पाद-रूप समाधान नहीं होता है। उत्पाद-रूप स्थिर वितरण होता है, इसलिए सन्निकटन मांगा जाता है।<ref>{{cite book|title=Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization|first1=Hong|last1=Chen|first2=David D.|last2=Yao|publisher=Springer|year=2001|isbn=0-387-95166-0}}</ref> | |||
=== ब्राउनियन सन्निकटन === | === ब्राउनियन सन्निकटन === | ||
Revision as of 16:57, 12 June 2023
पंक्तियां सिद्धांत में, संभावना के गणितीय सिद्धांत के भीतर अनुशासन, जैक्सन नेटवर्क (कभी-कभी जैकसोनियन नेटवर्क[1]) पंक्तिबद्ध नेटवर्क का वर्ग है जहां संतुलन वितरण विशेष रूप से गणना करने के लिए सरल होता है क्योंकि नेटवर्क में उत्पाद-रूप समाधान होता है। पंक्तियां के नेटवर्क के सिद्धांत में यह पहला महत्वपूर्ण विकास था, और अन्य नेटवर्कों में समान उत्पाद-रूप समाधानों की खोज के लिए प्रमेय के विचारों को सामान्य बनाना और लागू करना बहुत शोध का विषय रहा है,[2] इंटरनेट के विकास में प्रयुक्त विचारों सहित।[3] नेटवर्क की जेम्स आर. जैक्सन द्वारा पहचान सबसे पहले की गई थी[4][5] और उनके पेपर को जर्नल मैनेजमेंट साइंस के 'टेन मोस्ट इन्फ्लुएंशियल टाइटल्स ऑफ मैनेजमेंट साइंसेज फर्स्ट फिफ्टी इयर्स' में फिर से छापा गया था।[6]
जैक्सन बर्क और रीच के काम से प्रेरित थे,[7] यद्यपि जीन वालरैंड ने "उत्पाद-रूप के परिणामों को नोट किया है ... [हैं] जैक्सन की तुलना में आउटपुट प्रमेय का बहुत कम तात्कालिक परिणाम है जो खुद अपने मौलिक पेपर में विश्वास करने के लिए दिखाई दिया"।[8]
अग्रानुक्रम पंक्तियां (पंक्तियां की परिमित श्रृंखला जहां प्रत्येक ग्राहक को प्रत्येक पंक्ति में क्रम से जाना चाहिए) और चक्रीय नेटवर्क (पंक्तियां का लूप जहां प्रत्येक ग्राहक को क्रम में प्रत्येक पंक्ति में जाना चाहिए) के लिए आर.आर.पी. जैक्सन द्वारा पूर्व उत्पाद-रूप समाधान पाया गया था।[9]
जैक्सन नेटवर्क में कई नोड्स होते हैं, जहां प्रत्येक नोड पंक्ति का प्रतिनिधित्व करता है जिसमें सेवा दर दोनों नोड-निर्भर हो सकती है (विभिन्न नोड्स में अलग-अलग सेवा दरें होती हैं) और स्थिति-निर्भर (पंक्ति की लंबाई के आधार पर सेवा दरें बदलती हैं)। निश्चित रूटिंग मैट्रिक्स के बाद नौकरियां नोड्स के बीच यात्रा करती हैं। प्रत्येक नोड पर सभी नौकरियां एक ही वर्ग से संबंधित हैं और नौकरियां समान सेवा-समय वितरण और समान रूटिंग तंत्र का पालन करती हैं। फलस्वरूप, नौकरियों की सेवा में प्राथमिकता की कोई धारणा नहीं है: प्रत्येक नोड पर सभी नौकरियां पहले आओ, पहले पाओ के आधार पर दी जाती हैं।
जैक्सन नेटवर्क जहां नौकरियों की सीमित आबादी एक बंद नेटवर्क के आसपास घूमती है, वहां गॉर्डन-नेवेल प्रमेय द्वारा वर्णित उत्पाद-रूप समाधान भी है।[10]
जैक्सन नेटवर्क के लिए आवश्यक शर्तें
m परस्पर जुड़ी पंक्तियां के नेटवर्क को 'जैक्सन नेटवर्क' [11] या जैकसोनियन नेटवर्क[12] के रूप में जाना जाता है यदि यह निम्नलिखित शर्तों को पूरा करता है:
- यदि नेटवर्क खुला है, नोड के लिए कोई भी बाहरी आगमन पॉसॉन प्रक्रिया बनाता है,
- सभी सेवा समय घातीय रूप से वितरित किए जाते हैं और सभी पंक्तियां में सेवा अनुशासन पहले आओ पहले पाओ वाला है,
- पंक्ति में सेवा पूरी करने वाला ग्राहक या तो संभावना के साथ कुछ नई पंक्ति j में चला जाएगा या प्रणाली को संभाव्यता के साथ छोड़ दें , जो खुले नेटवर्क के लिए पंक्तियां के कुछ सबसेट के लिए गैर-शून्य है,
- सभी पंक्तियां का उपयोग एक से कम है।
प्रमेय
एम एम/एम/1 पंक्तियां के खुले जैक्सन नेटवर्क में जहां उपयोग होता है प्रत्येक पंक्ति में 1 से कम है, संतुलन स्थिति संभाव्यता वितरण मौजूद है और स्थिति के लिए व्यक्तिगत पंक्ति संतुलन वितरण के उत्पाद द्वारा दिया जाता है
परिणाम ci सर्वर के साथ एम/एम/सी मॉडल स्टेशनों के लिए भी है स्टेशन, उपयोग की आवश्यकता के साथ .
परिभाषा
खुले नेटवर्क में, दर के साथ पॉइसन प्रक्रिया के बाद नौकरियां बाहर से आती हैं । प्रत्येक आगमन को संभावना के साथ स्वतंत्र रूप से नोड j पर रूट किया जाता है और . नोड I पर सेवा पूर्ण होने पर, कार्य संभाव्यता के साथ दूसरे नोड j पर जा सकता है या संभाव्यता के साथ नेटवर्क छोड़ दें