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

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

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

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

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

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

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

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

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

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

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

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

अभारित

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

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

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

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

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

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

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

वेटेड

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

Θ(n) समय में एकल अंतराल अनुसूची का अधिकतम भार ज्ञात करने के लिए, निम्नलिखित छद्म कोड निष्पादित करते हैं: <सिंटैक्सहाइलाइट लाइन = 1 लैंग = सी >

//वैक्टर पहले से ही प्रारंभिक से नवीनतम समाप्ति समय तक क्रमबद्ध हैं।

2. int v[numOfVectors + 1]; // अंतराल वैक्टर की सूची हैं।

3. int w[numOfVectors + 1]; // w[j], v[j] का भार है।

4. int p[numOfVectors + 1]; // p[j] उन # सदिशों में से है जो v[j] के प्रारंभ होने से पहले समाप्त होते हैं।

5. int M[numOfVectors + 1];

6. int अंतिम शेड्यूल[];

//v[0] उपस्थित नहीं है. पहला अंतराल वेक्टर v[1] पर सेट है।

w[0] = 0; p[0] = 0; M[0] = 0;

for (int i = 1; i < numOfVector + 1; i++) {

   M[i] = max(w[i] +Mp[i, M[i - 1]);

}

// शेड्यूल का अधिकतम भार M[numOfVectors + 1] के बराबर है।

अनुसूची (j) {

   यदि (जे == 0) {return;}
   अन्यथा यदि (w[j] + M[p[j >= M[j - 1]){
       प्रीपेन्ड(v[j], फाइनलशेड्यूल); // शेड्यूल करने के लिए v[j] को जोड़ता है।
       अनुसूची(p[j]);
   } अन्यथा { शेड्यूल(j - 1); }

} </सिंटैक्सहाइलाइट>

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

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

जीआईएसडीपीके एनपी-पूर्ण है जब $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 में प्रत्येक क्लॉज़ न्यूनतम एक सही शब्दसः होता हैं।

इस संतुष्टि समस्या के एक उदाहरण को देखते हुए, जीआईएसडीपी के निम्नलिखित उदाहरण का निर्माण करते हैं। सभी अंतरालों की लंबाई 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}}$के साथ जुड़े होते हैं।

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

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

बहुपद जब सभी समूहों में अधिकतम 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-एसएटी देखें)। इसलिए, GISDP2 को बहुपद समय में हल किया जा सकता है।

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

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

GISMPk तब भी NP-पूर्ण है $k\geq 2$. इसके अलावा, GISMPk MaxSNP-पूर्ण है, यानी, इसमें PTAS नहीं है जब तक कि P=NP न हो। इसे MAX 3-SAT-3 से GISMP2 तक अनुमानित-संरक्षण कमी दिखाकर सिद्ध किया जा सकता है।

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

निम्नलिखित लालची एल्गोरिदम एक समाधान ढूंढता है जिसमें अंतराल की इष्टतम संख्या का कम से कम 1/2 शामिल होता है:# जल्द से जल्द 'समाप्ति समय' के साथ अंतराल, 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 तक सुधार दिया गया।

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

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

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

भिन्नताएँ

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

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

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

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

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

स्रोत

श्रेणी:इष्टतम शेड्यूलिंग