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

Revision as of 10:08, 22 July 2023

एकल-मशीन शेड्यूलिंग या एकल-संसाधन शेड्यूलिंग कंप्यूटर विज्ञान और संचालन अनुसंधान में अनुकूलन समस्या है। हमें n नौकरियां जेJ₁, J₂, ..., J_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 1: / Line 1: @@
-एकल-मशीन शेड्यूलिंग या एकल-संसाधन शेड्यूलिंग [[कंप्यूटर विज्ञान]] और संचालन अनुसंधान में [[अनुकूलन समस्या]] है। हमें ''एन'' नौकरियां ''जे'' <sub>1</sub>, ''जे''<sub>2</sub>, ..., ''जे''<sub>n</sub> दी जाती हैं जो की अलग-अलग प्रसंस्करण समय की होती है, जिन्हें मशीन पर इस प्रकार से शेड्यूल करने की आवश्यकता होती है, जो की निर्धारित निश्चित उद्देश्य को अनुकूलित करती है, जैसा की [[THROUGHPUT|थ्रूपुट]] में होता है।
+'''एकल-मशीन शेड्यूलिंग''' या '''एकल-संसाधन शेड्यूलिंग''' [[कंप्यूटर विज्ञान]] और संचालन अनुसंधान में [[अनुकूलन समस्या]] है। हमें ''n'' नौकरियां ''जेJ''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' दी जाती हैं जो की अलग-अलग प्रसंस्करण समय की होती है, जिन्हें मशीन पर इस प्रकार से शेड्यूल करने की आवश्यकता होती है, जो की निर्धारित निश्चित उद्देश्य को अनुकूलित करती है, जैसा की [[THROUGHPUT|थ्रूपुट]] में होता है।
-एकल-मशीन शेड्यूलिंग [[समान-मशीन शेड्यूलिंग]] का विशेष मामला है, जो की स्वयं [[इष्टतम कार्य शेड्यूलिंग]] का विशेष मामला है। अनेक समस्याएं, जो सामान्य रूप से एनपी-हार्ड प्रकार की होती है उन्हें एकल-मशीन स्थितियों में बहुपद समय में हल किया जा सकता है।<ref name=":0">{{Cite journal|last=Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys|date=1993-01-01|title=Chapter 9 Sequencing and scheduling: Algorithms and complexity|url=https://www.sciencedirect.com/science/article/abs/pii/S0927050705801896|journal=Handbooks in Operations Research and Management Science|language=en|volume=4|pages=445–522|doi=10.1016/S0927-0507(05)80189-6|isbn=9780444874726 |issn=0927-0507}}</ref>{{Rp|10-20}}
+एकल-मशीन शेड्यूलिंग [[समान-मशीन शेड्यूलिंग]] का विशेष स्थिति है, जो की स्वयं [[इष्टतम कार्य शेड्यूलिंग]] का विशेष स्थिति है। अनेक समस्याएं, जो सामान्य रूप से एनपी-हार्ड प्रकार की होती है उन्हें एकल-मशीन स्थितियों में बहुपद समय में हल किया जा सकता है।<ref name=":0">{{Cite journal|last=Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys|date=1993-01-01|title=Chapter 9 Sequencing and scheduling: Algorithms and complexity|url=https://www.sciencedirect.com/science/article/abs/pii/S0927050705801896|journal=Handbooks in Operations Research and Management Science|language=en|volume=4|pages=445–522|doi=10.1016/S0927-0507(05)80189-6|isbn=9780444874726 |issn=0927-0507}}</ref>{{Rp|10-20}}
 इष्टतम कार्य शेड्यूलिंग समस्याओं के लिए तीन-क्षेत्रक नोटेशन में, एकल-मशीन संस्करण को पहले क्षेत्रक में 1 द्वारा दर्शाया जाता है। उदाहरण के लिए, "1||<math>\sum C_j</math>" बिना किसी बाधा के एकल-मशीन शेड्यूलिंग समस्या है, जहां कार्य के पूर्ण होने के समय के योग को कम करना ही लक्ष्य होता है।
@@ 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> समस्या का लक्ष्य अधिकतम विलंबता को न्यूनतम करना होता है। प्रत्येक कार्य ''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||'''<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 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>
-नौकरियों में निष्पादन अंतराल हो सकते हैं। प्रत्येक कार्य j के लिए, प्रसंस्करण समय t<sub>j</sub> हैऔर प्रारंभ-समय ''s<sub>j</sub>'' होता है, इसलिए इसे [''s<sub>j</sub>,'' ''s<sub>j</sub>+t<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 48: / Line 48: @@
 *[[तैयार किए हुयी धातु पे पानी चढाने की कला]]
 *[[चींटी कॉलोनी अनुकूलन]]
-*तब्बू की तलाश
+*तब्बू की अविष्कार
 ==संदर्भ==

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 10:08, 22 July 2023

Contents

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:08, 22 July 2023

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories