जेनेटिक एल्गोरिदम शेड्यूलिंग

जेनेटिक एल्गोरिद्म एक आपरेशनल रिसर्च विधि है जिसका उपयोग उत्पादन योजना में निर्धारण (उत्पादन प्रक्रियाएं) की समस्याओं को हल करने के लिए किया जा सकता है।

उत्पादन समयबद्धन का महत्व

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

• कार्यों का एक सेट जिसे निष्पादित किया जाना चाहिए
• संसाधनों का एक परिमित सेट जिसका उपयोग प्रत्येक कार्य को पूरा करने के लिए किया जा सकता है
• बाधाओं का एक सेट जो संतुष्ट होना चाहिए
  • अस्थायी बाधाएँ - कार्य को पूरा करने के लिए समय अवधि
  • प्रक्रियात्मक बाधाएँ - प्रत्येक कार्य को पूरा करने का क्रम
  • संसाधन की कमी - संसाधन उपलब्ध है
• शेड्यूलिंग प्रदर्शन का मूल्यांकन करने के लिए उद्देश्यों का एक सेट

एक विशिष्ट फ़ैक्टरी फ़्लोर सेटिंग इसका एक अच्छा उदाहरण है जहाँ यह शेड्यूल करना आवश्यक है कि किन मशीनों पर किन कर्मचारियों द्वारा किस क्रम में और किस समय पर कौन से काम पूरे किए जाने हैं।

शेड्यूलिंग में एल्गोरिदम का उपयोग

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

चित्र 1. शेड्यूलिंग में वरीयता

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

जैसे-जैसे हम उन उद्देश्यों की संख्या बढ़ाते हैं जिन्हें हम प्राप्त करने का प्रयास कर रहे हैं हम समस्या पर बाधाओं की संख्या भी बढ़ाते हैं और इसी तरह जटिलता भी बढ़ाते हैं। इस प्रकार की समस्याओं के लिए जेनेटिक एल्गोरिद्म आदर्श होते हैं जहां खोज स्थान बड़ा होता है और व्यवहार्य समाधानों की संख्या कम होती है।

एक आनुवंशिक एल्गोरिथम का अनुप्रयोग

अंजीर. 2 ए उदाहरण अनुसूची जीनोम

शेड्यूलिंग समस्या के लिए आनुवंशिक एल्गोरिथम प्रयुक्त करने के लिए हमें पहले इसे जीनोम के रूप में प्रस्तुत करना होगा। शेड्यूलिंग जीनोम का प्रतिनिधित्व करने का एक विधि कार्यों के अनुक्रम और उन कार्यों के प्रारंभ समय को एक दूसरे के सापेक्ष परिभाषित करना है। प्रत्येक कार्य और उसके अनुरूप प्रारंभ समय एक जीन का प्रतिनिधित्व करता है।

कार्यों का एक विशिष्ट क्रम और प्रारंभ समय (जीन) हमारी आबादी में एक जीनोम का प्रतिनिधित्व करता है। यह सुनिश्चित करने के लिए कि हमारा जीनोम एक कैंडिडेट समाधान है हमें ध्यान रखना चाहिए कि यह हमारी पूर्ववर्ती बाधाओं का पालन करता है। हम पूर्ववर्ती बाधाओं के अंदर यादृच्छिक प्रारंभ समय का उपयोग करके प्रारंभिक जनसंख्या उत्पन्न करते हैं। आनुवंशिक एल्गोरिदम के साथ हम इस प्रारंभिक आबादी को लेते हैं और इसे पार करते हैं जीनोम को यादृच्छिकता (उत्परिवर्तन) की एक छोटी मात्रा के साथ जोड़ते हैं। इस संयोजन की संतति का चयन एक फिटनेस कार्य के आधार पर किया जाता है जिसमें हमारी एक या कई बाधाएं सम्मिलित होती हैं जैसे समय को कम करना और दोषों को कम करना हम इस प्रक्रिया को या तो पूर्व-आवंटित समय के लिए जारी रखते हैं या जब तक हमें कोई ऐसा समाधान नहीं मिल जाता है जो हमारे न्यूनतम मानदंडों के अनुकूल हो कुल मिलाकर प्रत्येक अगली पीढ़ी की औसत फिटनेस अधिक होगी अर्थात पिछली पीढ़ियों की तुलना में उच्च गुणवत्ता के साथ कम समय लेना शेड्यूलिंग समस्याओं में जैसा कि अन्य जेनेटिक एल्गोरिथम समाधानों के साथ होता है हमें यह सुनिश्चित करना चाहिए कि हम ऐसी संतानों का चयन न करें जो अव्यवहार्य हों जैसे कि ऐसी संतानें जो हमारी पूर्ववर्ती बाधा का उल्लंघन करती हैं। निश्चित रूप से हमें अतिरिक्त फिटनेस मूल्यों को जोड़ना पड़ सकता है जैसे लागत को कम करना; चूँकि जोड़ा गया प्रत्येक अवरोध खोज स्थान को बहुत बढ़ा देता है और अच्छे मिलान वाले समाधानों की संख्या कम कर देता है।

यह भी देखें

• अर्थशास्त्र में आनुवंशिक एल्गोरिथम
• जॉब शॉप शेड्यूलिंग
• गुणवत्ता नियंत्रण और आनुवंशिक एल्गोरिदम

ग्रन्थसूची

• Wall, M., A Genetic Algorithm for Resource-Constrained Scheduling (PDF)
• Lim, C.; Sim, E., Production Planning in Manufacturing/Remanufacturing Environment using Genetic Algorithm (PDF)

बाहरी संबंध

• Demo applet of a genetic algorithm solving TSPs and VRPTW problems