एल्गोरिदम वर्कफ़्लो डीएजी को समांतर संसाधन आवंटन में बदलने के लिए?

Question

कहें कि मेरे पास एक ग्राफ है जहां नोड्स विभिन्न प्रकार के वर्कलोड हैं और किनारों वर्कलोड के बीच निर्भरता हैं। (यह एक डीएजी है क्योंकि चक्रीय निर्भरता मौजूद नहीं है।)

मेरे पास भी कई एजेंटों का एक सेट है जो काम कर सकते हैं।

किसी भी एजेंट को कुछ वर्कलोड किस्मों को दिया जा सकता है, अन्य को एक विशिष्ट एजेंट को दिया जाना चाहिए, और दूसरों को एजेंट के किसी विशेष समूह के बीच एक एजेंट को दिया जाना चाहिए।

मैं वर्कलोड कैसे निर्दिष्ट करूं ऐसी है कि:

• कोई काम का बोझ अपने सभी अवरुद्ध वर्कलोड पूरा कर रहे हैं जब तक एक एजेंट को दिया जाता है

• कम से कम समय की कुल काम का बोझ ग्राफ पूरा करने की आवश्यकता है । (ध्यान दें कि एजेंट निष्क्रिय समय कम से कम आम तौर पर अच्छा है, लेकिन नहीं एक मौलिक आवश्यकता - वहाँ परिदृश्यों जिसके तहत एक विशेष एजेंट अधिक समय के लिए idles लेकिन सभी एजेंटों भर में सभी नौकरियों को पूरा करने के कुल समय कम से कम है हो सकता है।)

वर्कलोड में अवधि अनुमान हैं, लेकिन सादगी के लिए मान लें कि प्रत्येक वर्कलोड को गणना करने के बराबर समय लगता है। (प्रत्येक वर्कलोड को एकाधिक, सीरियल-निर्भर वर्कलोड में तब तक विभाजित करें जब तक कि प्रत्येक वर्कलोड प्रभावी रूप से स्थिर-समय ऑपरेशन न हो।)

मुझे टोपोलॉजिकल डीएजी सॉर्टिंग के बारे में पता है, लेकिन यह नोड्स का एकल, सीरियल ऑर्डरिंग उत्पन्न करता है। मेरे पास समानांतर में चलने वाले कई एजेंट हैं, और रिश्तों ऐसे हैं कि संभावित रूप से बड़े समय अनुकूलन कार्यों के गैर-स्पष्ट पुनरावृत्ति द्वारा किए जा सकते हैं।

इसका परिणाम न्यूनतम समग्र अवधि के गैंट चार्ट के रूप में सर्वश्रेष्ठ प्रदान किया जाएगा। वास्तव में, यदि आप एक टीम में इंजीनियरों के लिए एक मील का पत्थर में बग टिकट आवंटन के रूप में समस्या के बारे में सोचते हैं, तो एएसएपी द्वारा किए गए मील का पत्थर प्राप्त करने के लक्ष्य के साथ, आपको विचार मिलता है। (नहीं ... कृपया मुझे एमएस प्रोजेक्ट में अपना ग्राफ आयात करने के लिए न कहें और फिर इसे निर्यात करें :) - मुझे इसके पीछे एल्गोरिदम में दिलचस्पी है!)

पॉइंटर्स को जाने-माने एल्गोरिदम, सॉफ़्टवेयर पुस्तकालय, या सामान्य मुद्दों और सिद्धांतों की बहुत सराहना की जाती है!

Answer 1

जब तक आपके पास एजेंटों की अनंत संख्या न हो ताकि एक संगत एजेंट उपलब्ध हो जैसे ही कार्य के सभी पूर्ववर्ती कार्य हो जाएं, यह एक एनपी-हार्ड समस्या है।

:

< बेशर्म प्लग>

एक बहुत ही इसी तरह की समस्या मेरी किताब "Algorithms For Interviews"

</बेशर्म प्लग में है>

यहाँ समस्या और पुस्तक से समाधान है

हमें एम कक्षाओं में एन व्याख्यान निर्धारित करने की आवश्यकता है। उनमें से कुछ व्याख्यान दूसरों के लिए पूर्व शर्त हैं। जितनी जल्दी हो सके सभी व्याख्यान समाप्त करने के लिए व्याख्यान कब और कहां आयोजित करें, आप कैसे चुनेंगे?

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

• रैंक आदेश व्याख्यान सबसे लंबे समय तक निर्भरता श्रृंखला है कि वे के शुरू में कर रहे हैं की लंबाई के आधार: सबसेट चयन कई मैट्रिक्स के आधार पर किया जा सकता है।
• रैंक ऑर्डर व्याख्यान व्याख्यान की संख्या के आधार पर कि वे तत्काल आवश्यकता के लिए हैं।
• रैंक ऑर्डर व्याख्यान व्याख्यान की कुल संख्या के आधार पर कि वे प्रत्यक्ष या अप्रत्यक्ष पूर्वापेक्षाएँ हैं।

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

Answer 2

PERT पर विकिपीडिया लेख शुरू करने के लिए एक उपयोगी स्थान हो सकता है।