تحميل الموازنة مع الوافدين العشوائيين

تدير أنظمة إدارة المجموعات ، مثل BORG من Google ، مئات الآلاف من الوظائف عبر عشرات الآلاف من الآلات بهدف تحقيق الاستخدام العالي من خلال موازنة التحميل الفعالة ، وضع المهمة الفعال ، ومشاركة الآلات. موازنة التحميل هي عملية توزيع حركة مرور الشبكة أو أعباء العمل الحسابية عبر خوادم متعددة أو موارد الحوسبة ، وهي واحدة من أكثر المكونات أهمية لنظام إدارة الكتلة الحديث. يعد موازنة التحميل الفعالة أمرًا بالغ الأهمية لتحسين أداء النظام وقابليته للتوسع.

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

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

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