🤖 AI

Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

यह शोध पत्र जॉब शॉप शेड्यूलिंग के लिए एक विश्वसनीय, कम लागत वाले लर्निंग-असिस्टेड हाइपर-ह्यूरिस्टिक का प्रस्ताव करता है जो रिग्रेट-नॉर्मलाइज्ड रोलआउट लेबल्स, कॉन्टेक्स्टुअल KNN अनसर्टेन्टी एस्टीमेट्स और एक गेटेड डिसीजन मैकेनिज्म को जोड़कर महंगे लेबल जनरेशन को कम करता है और चयन स्थिरता सुनिश्चित करता है।

मूल लेखक: Junhao Wei, Yanxiao Li, Yifu Zhao, Zhenhong Peng, Baili Lu, Dexing Yao, Haochen Li, Qinbin He, Sio-Kei Im, Yapeng Wang, Xu Yang

प्रकाशित 2026-05-26

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

CC BY 4.0

मूल लेखक: Junhao Wei, Yanxiao Li, Yifu Zhao, Zhenhong Peng, Baili Lu, Dexing Yao, Haochen Li, Qinbin He, Sio-Kei Im, Yapeng Wang, Xu Yang

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

कल्पना कीजिए कि आप एक व्यस्त कारखाने के प्रबंधक हैं जहाँ कई मशीनें और कई काम पूरे करने के लिए हैं। आपका लक्ष्य सब कुछ यथाशीघ्र पूरा करना है। यह जॉब शॉप शेड्यूलिंग प्रॉब्लम (JSSP) है।

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

यह शोध पत्र एक स्मार्ट "कोच" (प्रशिक्षक) पेश करता है जो प्रबंधकों को यह तय करने में मदद करता है कि किसी भी दिए गए क्षण में किस नियम का उपयोग किया जाए। हालाँकि, लेखकों ने देखा कि पिछले "स्मार्ट कोच" में दो बड़ी समस्याएँ थीं:

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

यहाँ उनका नया समाधान, रोलआउट-कैलिब्रेटेड हाइपर-ह्यूरिस्टिक्स (Rollout-Calibrated Hyper-Heuristics) कैसे काम करता है, सरल उपमाओं का उपयोग करके दिया गया है:

1. "रिग्रेट" (पछतावा) स्कोर (कच्चे स्कोर के बजाय)

कल्पना कीजिए कि आप एक छात्र को ग्रेड दे रहे हैं।

पुराना तरीका: आप स्कोर इस आधार पर देते हैं कि उन्होंने 100 में से कितने अंक प्राप्त किए। यदि उन्हें 95 मिलते हैं, तो यह बहुत अच्छा है। लेकिन यदि परीक्षा असंभव थी और किसी के भी अधिकतम अंक 95 ही आ सकते थे, तो 95 मिलना वास्तव में विशेष नहीं है।
नया तरीका (रिग्रेट): आप उन्हें इस आधार पर ग्रेड देते हैं कि उन्होंने उस विशिष्ट स्थिति में सर्वोत्तम प्रदर्शन की तुलना में कितना कम प्राप्त किया। यदि सर्वोत्तम संभव स्कोर 95 था और उन्हें 95 मिले, तो उनका "रिग्रेट" शून्य है। यदि उन्हें 90 मिले, तो उनका रिग्रेट 5 है।
यह क्यों मदद करता है: यह कोच को स्थानीय सुधारों (local improvements) पर ध्यान केंद्रित करना सिखाता है। यह कोच को दिन की पूर्ण कठिनाई के बारे में चिंता करने के बजाय इस पर ध्यान केंद्रित करने से रोकता है कि: "क्या हमने उपलब्ध अन्य विकल्पों की तुलना में अभी इसी क्षण सबसे अच्छा नियम चुना?"

2. "अनसर्टेन्टी गेट" (अनिश्चितता का द्वार - एक सुरक्षा स्विच)

कल्पना कीजिए कि एक ड्राइवर जो भरोसेमंद होने के कारण आमतौर पर मुख्य राजमार्ग (डिफ़ॉल्ट नियम) पर ही रहता है।

पुराना तरीका: यदि जीपीएस कहता है, "हे, एक शॉर्टकट है जिससे शायद 30 सेकंड बच सकते हैं," तो ड्राइवर तुरंत हाईवे से मुड़ जाता है। कभी-कभी जीपीएस गलत होता है, या शॉर्टकट पर ट्रैफिक वास्तव में बदतर होता है, और ड्राइवर अपना समय बर्बाद करता है।
नया तरीका (द गेट): कोच के पास एक "कॉन्फिडेंस मीटर" (विश्वास मीटर) होता है। वह ड्राइवर को हाईवे छोड़ने के लिए तभी कहता है जब अनुमानित शॉर्टकट हाईवे की तुलना में काफी बेहतर हो और कोच उस भविष्यवाणी के प्रति बहुत आश्वस्त हो।
यह कैसे काम करता है: कोच यह अनुमान लगाने के लिए कि उसकी भविष्यवाणी कितनी "डगमगाती" (shaky) है, एक सांख्यिकीय तकनीक (जिसे KNN कहा जाता है) का उपयोग करता है। यदि भविष्यवाणी डगमगाती है (उच्च अनिश्चितता), तो गेट बंद रहता है, और ड्राइवर सुरक्षित हाईवे पर ही रहता है। यदि भविष्यवाणी ठोस है और लाभ बड़ा है, तो गेट खुल जाता है।

3. "सिमुलेशन बजट" (गुणवत्ता के लिए समय का व्यापार)

कोच को सिखाने के लिए, आपको सिमुलेशन चलाने होते हैं।

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

परिणाम

जब उन्होंने कंप्यूटर-जनित फैक्ट्री परिदृश्यों पर इसका परीक्षण किया:

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

संक्षेप में

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

सफलता को कच्चे स्कोर के बजाय "हमने क्या मिस किया" के आधार पर मापना।
योजना को केवल तभी बदलना जब वह पूरी तरह सुनिश्चित हो कि नया प्लान बहुत बेहतर है।
हर एक संभावना को ओवर-सिमुलेट न करके समय बचाना।

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

तकनीकी सारांश: कम लागत वाले लेबल, विश्वसनीय विकल्प

समस्या विवरण
यह शोध पत्र चयन हाइपर-ह्यूरिस्टिक्स (selection hyper-heuristics) के दृष्टिकोण से जॉब शॉप शेड्यूलिंग समस्या (JSSP) को संबोधित करता है। जबकि लर्निंग-असिस्टेड हाइपर-ह्यूरिस्टिक्स, फिक्स्ड डिस्पैचिंग रूल्स और एंड-टू-एंड लर्नड कंस्ट्रक्टर्स के बीच एक मध्य मार्ग प्रदान करते हुए व्यवहार्यता और व्याख्यात्मकता बनाए रखते हैं, वे दो प्राथमिक बाधाओं का सामना करते हैं:

लेबल जनरेशन लागत: सुपरवाइज्ड लर्निंग के लिए उन लेबल्स की आवश्यकता होती है जो एक आंशिक शेड्यूल से टर्मिनल स्टेट तक कैंडिडेट डिस्पैचिंग रूल्स के "रोलआउट" (rollout) से उत्पन्न होते हैं। प्रत्येक निर्णय बिंदु पर प्रत्येक कैंडिडेट नियम के लिए एक पूर्ण रोलआउट करने में $O(|H|T)$ की कम्प्यूटेशनल लागत आती है, जहाँ $|H|$ नियमों की संख्या है और $T$ शेष निर्णय हैं।
चयन की विश्वसनीयता: एक सीखा हुआ सेलेक्टर शोर (noise) या ओवरफिटिंग के कारण एक मजबूत डिफॉल्ट नियम की तुलना में मामूली सुधार की भविष्यवाणी गलती से कर सकता है। निम्नतम अनुमानित स्कोर का आँख मूंदकर पालन करने से एक मजबूत फिक्स्ड नियम की तुलना में प्रदर्शन में गिरावट आ सकती है।

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

कार्यप्रणाली (Methodology)
प्रस्तावित दृष्टिकोण, जिसे रोलआउट-कैलिब्रेटेड हाइपर-ह्यूरिस्टिक्स (Rollout-Calibrated Hyper-Heuristics) कहा जाता है, तीन मुख्य घटकों को एकीकृत करता है:

रिग्रेट-नॉर्मलाइज्ड रोलआउट लेबल्स (Regret-Normalized Rollout Labels):
रॉ मेक्सपैन (makespan) या लोअर-बाउंड-नॉर्मलाइज्ड मेक्सपैन का उपयोग करने के बजाय, लेखक एक प्रति-स्टेट रिग्रेट लेबल को परिभाषित करते हैं:
$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$
जहाँ $m(s, h)$ उस मेक्सपैन को दर्शाता है जो स्थिति $s$ पर नियम $h$ को लागू करने से प्राप्त होता है। यह लक्ष्य को एक स्थानीय रैंकिंग सिग्नल में बदल देता है जहाँ एक विशिष्ट स्थिति में सबसे अच्छा नियम 0 का रिग्रेट रखता है, जो उस विशिष्ट संदर्भ के भीतर नियमों के सापेक्ष प्रदर्शन को अलग करता है।
अनसर्टेन्टी-गेटेड सिलेक्शन (Uncertainty-Gated Selection):
सिस्टम प्रत्येक कैंडिडेट नियम के रिग्रेट की भविष्यवाणी करने के लिए एक कॉन्टेक्स्टुअल K-नेरेस्ट नेबर्स (KNN) रिग्रेसर का उपयोग करता है। विश्वसनीयता सुनिश्चित करने के लिए, एक गेटिंग मैकेनिज्म पेश किया गया है। सेलेक्टर एक फिक्स्ड डिफॉल्ट नियम ( $h_0$ , जिसे ट्रेनिंग सेट पर सबसे अच्छे फिक्स्ड नियम के रूप में चुना गया है) से अनुमानित सर्वश्रेष्ठ नियम ( $h^*$ ) पर केवल तभी स्विच करेगा यदि अपेक्षित सुधार एक अनसर्टेन्टी-एडजस्टेड मार्जिन से अधिक हो:
$\pi_{gated}(s) = \begin{cases} h^* & \text{यदि } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{अन्यथा} \end{cases}$
यहाँ, $\hat{\sigma}$ K-नेरेस्ट नेबर्स का स्टैंडर्ड डेविएशन है (जो अनसर्टेन्टी एस्टीमेट के रूप में कार्य करता है), और $\lambda$ एक हाइपरपैरामीटर है जो स्विच करने की आक्रामकता को नियंत्रित करता है।
रोलआउट बजट ट्रेड-ऑफ (Rollout Budget Trade-off):
लेखक स्पष्ट रूप से रोलआउट ब्रैडथ ( $b$ , मूल्यांकित कैंडिडेट नियमों की संख्या) और रोलआउट डेप्थ ( $\kappa$ , वह संख्या जहाँ तक एक कैंडिडेट नियम को डिफॉल्ट पर वापस जाने से पहले फॉलो किया जाता है) को बदलते हैं ताकि लेबल जनरेशन लागत (सिमुलेशन स्टेप्स/वॉल-क्लॉक टाइम) और अंतिम टेस्ट परफॉरमेंस (रिलेटिव परसेंटेज डेविएशन, RPD) के बीच पेरेटो फ्रंटियर (Pareto frontier) को मैप किया जा सके।

मुख्य योगदान

एक कंजर्वेटिव सिलेक्शन फ्रेमवर्क: पेपर एक गेटिंग मैकेनिज्म का प्रस्ताव करता है जो आक्रामक अनुकूलन के बजाय विश्वसनीयता को प्राथमिकता देता है, यह सुनिश्चित करता है कि सीखा हुआ सेलेक्टर उच्च विश्वास के बिना मजबूत फिक्स्ड रूल्स को न छोड़े।
रिग्रेट-आधारित सुपरविजन: पूर्ण मेक्सपैन के बजाय प्रति-स्टेट रिग्रेट का उपयोग करके, विधि स्थानीय नियम रैंकिंग पर ध्यान केंद्रित करती है, जो आंशिक शेड्यूल में निर्णय लेने के लिए अधिक मजबूत है।
स्पष्ट लागत-गुणवत्ता विश्लेषण: कई कार्य जो लेबल जनरेशन को एक फिक्स्ड प्रीप्रोसेसिंग स्टेप के रूप में मानते हैं, इस अध्ययन में रोलआउट डेप्थ और ब्रैडथ को व्यवस्थित रूप से बदलकर लागत-गुणवत्ता ट्रेड-ऑफ को मात्रात्मक रूप से मापा गया है, जो तैनाती बजट के लिए व्यावहारिक मार्गदर्शन प्रदान करता है।
CPU-ओनली रिप्रोड्यूसिबिलिटी: पूरी पाइपलाइन, जिसमें लेबल जनरेशन, KNN फिटिंग और इन्फरेंस शामिल है, को बिना GPU एक्सेलरेशन के केवल CPU पर चलाने के लिए डिज़ाइन किया गया है।

प्रायोगिक परिणाम
प्रयोग $6\times6$ , $10\times10$ , और $15\times10$ आकार के सिंथेटिक JSSP इंस्टेंस पर किए गए।

परफॉरमेंस: रिग्रेट-गेटेड सेलेक्टर ने सभी स्केल्स पर सभी सीखे गए तरीकों में सबसे कम औसत RPD प्राप्त किया। यह सबसे अच्छे फिक्स्ड डिस्पैचिंग नियम (आमतौर पर इन सिंथेटिक सेटिंग्स में FIFO या MOPNR) के बहुत करीब रहा, जिसमें औसत RPD गैप क्रमशः 0.70, 0.67, और 0.06 था।
मजबूती (Robustness): गेटेड अप्रोच ने एक रैंडम-HH बेसलाइन के औसत RPD को एक क्रम से भी अधिक कम कर दिया (लगभग 36–54% से घटकर ~0.8–2.8% हो गया)।
एब्लेशन (Ablation): अध्ययन ने पुष्टि की कि गेटिंग हमेशा स्विच करने (argmin selection) की तुलना में अधिक स्थिर है। सबसे अच्छे परिणाम रिग्रेट लेबल्स और कॉन्फिडेंस थ्रेशोल्ड $\lambda=1.0$ के साथ प्राप्त हुए। LCB वेरिएंट्स ने खराब प्रदर्शन किया, जिससे पता चलता है कि अनसर्टेन्टी का उपयोग सीधे स्कोर बोनस के बजाय स्विचिंग टेस्ट के रूप में करना बेहतर है।
लागत विश्लेषण: फुल रोलआउट्स ( $\kappa=\infty, b=|H|$ ) ने उच्चतम गुणवत्ता लेकिन उच्चतम लागत प्रदान की। शैलो रोलआउट्स ( $\kappa=1$ ) के परिणामस्वरूप काफी अधिक RPD हुआ। इंटरमीडिएट डेप्थ्स एक व्यवहार्य ट्रेड-ऑफ प्रदान करते हैं, जो स्वीकार्य गुणवत्ता बनाए रखते हुए सिमुलेशन स्टेप्स को काफी कम कर देते हैं।

महत्व और दावे
पेपर विनम्रतापूर्वक एक रिप्रोड्यूसेबल, CPU-ओनली सेलेक्टर और इवैल्यूएशन प्रोटोकॉल प्रदान करने का दावा करता है, जिसका उपयोग लर्निंग-असिस्टेड हाइपर-ह्यूरिस्टिक्स में लेबल लागत और कंजर्वेटिव स्विचिंग का अध्ययन करने के लिए किया जा सकता है।

लेखक अपने कार्य को स्पेशलाइज्ड सॉल्वर्स, डीप-RL डिस्पैचर्स (जैसे L2D, ScheduleNet), और LLM-ड्रिवन प्रोग्राम सर्च (जैसे FunSearch, ReEvo) के पूरक के रूप में प्रस्तुत करते हैं। जबकि वे सिस्टम अलग-अलग डिजाइन स्पेस (अक्सर नए ऑपरेटर्स या एंड-टू-एंड पॉलिसी का आविष्कार करना) को लक्षित करते हैं, यह कार्य मौजूदा, व्याख्या योग्य नियमों के बीच चयन करने की समस्या को अलग करता है।

प्राथमिक महत्व व्यावहारिक परिनियोजन (deployment) चुनौती को संबोधित करने में निहित है: लेबल उत्पन्न करने के लिए कितना सिमुलेशन बजट खर्च किया जाना चाहिए, और यह कैसे सुनिश्चित किया जाए कि एक सीखा हुआ सेलेक्टर बहुत बार स्विच करके प्रदर्शन को कम न कर दे। लेखक नोट करते हैं कि उनके निष्कर्ष परीक्षण किए गए सिंथेटिक, स्टैटिक और डिटर्मिनिस्टिक रिजीम के लिए विशिष्ट हैं। वे स्वीकार करते हैं कि औद्योगिक इंस्टेंस या डायनेमिक वातावरण (जैसे मशीन ब्रेकडाउन, ऑनलाइन आगमन) तक स्केल करने के लिए अलग-अलग लागत-गुणवत्ता ट्रेड-ऑफ और संभावित रूप से अलग लेबल जनरेशन डायनेमिक्स की आवश्यकता होगी। यह कार्य JSS को सामान्य रूप से हल करने का दावा नहीं करता है बल्कि लर्निंग-असिस्टेड हाइपर-ह्यूरिस्टिक्स को विश्वसनीय और लागत प्रभावी बनाने पर एक नियंत्रित अध्ययन प्रदान करता है।