एकल-मशीन शेड्यूलिंग

एकल-मशीन शेड्यूलिंग या एकल-संसाधन शेड्यूलिंग कंप्यूटर विज्ञान और संचालन अनुसंधान में एक अनुकूलन समस्या है। हमें एन नौकरियां जे दी गई हैं₁, जे₂, ..., जे_nअलग-अलग प्रसंस्करण समय, जिसे एक ही मशीन पर इस तरह से शेड्यूल करने की आवश्यकता होती है, जो एक निश्चित उद्देश्य, जैसे THROUGHPUT, को अनुकूलित करता है।

एकल-मशीन शेड्यूलिंग समान-मशीन शेड्यूलिंग का एक विशेष मामला है, जो स्वयं इष्टतम कार्य शेड्यूलिंग का एक विशेष मामला है। कई समस्याएं, जो सामान्य रूप से एनपी-हार्ड हैं, एकल-मशीन मामले में बहुपद समय में हल की जा सकती हैं।

मानक ऑप्टिमल जॉब शेड्यूलिंग|इष्टतम जॉब शेड्यूलिंग समस्याओं के लिए तीन-फ़ील्ड नोटेशन में, एकल-मशीन संस्करण को पहले फ़ील्ड में 1 द्वारा दर्शाया जाता है। उदाहरण के लिए, 1||$\sum C_{j}$बिना किसी बाधा के एक एकल-मशीन शेड्यूलिंग समस्या है, जहां लक्ष्य पूरा होने के समय के योग को कम करना है।

मेकस्पैन-न्यूनतमीकरण समस्या 1||$C_{\max }$, जो कई मशीनों के लिए एक सामान्य उद्देश्य है, एक मशीन के लिए तुच्छ है, क्योंकि मेकस्पैन हमेशा समान होता है। इसलिए, अन्य उद्देश्यों का अध्ययन किया गया है।

समापन समय का योग न्यूनतम करना

समस्या 1||$\sum C_{j}$ इसका लक्ष्य समापन समय के योग को न्यूनतम करना है। इसे सबसे कम प्रसंस्करण समय पहले नियम (एसपीटी) द्वारा इष्टतम ढंग से हल किया जा सकता है: नौकरियों को उनके प्रसंस्करण समय के आरोही क्रम से निर्धारित किया जाता है $p_{j}$.

समस्या 1||$\sum w_{j}C_{j}$ इसका लक्ष्य समापन समय के भारित योग को कम करना है। इसे भारित लघुतम प्रसंस्करण समय प्रथम नियम ('डब्ल्यूएसपीटी') द्वारा इष्टतम ढंग से हल किया जा सकता है: नौकरियां अनुपात के आरोही क्रम द्वारा निर्धारित की जाती हैं $p_{j}/w_{j}$.

समस्या 1|जंजीरें|$\sum w_{j}C_{j}$ श्रृंखलाओं के रूप में निर्भरता वाली नौकरियों के लिए उपरोक्त समस्या का एक सामान्यीकरण है। इसे डब्ल्यूएसपीटी के उपयुक्त सामान्यीकरण द्वारा भी इष्टतम ढंग से हल किया जा सकता है।

विलंबता की लागत को न्यूनतम करना

समस्या 1||$L_{\max }$ इसका लक्ष्य अधिकतम विलंबता को न्यूनतम करना है। प्रत्येक कार्य के लिए एक नियत तिथि होती है $d_{j}$. यदि इसे नियत तिथि के बाद पूरा किया जाता है, तो इसे विलंब (शेड्यूलिंग) के रूप में परिभाषित किया जाता है $L_{j}:=C_{j}-d_{j}$. 1||$L_{\max }$ प्रारंभिक नियत तिथि प्रथम नियम (ईडीडी) द्वारा सर्वोत्तम तरीके से हल किया जा सकता है: नौकरियां उनकी समय सीमा के आरोही क्रम से निर्धारित की जाती हैं $d_{j}$.

समस्या 1|prec|$h_{\max }$ 1 को सामान्यीकृत करता है||$L_{\max }$ दो तरीकों से: पहला, यह नौकरियों पर मनमाने ढंग से पूर्ववर्ती बाधाओं की अनुमति देता है; दूसरा, यह प्रत्येक कार्य को एक मनमाना लागत फ़ंक्शन h रखने की अनुमति देता है_j, जो इसके पूरा होने के समय का एक फ़ंक्शन है (विलंबता लागत फ़ंक्शन का एक विशेष मामला है)। अधिकतम लागत को एक लालची एल्गोरिदम द्वारा कम किया जा सकता है जिसे लॉलर के एल्गोरिदम के रूप में जाना जाता है।लॉलर का एल्गोरिदम|

समस्या 1|$r_{j}$|$L_{\max }$ सामान्यीकरण 1||$L_{\max }$ प्रत्येक कार्य को अलग-अलग रिलीज़ समय की अनुमति देकर वह प्रसंस्करण के लिए उपलब्ध हो जाता है। रिलीज़ समय की उपस्थिति का मतलब है कि, कुछ मामलों में, किसी महत्वपूर्ण कार्य की प्रतीक्षा करने के लिए, जो अभी तक रिलीज़ नहीं हुआ है, मशीन को निष्क्रिय छोड़ना इष्टतम हो सकता है। इस सेटिंग में अधिकतम विलंबता को न्यूनतम करना एनपी-हार्ड है। लेकिन व्यवहार में, इसे शाखा और बंधन एल्गोरिदम का उपयोग करके हल किया जा सकता है।

कमाई का अधिकतम लाभ

समय सीमा वाली सेटिंग में, यह संभव है कि, यदि कार्य समय सीमा तक पूरा हो जाता है, तो लाभ हो_j. अन्यथा, कोई लाभ नहीं है. लक्ष्य अधिकतम लाभ कमाना है। समय सीमा के साथ एकल-मशीन शेड्यूलिंग एनपी-हार्ड है; साहनी सटीक घातांक-समय एल्गोरिदम और बहुपद-समय सन्निकटन एल्गोरिदम दोनों प्रस्तुत करता है।

थ्रूपुट को अधिकतम करना

समस्या 1||$\sum U_{j}$इसका लक्ष्य देर से आने वाली नौकरियों की संख्या को कम करना है, चाहे विलंबता की मात्रा कुछ भी हो। इसे हॉजसन-मूर एल्गोरिथम द्वारा इष्टतम ढंग से हल किया जा सकता है।लॉलर का एल्गोरिदम| इसकी व्याख्या समय पर पूरी होने वाली नौकरियों की संख्या को अधिकतम करने के रूप में भी की जा सकती है; इस संख्या को थ्रूपुट कहा जाता है.

समस्या 1||$\sum w_{j}U_{j}$इसका लक्ष्य देर से आने वाली नौकरियों के भार को कम करना है। यह एनपी-हार्ड है, क्योंकि विशेष मामले में सभी नौकरियों की समय सीमा समान होती है (1| द्वारा चिह्नित)।$d_{j}=d$|$\sum w_{j}U_{j}$) नैपसैक समस्या के समतुल्य है।लॉलर का एल्गोरिदम|

समस्या 1|$r_{j}$|$\sum U_{j}$सामान्यीकरण 1||$\sum U_{j}$ विभिन्न नौकरियों के लिए अलग-अलग रिलीज़ समय की अनुमति देकर। समस्या एनपी-हार्ड है. हालाँकि, जब सभी कार्य की लंबाई समान होती है, तो समस्या को बहुपद समय में हल किया जा सकता है। इसके कई प्रकार हैं:

• भारित अनुकूलन संस्करण, 1|$r_{j},p_{j}=p$|$\sum w_{j}U_{j}$,समय रहते समाधान किया जा सकता है$O(n^{7})$.
• अभारित अनुकूलन संस्करण, समय पर समाप्त होने वाली नौकरियों की संख्या को अधिकतम करता है, जिसे 1|$r_{j},p_{j}=p$|$\sum U_{j}$,समय रहते समाधान किया जा सकता है$O(n^{5})$गतिशील प्रोग्रामिंग का उपयोग करते हुए, जब सभी रिलीज़ समय और समय सीमाएँ पूर्णांक हों।
• निर्णय प्रकार - यह तय करना कि क्या यह संभव है कि सभी दिए गए कार्य समय पर पूरे हों - कई एल्गोरिदम द्वारा हल किया जा सकता है, उनमें से सबसे तेज़ समय में चलता है$O(n\log n)$.

नौकरियों में निष्पादन अंतराल हो सकते हैं। प्रत्येक कार्य j के लिए, एक प्रसंस्करण समय t है_jऔर एक प्रारंभ-समय एस_j, इसलिए इसे अंतराल में निष्पादित किया जाना चाहिए [s_j, एस_j+टी_j]. चूँकि कुछ अंतराल ओवरलैप होते हैं, इसलिए सभी कार्य पूरे नहीं किए जा सकते। लक्ष्य पूर्ण किए गए कार्यों की संख्या, यानी थ्रूपुट को अधिकतम करना है। अधिक सामान्यतः, प्रत्येक कार्य में कई संभावित अंतराल हो सकते हैं, और प्रत्येक अंतराल एक अलग लाभ से जुड़ा हो सकता है। लक्ष्य प्रत्येक कार्य के लिए अधिकतम एक अंतराल चुनना है, ताकि कुल लाभ अधिकतम हो। अधिक विवरण के लिए, अंतराल शेड्यूलिंग पर पृष्ठ देखें।

अधिक आम तौर पर, नौकरियों में समय-खिड़कियाँ हो सकती हैं, जिसमें प्रारंभ-समय और समय सीमा दोनों होती हैं, जो नौकरी की अवधि से बड़ी हो सकती हैं। प्रत्येक कार्य को उसकी समय-विंडो के भीतर कहीं भी निर्धारित किया जा सकता है। बार-नोय, बार-येहुदा, फ्रायंड, नाओर और शिबर एक (1-ε)/2 सन्निकटन प्रस्तुत करें।

यह भी देखें

• अंतराल शेड्यूलिंग

एकल मशीन शेड्यूलिंग समस्याओं को हल करने के लिए कई समाधान तकनीकों को लागू किया गया है। उनमें से कुछ नीचे सूचीबद्ध हैं।

• आनुवंशिक एल्गोरिदम
• तंत्रिका - तंत्र
• तैयार किए हुयी धातु पे पानी चढाने की कला
• चींटी कॉलोनी अनुकूलन
• तब्बू की तलाश