🤖 machine learning

Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

यह शोधपत्र अनरिलेटेड-मशीन मेक्सपैन शेड्यूलिंग के लिए एक लर्निंग-ऑगमेंटेड एल्गोरिदम प्रस्तुत करता है जो सटीक भविष्यवाणियों के लिए बहुपद-समय (polynomial-time) $(1+\varepsilon)$ -अनुमान प्राप्त करता है और जैसे-जैसे भविष्यवाणी की त्रुटि बढ़ती है, सुचारू रूप से सबसे खराब स्थिति वाले 2-अनुमान तक घट जाता है, जिससे चयन समस्याओं से परे एंटोनियाडिस एट अल (Antoniadis et al.) के ढांचे का विस्तार होता है।

मूल लेखक: Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos

प्रकाशित 2026-06-12

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक व्यस्त कारखाने के प्रबंधक हैं जहाँ बहुत सारी अलग-अलग मशीनें हैं (मान लीजिए कि 100 मशीनें) और काम का एक विशाल ढेर लगा है। प्रत्येक काम को प्रत्येक मशीन पर करने में अलग-अलग समय लगता है। आपका लक्ष्य कामों को इस तरह बांटना है कि जिस मशीन पर सबसे अधिक काम का भार है, वह जितनी जल्दी हो सके काम पूरा कर ले। यह एक क्लासिक, अत्यंत कठिन पहेली है जिसे अनरिलेटेड-मशीन मेक्सपैन शेड्यूलिंग (Unrelated-Machines Makespan Scheduling) कहा जाता है।

कंप्यूटर विज्ञान की दुनिया में, इसे पूरी तरह से हल करना एक अंधे व्यक्ति के लिए घास के ढेर में सुई खोजने जैसा है; यह बड़े कारखानों के लिए तेजी से करना गणनात्मक रूप से असंभव है। हम आमतौर पर जो सबसे अच्छा कर सकते हैं वह एक "पर्याप्त अच्छा" समाधान है जो यह गारंटी देता है कि हम आदर्श शेड्यूल से दोगुने से अधिक धीमे नहीं होंगे।

नया विचार: एक "क्रिस्टल बॉल" (भविष्यवाणी) का उपयोग करना

हाल ही में, शोधकर्ताओं ने यह पूछना शुरू किया है: क्या होगा अगर हमारे पास एक क्रिस्टल बॉल हो? क्या होगा अगर कोई मशीन लर्निंग मॉडल हमें संकेत दे सके कि कौन से काम किन मशीनों पर जाने चाहिए?

समस्या यह है कि क्रिस्टल बॉल परफेक्ट नहीं होतीं। कभी-कभी वे सही होती हैं, और कभी-कभी वे गलत होती हैं। यदि आप किसी गलत संकेत का आँख मूंदकर पालन करते हैं, तो आप बिना किसी संकेत के काम करने की तुलना में शेड्यूल को और भी खराब कर सकते हैं।

यह पेपर एक नए एल्गोरिदम को पेश करता है जो एक "क्रिस्टल बॉल वाले स्मार्ट मैनेजर" की तरह काम करता है। यह भविष्यवाणी का उपयोग प्रक्रिया को तेज करने के लिए करता है, लेकिन इसमें एक सुरक्षा जाल (सेफ्टी नेट) भी बना हुआ है।

यह कैसे काम करता है: "भारी" बनाम "हल्का" सादृश्य (Analogy)

इस ट्रिक को समझने के लिए, कल्पना कीजिए कि काम बक्से हैं। कुछ बक्से बहुत बड़े (Huge) हैं (भारी) और कुछ बहुत छोटे (Tiny) हैं (हल्के)।

कठिन हिस्सा: भारी बक्सों को कहाँ रखना है, इसका निर्णय लेना असली सिरदर्द है। यदि आप एक भारी बक्सा गलत मशीन पर रखते हैं, तो यह पूरे शेड्यूल को बिगाड़ देता है।
आसान हिस्सा: एक बार जब भारी बक्से रख दिए जाते हैं, तो खाली जगहों को भरने के लिए छोटे बक्सों को इधर-उधर व्यवस्थित करना आसान होता है।

लेखकों का एल्गोरिदम दो परतों में काम करता है:

भविष्यवाणी (क्रिस्टल बॉल): एल्गोरिदम भविष्यवाणी को देखता है और कहता है, "ठीक है, क्रिस्टल बॉल कहती है कि ये विशिष्ट भारी बक्से यहाँ जाते हैं।" यह स्पष्ट रूप से भारी कामों के लिए भविष्यवाणी पर भरोसा करता है।
सुरक्षा जाल (लोकल सर्च): एल्गोरिदम जानता है कि क्रिस्टल बॉल कुछ भारी बक्सों को छोड़ सकती है या कुछ को गलत कर सकती है। इसलिए, यह केवल संकेत का आँख मूंदकर पालन नहीं करता है। यह भविष्यवाणी के आसपास एक सीमित खोज (Limited Search) करता है।
- यह पूछता है: "क्या क्रिस्टल बॉल ने कुछ भारी बक्सों को छोड़ दिया है? बड़ी गलतियों को ठीक करने के लिए आइए कुछ संभावनाओं की जाँच करूँ।"
- यह पूछता है: "क्या क्रिस्टल बॉल ने एक भारी बक्सा गलत मशीन पर रख दिया है? देखते हैं कि क्या मैं इसे बदल (swap) सकता हूँ।"

जादुई परिणाम: सुचारू गिरावट (Smooth Degradation)

इस पेपर की खासियत यह है कि एल्गोरिदम भविष्यवाणी की गुणवत्ता के आधार पर कैसा व्यवहार करता है:

यदि क्रिस्टल बॉल एकदम सटीक है: एल्गोरिदम एक ऐसा शेड्यूल पाता है जो लगभग आदर्श है (सर्वश्रेष्ठ संभव समय के 1% के भीतर)। यह अविश्वसनीय रूप से तेजी से चलता है।
यदि क्रिस्टल बॉल थोड़ी गलत है: एल्गोरिदम छोटी गलतियों को नोटिस करता है। यह बड़ी गलतियों को ठीक करने के लिए अपने "लोकल सर्च" का उपयोग करता है। शेड्यूल थोड़ा धीमा हो जाता है, लेकिन यह सुचारू रूप से (smoothly) घटता है। यह क्रैश नहीं होता; यह बस थोड़ा कम कुशल हो जाता है।
यदि क्रिस्टल बॉल बहुत खराब है: भले ही भविष्यवाणी बेकार हो, एल्गोरिदम के पास एक बैकअप प्लान है। यह एक मानक, विश्वसनीय तरीके पर वापस आ जाता है जो गारंटी देता है कि आपका शेड्यूल कभी भी इष्टतम (optimal) समय के दोगुने से बुरा नहीं होगा।

इसे जीपीएस (GPS) के साथ गाड़ी चलाने की तरह समझें।

यदि जीपीएस सही है, तो आप सबसे अच्छा रास्ता चुनते हैं।
यदि जीपीएस थोड़ा गलत है, तो आप शायद एक छोटा मोड़ लें, लेकिन फिर भी आप काफी तेजी से पहुँच जाते हैं।
यदि जीपीएस पूरी तरह से खराब है, तो आप उसे अनदेखा कर देते हैं और मुख्य हाईवे पर चलते हैं। हो सकता है कि आपको सबसे तेज रास्ता न मिले, लेकिन यह गारंटी है कि आप रास्ता भटके बिना या ऐसे ट्रैफिक जाम में फंसे बिना पहुँच जाएंगे जो बहुत लंबा हो सकता है।

ट्रेड-ऑफ: कितना भरोसा करें?

पेपर एक "सर्च बजट" पेश करता है (मान लीजिए कि इसे K कहते हैं)। यह एक डायल की तरह है जिसे आप घुमा सकते हैं:

इसे कम करें (Low K): आप भविष्यवाणी पर अधिक भरोसा करते हैं और कम जाँच करते हैं। यह बहुत तेज़ है, लेकिन यदि भविष्यवाणी गलत है, तो आपका शेड्यूल थोड़ा खराब हो सकता है।
इसे बढ़ाएं (High K): आप भविष्यवाणी पर कम भरोसा करते हैं और अधिक जाँच करते हैं। इसमें चलने में थोड़ा अधिक समय लगता है, लेकिन यह अधिक गलतियों को ठीक कर सकता है, जिससे एक बेहतर शेड्यूल मिलता है भले ही भविष्यवाणी अव्यवस्थित हो।

यह क्यों महत्वपूर्ण है

इस पेपर से पहले, हमारे पास दो विकल्प थे:

तेज़ तरीका: जल्दी से एक "पर्याप्त अच्छा" शेड्यूल (2x वर्स्ट-केस) प्राप्त करना, लेकिन किसी भी भविष्यवाणी को अनदेखा करना।
परफेक्ट तरीका: सर्वोत्तम शेड्यूल खोजने के लिए भविष्यवाणियों का उपयोग करने का प्रयास करना, लेकिन इसे कंप्यूट करने में इतना समय लगेगा कि यह वास्तविक कारखानों के लिए बेकार हो जाएगा।

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

सारांश

लेखकों ने एक शेड्यूलिंग एल्गोरिदम बनाया है जो मशीन लर्निंग भविष्यवाणी को सुनता है लेकिन एक आँख दरवाजे पर रखता है। यदि भविष्यवाणी अच्छी है, तो यह तेजी से आगे बढ़ता है। यदि भविष्यवाणी खराब है, तो यह धीमा हो जाता है, अपने काम की जाँच करता है, और यह सुनिश्चित करता है कि यह कभी भी एक विश्वसनीय, मानक बेसलाइन से नीचे न गिरे। यह एक "अनुमान लगाने के खेल" को एक "स्मार्ट, सुरक्षित रणनीति" में बदल देता है।

तकनीकी सारांश: अनरिलेटेड-मशीन्स मेक्सपैन शेड्यूलिंग के लिए लर्निंग-ऑगमेंटेड एप्रोक्सिमेशन

समस्या की परिभाषा
यह शोध पत्र अनरिलेटेड-मशीन्स मेक्सपैन शेड्यूलिंग समस्या को संबोधित करता है, जिसे $R\|C_{\max}$ द्वारा दर्शाया गया है। यहाँ $n$ जॉब्स और $m$ मशीनें दी गई हैं, जहाँ प्रत्येक जॉब $j$ का एक मशीन-निर्भर प्रोसेसिंग समय $p_{ij}$ होता है। उद्देश्य प्रत्येक जॉब को एक मशीन पर असाइन करना है ताकि सभी मशीनों पर अधिकतम लोड (मेक्सपैन) को कम किया जा सके। यह समस्या अत्यंत जटिल (NP-hard) है; लेनस्ट्रै एट अल. (1990) ने एक बहुपद-समय (polynomial-time) 2-एप्रोक्सिमेशन स्थापित किया और सिद्ध किया कि इस कारक को $3/2$ से बेहतर बनाना NP-hard है। जबकि फिक्स्ड संख्या में मशीनों $m$ के लिए एक $(1+\epsilon)$ -एप्रोक्सिमेशन मौजूद है, यह "हेवी" असाइनमेंट्स (ऐसे जॉब्स जिनका प्रोसेसिंग समय $> \epsilon T$ है) के विस्तृत खोज (exhaustive search) पर निर्भर करता है, जिसके परिणामस्वरूप जब $m$ इनपुट का हिस्सा होता है, तो यह नॉन-पॉलिनोमियल टाइम कॉम्प्लेक्सिटी की ओर ले जाता है।

कार्यप्रणाली (Methodology)
लेखक एक लर्निंग-ऑगमेंटेड एप्रोक्सिमेशन एल्गोरिदम प्रस्तावित करते हैं जो क्लासिकल 2-एप्रोक्सिमेशन और $(1+\epsilon)$ -एप्रोक्सिमेशन के बीच के अंतर को पाटने के लिए 'हेवी जॉब असाइनमेंट्स' के भविष्यवाणियों (predictions) को शामिल करता है। एल्गोरिदम क्लासिकल हेवी/शॉर्ट डिकम्पोजिशन प्रतिमान (paradigm) पर कार्य करता है लेकिन भविष्यवाणियों का उपयोग करके सर्च स्पेस को स्थानीयकृत (localize) करता है।

प्रेडिक्शन मॉडल: एल्गोरिदम एक प्रेडिक्टेड पार्शियल असाइनमेंट $\hat{\phi}$ प्राप्त करता है, जो जॉब्स के एक उपसमूह के लिए मशीन असाइनमेंट का सुझाव देता है। जिन जॉब्स की भविष्यवाणी नहीं की गई है, उन्हें $\perp$ के रूप में चिह्नित किया जाता है।
दो-स्तरीय संरचना (Two-Layer Structure):
- इनर लेयर (प्रेडिक्शन-गाइडेड कम्प्लीशन): एक निश्चित लक्ष्य मेक्सपैन $T$ के लिए, एल्गोरिदम केवल "T-हेवी" असाइनमेंट्स (जहाँ $p_{ij} > \epsilon T$ ) को बनाए रखने के लिए प्रेडिक्शन को फ़िल्टर करता है। इसके बाद, यह प्रेडिक्शन द्वारा छूटे हुए अधिकतम $K$ मिसिंग हेवी असाइनमेंट्स (augmentations) को खोजने के लिए एक लोकल सर्च करता है। प्रत्येक कैंडिडेट सेट के लिए, यह शेष जॉब्स के लिए एक रेसिडुअल लीनियर प्रोग्राम (LP) हल करता है और शमोस-टार्डोस राउंडिंग (Shmoys–Tardos rounding) लागू करता है।
- आउटर लेयर (थ्रेशोल्ड सर्च): बाइनरी सर्च के बजाय, एल्गोरिदम "क्रिटिकल थ्रेशोल्ड्स" की एक बहुपद संख्या को सूचीबद्ध करता है जहाँ हेवी/शॉर्ट वर्गीकरण बदलता है। यह इन थ्रेशोल्ड्स पर इनर लेयर को चलाता है और पाया गया सबसे अच्छा शेड्यूल लौटाता है, यह सुनिश्चित करते हुए कि परिणाम कभी भी क्लासिकल 2-एप्रोक्सिमेशन बेसलाइन से अधिक न हो।
त्रुटि माप (Error Measures): विश्लेषण विशिष्ट त्रुटि मेट्रिक्स को परिभाषित करता है:
- फॉल्स नेगेटिव्स ( $R^-_{OPT}$ ): प्रेडिक्शन द्वारा छूटे गए हेवी जॉब्स का अधिकतम प्रोसेसिंग समय।
- फॉल्स पॉजिटिव्स ( $R^+_{OPT}$ ): प्रेडिक्टेड हेवी असाइनमेंट्स द्वारा किया गया अधिकतम ओवरलोड जो अनुकूलतम (optimal) शेड्यूल से भिन्न है।
- $K$ -रेसिडुअल एरर ( $R^-_{OPT,K}$ ): $K$ मिस किए गए हेवी जॉब्स को इष्टतम रूप से रिकवर करने के बाद शेष बची त्रुटि।

प्रमुख योगदान

लर्निंग-ऑगमेंटेड फ्रेमवर्क्स का विस्तार: यह कार्य एंटोनियाडिस एट अल. (2025) द्वारा उठाए गए एक खुले प्रश्न को संबोधित करता है, जो लीनियर-ऑब्जेक्टिव सिलेक्शन समस्याओं से मेक्सपैन ऑब्जेक्टिव वाली शेड्यूलिंग समस्याओं तक स्मूथ प्रेडिक्शन-डिपेंडेंट गारंटियों के विस्तार से संबंधित है।
स्मूथ ट्रेडऑफ गारंटियां: एल्गोरिदम सटीक भविष्यवाणियों के मामले में $(1+\epsilon)OPT$ गारंटी प्राप्त करता है। जैसे-जैसे प्रेडिक्शन एरर बढ़ता है, गारंटी फॉल्स नेगेटिव्स और फॉल्स पॉजिटिव्स से संबंधित एडिटिव टर्म्स द्वारा सीमित होते हुए सुचारू रूप से घटती जाती है। महत्वपूर्ण रूप से, वर्स्ट-केस प्रदर्शन कभी भी क्लासिकल 2-एप्रोक्सिमेशन से खराब नहीं होता।
पॉलिनोमियल-टाइम एफिशिएंसी: क्लासिकल $(1+\epsilon)$ स्कीम्स के विपरीत, जिन्हें $m$ में घातीय (exponential) समय की आवश्यकता होती है, यह एल्गोरिदम किसी भी फिक्स्ड सर्च बजट $K$ के लिए $m$ और $n$ में बहुपद समय ( $O((mn)^K \cdot \text{poly}(\dots))$ ) में चलता है। पैरामीटर $K$ रनिंग टाइम और फॉल्स-नेगेटिव प्रेडिक्शंस को ठीक करने की क्षमता के बीच के ट्रेडऑफ को नियंत्रित करता है।
त्रुटियों की विषमता (Asymmetry of Errors): विश्लेषण एक विषमता प्रकट करता है: फॉल्स नेगेटिव्स को लोकल सर्च के माध्यम से रिकवर किया जा सकता है (समय जटिलता $K$ की कीमत पर), जबकि फॉल्स पॉजिटिव्स सीधे मेक्सपैन बाउंड में योगदान देते हैं और प्रेडिक्शन ट्रस्ट मॉडल को बदले बिना उन्हें "सर्च" के जरिए हटाया नहीं जा सकता।

परिणाम

सैद्धांतिक सीमाएं (Theoretical Bounds): थ्योरम 5.2 स्थापित करता है कि मेक्सपैन $C_{\max}(S)$ निम्नलिखित है:
$C_{\max}(S) \le \min \left\{ (1+\epsilon)OPT + R^-_{OPT,K} + R^+_{OPT}, \ 2OPT \right\}$
यह कंसिस्टेंसी (सटीक भविष्यवाणियों पर इष्टतम प्रदर्शन), रोबस्टनेस (खराब भविष्यवाणियों पर 2-एप्रोक्सिमेशन द्वारा सीमित), और स्मूथनेस (त्रुटि के अनुपात में गिरावट) की पुष्टि करता है।
अनुभवजन्य सत्यापन (Empirical Validation): सिंथेटिक इंस्टेंस पर संख्यात्मक प्रयोगों से पता चलता है कि:
- सटीक भविष्यवाणियों के साथ, एल्गोरिदम मेक्सपैन क्वालिटी में क्लासिकल 2-एप्रोक्सिमेशन बेसलाइन से काफी बेहतर प्रदर्शन करता है।
- एल्गोरिदम क्लासिकल $(1+\epsilon)$ -टाइप बेसलाइन्स की तुलना में कई गुना तेज़ चलता है (जो $m$ बढ़ने पर अव्यवहारिक हो जाते हैं), और 2-एप्रोक्सिमेशन की गति से मेल खाता है।
- $K$ के सर्च बजट को बढ़ाने से फॉल्स नेगेटिव्स की उपस्थिति में मेक्सपैन क्वालिटी में सुधार होता है, जो सैद्धांतिक ट्रेडऑफ को प्रमाणित करता है।
- एल्गोरिदम अनुमानित विषमता प्रदर्शित करता है: $K$ को बढ़ाने से फॉल्स नेगेटिव्स में मदद मिलती है लेकिन फॉल्स पॉजिटिव्स पर इसका प्रभाव नगण्य रहता है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह $R\|C_{\max}$ के लिए पहला लर्निंग-ऑगमेंटेड एप्रोक्सिमेशन फ्रेमवर्क प्रदान करता है जो स्मूथ, प्रेडिक्शन-डिपेंडेंट गारंटियां प्रदान करता है और साथ ही मशीन की संख्या से स्वतंत्र पॉलिनोमियल-टाइम कॉम्प्लेक्सिटी बनाए रखता है। भविष्यवाणियों द्वारा परिभाषित एक पड़ोस (neighborhood) में महंगी स्ट्रक्चरल सर्च (हेवी असाइनमेंट्स) को स्थानीयकृत करके, यह विधि शेड्यूलिंग एल्गोरिदम को क्लासिकल वर्स्ट-केस बेसलाइन्स से समझौता किए बिना उच्च-गुणवत्ता वाली मशीन लर्निंग भविष्यवाणियों का लाभ उठाने की अनुमति देती है। लेखक इसे उन ऑप्टिमाइज़ेशन समस्याओं तक लर्निंग-ऑगमेंटेड गारंटियों को विस्तारित करने की दिशा में एक कदम के रूप में देखते हैं जहाँ क्लासिकल एल्गोरिदम महंगी स्ट्रक्चरल गेसिंग (structural guessing) पर निर्भर करते हैं।