A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

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

समस्या की परिभाषा
यह शोध पत्र फ्लेक्सिबल जॉब शॉप शेड्यूलिंग प्रॉब्लम (FJSP) को संबोधित करता है, जो आधुनिक विनिर्माण में प्रचलित एक अत्यंत कठिन (strongly NP-hard) अनुकूलन चुनौती है। क्लासिकल जॉब शॉप शेड्यूलिंग प्रॉब्लम (JSP) के विपरीत, जहाँ ऑपरेशन्स के लिए मशीन असाइनमेंट निश्चित होते हैं, FJSP प्रत्येक ऑपरेशन को वैकल्पिक उम्मीदवारों के एक सेट में से किसी भी मशीन पर संसाधित करने की अनुमति देता है, जिनके प्रसंस्करण समय (processing times) भिन्न हो सकते हैं। प्राथमिक उद्देश्य मेक्सपैन ($C_{max}$) को कम करना है, जिसे सभी जॉब्स के अधिकतम पूर्णता समय के रूप में परिभाषित किया गया है। इस समस्या में प्रीसीडेंस बाधाओं (precedence constraints) और मशीन उपलब्धता को संतुष्ट करते हुए, प्रत्येक ऑपरेशन के लिए मशीन चयन और प्रत्येक मशीन पर ऑपरेशन्स के प्रसंस्करण क्रम दोनों को निर्धारित करना शामिल है।

कार्यप्रणाली: HGVNSA
लेखक एक हाइब्रिड जेनेटिक वेरिएबल नेबरहुड सर्च एल्गोरिदम (HGVNSA) का प्रस्ताव करते हैं जो वैश्विक अन्वेषण (global exploration) के लिए जेनेटिक एल्गोरिदम (GA) को क्रिटिकल-पाथ-ड्रिवन वेरिएबल नेबरहुड सर्च (VNS) के साथ एकीकृत करता है।

1. एन्कोडिंग और डिकोडिंग: समाधान को दो-स्तरीय एन्कोडिंग का उपयोग करके दर्शाया गया है: एक ऑपरेशन सीक्वेंस (OS) वेक्टर और एक मशीन सिलेक्शन (MS) वेक्टर। व्यवहार्य शेड्यूल्स उत्पन्न करने के लिए एक एक्टिव डिकोडिंग रणनीति का उपयोग किया जाता है।
2. जनसंख्या इनिशियलाइज़ेशन: गुणवत्ता और विविधता को संतुलित करने के लिए, प्रारंभिक जनसंख्या को एक हाइब्रिड रणनीति का उपयोग करके उत्पन्न किया जाता है: ग्लोबल सिलेक्शन (60%, ग्लोबल लोड इंक्रीमेंट को न्यूनतम करना), लोकल सिलेक्शन (30%, जॉब्स के भीतर लोड को संतुलित करना), और रैंडम सिलेक्शन (10%)।
3. जेनेटिक ऑपरेशन्स:
   • क्रॉसओवर: एक पाथ-रिलंकिंगिंग (PR) आधारित क्रॉसओवर ऑपरेटर पेश किया गया है। रैंडम जीन स्वैपिंग के बजाय, यह व्यवस्थित रूप से एक पैरेंट सॉल्यूशन को दूसरे में परिवर्तित करता है, जिससे पैरेंट्स के बीच के सर्च स्पेस का लाभ उठाने के लिए मध्यवर्ती समाधानों को रिकॉर्ड और मूल्यांकित किया जाता है।
   • म्यूटेशन: एक एडेप्टिव म्यूटेशन मैकेनिज्म व्यक्तिगत फिटनेस और जनरेशन काउंट के आधार पर संभावनाओं को समायोजित करता है। दो प्रकार के म्यूटेशन का उपयोग किया जाता है: OS म्यूटेशन (ऑपरेशन ऑर्डर को बदलना) और MS म्यूटेशन (मशीन असाइनमेंट बदलना)।
   • विविधता संरक्षण: जनसंख्या की विविधता बनाए रखने और समयपूर्व अभिसरण (premature convergence) को रोकने के लिए हैमिंग डिस्टेंस-आधारित रणनीति का उपयोग किया जाता है।
4. क्रिटिकल-पाथ-ड्रिवन डुअल-नेबरहुड VNS: GA फ्रेमवर्क के भीतर अंतर्निहित, यह लोकल सर्च क्रिटिकल पाथ (डिस्जंक्टिव ग्राफ में सबसे लंबा रास्ता) पर स्थित ऑपरेशन्स पर ध्यान केंद्रित करता है। यह दो पूरक नेबरहुड संरचनाओं का उपयोग करता है:
   • N8 नेबरहुड: एक ही मशीन पर ऑपरेशन्स के क्रम को अनुकूलित करता है। यह पारंपरिक N5-N7 मूव्स का विस्तार करता है, जिससे क्रिटिकल ब्लॉक्स के बाहर के क्रिटिकल ऑपरेशन्स को ब्लॉक एंडपॉइंट्स या प्री/पोस्ट-ब्लॉक स्थितियों में ले जाने की अनुमति मिलती है।
   • k-इंसर्शन नेबरहुड: क्रिटिकल ऑपरेशन्स को अलग-अलग मशीनों पर पुनर्वितरित करता है। इसमें वैकल्पिक मशीनों का भ्रमण करना और साइक्लिक डिपेंडेंसी की जाँच करते हुए, व्यवहार्य स्थितियों में ऑपरेशन को सम्मिलित करना शामिल है।
   • सर्च स्ट्रैटेजी: VNS प्रक्रिया N8 नेबरहुड (कम कम्प्यूटेशनल लागत) को प्राथमिकता देती है और यदि कोई सुधार नहीं मिलता है तो k-इंसर्शन (उच्च लागत, व्यापक खोज) पर स्विच करती है, जो दक्षता और अन्वेषण गहराई के बीच संतुलन सुनिश्चित करती है।

प्रमुख योगदान
शोध पत्र पाँच मुख्य योगदानों को रेखांकित करता है:

1. हाइब्रिड फ्रेमवर्क: यह एक सहक्रियात्मक "पहले वैश्विक अन्वेषण, उसके बाद स्थानीय शोषण" फ्रेमवर्क स्थापित करता है, जो समाधान की सटीकता और कम्प्यूटेशनल दक्षता को प्रभावी ढंग से संतुलित करता है।
2. डुअल-नेबरहुड इंटीग्रेशन: यह FJSP के लिए एक एकीकृत VNS फ्रेमवर्क के भीतर N8 और k-insertion नेबरहुड्स को एकीकृत करने वाला पहला है। यह संयोजन इंट्रा-मशीन सीक्वेंसिंग और इंटर-मशीन रीलोकेशन दोनों को संबोधित करता है, जिससे स्थानीय खोज क्षमता में महत्वपूर्ण वृद्धि होती है।
3. उन्नत जेनेटिक ऑपरेटर्स: पाथ-रिलंकिंग क्रॉसओवर और एडेप्टिव म्यूटेशन संभावनाओं का परिचय समाधान स्थान का अन्वेषण करने और अभिसरण स्थिरता बनाए रखने की एल्गोरिदम की क्षमता को मजबूत करता है।
4. बेंचमार्क प्रदर्शन: ब्रैंडिमार्टे MK बेंचमार्क सेट पर, HGVNSA लगातार 10 में से 6 इंस्टेंस (MK01-MK04, MK08-MK09) में ज्ञात इष्टतम समाधानों तक पहुँचता है और तुलना किए गए एल्गोरिदम (HGWO, HLO-PSO, HA, SLGA, ISLGA) के बीच सबसे कम औसत रिलेटिव परसेंटेज डेविएशन (RPD) 0.06% प्राप्त करता है।
5. वास्तविक दुनिया का अनुप्रयोग: एल्गोरिदम का उपयोग कंपनी A में गियर शाफ्ट प्रोसेसिंग परिदृश्य के लिए किया गया था। पारंपरिक जेनेटिक एल्गोरिदम की तुलना में, HGVNSA ने उत्पादन दक्षता में 8.81% सुधार किया, जो इसकी इंजीनियरिंग व्यावहारिकता को प्रदर्शित करता है।

परिणाम और सत्यापन

• बेंचमार्क टेस्टिंग: MK01-MK10 इंस्टेंस पर व्यापक प्रयोगों ने दिखाया कि HGVNSA ने समाधान की गुणवत्ता और स्थिरता के मामले में तुलनात्मक एल्गोरिदम को पछाड़ दिया। एब्लेशन अध्ययन ने पुष्टि की कि VNS घटक, डुअल-नेबरहुड संरचना, या एडेप्टिव मैकेनिज्म को हटाने से प्रदर्शन में महत्वपूर्ण गिरावट आई (उदाहरण के लिए, VNS को हटाने से MK02 पर औसत मेक्सपैन 26 से बढ़कर 30.4 हो गया)।
• केस स्टडी: 15 मशीनों पर 10 जॉब्स और 59 ऑपरेशन्स वाले कंपनी A के केस स्टडी में, एल्गोरिदम ने मेक्सपैन को पारंपरिक GA के 522 से घटाकर 476 कर दिया।
• अभिसरण (Convergence): अभिसरण विश्लेषण ने संकेत दिया कि जबकि अन्य एल्गोरिदम प्रारंभिक तीव्र अभिसरण के बाद स्थिर हो गए, HGVNSA ने अपने स्थानीय खोज तंत्रों के माध्यम से समाधानों को परिष्कृत करना जारी रखा, जिससे बाद के इटरेशन्स में लोकल ऑप्टिमा को तोड़ना संभव हुआ।

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