अंतराल निर्धारण: Difference between revisions

Latest revision as of 17:19, 21 August 2023

अंतराल शेड्यूलिंग कंप्यूटर विज्ञान में समस्याओं का वर्ग है, विशेष रूप से एल्गोरिथ्म डिजाइन के क्षेत्र में। समस्याएँ कार्यों के समूह पर विचार करती हैं। प्रत्येक कार्य को एक अंतराल द्वारा दर्शाया जाता है जो उस समय का वर्णन करता है जिसमें इसे किसी मशीन द्वारा संसाधित (या, समकक्ष, कुछ संसाधनों पर निर्धारित) करने की आवश्यकता होती है। उदाहरण के लिए, कार्य A 2:00 से 5:00 तक चल सकता है, कार्य B 4:00 से 10:00 तक चल सकता है और कार्य C 9:00 से 11:00 तक चल सकता है। यदि मशीन/संसाधन पर कोई दो अंतराल ओवरलैप नहीं होते हैं तो अंतरालों का सबसेट संगत होता है। उदाहरण के लिए, उपसमुच्चय {A,C} संगत है, जैसा कि उपसमुच्चय {B} है; लेकिन न तो {A,B} और न ही {B,C} संगत उपसमुच्चय हैं, क्योंकि प्रत्येक सबसेट के अंदर संबंधित अंतराल ओवरलैप होते हैं।

अंतराल शेड्यूलिंग मक्सिमाईजेशन समस्या (ISMP) सबसे बड़ा संगत सेट ढूंढना है, अर्थात, अधिकतम आकार के गैर-अतिव्यापी अंतराल का सेट होता हैं। यहां लक्ष्य अधिक से अधिक कार्यों को निष्पादित करना है, अर्थात थ्रूपुट को अधिकतम करना है। यह अंतराल ग्राफ में एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) ढूंढने के समान है।

$k>1$ मशीनें/संसाधन समस्या के सामान्यीकरण पर विचार करता है।^[1] $k$ संगत सबसेट जिनका सेट सबसे बड़ा है को यहां ढूंढ़ना लक्ष्य हैं।

समस्या के उन्नत संस्करण में, अंतरालों को समूहों में विभाजित किया गया है। यदि कोई दो अंतराल ओवरलैप नहीं होते हैं, तो अंतराल का एक उपसमूह संगत होता है, और इसके अतिरिक्त, कोई भी दो अंतराल एक ही समूह से संबंधित नहीं होते हैं (अर्थात, सबसेट में प्रत्येक समूह का अधिकतम एक ही प्रतिनिधि होता है)। अंतरालों का प्रत्येक समूह एक ही कार्य से मिलता हैं, और कई वैकल्पिक अंतरालों का प्रतिनिधित्व करता है जिसमें इसे निष्पादित किया जा सकता है।

समूह अंतराल शेड्यूलिंग निर्णय समस्या (GISDP) यह तय करने के लिए है कि क्या कोई संगत सेट उपस्थित है जिसमें सभी समूहों का प्रतिनिधित्व किया गया है। यहां लक्ष्य प्रत्येक समूह से प्रतिनिधि कार्य निष्पादित करना है। GISDPK, GISDP का प्रतिबंधित संस्करण है जिसमें प्रत्येक समूह में अंतराल की संख्या अधिकतम k है।

समूह अंतराल शेड्यूलिंग अधिकतमकरण समस्या (GISMP) सबसे बड़ा संगत सेट ढूंढना है - अधिकतम आकार के गैर-अतिव्यापी प्रतिनिधियों का सेट हैं। यहां लक्ष्य अधिक से अधिक समूहों से प्रतिनिधि कार्य निष्पादित करना है। GISMPk, GISMP का एक प्रतिबंधित संस्करण है जिसमें प्रत्येक समूह में अंतराल की संख्या अधिकतम k है। इस समस्या को प्रायः JISPk कहा जाता है, जहां J का अर्थ जॉब है।

जीआईएसएमपी सबसे सामान्य समस्या है; अन्य दो समस्याओं को इसके विशेष स्थितियों के रूप में देखा जा सकता है:

ISMP वह विशेष स्थिति है जिसमें प्रत्येक कार्य अपने स्वयं के समूह से संबंधित होता है (अर्थात यह जीआईएसएम्पी1 के बराबर होता है)।
GISDP यह तय करने की समस्या है कि क्या अधिकतम वास्तव में समूहों की संख्या के बराबर है।

इन सभी समस्याओं को प्रत्येक अंतराल के लिए भार जोड़कर सामान्यीकृत किया जा सकता है, जो उस अंतराल में कार्य को निष्पादित करने से होने वाले लाभ का प्रतिनिधित्व करता है। फिर, लक्ष्य कुल भार को अधिकतम करना है।

ये सभी समस्याएं एकल-मशीन शेड्यूलिंग के विशेष स्थितियाँ हैं, क्योंकि वे मानते हैं कि सभी कार्यों को एक ही प्रोसेसर पर चलना होता हैं। एकल-मशीन शेड्यूलिंग इष्टतम कार्य शेड्यूलिंग की विशेष स्थिति है।

एकल-अंतराल शेड्यूलिंग अधिकतमीकरण

अभारित

कई एल्गोरिदम, जो पहली बार में आशाजनक लग सकते हैं, वास्तव में इष्टतम समाधान नहीं ढूंढते हैं:^[2]

जल्द से जल्द प्रारम्भ होने वाले अंतराल का चयन करना इष्टतम समाधान नहीं है, क्योंकि यदि प्रारंभिक अंतराल बहुत लंबा होता है, तो इसे स्वीकार करने से हमें कई अन्य छोटे अनुरोधों को अस्वीकार करना पड़ता हैं।
सबसे छोटे अंतराल का चयन करना या सबसे कम विरोध वाले अंतराल का चयन करना भी इष्टतम नहीं है।

निम्नलिखित ग्रीडी एल्गोरिदम, जिसे अर्लीएस्ट डेडलाइन फर्स्ट स्केड्यूलिंग कहा जाता है, अनवेटेड सिंगल-इंटरवल शेड्यूलिंग के लिए इष्टतम समाधान ढूंढता है:

जल्द से जल्द 'फिनिशिंग टाइम' के साथ अंतराल, x का चयन करते हैं।
कैंडिडेट अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों को हटा देते हैं।
कैंडिडेट अंतराल का सेट रिक्त होने तक दुहराया जाता हैं।

जब भी हम चरण 1 पर अंतराल का चयन करते हैं, तो हमें चरण 2 में कई अंतरालों को हटाना पड़ सकता है। यद्यपि की, ये सभी अंतराल आवश्यक रूप से x के समापन समय को पार करते हैं, और इस प्रकार वे सभी एक दूसरे को पार करते हैं। इसलिए, इनमें से अधिकतम 1 अंतराल इष्टतम समाधान में हो सकता है। इसलिए, इष्टतम समाधान में प्रत्येक अंतराल के लिए, ग्रीडी समाधान में एक अंतराल होता है। इससे सिद्ध होता है कि ग्रीडी एल्गोरिदम वास्तव में इष्टतम समाधान ढूंढता है।

चार्जिंग तर्क द्वारा एक अधिक औपचारिक व्याख्या दी गई है।

ग्रीडी एल्गोरिदम को समय O (n log n) में निष्पादित किया जा सकता है, जहां n प्रीप्रोसेसिंग चरण का उपयोग करके कार्यों की संख्या है जिसमें कार्यों को उनके समापन समय के अनुसार क्रमबद्ध किया जाता है।

भारित

जब अंतरालों में भार होता है, तो समस्या अंतराल ग्राफ़ में अधिकतम-भार स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर होती है। इसे बहुपद समय में हल किया जा सकता है।^[3]

To find the maximum weight of a single interval schedule in Θ(n) time, perform the following pseudocode:

// The vectors are already sorted from earliest to latest finish time.
int v[numOfVectors + 1]; // list of interval vectors
int w[numOfVectors + 1]; // w[j] is the weight for v[j].
int p[numOfVectors + 1]; // p[j] is the # of vectors that end before v[j] begins.
int M[numOfVectors + 1];
int finalSchedule[];

// v[0] does not exist. The first interval vector is set to v[1].
w[0] = 0; p[0] = 0; M[0] = 0;

for (int i = 1; i < numOfVector + 1; i++) {
    M[i] = max(w[i] + M[p[i]], M[i - 1]);
}

// The maximum weight of the schedule is equal to M[numOfVectors + 1].

schedule (j) {
    if (j == 0) { return; }
    else if (w[j] + M[p[j]] >= M[j - 1]){
        prepend(v[j], finalSchedule); // prepends v[j] to schedule.
        schedule(p[j]);
    } else { schedule(j - 1); }
}

^[4]

Documentation/doc

समूह अंतराल निर्धारण निर्णय

एनपी-पूर्ण जब कुछ समूहों में 3 या अधिक अंतराल होते हैं

GISDPk एनपी-पूर्ण है जब $k\geq 3$ ,^[5] तब भी जब सभी अंतरालों की लंबाई समान होती हैं।^[6] इसे बूलियन संतुष्टि समस्या के निम्नलिखित संस्करण में कमी करके दिखाया जा सकता है, जो ^[7] अप्रतिबंधित संस्करण की तरह ही एनपी-पूर्ण होना में दिखाया गया था।

माना

X=\{x_{1},x_{2},\dots ,x_{p}\}

बूलियन वेरिएबल्स का सेट बनता हैं। माना

C=\{c_{1},c_{2},\dots ,c_{q}\}

X पर उपवाक्यों का समूह इस प्रकार हो कि (1) C में प्रत्येक उपवाक्य में अधिकतम तीन अक्षर हों और (2) प्रत्येक चर C में एक या दो बार धनात्मक और एक बार ऋणात्मक रूप से प्रकट होने के लिए प्रतिबंधित हो। यह तय करें कि क्या X का चरों में असाइनमेंट हैं क्योंकि C में प्रत्येक क्लॉज़ न्यूनतम एक सही शब्दसः होता हैं।

इस संतुष्टि समस्या के एक उदाहरण को देखते हुए, GISDP के निम्नलिखित उदाहरण का निर्माण करते हैं। सभी अंतरालों की लंबाई 3 है, इसलिए प्रत्येक अंतराल को उसके प्रारंभिक समय से दर्शाना पर्याप्त है:

प्रत्येक चर के लिए $x_{i}$ (के लिए i=1,...,p), दो अंतरालों वाला समूह बनाएं: प्रारंभ से $50i-10$ (असाइनमेंट का प्रतिनिधित्व करते हुए $x_{i}=\mathrm {false}$ ) और दूसरा प्रारम्भ $50i+10$ हो रहा है (असाइनमेंट का प्रतिनिधित्व करते हुए $x_{i}=\mathrm {true}$ )।
प्रत्येक खंड के लिए $c_{j}$ $c_{j}$ (के लिए j=1,...,q), निम्नलिखित अंतराल के साथ एक समूह बनाते हैं:
- प्रत्येक चर के लिए $x_{i}$ यह C में पहली बार धनात्मक रूप से प्रकट होता है — से प्रारम्भ होने वाला अंतराल $50i-12$ .
- प्रत्येक चर के लिए $x_{i}$ जो C में दूसरी बार धनात्मक रूप से प्रकट होता है — से प्रारम्भ होने वाला अंतराल $50i-8$ होता हैं। ध्यान दें कि ये दोनों अंतराल $50i-10$ अंतराल को काटते हैं, जो $x_{i}=\mathrm {false}$ के साथ जुड़े होते हैं।
- प्रत्येक चर के लिए $x_{i}$ जो ऋणात्मक रूप से प्रकट होता है - एक अंतराल जो $50i+8$ से प्रारम्भ होता है। यह अंतराल $50i+10$ अंतराल को प्रतिच्छेद करता है, जो $x_{i}={\text{true}}$ के साथ जुड़े होते हैं।

ध्यान दें कि विभिन्न उपवाक्यों से जुड़े समूहों में अंतरालों के बीच कोई ओवरलैप नहीं है। यह सुनिश्चित किया जाता है क्योंकि एक चर अधिकतम दो बार धनात्मक और एक बार ऋणात्मक रूप में प्रकट होता है।

निर्मित GISDP के पास व्यवहार्य समाधान है (अर्थात एक शेड्यूलिंग जिसमें प्रत्येक समूह का प्रतिनिधित्व किया जाता है), यदि और केवल तभी जब बूलियन क्लॉज के दिए गए सेट में एक संतोषजनक असाइनमेंट होता हैं। इसलिए GISDP3 एनपी-पूर्ण है, और इसी प्रकार प्रत्येक $k\geq 3$ के लिए GISDPk भी है।

बहुपद जब सभी समूहों में अधिकतम 2 अंतराल हों

GISDP2 को 2-संतुष्टि समस्या में निम्नलिखित कमी करके बहुपद समय पर हल किया जा सकता है:^[6]*

. प्रत्येक समूह के लिए, दो चर बनाते हैं, जो उसके दो अंतरालों $x_{i}$ और $y_{i}$ का प्रतिनिधित्व करते हैं:

प्रत्येक समूह के लिए, $x_{i}\cup y_{i}$ और $\neg {x_{i}}\cup \neg {y_{i}}$ खंड बनाएं: जो इस कथन का प्रतिनिधित्व करता है कि इन दो अंतरालों में से वास्तव में एक का चयन किया जाता हैं।
प्रत्येक दो प्रतिच्छेदी अंतरालों के लिए (अर्थात $x_{i}$ और $y_{j}$ ) उपवाक्य बनाएं: $\neg {x_{i}}\cup \neg {y_{j}}$ , जो इस कथन का प्रतिनिधित्व करता है कि इन दो अंतरालों में से अधिक से अधिक एक का चयन किया जाता हैं।

इस निर्माण में अधिकतम O(n²) सम्मलित है खंड (अंतराल के बीच प्रत्येक प्रतिच्छेदन के लिए एक, साथ ही प्रत्येक समूह के लिए दो)। प्रत्येक उपवाक्य में 2 अक्षर हैं। ऐसे सूत्रों की संतुष्टि खंडों की संख्या में रैखिक समय में तय की जा सकती है (2-SAT देखें)। इसलिए, GISDP2 को बहुपद समय में हल किया जा सकता है।

समूह अंतराल निर्धारण अधिकतमकरण

MaxSNP-पूर्ण जब कुछ समूहों में 2 या अधिक अंतराल होते हैं

GISMPk जब $k\geq 2$ भी एनपी-पूर्ण है। ^[8]

इसके अतिरिक्त, GISMPk MaxSNP-पूर्ण है, अर्थात, इसमें PTAS नहीं है जब तक कि P=NP नहीं होता हैं। इसे Max 3-SAT-3 से GISMP2 तक अनुमानित-संरक्षण कमी दिखाकर सिद्ध किया जा सकता है।^[8]

बहुपद 2-सन्निकटन

निम्नलिखित ग्रीडी एल्गोरिदम एक समाधान ढूंढता है जिसमें अंतराल की इष्टतम संख्या का कम से कम 1/2 सम्मलित होता है:^[8]#

1.जल्द से जल्द 'फिनिशिंग टाइम' के साथ अंतराल, x का चयन करते हैं।

कैंडिडेट अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों और x के एक ही समूह के सभी अंतरालों को हटा देते हैं।
तब तक जारी रखें जब तक कि कैंडिडेट अंतराल का सेट खाली नहीं हो जाता हैं।

एक औपचारिक स्पष्टीकरण चार्जिंग आर्गुमेंट द्वारा दिया गया है।

2 का सन्निकटन कारक टाइट है। उदाहरण के लिए, GISMP2 के निम्नलिखित उदाहरण में:

समूह #1: {[0..2], [4..6]}
समूह #2: {[1..3]}

ग्रीडी एल्गोरिदम समूह #1 से केवल 1 अंतराल [0..2] का चयन करता है, जबकि एक इष्टतम शेड्यूलिंग समूह #2 से [1..3] और फिर समूह #1 से [4..6] का चयन करना है।

एक अधिक सामान्य सन्निकटन एल्गोरिथ्म भारित स्थिति के लिए 2-कारक सन्निकटन प्राप्त करता है।^[3]

एलपी-आधारित सन्निकटन एल्गोरिदम

लीनियर प्रोग्रामिंग रिलैक्सेशन की तकनीक का उपयोग करके, थोड़े अच्छे सन्निकटन कारकों के साथ इष्टतम शेड्यूलिंग का अनुमान लगाना संभव है। जब k बड़ा होता है तो ऐसे पहले एल्गोरिदम का सन्निकटन अनुपात स्पर्शोन्मुख रूप से 2 होता है, लेकिन जब k=2 होता है तो एल्गोरिथ्म 5/3 का सन्निकटन अनुपात प्राप्त करता है।^[8] यादृच्छिक k के लिए सन्निकटन कारक को बाद में 1.582 तक सुधार दिया गया हैं।^[9]

भिन्नताएँ

शेड्यूलिंग एल्गोरिदम का महत्वपूर्ण वर्ग गतिशील प्राथमिकता एल्गोरिदम का वर्ग है। जब कोई भी अंतराल ओवरलैप नहीं होता है तो इष्टतम समाधान निम्न होता है। अभारित संस्करण के लिए इष्टतम को सबसे पहले समय सीमा निर्धारण के साथ पाया जा सकता है। भारित अंतराल शेड्यूलिंग एक सामान्यीकरण है जहां प्रत्येक निष्पादित कार्य के लिए एक मान निर्दिष्ट किया जाता है और लक्ष्य कुल मूल्य को अधिकतम करना है। समाधान का अद्वितीय होना आवश्यक नहीं है।

अंतराल शेड्यूलिंग समस्या एक-आयामी है - केवल समय आयाम प्रासंगिक है। अधिकतम असंयुक्त सेट समस्या 2 या अधिक आयामों का सामान्यीकरण है। यह सामान्यीकरण भी एनपी-पूर्ण है।

एक अन्य भिन्नता संसाधन आवंटन है, जिसमें संसाधनों k का उपयोग करके अंतराल s का एक सेट निर्धारित किया जाता है जिससे की k को न्यूनतम किया जा सकता हैं। अर्थात्, सभी अंतराल निर्धारित होने चाहिए, लेकिन उद्देश्य संसाधनों के उपयोग को कम करना है।

एक और भिन्नता तब होती है जब एकल प्रोसेसर के अतिरिक्त m प्रोसेसर होते हैं। अर्थात, अलग-अलग कार्य समानांतर में चल सकते हैं। इसके लिए समान-मशीन शेड्यूलिंग देखते हैं।

सिंगल-मशीन शेड्यूलिंग भी बहुत ही समान समस्या है।

स्रोत

↑ Kolen, A. (2007). "Interval scheduling: A survey". Naval Research Logistics. 54 (5): 530–543. doi:10.1002/nav.20231. S2CID 15288326.
↑ Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिज़ाइन. ISBN 978-0-321-29535-4.
↑ ^3.0 ^3.1 Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "A unified approach to approximating resource allocation and scheduling". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294.
↑ Kleinberg, Jon; Tardos, Eva (2006). Algorithm Design (1st ed.). Pearson. p. 254. ISBN 9780321295354.
↑ Nakajima, K.; Hakimi, S. L. (1982). "अलग-अलग शुरुआती समय के साथ शेड्यूलिंग कार्यों के लिए जटिलता परिणाम". Journal of Algorithms. 3 (4): 344. doi:10.1016/0196-6774(82)90030-X.
↑ ^6.0 ^6.1 Mark Keil, J. (1992). "अलग-अलग शुरुआती समय के साथ कार्यों को शेड्यूल करने की जटिलता पर". Operations Research Letters. 12 (5): 293–295. doi:10.1016/0167-6377(92)90087-j.
↑ Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998). Combinatorial Optimization : Algorithms and Complexity. Dover. ISBN 978-0-486-40258-1.
↑ ^8.0 ^8.1 ^8.2 ^8.3 Spieksma, F. C. R. (1999). "अंतराल शेड्यूलिंग समस्या की सन्निकटनता पर". Journal of Scheduling. 2 (5): 215–227. CiteSeerX 10.1.1.603.5538. doi:10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y. citing Kolen in personal communication
↑ Chuzhoy, J.; Ostrovsky, R.; Rabani, Y. (2006). "कार्य अंतराल चयन समस्या और संबंधित शेड्यूलिंग समस्याओं के लिए अनुमान एल्गोरिदम". Mathematics of Operations Research. 31 (4): 730. CiteSeerX 10.1.1.105.2578. doi:10.1287/moor.1060.0218.

[Survey-1] Kolen, A. (2007). "Interval scheduling: A survey". Naval Research Logistics. 54 (5): 530–543. doi:10.1002/nav.20231. S2CID 15288326.

[KleinbergTardos-2] Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिज़ाइन. ISBN 978-0-321-29535-4.

[:0-3] 3.0 ^3.1 Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "A unified approach to approximating resource allocation and scheduling". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294.

[4] Kleinberg, Jon; Tardos, Eva (2006). Algorithm Design (1st ed.). Pearson. p. 254. ISBN 9780321295354.

[NakajimaHakimi-5] Nakajima, K.; Hakimi, S. L. (1982). "अलग-अलग शुरुआती समय के साथ शेड्यूलिंग कार्यों के लिए जटिलता परिणाम". Journal of Algorithms. 3 (4): 344. doi:10.1016/0196-6774(82)90030-X.

[Keil-6] 6.0 ^6.1 Mark Keil, J. (1992). "अलग-अलग शुरुआती समय के साथ कार्यों को शेड्यूल करने की जटिलता पर". Operations Research Letters. 12 (5): 293–295. doi:10.1016/0167-6377(92)90087-j.

[7] Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998). Combinatorial Optimization : Algorithms and Complexity. Dover. ISBN 978-0-486-40258-1.

[Spieksma-8] 8.0 ^8.1 ^8.2 ^8.3 Spieksma, F. C. R. (1999). "अंतराल शेड्यूलिंग समस्या की सन्निकटनता पर". Journal of Scheduling. 2 (5): 215–227. CiteSeerX 10.1.1.603.5538. doi:10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y. citing Kolen in personal communication

[ChuzoiEtAl-9] Chuzhoy, J.; Ostrovsky, R.; Rabani, Y. (2006). "कार्य अंतराल चयन समस्या और संबंधित शेड्यूलिंग समस्याओं के लिए अनुमान एल्गोरिदम". Mathematics of Operations Research. 31 (4): 730. CiteSeerX 10.1.1.105.2578. doi:10.1287/moor.1060.0218.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 {{short description|Class of problems in computer science}}
-अंतराल शेड्यूलिंग [[कंप्यूटर विज्ञान]] में समस्याओं का एक वर्ग है, विशेष रूप से [[कलन विधि]] डिजाइन के क्षेत्र में। समस्याएँ कार्यों के एक समूह पर विचार करती हैं। प्रत्येक कार्य को एक ''अंतराल'' द्वारा दर्शाया जाता है जो उस समय का वर्णन करता है जिसमें इसे किसी मशीन द्वारा संसाधित करने की आवश्यकता होती है (या, समकक्ष, कुछ संसाधनों पर निर्धारित)। उदाहरण के लिए, कार्य A 2:00 से 5:00 तक चल सकता है, कार्य B 4:00 से 10:00 तक चल सकता है और कार्य C 9:00 से 11:00 तक चल सकता है। यदि मशीन/संसाधन पर कोई दो अंतराल ओवरलैप नहीं होते हैं तो अंतरालों का एक उपसमूह ''संगत'' होता है। उदाहरण के लिए, उपसमुच्चय {ए,सी} संगत है, जैसा कि उपसमुच्चय {बी} है; लेकिन न तो {ए,बी} और न ही {बी,सी} संगत उपसमुच्चय हैं, क्योंकि प्रत्येक उपसमुच्चय के भीतर संबंधित अंतराल ओवरलैप होते हैं।
+'''अंतराल शेड्यूलिंग''' [[कंप्यूटर विज्ञान]] में समस्याओं का वर्ग है, विशेष रूप से [[कलन विधि|एल्गोरिथ्म]] डिजाइन के क्षेत्र में। समस्याएँ कार्यों के समूह पर विचार करती हैं। प्रत्येक कार्य को एक ''अंतराल''  द्वारा दर्शाया जाता है जो उस समय का वर्णन करता है जिसमें इसे किसी मशीन द्वारा संसाधित (या, समकक्ष, कुछ संसाधनों पर निर्धारित) करने की आवश्यकता होती है। उदाहरण के लिए, कार्य A 2:00 से 5:00 तक चल सकता है, कार्य B 4:00 से 10:00 तक चल सकता है और कार्य C 9:00 से 11:00 तक चल सकता है। यदि मशीन/संसाधन पर कोई दो अंतराल ओवरलैप नहीं होते हैं तो अंतरालों का सबसेट ''संगत''  होता है। उदाहरण के लिए, उपसमुच्चय {A,C} संगत है, जैसा कि उपसमुच्चय {B} है; लेकिन न तो {A,B} और न ही {B,C} संगत उपसमुच्चय हैं, क्योंकि प्रत्येक सबसेट के अंदर संबंधित अंतराल ओवरलैप होते हैं।
-''अंतराल शेड्यूलिंग अधिकतमीकरण समस्या'' (आईएसएमपी) एक सबसे बड़ा संगत सेट ढूंढना है, यानी, अधिकतम आकार के गैर-अतिव्यापी अंतराल का एक सेट। यहां लक्ष्य अधिक से अधिक कार्यों को निष्पादित करना है, अर्थात [[THROUGHPUT]] को अधिकतम करना है। यह एक [[अंतराल ग्राफ]]़ में एक [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] खोजने के बराबर है।
+''अंतराल शेड्यूलिंग मक्सिमाईजेशन समस्या'' (ISMP) सबसे बड़ा संगत सेट ढूंढना है, अर्थात, अधिकतम आकार के गैर-अतिव्यापी अंतराल का सेट होता हैं। यहां लक्ष्य अधिक से अधिक कार्यों को निष्पादित करना है, अर्थात [[THROUGHPUT|थ्रूपुट]] को अधिकतम करना है। यह [[अंतराल ग्राफ]] में एक [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] ढूंढने के समान है।
-समस्या के सामान्यीकरण पर विचार करता है <math>k>1</math> मशीनें/संसाधन.<ref name=Survey>{{Cite journal | title = Interval scheduling: A survey| year = 2007| last1 = Kolen| first1 = A. | journal = Naval Research Logistics| volume = 54| issue = 5| pages = 530–543| doi = 10.1002/nav.20231| s2cid = 15288326}}</ref> यहां लक्ष्य खोजना है <math>k</math> संगत उपसमुच्चय जिनका संघ सबसे बड़ा है।
+<math>k>1</math> मशीनें/संसाधन समस्या के सामान्यीकरण पर विचार करता है।<ref name=Survey>{{Cite journal | title = Interval scheduling: A survey| year = 2007| last1 = Kolen| first1 = A. | journal = Naval Research Logistics| volume = 54| issue = 5| pages = 530–543| doi = 10.1002/nav.20231| s2cid = 15288326}}</ref> <math>k</math> संगत सबसेट जिनका सेट सबसे बड़ा है को यहां ढूंढ़ना लक्ष्य हैं।
-समस्या के उन्नत संस्करण में, अंतरालों को समूहों में विभाजित किया गया है। यदि कोई दो अंतराल ओवरलैप नहीं होते हैं, तो अंतराल का एक उपसमूह संगत होता है, और इसके अलावा, कोई भी दो अंतराल एक ही समूह से संबंधित नहीं होते हैं (यानी, उपसमूह में प्रत्येक समूह का अधिकतम एक ही प्रतिनिधि होता है)। अंतरालों का प्रत्येक समूह एक ही कार्य से मेल खाता है, और कई वैकल्पिक अंतरालों का प्रतिनिधित्व करता है जिसमें इसे निष्पादित किया जा सकता है।
+समस्या के उन्नत संस्करण में, अंतरालों को समूहों में विभाजित किया गया है। यदि कोई दो अंतराल ओवरलैप नहीं होते हैं, तो अंतराल का एक उपसमूह संगत होता है, और इसके अतिरिक्त, कोई भी दो अंतराल एक ही समूह से संबंधित नहीं होते हैं (अर्थात, सबसेट  में प्रत्येक समूह का अधिकतम एक ही प्रतिनिधि होता है)। अंतरालों का प्रत्येक समूह एक ही कार्य से मिलता हैं, और कई वैकल्पिक अंतरालों का प्रतिनिधित्व करता है जिसमें इसे निष्पादित किया जा सकता है।
-समूह अंतराल शेड्यूलिंग निर्णय समस्या (जीआईएसडीपी) यह तय करने के लिए है कि क्या कोई संगत सेट मौजूद है जिसमें सभी समूहों का प्रतिनिधित्व किया गया है। यहां लक्ष्य प्रत्येक समूह से एक प्रतिनिधि कार्य निष्पादित करना है। जीआईएसडीपीके जीआईएसडीपी का एक प्रतिबंधित संस्करण है जिसमें प्रत्येक समूह में अंतराल की संख्या अधिकतम k है।
+''समूह अंतराल शेड्यूलिंग निर्णय समस्या'' (GISDP) यह तय करने के लिए है कि क्या कोई संगत सेट उपस्थित है जिसमें सभी समूहों का प्रतिनिधित्व किया गया है। यहां लक्ष्य प्रत्येक समूह से प्रतिनिधि कार्य निष्पादित करना है। GISDP<small>K,</small> GISDP का प्रतिबंधित संस्करण है जिसमें प्रत्येक समूह में अंतराल की संख्या अधिकतम k है।
-समूह अंतराल शेड्यूलिंग अधिकतमकरण समस्या (जीआईएसएमपी) एक सबसे बड़ा संगत सेट ढूंढना है - अधिकतम आकार के गैर-अतिव्यापी प्रतिनिधियों का एक सेट। यहां लक्ष्य अधिक से अधिक समूहों से एक प्रतिनिधि कार्य निष्पादित करना है। GISMPk GISMP का एक प्रतिबंधित संस्करण है जिसमें प्रत्येक समूह में अंतराल की संख्या अधिकतम k है। इस समस्या को अक्सर JISPk कहा जाता है, जहां J का मतलब [[ नौकरी धारा ]] है।
+''समूह अंतराल शेड्यूलिंग अधिकतमकरण समस्या'' (GISMP) सबसे बड़ा संगत सेट ढूंढना है - अधिकतम आकार के गैर-अतिव्यापी प्रतिनिधियों का सेट हैं। यहां लक्ष्य अधिक से अधिक समूहों से प्रतिनिधि कार्य निष्पादित करना है। GISMPk, GISMP का एक प्रतिबंधित संस्करण है जिसमें प्रत्येक समूह में अंतराल की संख्या अधिकतम k है। इस समस्या को प्रायः JISP<small>k</small> कहा जाता है, जहां J का अर्थ  [[Index.php?title=जॉब|जॉब]] है।
-जीआईएसएमपी सबसे सामान्य समस्या है; अन्य दो समस्याओं को इसके विशेष मामलों के रूप में देखा जा सकता है:
+जीआईएसएमपी सबसे सामान्य समस्या है; अन्य दो समस्याओं को इसके विशेष स्थितियों के रूप में देखा जा सकता है:
-* ISMP वह विशेष मामला है जिसमें प्रत्येक कार्य अपने स्वयं के समूह से संबंधित होता है (अर्थात यह GISMP1 के बराबर होता है)।
+* ISMP वह विशेष स्थिति है जिसमें प्रत्येक कार्य अपने स्वयं के समूह से संबंधित होता है (अर्थात यह जीआईएसएम्पी1 के बराबर होता है)।
-* जीआईएसडीपी यह तय करने की समस्या है कि क्या अधिकतम वास्तव में समूहों की संख्या के बराबर है।
+* GISDP यह तय करने की समस्या है कि क्या अधिकतम वास्तव में समूहों की संख्या के बराबर है।
-इन सभी समस्याओं को प्रत्येक अंतराल के लिए एक वजन जोड़कर सामान्यीकृत किया जा सकता है, जो उस अंतराल में कार्य को निष्पादित करने से होने वाले लाभ का प्रतिनिधित्व करता है। फिर, लक्ष्य कुल वजन को अधिकतम करना है।
+इन सभी समस्याओं को प्रत्येक अंतराल के लिए भार जोड़कर सामान्यीकृत किया जा सकता है, जो उस अंतराल में कार्य को निष्पादित करने से होने वाले लाभ का प्रतिनिधित्व करता है। फिर, लक्ष्य कुल भार को अधिकतम करना है।
-ये सभी समस्याएं [[एकल-मशीन शेड्यूलिंग]] के विशेष मामले हैं, क्योंकि वे मानते हैं कि सभी कार्यों को एक ही प्रोसेसर पर चलना चाहिए। एकल-मशीन शेड्यूलिंग [[इष्टतम कार्य शेड्यूलिंग]] का एक विशेष मामला है।
+ये सभी समस्याएं [[एकल-मशीन शेड्यूलिंग]] के विशेष स्थितियाँ हैं, क्योंकि वे मानते हैं कि सभी कार्यों को एक ही प्रोसेसर पर चलना होता हैं। एकल-मशीन शेड्यूलिंग [[इष्टतम कार्य शेड्यूलिंग]] की विशेष स्थिति है।
 ==एकल-अंतराल शेड्यूलिंग अधिकतमीकरण==
 === अभारित ===
-कई एल्गोरिदम, जो पहली नज़र में आशाजनक लग सकते हैं, वास्तव में इष्टतम समाधान नहीं ढूंढते हैं:<ref name="KleinbergTardos">{{cite book|last=Kleinberg|first=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=एल्गोरिथम डिज़ाइन|author2=Tardos, Éva|year=2006|isbn=978-0-321-29535-4|url-access=registration}}</ref>
+कई एल्गोरिदम, जो पहली बार में आशाजनक लग सकते हैं, वास्तव में इष्टतम समाधान नहीं ढूंढते हैं:<ref name="KleinbergTardos">{{cite book|last=Kleinberg|first=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=एल्गोरिथम डिज़ाइन|author2=Tardos, Éva|year=2006|isbn=978-0-321-29535-4|url-access=registration}}</ref>
-* जल्द से जल्द शुरू होने वाले अंतराल का चयन करना एक इष्टतम समाधान नहीं है, क्योंकि यदि शुरुआती अंतराल बहुत लंबा होता है, तो इसे स्वीकार करने से हमें कई अन्य छोटे अनुरोधों को अस्वीकार करना पड़ेगा।
+* जल्द से जल्द प्रारम्भ होने वाले अंतराल का चयन करना इष्टतम समाधान नहीं है, क्योंकि यदि प्रारंभिक अंतराल बहुत लंबा होता है, तो इसे स्वीकार करने से हमें कई अन्य छोटे अनुरोधों को अस्वीकार करना पड़ता हैं।
 * सबसे छोटे अंतराल का चयन करना या सबसे कम विरोध वाले अंतराल का चयन करना भी इष्टतम नहीं है।
-निम्नलिखित [[लालची एल्गोरिदम]], जिसे [[सबसे पहले समयसीमा का पहला निर्धारण]] कहा जाता है, अनवेटेड सिंगल-इंटरवल शेड्यूलिंग के लिए इष्टतम समाधान ढूंढता है:
+निम्नलिखित [[लालची एल्गोरिदम|ग्रीडी एल्गोरिदम]], जिसे [[सबसे पहले समयसीमा का पहला निर्धारण|अर्लीएस्ट डेडलाइन फर्स्ट स्केड्यूलिंग]] कहा जाता है, अनवेटेड सिंगल-इंटरवल शेड्यूलिंग के लिए इष्टतम समाधान ढूंढता है:
-# जल्द से जल्द 'समाप्ति समय' के साथ अंतराल, x का चयन करें।
+# जल्द से जल्द '''<nowiki/>'फिनिशिंग टाइम'''' के साथ अंतराल, x का चयन करते हैं।
-# उम्मीदवार अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों को हटा दें।
+# कैंडिडेट अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों को हटा देते हैं।
-# उम्मीदवार अंतराल का सेट खाली होने तक दोहराएं।
+# कैंडिडेट अंतराल का सेट रिक्त होने तक दुहराया जाता हैं।
-जब भी हम चरण 1 पर एक अंतराल का चयन करते हैं, तो हमें चरण 2 में कई अंतरालों को हटाना पड़ सकता है। हालाँकि, ये सभी अंतराल आवश्यक रूप से x के समापन समय को पार करते हैं, और इस प्रकार वे सभी एक दूसरे को पार करते हैं। इसलिए, इनमें से अधिकतम 1 अंतराल इष्टतम समाधान में हो सकता है। इसलिए, इष्टतम समाधान में प्रत्येक अंतराल के लिए, लालची समाधान में एक अंतराल होता है। इससे साबित होता है कि लालची एल्गोरिदम वास्तव में एक इष्टतम समाधान ढूंढता है।
+जब भी हम चरण 1 पर अंतराल का चयन करते हैं, तो हमें चरण 2 में कई अंतरालों को हटाना पड़ सकता है। यद्यपि की, ये सभी अंतराल आवश्यक रूप से x के समापन समय को पार करते हैं, और इस प्रकार वे सभी एक दूसरे को पार करते हैं। इसलिए, इनमें से अधिकतम 1 अंतराल इष्टतम समाधान में हो सकता है। इसलिए, इष्टतम समाधान में प्रत्येक अंतराल के लिए, ग्रीडी समाधान में एक अंतराल होता है। इससे सिद्ध होता है कि ग्रीडी एल्गोरिदम वास्तव में इष्टतम समाधान ढूंढता है।
 चार्जिंग तर्क द्वारा एक अधिक औपचारिक व्याख्या दी गई है।
-लालची एल्गोरिदम को समय ओ (एन लॉग एन) में निष्पादित किया जा सकता है, जहां एन प्रीप्रोसेसिंग चरण का उपयोग करके कार्यों की संख्या है जिसमें कार्यों को उनके समापन समय के अनुसार क्रमबद्ध किया जाता है।
+ग्रीडी एल्गोरिदम को समय O (''n log n'') में निष्पादित किया जा सकता है, जहां n प्रीप्रोसेसिंग चरण का उपयोग करके कार्यों की संख्या है जिसमें कार्यों को उनके समापन समय के अनुसार क्रमबद्ध किया जाता है।
 === भारित ===
-जब अंतरालों में भार होता है, तो समस्या एक अंतराल ग्राफ़ में अधिकतम-भार स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर होती है। इसे बहुपद समय में हल किया जा सकता है।<ref name=":0">{{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>
+जब अंतरालों में भार होता है, तो समस्या अंतराल ग्राफ़ में अधिकतम-भार स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर होती है। इसे बहुपद समय में हल किया जा सकता है।<ref name=":0">{{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=A unified approach to approximating resource allocation and scheduling|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>
-Θ(n) समय में एकल अंतराल अनुसूची का अधिकतम भार ज्ञात करने के लिए, निम्नलिखित छद्म कोड निष्पादित करें:
-<सिंटैक्सहाइलाइट लाइन = 1 लैंग = सी >
+To find the maximum weight of a single interval schedule in Θ(n) time, perform the following pseudocode:
-// वैक्टर पहले से ही शुरुआती से नवीनतम समाप्ति समय तक क्रमबद्ध हैं।
+<syntaxhighlight line="1" lang="c">
-int v[numOfVectors + 1]; // अंतराल वैक्टर की सूची
+// The vectors are already sorted from earliest to latest finish time.
-int w[numOfVectors + 1]; // w[j], v[j] का भार है।
+int v[numOfVectors + 1]; // list of interval vectors
-int p[numOfVectors + 1]; // p[j] उन सदिशों में से # है जो v[j] के प्रारंभ होने से पहले समाप्त होते हैं।
+int w[numOfVectors + 1]; // w[j] is the weight for v[j].
+int p[numOfVectors + 1]; // p[j] is the # of vectors that end before v[j] begins.
 int M[numOfVectors + 1];
-int अंतिम शेड्यूल[];
+int finalSchedule[];
-//v[0] मौजूद नहीं है. पहला अंतराल वेक्टर v[1] पर सेट है।
+// v[0] does not exist. The first interval vector is set to v[1].
-डब्ल्यू[0] = 0; पी[0] = 0; एम[0] = 0;
+w[0] = 0; p[0] = 0; M[0] = 0;
 for (int i = 1; i < numOfVector + 1; i++) {
-     एम[आई] = अधिकतम(डब्ल्यू[आई] + एम[पी[आई, एम[आई - 1]);
+     M[i] = max(w[i] + M[p[i]], M[i - 1]);
 }
-// शेड्यूल का अधिकतम भार M[numOfVectors + 1] के बराबर है।
+// The maximum weight of the schedule is equal to M[numOfVectors + 1].
-अनुसूची (जे) {
+schedule (j) {
-     अगर (जे == 0) {वापसी; }
+     if (j == 0) { return; }
-     अन्यथा यदि (w[j] + M[p[j >= M[j - 1]){
+     else if (w[j] + M[p[j]] >= M[j - 1]){
-         प्रीपेन्ड(v[j], फाइनलशेड्यूल); // शेड्यूल करने के लिए v[j] को जोड़ता है।
+         prepend(v[j], finalSchedule); // prepends v[j] to schedule.
-         अनुसूची(पी[जे]);
+         schedule(p[j]);
-     } अन्यथा { शेड्यूल(जे - 1); }
+     } else { schedule(j - 1); }
 }
-</सिंटैक्सहाइलाइट><ref>{{Cite book |last1=Kleinberg |first1=Jon |title=एल्गोरिथम डिज़ाइन|last2=Tardos |first2=Eva |publisher=Pearson |year=2006 |isbn=9780321295354 |edition=1st |pages=254}}</ref>
+</syntaxhighlight><ref>{{Cite book |last1=Kleinberg |first1=Jon |title=Algorithm Design |last2=Tardos |first2=Eva |publisher=Pearson |year=2006 |isbn=9780321295354 |edition=1st |pages=254}}</ref>
+[[index.php?title=Category:Navigational boxes| ]]
+[[index.php?title=Category:Template documentation pages|Documentation/doc]]
@@ Line 70: / Line 80: @@
 === एनपी-पूर्ण जब कुछ समूहों में 3 या अधिक अंतराल होते हैं ===
-जीआईएसडीपीके एनपी-पूर्ण है जब <math>k\geq 3</math>,<ref name=NakajimaHakimi>{{Cite journal | doi = 10.1016/0196-6774(82)90030-X| title = अलग-अलग शुरुआती समय के साथ शेड्यूलिंग कार्यों के लिए जटिलता परिणाम| year = 1982| last1 = Nakajima | first1 = K. | last2 = Hakimi | first2 = S. L. | journal = Journal of Algorithms| volume = 3| issue = 4| pages = 344}}</ref> तब भी जब सभी अंतरालों की लंबाई समान हो।<ref name=Keil>{{Cite journal | doi = 10.1016/0167-6377(92)90087-j| title = अलग-अलग शुरुआती समय के साथ कार्यों को शेड्यूल करने की जटिलता पर| year = 1992| last1 = Mark Keil | first1 = J. | journal = Operations Research Letters| volume = 12| issue = 5| pages = 293–295}}</ref> इसे [[बूलियन संतुष्टि समस्या]] के निम्नलिखित संस्करण में कमी करके दिखाया जा सकता है, जो दिखाया गया था <ref>{{Cite book|last1=Papadimitriou|first1=Christos H.|title=Combinatorial Optimization : Algorithms and Complexity|last2=Steiglitz|first2=Kenneth|date=July 1998|publisher=Dover|isbn=978-0-486-40258-1|author2-link=Kenneth Steiglitz}}</ref> अप्रतिबंधित संस्करण की तरह ही एनपी-पूर्ण होना।
+GISDPk एनपी-पूर्ण है जब <math>k\geq 3</math>,<ref name=NakajimaHakimi>{{Cite journal | doi = 10.1016/0196-6774(82)90030-X| title = अलग-अलग शुरुआती समय के साथ शेड्यूलिंग कार्यों के लिए जटिलता परिणाम| year = 1982| last1 = Nakajima | first1 = K. | last2 = Hakimi | first2 = S. L. | journal = Journal of Algorithms| volume = 3| issue = 4| pages = 344}}</ref> तब भी जब सभी अंतरालों की लंबाई समान होती हैं।<ref name=Keil>{{Cite journal | doi = 10.1016/0167-6377(92)90087-j| title = अलग-अलग शुरुआती समय के साथ कार्यों को शेड्यूल करने की जटिलता पर| year = 1992| last1 = Mark Keil | first1 = J. | journal = Operations Research Letters| volume = 12| issue = 5| pages = 293–295}}</ref> इसे [[बूलियन संतुष्टि समस्या]] के निम्नलिखित संस्करण में कमी करके दिखाया जा सकता है, जो <ref>{{Cite book|last1=Papadimitriou|first1=Christos H.|title=Combinatorial Optimization : Algorithms and Complexity|last2=Steiglitz|first2=Kenneth|date=July 1998|publisher=Dover|isbn=978-0-486-40258-1|author2-link=Kenneth Steiglitz}}</ref> अप्रतिबंधित संस्करण की तरह ही एनपी-पूर्ण होना में दिखाया गया था।
-::होने देना <math>X = \{x_1, x_2, \dots, x_p\}</math> बूलियन वेरिएबल्स का एक सेट बनें। होने देना <math>C = \{c_1, c_2, \dots, c_q\}</math> X पर उपवाक्यों का एक समूह इस प्रकार हो कि (1) C में प्रत्येक उपवाक्य में अधिकतम तीन अक्षर हों और (2) प्रत्येक चर C में एक या दो बार सकारात्मक और एक बार नकारात्मक रूप से प्रकट होने के लिए प्रतिबंधित हो। यह तय करें कि क्या
+::माना <math>X = \{x_1, x_2, \dots, x_p\}</math> बूलियन वेरिएबल्स का सेट बनता हैं। माना <math>C = \{c_1, c_2, \dots, c_q\}</math> X पर उपवाक्यों का समूह इस प्रकार हो कि (1) C में प्रत्येक उपवाक्य में अधिकतम तीन अक्षर हों और (2) प्रत्येक चर C में एक या दो बार धनात्मक और एक बार ऋणात्मक रूप से प्रकट होने के लिए प्रतिबंधित हो। यह तय करें कि क्या X का चरों में असाइनमेंट हैं क्योंकि C में प्रत्येक क्लॉज़ न्यूनतम एक सही शब्दसः होता हैं।
-इस संतुष्टि समस्या के एक उदाहरण को देखते हुए, GISDP के निम्नलिखित उदाहरण का निर्माण करें। सभी अंतरालों की लंबाई 3 है, इसलिए प्रत्येक अंतराल को उसके शुरुआती समय से दर्शाना पर्याप्त है:
+इस संतुष्टि समस्या के एक उदाहरण को देखते हुए, GISDP के निम्नलिखित उदाहरण का निर्माण करते हैं। सभी अंतरालों की लंबाई 3 है, इसलिए प्रत्येक अंतराल को उसके प्रारंभिक समय से दर्शाना पर्याप्त है:
-* प्रत्येक चर के लिए <math>x_i</math> (के लिए {{gaps|''i''|{{=}}|1,...,''p''}}), दो अंतरालों वाला एक समूह बनाएं: एक प्रारंभ से <math>50i-10</math> (असाइनमेंट का प्रतिनिधित्व करते हुए <math>x_i = \mathrm{false}</math>) और दूसरा शुरू हो रहा है <math>50i+10</math> (असाइनमेंट का प्रतिनिधित्व करते हुए <math>x_i = \mathrm{true}</math>).
+* प्रत्येक चर के लिए <math>x_i</math> (के लिए {{gaps|''i''|{{=}}|1,...,''p''}}), दो अंतरालों वाला समूह बनाएं: प्रारंभ से <math>50i-10</math> (असाइनमेंट का प्रतिनिधित्व करते हुए <math>x_i = \mathrm{false}</math>) और दूसरा प्रारम्भ <math>50i+10</math> हो रहा है (असाइनमेंट का प्रतिनिधित्व करते हुए <math>x_i = \mathrm{true}</math>)।
-* प्रत्येक खंड के लिए <math>c_j</math> (के लिए {{gaps|''j''|{{=}}|1,...,''q''}}), निम्नलिखित अंतराल के साथ एक समूह बनाएं:
+* प्रत्येक खंड के लिए <math>c_j</math> (के लिए {{gaps|''j''|{{=}}|1,...,''q''}}), निम्नलिखित अंतराल के साथ एक समूह बनाते हैं:
-** प्रत्येक चर के लिए <math>x_i</math> यह सी में पहली बार सकारात्मक रूप से प्रकट होता है {{--}} से शुरू होने वाला अंतराल <math>50i-12</math>.
+** प्रत्येक चर के लिए <math>x_i</math> यह C में पहली बार धनात्मक रूप से प्रकट होता है {{--}} से प्रारम्भ होने वाला अंतराल <math>50i-12</math>.
-** प्रत्येक चर के लिए <math>x_i</math> जो सी में दूसरी बार सकारात्मक रूप से प्रकट होता है {{--}} से शुरू होने वाला अंतराल <math>50i-8</math>. ध्यान दें कि ये दोनों अंतराल अंतराल को काटते हैं <math>50i-10</math>, के साथ जुड़े <math>x_i = \mathrm{false}</math>.
+** प्रत्येक चर के लिए <math>x_i</math> जो C में दूसरी बार धनात्मक रूप से प्रकट होता है {{--}} से प्रारम्भ होने वाला अंतराल <math>50i-8</math> होता हैं। ध्यान दें कि ये दोनों अंतराल <math>50i-10</math> अंतराल को काटते हैं, जो <math>x_i = \mathrm{false}</math>के साथ जुड़े होते हैं।
-** प्रत्येक चर के लिए <math>x_i</math> जो नकारात्मक रूप से प्रकट होता है - एक अंतराल जो शुरू होता है <math>50i+8</math>. यह अंतराल अंतराल को प्रतिच्छेद करता है <math>50i+10</math> के साथ जुड़े <math>x_i=\text{true}</math>.
+** प्रत्येक चर के लिए <math>x_i</math> जो ऋणात्मक रूप से प्रकट होता है - एक अंतराल जो <math>50i+8</math> से प्रारम्भ होता है। यह अंतराल <math>50i+10</math> अंतराल को प्रतिच्छेद करता है, जो <math>x_i=\text{true}</math>के साथ जुड़े होते हैं।
-ध्यान दें कि विभिन्न उपवाक्यों से जुड़े समूहों में अंतरालों के बीच कोई ओवरलैप नहीं है। यह सुनिश्चित किया जाता है क्योंकि एक चर अधिकतम दो बार सकारात्मक और एक बार नकारात्मक रूप में प्रकट होता है।
+ध्यान दें कि विभिन्न उपवाक्यों से जुड़े समूहों में अंतरालों के बीच कोई ओवरलैप नहीं है। यह सुनिश्चित किया जाता है क्योंकि एक चर अधिकतम दो बार धनात्मक और एक बार ऋणात्मक रूप में प्रकट होता है।
-निर्मित जीआईएसडीपी के पास एक व्यवहार्य समाधान है (यानी एक शेड्यूलिंग जिसमें प्रत्येक समूह का प्रतिनिधित्व किया जाता है), यदि और केवल तभी जब बूलियन क्लॉज के दिए गए सेट में एक संतोषजनक असाइनमेंट हो। इसलिए GISDP3 NP-पूर्ण है, और इसी प्रकार प्रत्येक के लिए GISDPk भी है <math>k\geq 3</math>.
+निर्मित GISDP के पास व्यवहार्य समाधान है (अर्थात एक शेड्यूलिंग जिसमें प्रत्येक समूह का प्रतिनिधित्व किया जाता है), यदि और केवल तभी जब बूलियन क्लॉज के दिए गए सेट में एक संतोषजनक असाइनमेंट होता हैं। इसलिए GISDP3 एनपी-पूर्ण है, और इसी प्रकार प्रत्येक <math>k\geq 3</math> के लिए GISDPk भी है।
 === बहुपद जब सभी समूहों में अधिकतम 2 अंतराल हों ===
-GISDP2 को 2-संतुष्टि समस्या में निम्नलिखित कमी करके बहुपद समय पर हल किया जा सकता है:<ref name=Keil />* प्रत्येक समूह के लिए मैं दो चर बनाता हूं, जो उसके दो अंतरालों का प्रतिनिधित्व करते हैं: <math>x_i</math> और <math>y_i</math>.
+GISDP2 को 2-संतुष्टि समस्या में निम्नलिखित कमी करके बहुपद समय पर हल किया जा सकता है:<ref name=Keil />*
-* प्रत्येक समूह के लिए, खंड बनाएं: <math>x_i \cup y_i</math> और <math>\neg{x_i} \cup \neg{y_i}</math>, जो इस दावे का प्रतिनिधित्व करता है कि इन दो अंतरालों में से वास्तव में एक का चयन किया जाना चाहिए।
-* प्रत्येक दो प्रतिच्छेदी अंतरालों के लिए (अर्थात <math>x_i</math> और <math>y_j</math>) उपवाक्य बनाएं: <math>\neg{x_i} \cup \neg{y_j}</math>, जो इस दावे का प्रतिनिधित्व करता है कि इन दो अंतरालों में से अधिक से अधिक एक का चयन किया जाना चाहिए।
+'''<big>.</big>''' प्रत्येक समूह के लिए, दो चर बनाते हैं, जो उसके दो अंतरालों <math>x_i</math> और <math>y_i</math> का प्रतिनिधित्व करते हैं:
+* प्रत्येक समूह के लिए, <math>x_i \cup y_i</math> और <math>\neg{x_i} \cup \neg{y_i}</math> खंड बनाएं: जो इस कथन का प्रतिनिधित्व करता है कि इन दो अंतरालों में से वास्तव में एक का चयन किया जाता हैं।
+* प्रत्येक दो प्रतिच्छेदी अंतरालों के लिए (अर्थात <math>x_i</math> और <math>y_j</math>) उपवाक्य बनाएं: <math>\neg{x_i} \cup \neg{y_j}</math>, जो इस कथन का प्रतिनिधित्व करता है कि इन दो अंतरालों में से अधिक से अधिक एक का चयन किया जाता हैं।
-इस निर्माण में अधिकतम O(n) शामिल है<sup>2</sup>) खंड (अंतराल के बीच प्रत्येक प्रतिच्छेदन के लिए एक, साथ ही प्रत्येक समूह के लिए दो)। प्रत्येक उपवाक्य में 2 अक्षर हैं। ऐसे सूत्रों की संतुष्टि खंडों की संख्या में रैखिक समय में तय की जा सकती है (2-एसएटी देखें)। इसलिए, GISDP2 को बहुपद समय में हल किया जा सकता है।
+इस निर्माण में अधिकतम O(n<sup>2</sup>) सम्मलित है खंड (अंतराल के बीच प्रत्येक प्रतिच्छेदन के लिए एक, साथ ही प्रत्येक समूह के लिए दो)। प्रत्येक उपवाक्य में 2 अक्षर हैं। ऐसे सूत्रों की संतुष्टि खंडों की संख्या में रैखिक समय में तय की जा सकती है (2-SAT देखें)। इसलिए, GISDP2 को बहुपद समय में हल किया जा सकता है।
 ==समूह अंतराल निर्धारण अधिकतमकरण==
-=== मैक्सएसएनपी-पूर्ण जब कुछ समूहों में 2 या अधिक अंतराल होते हैं ===
+=== MaxSNP-पूर्ण जब कुछ समूहों में 2 या अधिक अंतराल होते हैं ===
-GISMPk तब भी NP-पूर्ण है <math>k\geq 2</math>.<ref name=Spieksma>{{Cite journal | last1 = Spieksma | first1 = F. C. R. | title = अंतराल शेड्यूलिंग समस्या की सन्निकटनता पर| doi = 10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y | journal = Journal of Scheduling | volume = 2 | issue = 5 | pages = 215–227 | year = 1999 | citeseerx = 10.1.1.603.5538 }} citing Kolen in personal communication</ref>
+GISMPk जब <math>k\geq 2</math> भी एनपी-पूर्ण है। <ref name=Spieksma>{{Cite journal | last1 = Spieksma | first1 = F. C. R. | title = अंतराल शेड्यूलिंग समस्या की सन्निकटनता पर| doi = 10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y | journal = Journal of Scheduling | volume = 2 | issue = 5 | pages = 215–227 | year = 1999 | citeseerx = 10.1.1.603.5538 }} citing Kolen in personal communication</ref>
-इसके अलावा, GISMPk [[MaxSNP]]-पूर्ण है, यानी, इसमें PTAS नहीं है जब तक कि P=NP न हो। इसे MAX 3-SAT-3 से GISMP2 तक अनुमानित-संरक्षण कमी दिखाकर सिद्ध किया जा सकता है।<ref name=Spieksma/>
+इसके अतिरिक्त, GISMPk MaxSNP-पूर्ण है, अर्थात, इसमें PTAS नहीं है जब तक कि P=NP नहीं होता हैं। इसे Max 3-SAT-3 से GISMP2 तक अनुमानित-संरक्षण कमी दिखाकर सिद्ध किया जा सकता है।<ref name="Spieksma" />
+=== बहुपद 2-सन्निकटन ===
+निम्नलिखित ग्रीडी एल्गोरिदम एक समाधान ढूंढता है जिसमें अंतराल की इष्टतम संख्या का कम से कम 1/2 सम्मलित होता है:<ref name=Spieksma/>#
-=== बहुपद 2-सन्निकटन ===
+.जल्द से जल्द '''<nowiki/>'फिनिशिंग टाइम'''' के साथ अंतराल, x का चयन करते हैं।
-निम्नलिखित लालची एल्गोरिदम एक समाधान ढूंढता है जिसमें अंतराल की इष्टतम संख्या का कम से कम 1/2 शामिल होता है:<ref name=Spieksma/># जल्द से जल्द 'समाप्ति समय' के साथ अंतराल, x का चयन करें।
+# कैंडिडेट अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों और x के एक ही समूह के सभी अंतरालों को हटा देते हैं।
-# उम्मीदवार अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों और x के एक ही समूह के सभी अंतरालों को हटा दें।
+# तब तक जारी रखें जब तक कि कैंडिडेट अंतराल का सेट खाली नहीं हो जाता हैं।
-# तब तक जारी रखें जब तक कि उम्मीदवार अंतराल का सेट खाली न हो जाए।
-एक औपचारिक स्पष्टीकरण चार्जिंग तर्क#जॉब इंटरवल शेड्यूलिंग समस्या द्वारा दिया गया है।
+एक औपचारिक स्पष्टीकरण चार्जिंग आर्गुमेंट द्वारा दिया गया है।
-का सन्निकटन कारक सख्त है। उदाहरण के लिए, GISMP2 के निम्नलिखित उदाहरण में:
+का सन्निकटन कारक टाइट है। उदाहरण के लिए, GISMP2 के निम्नलिखित उदाहरण में:
 * समूह #1: {[0..2], [4..6]}
 * समूह #2: {[1..3]}
-लालची एल्गोरिदम समूह #1 से केवल 1 अंतराल [0..2] का चयन करता है, जबकि एक इष्टतम शेड्यूलिंग समूह #2 से [1..3] और फिर समूह #1 से [4..6] का चयन करना है।
+ग्रीडी एल्गोरिदम समूह #1 से केवल 1 अंतराल [0..2] का चयन करता है, जबकि एक इष्टतम शेड्यूलिंग समूह #2 से [1..3] और फिर समूह #1 से [4..6] का चयन करना है।
-एक अधिक सामान्य सन्निकटन एल्गोरिथ्म भारित मामले के लिए 2-कारक सन्निकटन प्राप्त करता है।<ref name=":0" />
+एक अधिक सामान्य सन्निकटन एल्गोरिथ्म भारित स्थिति के लिए 2-कारक सन्निकटन प्राप्त करता है।<ref name=":0" />
 === एलपी-आधारित सन्निकटन एल्गोरिदम ===
-[[रैखिक प्रोग्रामिंग विश्राम]] की तकनीक का उपयोग करके, थोड़े बेहतर सन्निकटन कारकों के साथ इष्टतम शेड्यूलिंग का अनुमान लगाना संभव है। जब k बड़ा होता है तो ऐसे पहले एल्गोरिदम का सन्निकटन अनुपात स्पर्शोन्मुख रूप से 2 होता है, लेकिन जब k=2 होता है तो एल्गोरिथ्म 5/3 का सन्निकटन अनुपात प्राप्त करता है।<ref name=Spieksma/>मनमाना k के लिए सन्निकटन कारक को बाद में 1.582 तक सुधार दिया गया।<ref name="ChuzoiEtAl">{{Cite journal | doi = 10.1287/moor.1060.0218| title = कार्य अंतराल चयन समस्या और संबंधित शेड्यूलिंग समस्याओं के लिए अनुमान एल्गोरिदम| journal = Mathematics of Operations Research| volume = 31| issue = 4| pages = 730| year = 2006| last1 = Chuzhoy | first1 = J. | author1-link = Julia Chuzhoy | last2 = Ostrovsky | first2 = R. | author2-link = Rafail Ostrovsky| last3 = Rabani | first3 = Y. | citeseerx = 10.1.1.105.2578}}</ref>
+[[रैखिक प्रोग्रामिंग विश्राम|लीनियर प्रोग्रामिंग रिलैक्सेशन]] की तकनीक का उपयोग करके, थोड़े अच्छे सन्निकटन कारकों के साथ इष्टतम शेड्यूलिंग का अनुमान लगाना संभव है। जब k बड़ा होता है तो ऐसे पहले एल्गोरिदम का सन्निकटन अनुपात स्पर्शोन्मुख रूप से 2 होता है, लेकिन जब k=2 होता है तो एल्गोरिथ्म 5/3 का सन्निकटन अनुपात प्राप्त करता है।<ref name=Spieksma/> यादृच्छिक k के लिए सन्निकटन कारक को बाद में 1.582 तक सुधार दिया गया हैं।<ref name="ChuzoiEtAl">{{Cite journal | doi = 10.1287/moor.1060.0218| title = कार्य अंतराल चयन समस्या और संबंधित शेड्यूलिंग समस्याओं के लिए अनुमान एल्गोरिदम| journal = Mathematics of Operations Research| volume = 31| issue = 4| pages = 730| year = 2006| last1 = Chuzhoy | first1 = J. | author1-link = Julia Chuzhoy | last2 = Ostrovsky | first2 = R. | author2-link = Rafail Ostrovsky| last3 = Rabani | first3 = Y. | citeseerx = 10.1.1.105.2578}}</ref>
 ==संबंधित समस्याएँ==
-एक अंतराल शेड्यूलिंग समस्या को एक [[प्रतिच्छेदन ग्राफ]] द्वारा वर्णित किया जा सकता है, जहां प्रत्येक शीर्ष एक अंतराल है, और दो शीर्षों के बीच एक किनारा होता है यदि और केवल यदि उनके अंतराल ओवरलैप होते हैं। इस प्रतिनिधित्व में, अंतराल शेड्यूलिंग समस्या इस प्रतिच्छेदन ग्राफ में अधिकतम स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर है। सामान्य ग्राफ़ में अधिकतम स्वतंत्र सेट ढूंढना एनपी-कठिन है, लेकिन इसे प्रतिच्छेदन ग्राफ़ (आईएसएमपी) के विशेष मामले में बहुपद समय में किया जा सकता है।
+एक अंतराल शेड्यूलिंग समस्या को [[प्रतिच्छेदन ग्राफ]] द्वारा वर्णित किया जा सकता है, जहां प्रत्येक शीर्ष अंतराल है, और दो शीर्षों के बीच एक कोंड़बिन्दु होता है यदि और केवल यदि उनके अंतराल ओवरलैप होते हैं। इस प्रतिनिधित्व में, अंतराल शेड्यूलिंग समस्या इस प्रतिच्छेदन ग्राफ में अधिकतम स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर है। सामान्य ग्राफ़ में अधिकतम स्वतंत्र सेट ढूंढना एनपी-कठिन है, लेकिन इसे प्रतिच्छेदन ग्राफ़ (ISMP) के विशेष स्थिति में बहुपद समय में किया जा सकता है।
-एक समूह-अंतराल शेड्यूलिंग समस्या (जीआईएसएमपीके) को एक समान अंतराल-प्रतिच्छेदन ग्राफ द्वारा वर्णित किया जा सकता है, जिसमें एक ही समूह के प्रत्येक दो अंतराल के बीच अतिरिक्त किनारे होते हैं, यानी, यह एक अंतराल ग्राफ का किनारा संघ है और एक ग्राफ जिसमें आकार के एन असंयुक्त क्लिक्स शामिल हैं।
+समूह-अंतराल शेड्यूलिंग समस्या (GISMPk) को एक समान अंतराल-प्रतिच्छेदन ग्राफ द्वारा वर्णित किया जा सकता है, जिसमें एक ही समूह के प्रत्येक दो अंतराल के बीच अतिरिक्त कोंड़बिन्दु होते हैं, अर्थात, यह एक अंतराल ग्राफ का कोंड़बिन्दु संघ है और एक ग्राफ जिसमें आकार के n असंयुक्त क्लिक्स सम्मलित हैं।
 ==भिन्नताएँ==
-शेड्यूलिंग एल्गोरिदम का एक महत्वपूर्ण वर्ग गतिशील प्राथमिकता एल्गोरिदम का वर्ग है। जब कोई भी अंतराल ओवरलैप नहीं होता है तो इष्टतम समाधान तुच्छ होता है। गैर-भारित संस्करण के लिए इष्टतम को सबसे पहले समय सीमा निर्धारण के साथ पाया जा सकता है। भारित अंतराल शेड्यूलिंग एक सामान्यीकरण है जहां प्रत्येक निष्पादित कार्य के लिए एक मान निर्दिष्ट किया जाता है और लक्ष्य कुल मूल्य को अधिकतम करना है। समाधान का अद्वितीय होना आवश्यक नहीं है.
+शेड्यूलिंग एल्गोरिदम का महत्वपूर्ण वर्ग गतिशील प्राथमिकता एल्गोरिदम का वर्ग है। जब कोई भी अंतराल ओवरलैप नहीं होता है तो इष्टतम समाधान निम्न होता है। अभारित संस्करण के लिए इष्टतम को सबसे पहले समय सीमा निर्धारण के साथ पाया जा सकता है। भारित अंतराल शेड्यूलिंग एक सामान्यीकरण है जहां प्रत्येक निष्पादित कार्य के लिए एक मान निर्दिष्ट किया जाता है और लक्ष्य कुल मूल्य को अधिकतम करना है। समाधान का अद्वितीय होना आवश्यक नहीं है।
 अंतराल शेड्यूलिंग समस्या एक-आयामी है - केवल समय आयाम प्रासंगिक है। [[अधिकतम असंयुक्त सेट]] समस्या 2 या अधिक आयामों का सामान्यीकरण है। यह सामान्यीकरण भी एनपी-पूर्ण है।
-एक अन्य भिन्नता संसाधन आवंटन है, जिसमें संसाधनों k का उपयोग करके अंतराल s का एक सेट निर्धारित किया जाता है ताकि k को न्यूनतम किया जा सके। अर्थात्, सभी अंतराल निर्धारित होने चाहिए, लेकिन उद्देश्य संसाधनों के उपयोग को कम करना है।
+एक अन्य भिन्नता संसाधन आवंटन है, जिसमें संसाधनों k का उपयोग करके अंतराल s का एक सेट निर्धारित किया जाता है जिससे की k को न्यूनतम किया जा सकता हैं। अर्थात्, सभी अंतराल निर्धारित होने चाहिए, लेकिन उद्देश्य संसाधनों के उपयोग को कम करना है।
-एक और भिन्नता तब होती है जब एकल प्रोसेसर के बजाय एम प्रोसेसर होते हैं। यानी, अलग-अलग कार्य समानांतर में चल सकते हैं। [[समान-मशीन शेड्यूलिंग]] देखें।
+एक और भिन्नता तब होती है जब एकल प्रोसेसर के अतिरिक्त ''m'' प्रोसेसर होते हैं। अर्थात, अलग-अलग कार्य समानांतर में चल सकते हैं। इसके लिए [[समान-मशीन शेड्यूलिंग]] देखते हैं।
-सिंगल-मशीन शेड्यूलिंग भी एक बहुत ही समान समस्या है।
+सिंगल-मशीन शेड्यूलिंग भी बहुत ही समान समस्या है।
 ==स्रोत==
 {{reflist}}
-{{Scheduling problems}}
-श्रेणी:इष्टतम शेड्यूलिंग
-[[Category: Machine Translated Page]]
+[[Category:Collapse templates]]
 [[Category:Created On 25/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]

Anonymous

Search

अंतराल निर्धारण: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:19, 21 August 2023

Contents