मान लें कि मेरे पास काम की 300-400 इकाइयाँ हैं, सभी विभिन्न आकारों के साथ, जहाँ कुछ मामलों में आकार का अंतर काफी बड़ा है। क्या उन्हें एक निश्चित संख्या में बाल्टियों में विभाजित करना संभव है ताकि मैं एक निश्चित संख्या में कार्यकर्ता धागे में भार को संतुलित कर सकूं?

0
CuriousGeorge 16 जुलाई 2020, 17:04

1 उत्तर

सबसे बढ़िया उत्तर

आप जिस समस्या का वर्णन करते हैं उसे मल्टीप्रोसेसर शेड्यूलिंग समस्या के रूप में जाना जाता है (जो बिन पैकिंग समस्या के समान है जो कि नैपसैक समस्या का सामान्यीकरण है)। इष्टतम शेड्यूलिंग ढूँढना एनपी-हार्ड के रूप में जाना जाता है। इसलिए इष्टतम शेड्यूलिंग खोजने के लिए कोई ज्ञात बहुपद समय एल्गोरिदम नहीं है।

एक साधारण अनुमानी (गैर-इष्टतम) एल्गोरिथ्म सबसे लंबा प्रसंस्करण समय है:

  • कार्य की इकाइयों को क्रमबद्ध करें, सबसे पहले सबसे बड़ा
  • प्रत्येक इकाई के लिए, जल्द से जल्द समाप्ति समय के साथ बाल्टी में रखें
3
eerorika 16 जुलाई 2020, 14:19