A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization
यह शोध पत्र समान मशीनों पर अनवेटेड नॉनप्रीएम्प्टिव थ्रूपुट मैक्सिमाइजेशन में शेड्यूल्ड जॉब्स की संख्या को अधिकतम करने के लिए एक रैंडमाइज्ड -अनुमानित एल्गोरिदम प्रस्तुत करता है, जो पिछले और के अनुमानित कारकों में सुधार करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखक ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कंप्यूटिंग की दुनिया में, एक मौलिक चुनौती एक निश्चित समय सीमा के भीतर अधिक से अधिक काम पूरा करने के लिए कार्यों की एक धारा को व्यवस्थित करने से जुड़ी है। कल्पना कीजिए कि एक फैक्ट्री फ्लोर पर कई समान मशीनें हैं, जिनमें से प्रत्येक एक समय में एक वस्तु को संसाधित करने में सक्षम है। प्रत्येक वस्तु, या "जॉब," अपने साथ एक विशिष्ट प्रारंभ समय और एक सख्त समय सीमा लेकर आती है जिसके भीतर उसे पूरा किया जाना चाहिए। प्रत्येक जॉब को पूरा करने के लिए कुछ निश्चित समय की आवश्यकता होती है। लक्ष्य प्रत्येक जॉब को पूरा करना नहीं है, बल्कि अधिकतम संभव संख्या में जॉब्स का चयन करना और उन्हें मशीनों पर इस तरह व्यवस्थित करना है कि एक ही मशीन पर दो जॉब्स आपस में न टकराएं और चुना गया प्रत्येक जॉब अपनी समय सीमा से पहले समाप्त हो जाए। यह थ्रूपुट मैक्सिमाइजेशन (throughput maximization) का एक मामला है। यह कहने में बहुत सरल है लेकिन इसे पूरी तरह से हल करना कठिन है, विशेष रूप से जब जॉब्स की संख्या बहुत अधिक हो और उनके समय अंतराल बहुत भिन्न हों। चूंकि बड़े जॉब सेट के लिए सबसे अच्छा शेड्यूल खोजना अक्सर गणनात्मक रूप से असंभव होता है, इसलिए शोधकर्ता ऐसे एल्गोरिदम बनाने पर ध्यान केंद्रित करते हैं जो तेजी से एक ऐसा शेड्यूल खोज सकें जो सर्वोत्तम संभव शेड्यूल के बहुत करीब हो। सफलता का पैमाना यह है कि एल्गोरिदम सर्वोत्तम के सैद्धांतिक अधिकतम की तुलना में कितने जॉब्स को शेड्यूल कर पाता है।
वर्षों तक, मनमाने ढंग की संख्या में मशीनों पर इस समस्या को हल करने के लिए ज्ञात सर्वोत्तम विधियां लगभग 4/3 (लगभग 0.76) और 17/13 (लगभग 1.3) के कारकों के करीब गारंटी दे सकती थीं। शोधकर्ताओं की एक टीम ने अब इस सीमा को काफी आगे बढ़ा दिया है। उन्होंने एक नया एल्गोरिदम विकसित किया है जो, किसी भी वांछित सटीकता स्तर के लिए, अधिकतम संभव जॉब्स के कम से कम ग्यारह-बारहवें (11/12) हिस्से के बराबर शेड्यूल की गारंटी दे सकता है। यह सुधार, भले ही अंश में छोटा लगे, इस प्रकार की शेड्यूलिंग समस्याओं के लिए प्राप्त करने योग्य सैद्धांतिक सीमाओं में एक बड़ी छलांग का प्रतिनिधित्व करता है। यह विधि पहले एक लचीला, संभाव्य ब्लूप्रिंट (probabilistic blueprint) बनाती है कि जॉब्स को कैसे व्यवस्थित किया जा सकता है, और फिर उस ब्लूप्रिंट को एक ठोस, व्यवहार्य शेड्यूल में सावधानीपूर्वक परिवर्तित करती है ताकि प्रक्रिया में बहुत अधिक मूल्य का नुकसान न हो।
इस समस्या को हल करने की मुख्य कठिनाई जॉब्स की प्रकृति में निहित है। एक एकल जॉब कई अलग-अलग टाइम स्लॉट्स में फिट हो सकती है, लेकिन अंतिम शेड्यूल में इसे केवल एक बार ही गिना जा सकता है। यदि कोई कंप्यूटर सभी संभावित वैध स्लॉट्स में से यादृच्छिक रूप से चुनकर जॉब्स को रखने का अनुमान लगाने की कोशिश करता है, तो परिणाम अक्सर अस्त-व्यस्त होता है: कुछ जॉब्स को विभिन्न स्थानों पर कई बार चुना जा सकता है, जबकि अन्य को पूरी तरह से छोड़ दिया जाता है। शोधकर्ताओं का दृष्टिकोण नियमों को थोड़ा शिथिल करके शुरू होता है ताकि एक गणितीय मॉडल में एक जॉब को कई संभावित स्लॉट्स में "फैलाया" जा सके। यह मॉडल व्यवस्थाओं को विभिन्न संभावनाएँ (probabilities) आवंटित करता है, जो प्रभावी रूप से कहता है, "इस जॉब के यहाँ जाने की एक निश्चित संभावना है, और वहाँ जाने की एक निश्चित संभावना है।" चुनौती इस धुंधली, भिन्नात्मक तस्वीर को एक वास्तविक, ठोस शेड्यूल में बदलना है जहाँ प्रत्येक जॉब या तो पूरी तरह से मौजूद है या पूरी तरह से अनुपस्थित है, बिना मशीन की क्षमता या जॉब की समय सीमा का उल्लंघन किए।
गणितीय मॉडल और वास्तविक शेड्यूल के बीच के अंतर को पाटने के लिए, टीम ने एक रणनीति पेश की जो टाइमलाइन को ब्लॉकों की एक श्रृंखला के रूप में मानती है। वे इन ब्लॉकों को एक साथ समूहबद्ध करते हैं और पूर्व-निर्धारित संभावनाओं की एक सूची से व्यवस्थाओं का नमूना लेते हैं। मुख्य नवाचार यह है कि वे उन जॉब्स को कैसे संभालते हैं जो कई ब्लॉक्स में दिखाई देते हैं। उनके मॉडल में, एक जॉब एक ब्लॉक में अपने प्रारंभ समय पर और दूसरे ब्लॉक में अपने अंत समय पर दिखाई दे सकती है। यदि एल्गोरिदम यादृच्छिक रूप से इनमें से एक उपस्थिति को चुनता है, तो यह गलती से दोनों को चुन सकता है, जिससे डुप्लिकेट बन सकता है, या किसी को भी नहीं चुन सकता, जिससे जॉब पूरी तरह से छूट सकती है। शोधकर्ताओं ने एक ऐसी प्रणाली डिजाइन की है जो पता लगाती है कि कब किसी जॉब के डुप्लिकेट होने या छूट जाने की संभावना है और फिर शेड्यूल को "मरम्मत" (repair) करती है। उन्होंने जॉब्स के विशिष्ट जोड़ों की पहचान की जहाँ एक जॉब का टाइम स्लॉट दूसरी जॉब के लिए बैकअप के रूप में कार्य कर सकता है। यदि कोई जॉब डुप्लिकेट हो जाती है, तो अतिरिक्त प्रति को हटाया जा सकता है, और उसका टाइम स्लॉट किसी अन्य जॉब को दिया जा सकता है जिसे मिस कर दिया गया था, बशर्ते कि समय की अनुमति हो।
यह मरम्मत तंत्र संभावनाओं के सावधानीपूर्ण लेखांकन पर निर्भर करता है। एल्गोरिदम ट्रैक करता है कि किसी जॉब के डुप्लिकेट होने की कितनी संभावना है और उसके छूट जाने की कितनी संभावना है। इसके बाद, वह इन मरम्मतों के लिए विशेष रूप से शेड्यूल की क्षमता का एक हिस्सा अलग रख देता है। इसे एक बजट की तरह समझें जहाँ आप अप्रत्याशित खर्चों के लिए कुछ पैसा आरक्षित करते है; यदि कोई जॉब डुप्लिकेट होती है, तो एल्गोरिदम अतिरिक्त समय को उस जॉब की ओर स्थानांतरित करने के लिए आरक्षित क्षमता का उपयोग करता है जिसे इसकी आवश्यकता है। शोधकर्ताओं ने सिद्ध किया कि इन आरक्षणों और मरम्मत के प्रवाह का प्रबंधन करके, वे पर्याप्त मूल्य को पुनः प्राप्त कर सकते हैं ताकि यह सुनिश्चित हो सके कि अंतिम शेड्यूल सर्वोत्तम संभव एक के बहुत करीब है। उन्होंने टाइम ब्लॉक्स को इस तरह से समूहबद्ध करने का एक तरीका भी विकसित किया जो संघर्षों की संभावना को कम करता है, जिसमें एक ऐसी तकनीक का उपयोग किया गया है जो टाइमलाइन को प्रबंधनीय खंडों में विभाजित करती है ताकि मरम्मत प्रक्रिया बहुत जटिल न हो जाए।
इस जटिल प्रक्रिया का परिणाम एक ऐसा एल्गोरिदम है जो बहुत बड़े जॉब सेट्स के लिए भी कुशलतापूर्वक चलता है। इसके लिए मशीनों के तेज़ होने या डेडलाइन्स के ढीले होने की आवश्यकता नहीं है; यह केवल मौजूदा बाधाओं को व्यवस्थित करने का एक बेहतर तरीका खोजता है। टीम ने प्रदर्शित किया है कि उनकी विधि एक अपेक्षित आकार का शेड्यूल प्राप्त कर सकती है जो इष्टतम समाधान के कम से कम ग्यारह-बारहवें (11/12) के बराबर है, जो पिछले सर्वोत्तम गारंटियों (जैसे 4/3 और 17/13) में सुधार करता है। इसका अर्थ है कि प्रत्येक बारह जॉब जो सैद्धांतिक रूप से शेड्यूल की जा सकती हैं, उनका एल्गोरिदम कम से कम ग्यारह जॉब्स को शेड्यूल करने का रास्ता खोजने की गारंटी देता है। उनका प्रमाण कठोर है और किसी भी संख्या में समान मशीनों के लिए मान्य है, चाहे जॉब्स समय में कैसे भी वितरित हों। अपने संभाव्य मॉडलों को वास्तविक शेड्यूल में बदलने के तरीके को परिष्कृत करके, शोधकर्ताओं ने दिखाया है कि शेड्यूलिंग के लिए हम जो हासिल कर सकते हैं उसकी सीमाएं पहले की तुलना में अधिक हैं, जो कंप्यूटिंग सिस्टम में कार्यों की जटिल धाराओं को व्यवस्थित करने के लिए एक अधिक कुशल मार्ग प्रदान करती हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।