प्रोसेसर पर नौकरियों को शेड्यूल करने के लिए एल्गोरिदम

Question

आईरिलिच की टिप्पणी (धन्यवाद बीटीडब्ल्यू) के अनुसार, "शेड्यूलिंग" शब्द भ्रामक हो सकता है और यह एक और उचित वर्णन हो सकता है: मैट्रिक्स एन * एन दिया गया है, एक पंक्ति क्रमपरिवर्तन प्राप्त करें जो उपज करेगा सबसे बड़ा विकर्ण योग।

मेरे पास एन नौकरियों और एन प्रोसेसर का एक सेट है। सभी प्रोसेसर एक दूसरे से अलग हो सकते हैं। प्रत्येक (नौकरी, प्रोसेसर) जोड़ी के लिए, मेरे पास उस प्रोसेसर पर चल रहे उस काम का प्रदर्शन है। प्रदर्शन आईपीसी (प्रति चक्र निर्देश) में मापा जाता है।

मैं एक शेड्यूल (1-टू-1 आवंटन) खोजने की कोशिश कर रहा हूं जो आईपीसी की कुल योग को अधिकतम करता है। मैं ओ (एन!) के साथ सभी संभव कार्यक्रमों पर जाकर ऐसा कर सकता हूं, जो व्यवहार्य नहीं है।

फिर मैंने वर्कलोड 'और प्रोसेसर की प्राथमिकताओं को सॉर्ट करने के लिए आईपीसी का उपयोग करके "स्थिर मिलान" एल्गोरिदम ओ (एन^2) का उपयोग करने का प्रयास किया। यह बहुत तेज़ चलता है और एक सभ्य कार्यक्रम देता है, लेकिन इष्टतम नहीं।

मेरे प्रश्न हैं:

1) मैं वास्तव में उम्मीद स्थिर मिलान एल्गोरिथ्म इष्टतम काम पर लौटने के लिए सक्षम होने के लिए। क्या कोई समझा सकता है कि यह क्यों विफल रहता है? मेरा सबसे अच्छा अनुमान अब तक (नौकरी, प्रोसेसर) जोड़े के बीच संबंधों का अस्तित्व है। मैंने भाग्य के साथ "उदासीनता के साथ स्थिर मिलान" एल्गोरिदम की भी कोशिश की। मुझे यह उल्लेख करना चाहिए कि इसके कार्यान्वयन के कारण एल्गोरिदम विफल नहीं होता है। मैं एक और सैद्धांतिक उत्तर की तलाश में हूं कि क्यों एल्गोरिदम स्वयं इस समस्या को हल नहीं कर सकता है।

2) क्या आप इस एल्गोरिदम के बारे में जानते हैं जिसका मैं उपयोग कर सकता हूं? क्या कोई भी अस्तित्व में है?

Answer 1

स्थिर मेलिंग गलत एल्गोरिदम का कारण यह है कि आप एक मिलान के साथ हवादार हो सकते हैं जहां प्रोसेसर की एक जोड़ी एक दूसरे की नौकरियों को पसंद करेगी, लेकिन नौकरियों में से एक यह प्रोसेसर पसंद करता है। स्विचिंग किसी को भी खराब कर देता है, इसलिए यह मिलान स्थिर है।

हालांकि आपकी समस्या में हम वैश्विक इष्टतम परवाह करते हैं। यदि एक नौकरी में सुधार से अधिक हो जाता है तो दूसरे को कितना बुरा होता है, आप स्विच करना चाहते हैं। वैश्विक अनुकूलतम स्थिर मिलान होने के लिए आवश्यक है लेकिन पर्याप्त नहीं है।

वास्तव में हंगेरियन एल्गोरिदम वैश्विक स्तर पर इष्टतम समाधान खोजने के लिए सही है।