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

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

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

इष्टतम कार्य शेड्यूलिंग समस्याओं के लिए तीन-क्षेत्रक नोटेशन में, एकल-मशीन संस्करण को पहले क्षेत्रक में 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 }$ समस्या का लक्ष्य अधिकतम विलंबता को न्यूनतम करना होता है। प्रत्येक कार्य j के लिए नियत तिथि $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 }$ को सामान्यीकृत करता है जिसके कारण वह प्रसंस्करण के लिए उपलब्ध हो जाते है। अवमुक्त समय की उपस्थिति का तात्पर्य यह है कि, कुछ स्थितियों में, किसी महत्वपूर्ण कार्य की प्रतीक्षा करने के लिए, जो अभी तक अवमुक्त नहीं हुआ है, मशीन को निष्क्रिय छोड़ना इष्टतम हो सकता है। इस सेटिंग में अधिकतम विलंबता को न्यूनतम करना एनपी-हार्ड होता है। लेकिन व्यवहार में, इसे शाखा और बंधन ऐल्गरिदम विधि का उपयोग करके हल किया जा सकता है।

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

इस प्रकार समय सीमा वाली सेटिंग में, यह संभव है कि, यदि कार्य समय सीमा के अंतर्गत पूरा हो जाता है, तो लाभ p_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 है और प्रारंभ-समय s_j होता है, इसलिए इसे [s_j, s_j+t_j] अंतराल में निष्पादित किया जाना चाहिए। चूँकि कुछ अंतराल अतिव्याप्ति होते हैं, इसलिए सभी कार्य को पूरा किया नहीं जा सकता है। लक्ष्य है कि पूर्ण किए गए कार्य की संख्या, अर्थात प्रवाह, को अधिकतम करना है।अधिक सामान्य रूप से, प्रत्येक कार्य के कई संभावित अंतराल हो सकते हैं, और प्रत्येक अंतराल अलग लाभ से जुड़ा हो सकता है। प्रत्येक कार्य के लिए अधिकतम अंतराल चुनना ही इसका लक्ष्य होता है , जिससे कुल लाभ अधिकतम हो। अधिक विवरण के लिए, अंतराल शेड्यूलिंग पर पृष्ठ देखें।

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

यह भी देखें

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

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

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