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

Revision as of 18:59, 21 July 2023

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

एकल-मशीन शेड्यूलिंग समान-मशीन शेड्यूलिंग का विशेष मामला है, जो स्वयं इष्टतम कार्य शेड्यूलिंग का विशेष मामला है। कई समस्याएं, जो सामान्य रूप से एनपी-हार्ड हैं, एकल-मशीन मामले में बहुपद समय में हल की जा सकती हैं।^[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 }$ इसका लक्ष्य अधिकतम विलंबता को न्यूनतम करना है। प्रत्येक कार्य के लिए नियत तिथि होती है $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}

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

समय सीमा वाली सेटिंग में, यह संभव है कि, यदि कार्य समय सीमा तक पूरा हो जाता है, तो लाभ हो_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और प्रारंभ-समय एस_j, इसलिए इसे अंतराल में निष्पादित किया जाना चाहिए [s_j, एस_j+टी_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]], को अनुकूलित करता है।
+एकल-मशीन शेड्यूलिंग या एकल-संसाधन शेड्यूलिंग [[कंप्यूटर विज्ञान]] और संचालन अनुसंधान में [[अनुकूलन समस्या]] है। हमें ''एन'' नौकरियां ''जे'' दी गई हैं<sub>1</sub>, जे<sub>2</sub>, ..., जे<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>बिना किसी बाधा के एक एकल-मशीन शेड्यूलिंग समस्या है, जहां लक्ष्य पूरा होने के समय के योग को कम करना है।
+मानक ऑप्टिमल जॉब शेड्यूलिंग|इष्टतम जॉब शेड्यूलिंग समस्याओं के लिए तीन-फ़ील्ड नोटेशन में, एकल-मशीन संस्करण को पहले फ़ील्ड में 1 द्वारा दर्शाया जाता है। उदाहरण के लिए, 1||<math>\sum C_j</math>बिना किसी बाधा के एकल-मशीन शेड्यूलिंग समस्या है, जहां लक्ष्य पूरा होने के समय के योग को कम करना है।
-मेकस्पैन-न्यूनतमीकरण समस्या 1||<math>C_{\max}</math>, जो कई मशीनों के लिए एक सामान्य उद्देश्य है, एक मशीन के लिए तुच्छ है, क्योंकि मेकस्पैन हमेशा समान होता है। इसलिए, अन्य उद्देश्यों का अध्ययन किया गया है।<ref name=":1">{{Cite web|last=Grinshpoun|first=Tal|date=2020|title=शेड्यूलिंग में विषय|url=https://www.youtube.com/user/grinshpo|url-status=live|access-date=2021-09-12|website=www.youtube.com}}</ref>
+मेकस्पैन-न्यूनतमीकरण समस्या 1||<math>C_{\max}</math>, जो कई मशीनों के लिए सामान्य उद्देश्य है, मशीन के लिए तुच्छ है, क्योंकि मेकस्पैन हमेशा समान होता है। इसलिए, अन्य उद्देश्यों का अध्ययन किया गया है।<ref name=":1">{{Cite web|last=Grinshpoun|first=Tal|date=2020|title=शेड्यूलिंग में विषय|url=https://www.youtube.com/user/grinshpo|url-status=live|access-date=2021-09-12|website=www.youtube.com}}</ref>
@@ Line 11: / Line 11: @@
 समस्या 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> इसका लक्ष्य अधिकतम विलंबता को न्यूनतम करना है। प्रत्येक कार्य के लिए नियत तिथि होती है <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}}
 == कमाई का अधिकतम लाभ ==
@@ Line 35: / Line 35: @@
 * अभारित अनुकूलन संस्करण, समय पर समाप्त होने वाली नौकरियों की संख्या को अधिकतम करता है, जिसे 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>और एक प्रारंभ-समय एस<sub>j</sub>, इसलिए इसे अंतराल में निष्पादित किया जाना चाहिए [s<sub>j</sub>, एस<sub>j</sub>+टी<sub>j</sub>]. चूँकि कुछ अंतराल ओवरलैप होते हैं, इसलिए सभी कार्य पूरे नहीं किए जा सकते। लक्ष्य पूर्ण किए गए कार्यों की संख्या, यानी थ्रूपुट को अधिकतम करना है। अधिक सामान्यतः, प्रत्येक कार्य में कई संभावित अंतराल हो सकते हैं, और प्रत्येक अंतराल एक अलग लाभ से जुड़ा हो सकता है। लक्ष्य प्रत्येक कार्य के लिए अधिकतम एक अंतराल चुनना है, ताकि कुल लाभ अधिकतम हो। अधिक विवरण के लिए, [[अंतराल शेड्यूलिंग]] पर पृष्ठ देखें।
+नौकरियों में निष्पादन अंतराल हो सकते हैं। प्रत्येक कार्य j के लिए, प्रसंस्करण समय t है<sub>j</sub>और प्रारंभ-समय एस<sub>j</sub>, इसलिए इसे अंतराल में निष्पादित किया जाना चाहिए [s<sub>j</sub>, एस<sub>j</sub>+टी<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 सन्निकटन प्रस्तुत करें।
 == यह भी देखें ==

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 18:59, 21 July 2023

Contents

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 18:59, 21 July 2023

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories