जॉब-शॉप शेड्यूलिंग (GA)

जॉब-शॉप शेड्यूलिंग क्या है? GA कैसे हल करता है?

जॉब-शॉप शेड्यूलिंग कई कार्यों के संचालन को मशीनों पर असाइन करता है ताकि मेकस्पैन या देरी न्यूनतम हो। प्रत्येक कार्य में विभिन्न मशीनों पर क्रमबद्ध संचालन होते हैं।

JSSP NP-कठिन है। GA उम्मीदवार शेड्यूल की आबादी विकसित करता है। POX क्रॉसओवर कार्य क्रम बनाए रखता है; स्वैप म्यूटेशन स्थिति बदलता है।

JSSP मशीनिंग, सेमीकंडक्टर, प्रिंटिंग में महत्वपूर्ण है। 10-15% मेकस्पैन कमी सीधे थ्रूपुट बढ़ाती है।

Formula: मेकस्पैन = max(सभी संचालन के पूर्ण होने का समय) देरी = Σ max(0, पूर्ण_j − नियत_j) GA: आरंभ → मूल्यांकन → चयन → POX → म्यूटेशन → पुनरावृत्ति

गणना उदाहरण

3 कार्य, 3 मशीनें। कार्य 1: M1(3)→M2(2)→M3(4)। इष्टतम मेकस्पैन = 12। GA (आबादी 100, 200 पीढ़ियाँ) सामान्यतः यह या 5% के भीतर खोजता है।

इस कैलकुलेटर का उपयोग कब करें

• एक प्रोडक्शन प्लानर पूर्णता समय न्यूनतम करने के लिए साझा उपकरणों वाली मशीन शॉप में कई जॉब शेड्यूल कर रहा है
• एक मैन्युफैक्चरिंग इंजीनियर समग्र थ्रूपुट पर नई मशीन जोड़ने या ऑपरेशन अनुक्रम बदलने के प्रभाव का मूल्यांकन कर रहा है
• एक प्रिंट शॉप या सेमीकंडक्टर फैब में शेड्यूलर न्यूनतम विलंब के साथ ग्राहक नियत तिथियों को पूरा करने के लिए जॉब प्राथमिकताएं निर्धारित कर रहा है
• एक ऑपरेशंस रिसर्चर वर्तमान मैनुअल या प्रायोरिटी-रूल शेड्यूलिंग विधियों के विरुद्ध GA-आधारित शेड्यूलिंग का बेंचमार्किंग कर रहा है

बचने योग्य सामान्य गलतियाँ

• जटिल समस्याओं के लिए पॉपुलेशन साइज़ बहुत छोटा सेट करना — 10+ जॉब और 5+ मशीनों के साथ, आनुवंशिक विविधता बनाए रखने और समयपूर्व अभिसरण से बचने के लिए कम से कम 100-200 व्यक्तियों का उपयोग करें
• बहुत कम पीढ़ियां चलाना और उप-इष्टतम समाधान स्वीकार करना — निगरानी करें कि क्या फिटनेस अभी भी सुधर रही है; यदि यह स्थिर हो जाती है, तो समाधान अभिसरित हो गया है; यदि अभी भी सुधर रही है, तो पीढ़ियां बढ़ाएं
• जब वे मौजूद हों तब रिलीज़ टाइम और नियत तिथियों को अनदेखा करना — इन प्रतिबंधों के बिना, GA केवल makespan का अनुकूलन करता है, जो वास्तविक-विश्व समय आवश्यकताओं का उल्लंघन करने वाले शेड्यूल उत्पन्न कर सकता है
• विभिन्न रैंडम सीड के साथ GA कई बार न चलाना — GA स्टोकेस्टिक है; एक ही रन स्थानीय इष्टतम में फंस सकता है; 3-5 बार चलाएं और सर्वश्रेष्ठ परिणाम लें

परिणामों की व्याख्या कैसे करें

• यदि कुल विलंब शून्य है, तो सभी जॉब अपनी नियत तिथियों से पहले पूरे हो जाते हैं — शेड्यूल व्यवहार्य है और ध्यान makespan को और कम करने पर स्थानांतरित होना चाहिए
• यदि makespan बॉटलनेक मशीन पर प्रोसेसिंग समय के योग के करीब है, तो शेड्यूल लगभग-इष्टतम है — सुधार की बहुत कम गुंजाइश बची है
• गैंट चार्ट मशीनों पर निष्क्रिय समय प्रकट करता है: बड़े अंतराल शेड्यूलिंग अक्षमता या अपरिहार्य अनुक्रमण प्रतिबंधों को इंगित करते हैं

संबंधित मानक और संदर्भ

• Garey, Johnson & Sethi (1976) — जॉब-शॉप makespan न्यूनीकरण की NP-कठिनता स्थापित की
• Makespan (C_max) और कुल विलंबता — उत्पादन शेड्यूलिंग में मानक उद्देश्य फलन
• आनुवंशिक एल्गोरिथम (Holland, 1975) — शेड्यूल स्थान की खोज के लिए यहाँ लागू की गई मेटाह्यूरिस्टिक श्रेणी

अक्सर पूछे जाने वाले प्रश्न

GA पैरामीटर कैसे सेट करें?

आबादी 50-200, म्यूटेशन दर 0.05-0.15, 200-500 पीढ़ियाँ। 10+ कार्यों के लिए आबादी ≥100, पीढ़ियाँ ≥300।

मेकस्पैन और देरी अनुकूलन में क्या अंतर है?

मेकस्पैन न्यूनीकरण सभी कार्यों को जल्दी पूरा करने पर केंद्रित — थ्रूपुट के लिए आदर्श। देरी न्यूनीकरण नियत तिथि पूर्ति को प्राथमिकता देता है। बहु-उद्देश्य अनुकूलन दोनों को संतुलित कर सकता है।