गैर शून्य कम बाध्य या 0 क्षमता वाला फ्लो ग्राफ
मुझे डर है कि प्रश्न शीर्षक पर्याप्त रूप से सटीक नहीं हो सकता है, लेकिन मैं कुछ अधिक सटीक नहीं ले सकता
यहाँ समस्या है
Given एन ’मशीनों को दिया
- प्रत्येक मशीन में क्षमताओं का एक सेट होता है
- प्रत्येक मशीन की अधिकतम उपलब्धता होती है (ए)
दिए गए 'एम' कार्यों
- प्रत्येक कार्य को क्षमताओं के एक सेट की आवश्यकता होती है
- प्रत्येक कार्य में एक निश्चित समय लगता है (D (t))
- एक कार्य केवल एक मशीन पर किया जाना है
समस्या यह निर्धारित करने के लिए है कि क्या सभी कार्य पूरे हो सकते हैं।
मैं 'एक मशीन केवल' आवश्यकता के साथ फंस गया। एकमात्र प्रवाह रेखांकन जो मैं काम कर सकता हूं गारंटी देता है कि एक कार्य एक मशीन से अधिक से जुड़ा नहीं है।
यह एक द्विदलीय मिलान समस्या की तरह है लेकिन क्षमता 1 के साथ है
मैं भी प्रवाह नेटवर्क में XOR- जैसा व्यवहार करता था जो समान है, लेकिन 'स्रोत' छोर पर 'xor' की आवश्यकता है जहां मुझे लक्ष्य छोर पर इसकी आवश्यकता होगी।
किसी को कोई सुझाव होगा? क्या यह एक प्रवाह ग्राफ के रूप में मॉडल करना संभव है?
टीएक्स!
पीटर
PS अधिक ठोस उदाहरण के साथ आवश्यकताओं को स्पष्ट करने की कोशिश कर रहा है
डिजिटल प्रिंट सिस्टम और प्रिंट नौकरियां मान लें
- प्रत्येक डिजिटल प्रेस कई घंटों तक चल सकता है
- प्रत्येक प्रेस में कुछ परिष्करण संभावनाएं होती हैं: जैसे 'शीट कटर', 'टुकड़े टुकड़े', 'लेजर कटर', 'पेज फोल्डिंग', ...।
- प्रत्येक प्रिंट जॉब के लिए कई घंटों की आवश्यकता होती है
- प्रत्येक प्रिंट जॉब में एक या अधिक फिनिशिंग संभावनाएं होती हैं
मशीनों के सेट, प्रत्येक के लिए उपलब्धता और परिष्करण की संभावनाओं और प्रिंट नौकरियों का एक सेट (अवधि, परिष्करण के लिए आवश्यक विकल्प) यह निर्धारित करते हैं कि क्या सभी प्रिंट नौकरियां समाप्त हो सकती हैं
इसलिए उदा
- प्रिंटर p1 10 घंटे की अवधि के लिए उपलब्ध है और इसमें f1 और f2 की विशेषताएं हैं
- प्रिंटर P2 10 घंटे की अवधि के लिए उपलब्ध है और इसमें f2 और f3 की विशेषताएं हैं
- Job1, f1 और f2 की सुविधाओं को चलाने में 8 घंटे लगते हैं
- Job2, f2 और f3 की विशेषताओं को चलाने में 8 घंटे लगते हैं
- Job3, फीचर f2 की आवश्यकता को चलाने के लिए 4 घंटे की आवश्यकता होती है
एक प्रिंटर जो 10 घंटे के लिए उपलब्ध है, 10 x 1 घंटे की नौकरी या 5 x 2 घंटे की नौकरी, या 1 x 8 घंटा की नौकरी और 1 x 2 घंटे की नौकरी चला सकता है, ... नौकरियां हमेशा एक प्रिंटर पर चलती हैं
प्रवाह आरेख मैं हमेशा उन मामलों में परिणाम के साथ आ सकता है जहां
P1 के 8 घंटे job1 को सौंपे जाते हैं (प्रिंटर p1 के लिए 2 घंटे छोड़कर) 8 घंटे के p2 को job2 को सौंपा जाता है (प्रिंटर P2 के लिए 2 घंटे छोड़कर)
(अब तक तो सब ठीक है)
परन्तु फिर
P1 और p2 के 2 घंटे का उपयोग job3 में करने के लिए किया जाता है और अधिकतम प्रवाह से संकेत मिलता है कि तीन नौकरियों को चलाया जा सकता है (जो ठीक नहीं है)
जवाब
आपकी समस्या एनपी-हार्ड है। विशेष मामले में जहां किसी भी नौकरी के लिए किसी विशेष सुविधाएँ की आवश्यकता नहीं होती है, और सभी प्रिंटरों की समान उपलब्धता होती है, यह सिर्फ बिन पैकिंग की समस्या बन जाती है , जो कि (दृढ़ता से) एनपी-पूर्ण है।
आप अपनी स्थिति के लिए बिन पैकिंग के लिए मानक एल्गोरिदम को अपनाने की कोशिश कर सकते हैं। उदाहरण के लिए, एक दृष्टिकोण पूर्णांक रैखिक प्रोग्रामिंग का उपयोग करना होगा और आशा है कि ILP सॉल्वर परिणामी समस्या को संभाल सकता है।