Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

तकनीकी सारांश: क्वांटम एनीलिंग के साथ ऊनी वस्त्र उद्योग में वितरित लचीली जॉब शॉप शेड्यूलिंग समस्याओं को हल करना

समस्या की परिभाषा
यह शोध पत्र ऊनी वस्त्र उद्योग के संदर्भ में डिस्ट्रिब्यूटेड फ्लेक्सिबल जॉब शॉप शेड्यूलिंग प्रॉब्लम (DFJSP) को संबोधित करता है। पारंपरिक जॉब शॉप शेड्यूलिंग (JSSP) या यहाँ तक कि मानक फ्लेक्सिबल जॉब शॉप शेड्यूलिंग (FJSP) के विपरीत, DFJSP भौगोलिक रूप से बिखरे हुए उत्पादन स्थलों से संबंधित है जहाँ एक एकल उत्पादन आदेश (जॉब) के लिए विभिन्न कारखानों में ऑपरेशन्स (कार्यों) को करने की आवश्यकता हो सकती है। यह विशिष्ट उपयोग मामला, जो एक वास्तविक दुनिया के ऊनी वस्त्र निर्माता से लिया गया है, एक अनूठी जटिलता पेश करता है: न केवल उत्पादन आदेश विभिन्न स्थलों पर वितरित हैं, बल्कि एक ही जॉब के व्यक्तिगत उत्पादन चरण (ऑपरेशन्स) भी वितरित हो सकते हैं। फलस्वरूप, मॉडल को मानक प्रोसेसिंग समय और मशीन बाधाओं के साथ-साथ विभिन्न कारखानों में स्थित मशीनों के बीच शिपिंग समय को भी ध्यान में रखना चाहिए। इसका उद्देश्य पूर्ववर्ती बाधाओं (precedence constraints) को संतुष्ट करते हुए, यह सुनिश्चित करते हुए कि ऑपरेशन्स केवल एक बार शुरू हों और मशीनों का ओवरलैप न हो, मेक्सपैन (कुल पूर्णता समय) को कम करना है। इस समस्या को NP-hard के रूप में पहचाना गया है, और अंतर-कारखाना शिपिंग समय का समावेश इसकी कॉम्बिनेटोरियल जटिलता को काफी बढ़ा देता है।

कार्यप्रणाली
लेखक विस्तारित DFJSP को एक क्वाड्रेटिक अनकन्स्ट्रेंड बाइनरी ऑप्टिमाइजेशन (QUBO) समस्या के रूप में तैयार करते हैं जिसे D-Wave Advantage System 4.1 क्वांटम एनीलर (QPU) का उपयोग करके हल किया जाना है।

1. QUBO फॉर्मूलेशन: समस्या को बाइनरी वेरिएबल्स $x_{i,o,m,t}$ में मैप किया गया है, जो यह दर्शाता है कि जॉब $i$ का ऑपरेशन $o$, मशीन $m$ पर समय $t$ पर शुरू होता है या नहीं। कॉस्ट फंक्शन $H(x)$ को बाधाओं (पूर्ववर्ती, ऑपरेशन-एक-बार, नो-ओवरलैप) के लिए पेनल्टी फंक्शन्स और मेक्सपैन को कम करने के लिए एक ऑब्जेक्टिव फंक्शन के भारित योग (weighted sum) के रूप में बनाया गया है।
2. वेरिएबल प्रूनिंग (Variable Pruning): QPU की भौतिक सीमाओं के भीतर समस्या के आकार को प्रबंधित करने के लिए, लेखक वेरिएबल प्रूनिंग का उपयोग करते हैं। इसमें न्यूनतम पूर्ववर्ती समय और अधिकतम मेक्सपैन सीमाओं के आधार पर ऑपरेशन स्टार्ट टाइम के निचले और ऊपरी स्तरों की गणना करना शामिल है, जिससे उन बाइनरी वेरिएबल्स को हटाया जा सके जो अमान्य शेड्यूल से संबंधित हैं।
3. पैरामीटर निर्धारण: एक महत्वपूर्ण पद्धतिगत चरण में पेनल्टी टर्म्स के लिए लैग्रेंज पैरामीटर्स ($\alpha, \beta, \gamma$) की व्यवस्थित गणना शामिल है। अनुमान-आधारित परीक्षण (trial-and-error) पर निर्भर रहने के बजाय, लेखक विशिष्ट समस्या उदाहरण के अधिकतम संभावित मेक्सपैन ($t_{max}$) के आधार पर इन वेट्स को गणितीय रूप से व्युत्पन्न करते हैं। यह सुनिश्चित करता है कि किसी भी वैध समाधान की ऊर्जा किसी भी अमान्य समाधान की ऊर्जा से कम हो।
4. एम्बेडिंग और कॉन्फ़िगरेशन: लॉजिकल QUBO वेरिएबल्स को क्वबिट्स की चेन्स (chains) का उपयोग करके भौतिक QPU टोपोलॉजी पर एम्बेड किया जाता है। लेखक समाधान की गुणवत्ता पर "चेन स्ट्रेंथ" (चेन में क्वबिट्स के बीच कपलिंग स्ट्रेंथ) के प्रभाव की जांच करते हैं, और सिस्टम ऊर्जा तथा टूटी हुई चेन्स के प्रतिशत के बीच ट्रेड-ऑफ का विश्लेषण करके इष्टतम मान निर्धारित करते हैं।
5. तुलना: क्वांटम एनीलिंग (QA) के परिणामों की तुलना D-Wave Ocean SDK का उपयोग करके सिमुलेटेड एनीलिंग (SA) के विरुद्ध बेंचमार्किंग की गई है। दोनों विधियों का परीक्षण 50 से 250 वेरिएबल्स वाले समस्या उदाहरणों पर किया गया है (परीक्षण किए गए QPU पर अधिकतम एम्बेडेबल आकार), जबकि SA को कंप्यूटेशनल स्केलिंग स्थापित करने के लिए बड़े उदाहरणों (400 वेरिएबल्स तक) पर भी परखा गया है।

प्रमुख योगदान
यह शोध पत्र तीन प्राथमिक योगदान प्रस्तुत करता है:

1. QA के साथ विस्तारित DFJSP मॉडल: लेखक विस्तारित DFJSP के पहले ज्ञात अनुप्रयोग को प्रस्तुत करते हैं जहाँ उत्पादन आदेश और व्यक्तिगत उत्पादन चरण दोनों कारखानों में वितरित हैं, जिसमें अंतर-साइट शिपिंग समय को स्पष्ट रूप से मॉडल किया गया है।
2. व्यवस्थित पैरामीटर गणना: पेपर समस्या के गणितीय फॉर्मूलेशन के आधार पर लैग्रेंज पैरामीटर्स और QPU कॉन्फ़िगरेशन सेटिंग्स (विशेष रूप से चेन स्ट्रेंथ) को निर्धारित करने की विधि का विवरण देता है, जो अनुमान-आधारित 'ट्रायल-एंड-एरर' दृष्टिकोण से दूर ले जाता है।
3. आर्थिक और प्रदर्शन मूल्यांकन: अध्ययन क्वांटम एनीलिंग का उपयोग करने के संभावित गति लाभ का मूल्यांकन करता है, जो समाधान की गुणवत्ता और गणना समय की तुलना शास्त्रीय SA के विरुद्ध करता है।

परिणाम

• समाधान की गुणवत्ता: 150 वेरिएबल्स तक के समस्या उदाहरणों के लिए, QA ने सुसंगत, वैध समाधान (कोई टूटी हुई बाधा नहीं) दिए, हालांकि सिमुलेटेड एनीलिंग (SA) ने आम तौर पर थोड़े कम ऊर्जा (बेहतर अनुकूलता) वाले समाधान वापस किए। जैसे-जैसे समस्या का आकार बढ़कर 200 और 250 वेरिएबल्स हुआ, QA समाधानों में टूटी हुई बाधाएं (क्रमशः 1 और 2 उल्लंघन) दिखने लगीं, जिससे उच्च ऊर्जा मान प्राप्त हुए। इस गिरावट का कारण भौतिक QPU ग्राफ पर बड़े लॉजिकल समस्याओं को एम्बेड करने की बढ़ती कठिनाई है, जिसके परिणामस्वरूप लंबी चेन्स और चेन ब्रेक की उच्च दर होती है।
• मेक्सपैन: अधिकांश समस्या आकारों के लिए QA समाधान संभावित मेक्सपैन रेंज के निचले आधे हिस्से में रहे, जो व्यवहार्य उत्पादन शेड्यूल का संकेत देते हैं। हालांकि, 250-वेरिएबल वाले उदाहरण के लिए, मेक्सपैन रेंज के ऊपरी आधे हिस्से में था।
• कंप्यूटेशनल समय: छोटे समस्या उदाहरणों के लिए SA ने तेज़ गणना समय प्रदर्शित किया। हालांकि, SA का CPU समय समस्या के आकार के साथ तेजी से (exponentially) बढ़ा। इसके विपरीत, QA के लिए QPU एक्सेस टाइम घटती दर (लॉगैरिद्मिक) पर बढ़ा। हालांकि वर्तमान हार्डवेयर सीमाएँ QA को 250 वेरिएबल्स तक की समस्याओं को एम्बेड करने तक सीमित करती हैं, लेकिन रुझान यह सुझाव देता है कि बड़े उदाहरणों के लिए (300 वेरिएबल्स से परे एक्सट्रपलेशन करते हुए), QA संभावित रूप से SA की तुलना में महत्वपूर्ण गति लाभ प्रदान कर सकता है।

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