خوارزمية جدولة الموارد الموزونة وموازنة التحميل

Question

يجب أن يكون التطبيق البرمجي الذي أعمل عليه قادرًا على تعيين المهام لمجموعة من المستخدمين استنادًا إلى عدد المهام المتوفرة لديهم حاليًا، حيث يكون المستخدمون الذين لديهم أقل عدد من المهام هم الأكثر احتمالية للحصول على المهمة التالية.ومع ذلك، يجب التعامل مع حمل المهمة الحالي على أنه ترجيح، بدلاً من تعريف أمر مطلق.IOW، أحتاج إلى تنفيذ خوارزمية مرجحة لموازنة التحميل.

لنفترض أن هناك خمسة مستخدمين، مع عدد المهام التالي:

أ:4 ب:5 ج:0 د:7 ه:9

أريد تحديد أولويات المستخدمين للمهمة التالية بالترتيب CABDE، حيث من المرجح أن يحصل C على المهمة وE، الأقل احتمالًا.هناك أمران مهمان يجب ملاحظتهما هنا:

• يمكن أن يختلف عدد المستخدمين من 2 إلى العشرات.
• يمكن أن يختلف عدد المهام المخصصة لكل مستخدم من 1 إلى المئات.

في الوقت الحالي، يمكننا التعامل مع جميع المهام على قدم المساواة، على الرغم من أنني لا أمانع في تضمين المهمة الصعبة كمتغير يمكنني استخدامه في المستقبل - ولكن هذا مجرد زينة على الكعكة.

الأفكار التي توصلت إليها حتى الآن ليست جيدة جدًا في بعض المواقف.قد تثقل كاهل المستخدمين ببعضهم البعض بشكل قريب جدًا إذا كان هناك عدد كبير من المستخدمين، أو قد تفشل إذا لم يكن لدى المستخدم مهام حالية، أو....

لقد حاولت البحث في الويب، ولكن لم يحالفني الحظ كثيرًا.هل يمكن لأي أحد أن يقدم لي ملخصًا سريعًا للخوارزمية التي قد تعمل بشكل جيد؟لا أحتاج إلى تنفيذ فعلي - سأقوم بهذا الجزء - مجرد وصف جيد.وبدلاً من ذلك، هل هناك موقع ويب جيد يمكن الوصول إليه مجانًا؟

أيضًا، على الرغم من أنني أقدر الجودة بالتأكيد، إلا أنه لا يلزم أن يكون هذا مثاليًا من الناحية الإحصائية.لذا، إذا كان بإمكانك التفكير في تقنية جيدة ولكنها ليست رائعة، فأنا مهتم!

Answer 1

كما أشرت، هذه مشكلة موازنة التحميل.إنها ليست مشكلة جدولة حقًا، نظرًا لأنك لا تحاول تقليل أي شيء (إجمالي الوقت، وعدد العمال المتزامنين، وما إلى ذلك).لا توجد قيود خاصة (مدة المهمة، والاشتباكات الزمنية، ومجموعات المهارات المناسبة وما إلى ذلك). لذا فإن مشكلتك تتلخص في اختيار وظيفة الترجيح المناسبة.

أنت تقول أن هناك بعض المواقف التي تريد تجنبها، مثل أوزان المستخدم القريبة جدًا من بعضها البعض.هل يمكنك أن تعطي معلومات إضافية؟على سبيل المثال، ما الخطأ في جعل فرصة التعيين متناسبة فقط مع عبء العمل الحالي، والذي يتم تطبيعه من خلال عبء العمل الواقع على العمال الآخرين؟يمكنك تصور ذلك كسلسلة من الكتل ذات الأطوال المختلفة (المهام)، والتي يتم تجميعها في مجموعة من الصناديق (العمال)، حيث تحاول الحفاظ على الارتفاع الإجمالي للصناديق قدر الإمكان.

ومع المزيد من المعلومات، يمكننا تقديم توصيات محددة بشأن الوظائف التي قد تناسبك.

يحرر:أمثلة على وظائف موازنة التحميل

بناءً على تعليقاتك، إليك بعض الأمثلة على الوظائف البسيطة التي يمكن أن تمنحك سلوكيات موازنة مختلفة.السؤال الأساسي هو ما إذا كنت تريد السلوك الحتمي أو الاحتمالي.سأقدم بضعة أمثلة على كل منهما.

لاستخدام المثال الموجود في السؤال - هناك 4 + 5 + 0 + 7 + 9 = 25 وظيفة مخصصة حاليًا.تريد اختيار من يحصل على الوظيفة 26.

1) مزرعة المهام البسيطة. لكل وظيفة، اختر دائمًا العامل الذي لديه أقل الوظائف المعلقة حاليًا.يحصل العمال السريعون على الكثير من المهام، لكن الجميع ينهون أعمالهم في الوقت نفسه تقريبًا.

2) ضمان عبء العمل العادل. إذا كان العمال يعملون بسرعات مختلفة، ولا تريد أن يقوم البعض بعمل أكثر من الآخرين، فقم بتتبع عدد المهام المكتملة والمعلقة لكل عامل.قم بتعيين الوظيفة التالية للحفاظ على هذا الرقم موزعًا بالتساوي (يحصل العمال السريعون على فترات راحة مجانية).

3) التطبيع الخطي الأساسي. اختر الحد الأقصى لعدد الوظائف التي يمكن أن يشغلها كل عامل.تتم تسوية عبء العمل لكل عامل إلى هذا الرقم.على سبيل المثال، إذا كان الحد الأقصى لعدد الوظائف/العامل هو 15، فيمكن إضافة 50 وظيفة أخرى قبل الوصول إلى السعة.لذا فإن احتمال تعيين الوظيفة التالية لكل عامل هو

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

إذا كنت لا تريد استخدام حد أقصى محدد، فيمكنك استخدام العامل الذي لديه أعلى عدد حالي من المهام المعلقة كحد أقصى.في هذه الحالة، هذا هو العامل E، لذا ستكون الاحتمالات

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

لاحظ أنه في هذه الحالة، تضمن التسوية عدم إمكانية تعيين العامل E لأية وظائف - فهو بالفعل عند الحد الأقصى.وأيضًا، لمجرد أن C ليس لديه أي شيء ليفعله، لا يعني أنه مضمون الحصول على وظيفة جديدة (هذا على الأرجح).

يمكنك بسهولة تنفيذ وظيفة الاختيار عن طريق إنشاء رقم عشوائي ص بين 0 و 1 ومقارنتها بهذه الحدود.حتى إذا ص <0.25، A يحصل على الوظيفة، 0.25< ص <0.45، B يحصل على الوظيفة، وما إلى ذلك.

4) التطبيع غير الخطي. يعد استخدام دالة السجل (بدلاً من الطرح الخطي) لترجيح أرقامك طريقة سهلة للحصول على تسوية غير خطية.يمكنك استخدام هذا لتحريف الاحتمالات، على سبيل المثال.لزيادة احتمالية حصول العمال الذين ليس لديهم العديد من الوظائف على المزيد.

النقطة المهمة هي أن عدد الطرق للقيام بذلك غير محدود عمليا.تعتمد وظيفة الترجيح التي تستخدمها على السلوك المحدد الذي تحاول تمكينه.نأمل أن يكون هذا قد أعطاك بعض الأفكار التي يمكنك استخدامها كنقطة انطلاق.