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

Revision as of 23:43, 21 July 2023

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

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

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

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

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

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

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

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

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

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

1|prec| $h_{\max }$ समस्या 1|| $L_{\max }$ को दो विधि से सामान्यीकृत करता है : पहली विधि में यह नौकरियों पर मनमाने विधि से पूर्ववर्ती बाधाओं की अनुमति देता है और दूसरी विधि में यह प्रत्येक कार्य को मनमाना लागत फलन h_j रखने की अनुमति भी देता है, जो इसके पुरे होने के समय का फलन है (विलंबता लागत फलन का विशेष मामला है)। अधिकतम लागत को लालची कलन विधि द्वारा कम किया जा सकता है जिसे लॉलर के कलन विधि के रूप में जाना जाता है।^[2]^{: lecture 2, part 1}

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

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

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

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

1|| $\sum U_{j}$ समस्या का लक्ष्य विलम्भ से आने वाली नौकरियों की संख्या को कम करना होता है, चाहे विलंबता की मात्रा कुछ भी हो। इसे हॉजसन-मूर कलन विधि द्वारा इष्टतम विधि से हल किया जा सकता है।^[4]^[2]लॉलर का कलन विधि|^{: lecture 3, part 1} इसकी व्याख्या समय पर पूरी होने वाली नौकरियों की संख्या को अधिकतम करने के रूप में भी की जा सकती है; इस संख्या को थ्रूपुट कहा जाता है।

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

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

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

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

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

यह भी देखें

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

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

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

संदर्भ

↑ Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science (in English). 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN 0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 Grinshpoun, Tal (2020). "शेड्यूलिंग में विषय". www.youtube.com. Retrieved 2021-09-12.{{cite web}}: CS1 maint: url-status (link)
↑ Sahni, Sartaj K. (1976-01-01). "स्वतंत्र कार्यों को शेड्यूल करने के लिए एल्गोरिदम". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411. S2CID 10956951.
↑ Lawler, E.L. (1994-07-01). "नैपसैक-जैसी शेड्यूलिंग समस्याएं, मूर-हॉजसन एल्गोरिदम और 'टॉवर ऑफ़ सेट' संपत्ति". Mathematical and Computer Modelling (in English). 20 (2): 91–106. doi:10.1016/0895-7177(94)90209-7. ISSN 0895-7177.
↑ Baptiste, P. (1999). "समान प्रसंस्करण समय के साथ एक ही मशीन पर विलंबित नौकरियों की भारित संख्या को कम करने के लिए बहुपद समय एल्गोरिदम". Journal of Scheduling. 2 (6): 245–252. doi:10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.
↑ Chrobak, Marek; Dürr, Christoph; Jawor, Wojciech; Kowalik, Łukasz; Kurowski, Maciej (2006-02-01). "थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट". Journal of Scheduling (in English). 9 (1): 71–73. arXiv:cs/0410046. doi:10.1007/s10951-006-5595-4. ISSN 1099-1425. S2CID 7359990.
↑ Chrobak, Marek; Durr, Christoph; Jawor, Wojciech; Kowalik, Lukasz; Kurowski, Maciej (2021-05-12). "थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट". arXiv:cs/0410046. {{cite journal}}: Cite journal requires |journal= (help)
↑ Simons, Barbara (1978-10-16). "एकल प्रोसेसर शेड्यूलिंग के लिए एक तेज़ एल्गोरिदम". Proceedings of the 19th Annual Symposium on Foundations of Computer Science. SFCS '78. USA: IEEE Computer Society: 246–252. doi:10.1109/SFCS.1978.4. S2CID 10284575.
↑ Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E. (1981-05-01). "Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines". SIAM Journal on Computing. 10 (2): 256–269. doi:10.1137/0210018. ISSN 0097-5397.
↑ Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "संसाधन आवंटन और शेड्यूलिंग का अनुमान लगाने के लिए एक एकीकृत दृष्टिकोण". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294.

[:0-1] Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science (in English). 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN 0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[:1-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 Grinshpoun, Tal (2020). "शेड्यूलिंग में विषय". www.youtube.com. Retrieved 2021-09-12.{{cite web}}: CS1 maint: url-status (link)

[3] Sahni, Sartaj K. (1976-01-01). "स्वतंत्र कार्यों को शेड्यूल करने के लिए एल्गोरिदम". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411. S2CID 10956951.

[4] Lawler, E.L. (1994-07-01). "नैपसैक-जैसी शेड्यूलिंग समस्याएं, मूर-हॉजसन एल्गोरिदम और 'टॉवर ऑफ़ सेट' संपत्ति". Mathematical and Computer Modelling (in English). 20 (2): 91–106. doi:10.1016/0895-7177(94)90209-7. ISSN 0895-7177.

[5] Baptiste, P. (1999). "समान प्रसंस्करण समय के साथ एक ही मशीन पर विलंबित नौकरियों की भारित संख्या को कम करने के लिए बहुपद समय एल्गोरिदम". Journal of Scheduling. 2 (6): 245–252. doi:10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.

[6] Chrobak, Marek; Dürr, Christoph; Jawor, Wojciech; Kowalik, Łukasz; Kurowski, Maciej (2006-02-01). "थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट". Journal of Scheduling (in English). 9 (1): 71–73. arXiv:cs/0410046. doi:10.1007/s10951-006-5595-4. ISSN 1099-1425. S2CID 7359990.

[7] Chrobak, Marek; Durr, Christoph; Jawor, Wojciech; Kowalik, Lukasz; Kurowski, Maciej (2021-05-12). "थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट". arXiv:cs/0410046. {{cite journal}}: Cite journal requires |journal= (help)

[8] Simons, Barbara (1978-10-16). "एकल प्रोसेसर शेड्यूलिंग के लिए एक तेज़ एल्गोरिदम". Proceedings of the 19th Annual Symposium on Foundations of Computer Science. SFCS '78. USA: IEEE Computer Society: 246–252. doi:10.1109/SFCS.1978.4. S2CID 10284575.

[9] Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E. (1981-05-01). "Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines". SIAM Journal on Computing. 10 (2): 256–269. doi:10.1137/0210018. ISSN 0097-5397.

[10] Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "संसाधन आवंटन और शेड्यूलिंग का अनुमान लगाने के लिए एक एकीकृत दृष्टिकोण". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 9: / Line 9: @@
 == समापन समय का योग न्यूनतम करना ==
-समस्या '''1||'''<math>\sum C_j</math> का लक्ष्य समापन समय के योग को न्यूनतम करना होता है। इसे '''सबसे कम प्रसंस्करण समय''' ('''एसपीटी''') के प्रथम नियम द्वारा इष्टतम विधि से हल किया जा सकता है जिसमे की नौकरियों को उनके प्रसंस्करण समय <math>p_j</math> के आरोही क्रम से निर्धारित किया जाता है।
+'''1||'''<math>\sum C_j</math> समस्या का लक्ष्य समापन समय के योग को न्यूनतम करना होता है। इसे '''सबसे कम प्रसंस्करण समय''' ('''एसपीटी''') के प्रथम नियम द्वारा इष्टतम विधि से हल किया जा सकता है जिसमे की नौकरियों को उनके प्रसंस्करण समय <math>p_j</math> के आरोही क्रम से निर्धारित किया जाता है।
-समस्या '''1||'''<math>\sum w_j C_j</math> का लक्ष्य समापन समय के भारित योग को कम करना होता है। इसे '''भारित लघुतम प्रसंस्करण समय (डब्ल्यूएसपीटी)''' के प्रथम नियम द्वारा इष्टतम विधि से हल किया जा सकता है जिसमे की नौकरियां  <math>p_j/w_j</math> के अनुपात के आरोही क्रम द्वारा निर्धारित की जाती हैं।<ref name=":1" />{{Rp|lecture 1, part 2}}
+'''1||'''<math>\sum w_j C_j</math> समस्या का लक्ष्य समापन समय के भारित योग को कम करना होता है। इसे '''भारित लघुतम प्रसंस्करण समय (डब्ल्यूएसपीटी)''' के प्रथम नियम द्वारा इष्टतम विधि से हल किया जा सकता है जिसमे की नौकरियां  <math>p_j/w_j</math> के अनुपात के आरोही क्रम द्वारा निर्धारित की जाती हैं।<ref name=":1" />{{Rp|lecture 1, part 2}}
-समस्या '''1|श्रृंखलाए|'''<math>\sum w_j C_j</math>, श्रृंखलाओं के रूप में निर्भरता वाली नौकरियों के लिए उपरोक्त समस्या का सामान्यीकरण है। इसे डब्ल्यूएसपीटी के उपयुक्त सामान्यीकरण द्वारा भी इष्टतम विधि से हल किया जा सकता है।<ref name=":1" />{{Rp|lecture 1, part 3}}
+'''1|श्रृंखलाए|'''<math>\sum w_j C_j</math> समस्या, श्रृंखलाओं के रूप में निर्भरता वाली नौकरियों के लिए उपरोक्त समस्या का सामान्यीकरण है। इसे डब्ल्यूएसपीटी के उपयुक्त सामान्यीकरण द्वारा भी इष्टतम विधि से हल किया जा सकता है।<ref name=":1" />{{Rp|lecture 1, part 3}}
 == विलंबता की लागत को न्यूनतम करना ==
-समस्या 1||<math>L_{\max}</math> इसका लक्ष्य अधिकतम विलंबता को न्यूनतम करना है। प्रत्येक कार्य के लिए नियत तिथि होती है <math>d_j</math>. यदि इसे नियत तिथि के बाद पूरा किया जाता है, तो इसे विलंब (शेड्यूलिंग) के रूप में परिभाषित किया जाता है <math>L_j := C_j - d_j </math>. 1||<math>L_{\max}</math> प्रारंभिक नियत तिथि प्रथम नियम (ईडीडी) द्वारा सर्वोत्तम तरीके से हल किया जा सकता है: नौकरियां उनकी समय सीमा के आरोही क्रम से निर्धारित की जाती हैं <math>d_j</math>.<ref name=":1" />{{Rp|lecture 2, part 2}}
+'''1||'''<math>L_{\max}</math> समस्या का लक्ष्य अधिकतम विलंबता को न्यूनतम करना होता है। प्रत्येक कार्य ''j'' के लिए नियत तिथि <math>d_j</math> होती है। यदि इसे नियत तिथि के बाद पूरा किया जाता है, तो इसे विलंबता के रूप में कुछ इस प्रकार <math>L_j := C_j - d_j </math> परिभाषित किया जाता है। '''1||'''<math>L_{\max}</math> को '''प्रारंभिक नियत तिथि (ईडीडी)''' के प्रथम नियम द्वारा सर्वोत्तम तरीके से हल किया जा सकता है जिसमे की नौकरियां उनकी समय सीमा <math>d_j</math> के आरोही क्रम से निर्धारित की जाती हैं। <ref name=":1" />{{Rp|lecture 2, part 2}}
-समस्या 1|prec|<math>h_{\max}</math> 1 को सामान्यीकृत करता है||<math>L_{\max}</math> दो तरीकों से: पहला, यह नौकरियों पर मनमाने विधि से पूर्ववर्ती बाधाओं की अनुमति देता है; दूसरा, यह प्रत्येक कार्य को मनमाना लागत फ़ंक्शन h रखने की अनुमति देता है<sub>j</sub>, जो इसके पूरा होने के समय का फ़ंक्शन है (विलंबता लागत फ़ंक्शन का विशेष मामला है)। अधिकतम लागत को लालची एल्गोरिदम द्वारा कम किया जा सकता है जिसे लॉलर के एल्गोरिदम के रूप में जाना जाता है।<ref name=":1" />लॉलर का एल्गोरिदम|{{Rp|lecture 2, part 1}}
+'''1|prec|'''<math>h_{\max}</math> समस्या '''1||'''<math>L_{\max}</math> को दो विधि से सामान्यीकृत करता है : पहली विधि में यह नौकरियों पर मनमाने विधि से पूर्ववर्ती बाधाओं की अनुमति देता है और दूसरी विधि में यह प्रत्येक कार्य को मनमाना लागत फलन ''h<sub>j</sub>'' रखने की अनुमति भी देता है, जो इसके पुरे होने के समय का फलन है (विलंबता लागत फलन का विशेष मामला है)। अधिकतम लागत को लालची कलन विधि द्वारा कम किया जा सकता है जिसे लॉलर के कलन विधि के रूप में जाना जाता है।<ref name=":1" />{{Rp|lecture 2, part 1}}
-समस्या 1|<math>r_j</math>|<math>L_{\max}</math> सामान्यीकरण 1||<math>L_{\max}</math> प्रत्येक कार्य को अलग-अलग रिलीज़ समय की अनुमति देकर वह प्रसंस्करण के लिए उपलब्ध हो जाता है। रिलीज़ समय की उपस्थिति का मतलब है कि, कुछ मामलों में, किसी महत्वपूर्ण कार्य की प्रतीक्षा करने के लिए, जो अभी तक रिलीज़ नहीं हुआ है, मशीन को निष्क्रिय छोड़ना इष्टतम हो सकता है। इस सेटिंग में अधिकतम विलंबता को न्यूनतम करना एनपी-हार्ड है। लेकिन व्यवहार में, इसे [[ शाखा और बंधन |शाखा और बंधन]] एल्गोरिदम का उपयोग करके हल किया जा सकता है।<ref name=":1" />{{Rp|lecture 2, part 3}}
+'''1|<math>r_j</math>|'''<math>L_{\max}</math> समस्या प्रत्येक कार्य को अलग-अलग अवमुक्त समय की अनुमति देकर  '''1||'''<math>L_{\max}</math>  को सामान्यीकृत करता है जिसके कारण वह प्रसंस्करण के लिए उपलब्ध हो जाते है। अवमुक्त समय की उपस्थिति का मतलब यह है कि, कुछ मामलों में, किसी महत्वपूर्ण कार्य की प्रतीक्षा करने के लिए, जो अभी तक अवमुक्त नहीं हुआ है, मशीन को निष्क्रिय छोड़ना इष्टतम हो सकता है। इस सेटिंग में अधिकतम विलंबता को न्यूनतम करना एनपी-हार्ड होता है। लेकिन व्यवहार में, इसे [[ शाखा और बंधन |शाखा और बंधन]] कलन विधि का उपयोग करके हल किया जा सकता है।<ref name=":1" />{{Rp|lecture 2, part 3}}
 == कमाई का अधिकतम लाभ ==
-समय सीमा वाली सेटिंग में, यह संभव है कि, यदि कार्य समय सीमा के अंतर्गत पूरा हो जाता है, तो लाभ ''p<sub>j</sub>'' होता है। अन्यथा, कोई लाभ नहीं होता है। इसका लक्ष्य अधिकतम लाभ कमाना होता है। समय सीमा के साथ एकल-मशीन शेड्यूलिंग एनपी-हार्ड है; साहनी<ref>{{Cite journal |last=Sahni |first=Sartaj K. |date=1976-01-01 |title=स्वतंत्र कार्यों को शेड्यूल करने के लिए एल्गोरिदम|journal=Journal of the ACM |volume=23 |issue=1 |pages=116–127 |doi=10.1145/321921.321934 |s2cid=10956951 |issn=0004-5411|doi-access=free }}</ref> सटीक घातांक-समय एल्गोरिदम और बहुपद-समय सन्निकटन एल्गोरिदम दोनों प्रस्तुत करता है।
+समय सीमा वाली सेटिंग में, यह संभव है कि, यदि कार्य समय सीमा के अंतर्गत पूरा हो जाता है, तो लाभ ''p<sub>j</sub>'' होता है। अन्यथा, कोई लाभ नहीं होता है। इसका लक्ष्य अधिकतम लाभ कमाना होता है। समय सीमा के साथ एकल-मशीन शेड्यूलिंग एनपी-हार्ड है; साहनी<ref>{{Cite journal |last=Sahni |first=Sartaj K. |date=1976-01-01 |title=स्वतंत्र कार्यों को शेड्यूल करने के लिए एल्गोरिदम|journal=Journal of the ACM |volume=23 |issue=1 |pages=116–127 |doi=10.1145/321921.321934 |s2cid=10956951 |issn=0004-5411|doi-access=free }}</ref> सटीक घातांक-समय कलन विधि और बहुपद-समय सन्निकटन कलन विधि दोनों प्रस्तुत करता है।
 == थ्रूपुट को अधिकतम करना ==
-समस्या 1||<math>\sum U_j</math>इसका लक्ष्य देर से आने वाली नौकरियों की ''संख्या'' को कम करना है, चाहे विलंबता की मात्रा कुछ भी हो। इसे हॉजसन-मूर एल्गोरिथम द्वारा इष्टतम विधि से हल किया जा सकता है।<ref>{{Cite journal|date=1994-07-01|title=नैपसैक-जैसी शेड्यूलिंग समस्याएं, मूर-हॉजसन एल्गोरिदम और 'टॉवर ऑफ़ सेट' संपत्ति|journal=Mathematical and Computer Modelling|language=en|volume=20|issue=2|pages=91–106|doi=10.1016/0895-7177(94)90209-7|issn=0895-7177|doi-access=free|last1=Lawler |first1=E.L. }}</ref><ref name=":1" />लॉलर का एल्गोरिदम|{{Rp|lecture 3, part 1}} इसकी व्याख्या समय पर पूरी होने वाली नौकरियों की संख्या को अधिकतम करने के रूप में भी की जा सकती है; इस संख्या को थ्रूपुट कहा जाता है.
+'''1||'''<math>\sum U_j</math> समस्या का लक्ष्य विलम्भ से आने वाली नौकरियों की ''संख्या'' को कम करना होता है, चाहे विलंबता की मात्रा कुछ भी हो। इसे हॉजसन-मूर कलन विधि द्वारा इष्टतम विधि से हल किया जा सकता है।<ref>{{Cite journal|date=1994-07-01|title=नैपसैक-जैसी शेड्यूलिंग समस्याएं, मूर-हॉजसन एल्गोरिदम और 'टॉवर ऑफ़ सेट' संपत्ति|journal=Mathematical and Computer Modelling|language=en|volume=20|issue=2|pages=91–106|doi=10.1016/0895-7177(94)90209-7|issn=0895-7177|doi-access=free|last1=Lawler |first1=E.L. }}</ref><ref name=":1" />लॉलर का कलन विधि|{{Rp|lecture 3, part 1}} इसकी व्याख्या समय पर पूरी होने वाली नौकरियों की संख्या को अधिकतम करने के रूप में भी की जा सकती है; इस संख्या को थ्रूपुट कहा जाता है।
-समस्या 1||<math>\sum w_j U_j</math>इसका लक्ष्य देर से आने वाली नौकरियों के ''भार'' को कम करना है। यह एनपी-हार्ड है, क्योंकि विशेष मामले में सभी नौकरियों की समय सीमा समान होती है (1| द्वारा चिह्नित)।<math>d_j=d</math>|<math>\sum w_j U_j</math>) नैपसैक समस्या के समतुल्य है।<ref name=":1" />लॉलर का एल्गोरिदम|{{Rp|lecture 3, part 2}}
+'''1||'''<math>\sum w_j U_j</math> समस्या का लक्ष्य देर से आने वाली नौकरियों के ''भार'' को कम करना होता है। यह एनपी-हार्ड है, क्योंकि विशेष मामले में सभी नौकरियों की समय सीमा समान होती है '''(1|'''<math>d_j=d</math>|<math>\sum w_j U_j</math> द्वारा चिह्नित''')''' नैपसैक समस्या के समतुल्य है।<ref name=":1" />{{Rp|lecture 3, part 2}}
-समस्या 1|<math>r_j</math>|<math>\sum U_j</math>सामान्यीकरण 1||<math>\sum U_j</math> विभिन्न नौकरियों के लिए अलग-अलग ''रिलीज़ समय'' की अनुमति देकर। समस्या एनपी-हार्ड है. हालाँकि, जब सभी कार्य की लंबाई समान होती है, तो समस्या को बहुपद समय में हल किया जा सकता है। इसके कई प्रकार हैं:
+'''1|<math>r_j</math>|'''<math>\sum U_j</math> समस्या, विभिन्न नौकरियों के लिए अलग-अलग ''अवमुक्त समय'' की अनुमति देकर '''1||'''<math>\sum U_j</math> को सामान्यीकृत करता है। समस्या एनपी-हार्ड है। हालाँकि, जब सभी कार्य की लंबाई समान होती है, तो समस्या को बहुपद समय में हल किया जा सकता है। इसके कई प्रकार हैं:
-* भारित अनुकूलन संस्करण, 1|<math>r_j, p_j=p</math>|<math>\sum w_j U_j</math>,समय रहते समाधान किया जा सकता है<math>O(n^7)</math>.<ref>{{Cite journal |last=Baptiste |first=P. |date=1999 |title=समान प्रसंस्करण समय के साथ एक ही मशीन पर विलंबित नौकरियों की भारित संख्या को कम करने के लिए बहुपद समय एल्गोरिदम|url=https://onlinelibrary.wiley.com/doi/10.1002/(SICI)1099-1425(199911/12)2:6%3C245::AID-JOS28%3E3.0.CO;2-5 |journal=Journal of Scheduling|volume=2 |issue=6 |pages=245–252 |doi=10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5 }}</ref>
+* भारित अनुकूलन संस्करण, 1|<math>r_j, p_j=p</math>|<math>\sum w_j U_j</math>,का समाधान <math>O(n^7)</math> समय में किया जा सकता है.<ref>{{Cite journal |last=Baptiste |first=P. |date=1999 |title=समान प्रसंस्करण समय के साथ एक ही मशीन पर विलंबित नौकरियों की भारित संख्या को कम करने के लिए बहुपद समय एल्गोरिदम|url=https://onlinelibrary.wiley.com/doi/10.1002/(SICI)1099-1425(199911/12)2:6%3C245::AID-JOS28%3E3.0.CO;2-5 |journal=Journal of Scheduling|volume=2 |issue=6 |pages=245–252 |doi=10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5 }}</ref>
-* अभारित अनुकूलन संस्करण, समय पर समाप्त होने वाली नौकरियों की संख्या को अधिकतम करता है, जिसे 1|<math>r_j, p_j=p</math>|<math>\sum U_j</math>,समय रहते समाधान किया जा सकता है<math>O(n^5)</math>गतिशील प्रोग्रामिंग का उपयोग करते हुए, जब सभी रिलीज़ समय और समय सीमाएँ पूर्णांक हों।<ref>{{Cite journal |last1=Chrobak |first1=Marek |last2=Dürr |first2=Christoph |last3=Jawor |first3=Wojciech |last4=Kowalik |first4=Łukasz |last5=Kurowski |first5=Maciej |date=2006-02-01 |title=थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट|url=https://doi.org/10.1007/s10951-006-5595-4 |journal=Journal of Scheduling |language=en |volume=9 |issue=1 |pages=71–73 |doi=10.1007/s10951-006-5595-4 |arxiv=cs/0410046 |s2cid=7359990 |issn=1099-1425}}</ref><ref>{{Cite journal |last1=Chrobak |first1=Marek |last2=Durr |first2=Christoph |last3=Jawor |first3=Wojciech |last4=Kowalik |first4=Lukasz |last5=Kurowski |first5=Maciej |date=2021-05-12 |title=थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट|arxiv=cs/0410046 }}</ref>
+* अभारित अनुकूलन संस्करण, समय पर समाप्त होने वाली नौकरियों की संख्या को अधिकतम करता है जिसका ,1|<math>r_j, p_j=p</math>|<math>\sum U_j</math> द्वारा चिह्नित, गतिशील प्रोग्रामिंग का उपयोग करते हुए <math>O(n^5)</math> समय रहते समाधान किया जा सकता है, जब सभी अवमुक्त समय और समय सीमाएँ पूर्णांक हों।<ref>{{Cite journal |last1=Chrobak |first1=Marek |last2=Dürr |first2=Christoph |last3=Jawor |first3=Wojciech |last4=Kowalik |first4=Łukasz |last5=Kurowski |first5=Maciej |date=2006-02-01 |title=थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट|url=https://doi.org/10.1007/s10951-006-5595-4 |journal=Journal of Scheduling |language=en |volume=9 |issue=1 |pages=71–73 |doi=10.1007/s10951-006-5595-4 |arxiv=cs/0410046 |s2cid=7359990 |issn=1099-1425}}</ref><ref>{{Cite journal |last1=Chrobak |first1=Marek |last2=Durr |first2=Christoph |last3=Jawor |first3=Wojciech |last4=Kowalik |first4=Lukasz |last5=Kurowski |first5=Maciej |date=2021-05-12 |title=थ्रूपुट को अधिकतम करने के लिए समान-लंबाई वाली नौकरियों को शेड्यूल करने पर एक नोट|arxiv=cs/0410046 }}</ref>
-* निर्णय प्रकार - यह तय करना कि क्या यह संभव है कि सभी दिए गए कार्य समय पर पूरे हों - कई एल्गोरिदम द्वारा हल किया जा सकता है,<ref>{{Cite journal |last=Simons |first=Barbara |date=1978-10-16 |title=एकल प्रोसेसर शेड्यूलिंग के लिए एक तेज़ एल्गोरिदम|url=https://doi.org/10.1109/SFCS.1978.4 |journal=Proceedings of the 19th Annual Symposium on Foundations of Computer Science |series=SFCS '78 |location=USA |publisher=IEEE Computer Society |pages=246–252 |doi=10.1109/SFCS.1978.4|s2cid=10284575 }}</ref> उनमें से सबसे तेज़ समय में चलता है<math>O(n \log n)</math>.<ref>{{Cite journal |last1=Garey |first1=M. R. |last2=Johnson |first2=D. S. |last3=Simons |first3=B. B. |last4=Tarjan |first4=R. E. |date=1981-05-01 |title=Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines |url=https://epubs.siam.org/doi/abs/10.1137/0210018 |journal=SIAM Journal on Computing |volume=10 |issue=2 |pages=256–269 |doi=10.1137/0210018 |issn=0097-5397}}</ref>
+* निर्णय प्रकार - यह तय करना कि क्या यह संभव है कि सभी दिए गए कार्य समय पर पूरे हों, इसे कई कलन विधि द्वारा हल किया जा सकता है,<ref>{{Cite journal |last=Simons |first=Barbara |date=1978-10-16 |title=एकल प्रोसेसर शेड्यूलिंग के लिए एक तेज़ एल्गोरिदम|url=https://doi.org/10.1109/SFCS.1978.4 |journal=Proceedings of the 19th Annual Symposium on Foundations of Computer Science |series=SFCS '78 |location=USA |publisher=IEEE Computer Society |pages=246–252 |doi=10.1109/SFCS.1978.4|s2cid=10284575 }}</ref> उनमें से सबसे तेज़ <math>O(n \log n)</math> समय में चलता है।<ref>{{Cite journal |last1=Garey |first1=M. R. |last2=Johnson |first2=D. S. |last3=Simons |first3=B. B. |last4=Tarjan |first4=R. E. |date=1981-05-01 |title=Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines |url=https://epubs.siam.org/doi/abs/10.1137/0210018 |journal=SIAM Journal on Computing |volume=10 |issue=2 |pages=256–269 |doi=10.1137/0210018 |issn=0097-5397}}</ref>
-नौकरियों में निष्पादन अंतराल हो सकते हैं। प्रत्येक कार्य j के लिए, प्रसंस्करण समय t है<sub>j</sub>और प्रारंभ-समय एस<sub>j</sub>, इसलिए इसे अंतराल में निष्पादित किया जाना चाहिए [s<sub>j</sub>, एस<sub>j</sub>+टी<sub>j</sub>]. चूँकि कुछ अंतराल ओवरलैप होते हैं, इसलिए सभी कार्य पूरे नहीं किए जा सकते। लक्ष्य पूर्ण किए गए कार्यों की संख्या, यानी थ्रूपुट को अधिकतम करना है। अधिक सामान्यतः, प्रत्येक कार्य में कई संभावित अंतराल हो सकते हैं, और प्रत्येक अंतराल अलग लाभ से जुड़ा हो सकता है। लक्ष्य प्रत्येक कार्य के लिए अधिकतम अंतराल चुनना है, ताकि कुल लाभ अधिकतम हो। अधिक विवरण के लिए, [[अंतराल शेड्यूलिंग]] पर पृष्ठ देखें।
+नौकरियों में निष्पादन अंतराल हो सकते हैं। प्रत्येक कार्य j के लिए, प्रसंस्करण समय t<sub>j</sub> हैऔर प्रारंभ-समय ''s<sub>j</sub>'' होता है, इसलिए इसे [''s<sub>j</sub>,'' ''s<sub>j</sub>+t<sub>j</sub>''] अंतराल में निष्पादित किया जाना चाहिए। चूँकि कुछ अंतराल अतिव्याप्ति होते हैं, इसलिए सभी कार्य पूरे नहीं किए जा सकते। लक्ष्य पूर्ण किए गए कार्यों की संख्या, यानी थ्रूपुट को अधिकतम करना है। अधिक सामान्यतः, प्रत्येक कार्य में कई संभावित अंतराल हो सकते हैं, और प्रत्येक अंतराल अलग लाभ से जुड़ा हो सकता है। प्रत्येक कार्य के लिए अधिकतम अंतराल चुनना ही इसका लक्ष्य होता है , ताकि कुल लाभ अधिकतम हो। अधिक विवरण के लिए, [[अंतराल शेड्यूलिंग]] पर पृष्ठ देखें।
-अधिक आम तौर पर, नौकरियों में समय-खिड़कियाँ हो सकती हैं, जिसमें प्रारंभ-समय और समय सीमा दोनों होती हैं, जो नौकरी की अवधि से बड़ी हो सकती हैं। प्रत्येक कार्य को उसकी समय-विंडो के भीतर कहीं भी निर्धारित किया जा सकता है। बार-नोय, बार-येहुदा, फ्रायंड, नाओर और शिबर<ref>{{Cite journal|last1=Bar-Noy|first1=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|author5-link=Baruch Schieber|date=2001-09-01|title=संसाधन आवंटन और शेड्यूलिंग का अनुमान लगाने के लिए एक एकीकृत दृष्टिकोण|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|s2cid=12329294 |issn=0004-5411}}</ref> (1-ε)/2 सन्निकटन प्रस्तुत करें।
+अधिक आम तौर पर, नौकरियों में समय-खिड़कियाँ हो सकती हैं, जिसमें प्रारंभ-समय और समय सीमा दोनों होती हैं, जो नौकरी की अवधि से बड़ी हो सकती हैं। प्रत्येक कार्य को उसकी समय-खिड़कि के भीतर कहीं भी निर्धारित किया जा सकता है। बार-नोय, बार-येहुदा, फ्रायंड, नाओर और शिबर<ref>{{Cite journal|last1=Bar-Noy|first1=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|author5-link=Baruch Schieber|date=2001-09-01|title=संसाधन आवंटन और शेड्यूलिंग का अनुमान लगाने के लिए एक एकीकृत दृष्टिकोण|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|s2cid=12329294 |issn=0004-5411}}</ref> (1-ε)/2 सन्निकटन प्रस्तुत करते है।
 == यह भी देखें ==
@@ Line 44: / Line 44: @@
 एकल मशीन शेड्यूलिंग समस्याओं को हल करने के लिए कई समाधान तकनीकों को लागू किया गया है। उनमें से कुछ नीचे सूचीबद्ध हैं।
-*आनुवंशिक एल्गोरिदम
+*आनुवंशिक कलन विधि
 *तंत्रिका - तंत्र
 *[[तैयार किए हुयी धातु पे पानी चढाने की कला]]

v t e Optimal job scheduling problems
One-stage jobs	Single machine Identical machines Uniform machines Unrelated machines
Multi-stage jobs	Parallel tasks Open shop Flow shop Job shop
Optimization objectives	Makespan Earliness Lateness Tardiness Throughput
Other requirements	Interval scheduling Truthful job scheduling

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 23:43, 21 July 2023

Contents

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 23:43, 21 July 2023

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories