अंतराल निर्धारण

अंतराल शेड्यूलिंग कंप्यूटर विज्ञान में समस्याओं का वर्ग है, विशेष रूप से एल्गोरिथ्म डिजाइन के क्षेत्र में। समस्याएँ कार्यों के समूह पर विचार करती हैं। प्रत्येक कार्य को एक अंतराल द्वारा दर्शाया जाता है जो उस समय का वर्णन करता है जिसमें इसे किसी मशीन द्वारा संसाधित (या, समकक्ष, कुछ संसाधनों पर निर्धारित) करने की आवश्यकता होती है। उदाहरण के लिए, कार्य 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$ मशीनें/संसाधन समस्या के सामान्यीकरण पर विचार करता है। $k$ संगत सबसेट जिनका सेट सबसे बड़ा है को यहां ढूंढ़ना लक्ष्य हैं।

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

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

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

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

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

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

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

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

अभारित

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

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

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

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

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

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

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

भारित

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

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); }
}

Documentation/doc

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

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

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

माना $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}$ (के लिए 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-संतुष्टि समस्या में निम्नलिखित कमी करके बहुपद समय पर हल किया जा सकता है:*

. प्रत्येक समूह के लिए, दो चर बनाते हैं, जो उसके दो अंतरालों $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$ भी एनपी-पूर्ण है।

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

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

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

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

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

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

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

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

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

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

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

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

संबंधित समस्याएँ

एक अंतराल शेड्यूलिंग समस्या को प्रतिच्छेदन ग्राफ द्वारा वर्णित किया जा सकता है, जहां प्रत्येक शीर्ष अंतराल है, और दो शीर्षों के बीच एक कोंड़बिन्दु होता है यदि और केवल यदि उनके अंतराल ओवरलैप होते हैं। इस प्रतिनिधित्व में, अंतराल शेड्यूलिंग समस्या इस प्रतिच्छेदन ग्राफ में अधिकतम स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर है। सामान्य ग्राफ़ में अधिकतम स्वतंत्र सेट ढूंढना एनपी-कठिन है, लेकिन इसे प्रतिच्छेदन ग्राफ़ (ISMP) के विशेष स्थिति में बहुपद समय में किया जा सकता है।

समूह-अंतराल शेड्यूलिंग समस्या (GISMPk) को एक समान अंतराल-प्रतिच्छेदन ग्राफ द्वारा वर्णित किया जा सकता है, जिसमें एक ही समूह के प्रत्येक दो अंतराल के बीच अतिरिक्त कोंड़बिन्दु होते हैं, अर्थात, यह एक अंतराल ग्राफ का कोंड़बिन्दु संघ है और एक ग्राफ जिसमें आकार के n असंयुक्त क्लिक्स सम्मलित हैं।

भिन्नताएँ

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

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

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

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

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