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

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

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

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

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

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

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

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

अभारित

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

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

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

1. जल्द से जल्द 'समाप्ति समय' के साथ अंतराल, x का चयन करें।
2. उम्मीदवार अंतरालों के सेट से x और x को प्रतिच्छेद करने वाले सभी अंतरालों को हटा दें।
3. उम्मीदवार अंतराल का सेट खाली होने तक दोहराएं।

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

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

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

भारित

जब अंतरालों में भार होता है, तो समस्या एक अंतराल ग्राफ़ में अधिकतम-भार स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजने के बराबर होती है। इसे बहुपद समय में हल किया जा सकता है। Θ(n) समय में एकल अंतराल अनुसूची का अधिकतम भार ज्ञात करने के लिए, निम्नलिखित छद्म कोड निष्पादित करें: <सिंटैक्सहाइलाइट लाइन = 1 लैंग = सी > // वैक्टर पहले से ही शुरुआती से नवीनतम समाप्ति समय तक क्रमबद्ध हैं। int v[numOfVectors + 1]; // अंतराल वैक्टर की सूची int w[numOfVectors + 1]; // w[j], v[j] का भार है। int p[numOfVectors + 1]; // p[j] उन सदिशों में से # है जो v[j] के प्रारंभ होने से पहले समाप्त होते हैं। int M[numOfVectors + 1]; int अंतिम शेड्यूल[];

//v[0] मौजूद नहीं है. पहला अंतराल वेक्टर v[1] पर सेट है। डब्ल्यू[0] = 0; पी[0] = 0; एम[0] = 0;

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

   एम[आई] = अधिकतम(डब्ल्यू[आई] + एम[पी[आई, एम[आई - 1]);

}

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

अनुसूची (जे) {

   अगर (जे == 0) {वापसी; }
   अन्यथा यदि (w[j] + M[p[j >= M[j - 1]){
       प्रीपेन्ड(v[j], फाइनलशेड्यूल); // शेड्यूल करने के लिए v[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 में एक या दो बार सकारात्मक और एक बार नकारात्मक रूप से प्रकट होने के लिए प्रतिबंधित हो। यह तय करें कि क्या

इस संतुष्टि समस्या के एक उदाहरण को देखते हुए, 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}$ यह सी में पहली बार सकारात्मक रूप से प्रकट होता है — से शुरू होने वाला अंतराल $50i-12$.
  • प्रत्येक चर के लिए $x_{i}$ जो सी में दूसरी बार सकारात्मक रूप से प्रकट होता है — से शुरू होने वाला अंतराल $50i-8$. ध्यान दें कि ये दोनों अंतराल अंतराल को काटते हैं $50i-10$, के साथ जुड़े $x_{i}=\mathrm {false}$.
  • प्रत्येक चर के लिए $x_{i}$ जो नकारात्मक रूप से प्रकट होता है - एक अंतराल जो शुरू होता है $50i+8$. यह अंतराल अंतराल को प्रतिच्छेद करता है $50i+10$ के साथ जुड़े $x_{i}={\text{true}}$.

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

निर्मित जीआईएसडीपी के पास एक व्यवहार्य समाधान है (यानी एक शेड्यूलिंग जिसमें प्रत्येक समूह का प्रतिनिधित्व किया जाता है), यदि और केवल तभी जब बूलियन क्लॉज के दिए गए सेट में एक संतोषजनक असाइनमेंट हो। इसलिए GISDP3 NP-पूर्ण है, और इसी प्रकार प्रत्येक के लिए GISDPk भी है $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 को न्यूनतम किया जा सके। अर्थात्, सभी अंतराल निर्धारित होने चाहिए, लेकिन उद्देश्य संसाधनों के उपयोग को कम करना है।

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

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

स्रोत

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