🤖 machine learning

Learning-Augmented Online Scheduling with Parsimonious Preemption

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

المؤلفون الأصليون: Mugen Blue, Sungjin Im, Alexander Lindermayr

نُشر 2026-05-25

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Mugen Blue, Sungjin Im, Alexander Lindermayr

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك مدير مطبخ مزدحم يضم عدة طهاة (آلات) وقائمة طويلة من الطلبات (مهام) تتدفق باستمرار. أنت لا تعرف بالضبط كم سيستغرق كل طبق للطهي حتى ينتهي. هذه هي مشكلة "الجدولة عبر الإنترنت" (online scheduling) الكلاسيكية.

في الماضي، كان أمام المديرين خياران سيئان:

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

تقدم هذه الورقة طريقة جديدة لإدارة المطبخ باستخدام تنبؤات الذكاء الاصطناعي. فكر في هذه التنبؤات كأنها "بطاقة وصفة سحرية" تعطيك تقديراً تقريبياً للوقت الذي سيستغرقه الطبق. قد تكون البطاقة غير دقيقة تماماً (بها ضجيج)، لكنها أفضل من لا شيء.

هدف المؤلفين هو بناء نظام يستخدم هذه البطاقات ليكون سريعاً، دون إجبار الطهاة على تبديل المهام باستمرار. هم يسمون هذا "المقاطعة المقتصدة" (parsimonious preemption) — وهو مجرد مصطلح معقد يعني "تبديل المهام فقط عند الضرورة القصوى".

إليك كيف يعمل حلهم، مقسماً إلى مفاهيم بسيطة:

1. "الطابور الذكي" (آلة واحدة)

تخيل طاهياً واحداً لديه مجموعة من خطوط الانتظار (الطوابير).

الطريقة القديمة: كل طلب جديد يذهب إلى مقدمة الخط مباشرة، بغض النظر عن نوعه.
الطريقة الجديدة (PMLF): عندما يصل طلب جديد، ينظر الطاهي إلى "البطاقة السحرية". إذا قالت البطاقة "5 دقائق"، يذهب الطلب إلى "خط الـ 5 دقائق". وإذا قالت "30 دقيقة"، يذهب إلى "خط الـ 30 دقيقة".
السر: بينما يعمل الطاهي على طبق ما، يتحقق من البطاقة. إذا استغرق الطبق وقتاً أطول مما توقعته البطاقة، يقوم الطاهي بنقله إلى "خط انتظار أطول".
النتيجة: إذا كانت البطاقات دقيقة، فسيقلل الطاهي من تبديل المهام؛ حيث سينهي الطبق فحسب. وإذا كانت البطاقات خاطئة، فإن النظام يصحح نفسه تلقائياً، لكنه لا يصاب بالذعر ويبدأ بالتبديل في كل ثانية.

2. "الواقع المحاكي" (طهاة متعددون)

الآن تخيل مطبخاً به العديد من الطهاة المختلفين، بعضهم بارع في الخبز، والبعض الآخر بارع في الشواء. هذه هي مشكلة "الآلات غير المرتبطة" (Unrelated Machines). فقد يستغرق الطبق دقيقة واحدة مع الطاهي (أ) لكن ساعة كاملة مع الطاهي (ب).

المشكلة: أفضل طريقة نظرية لإدارة هذا المطبخ تتضمن تبديل الأطباق بين الطهاة باستمرار لإبقائهم مشغولين، وهذا يسبب "تكاليف تبديل" هائلة.
الحل الجديد (SNAP): بدلاً من التبديل المستمر، يعمل المطبخ في "حقبات زمنية" (epochs) (كتل زمنية).
1. الخطة: في بداية الكتلة، يحسب الكمبيوتر الجدول الزمني المثالي النظري (من يجب أن يطبخ ماذا ولكم من الوقت).
2. نقطة التفتيش: يضع الكمبيوتر "علامات فارقة" بناءً على بطاقات الوصفة السحرية. على سبيل المثال: "اطبخ حتى تنجز 10 دقائق من العمل".
3. التنفيذ: يتبع الطهاة الخطة. هم لا يبدلون المهام إلا عندما تصل مجموعة معينة من الأطباق إلى علاماتها الفارقة.
4. التبديل: بمجرد الوصول إلى العلامات الفارقة، يعيد الكمبيوتر حساب الخطة للكتلة التالية.
الفائدة: هذا يحد من عدد المرات التي يضطر فيها الطهاة للتوقف وتبديل الأواني. الأمر يشبه تشغيل سباق تتابع حيث تمرر العصا فقط في نقاط محددة ومعدة مسبقاً، بدلاً من الركض حول المضمار في محاولة لإيجاء اللحظة المثالية لتمريرها.

3. التعامل مع التخمينات السيئة

ماذا لو كانت بطاقة الوصفة السحرية خاطئة تماماً؟

التقدير الأقل من الواقع (أقصر من الحقيقة): إذا قالت البطاقة "5 دقائق" ولكن الطبق يستغرق 20 دقيقة، يلاحظ النظام هذا التأخير وينقل الطبق إلى طابور انتظار أطول. إنه يتعامل مع الأمر بسلاسة.
التقدير الأعلى من الواقع (أطول من الحقيقة): إذا قالت البطاقة "20 دقيقة" ولكن الطبق يستغرق 5 دقائق فقط، فقد يضيع الطاهي وقتاً في الانتظار. وجد المؤلفون حيلة ذكية: فهم يقومون عمداً بـ "خفض" التقديرات قليلاً في البداية. هذا يضمن أنه حتى لو كانت بعض البطاقات خاطئة، فإن النظام سيعاملها كتقديرات "آمنة" (أقل من الواقع)، مما يمنع المطبخ من التعطل في انتظار أطباق انتهت بالفعل.

الخلا الخلاصة

تثبت الورقة رياضياً أنه يمكنك الحصول على كل شيء:

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

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

ملخص تقني: الجدولة عبر الإنترنت المعززة بالتعلم مع الاستباق المقتصد

تعريف المشكلة

يتناول هذا العمل مشكلة الجدولة عبر الإنترنت (Online Scheduling) لتقليل إجمالي وقت الاكتمال ( $\sum C_j$ ) في البيئات غير المتطلعة (Non-clairvoyant) حيث تكون متطلبات معالجة الوظائف ( $p_j$ ) غير معروفة حتى الاكتمال. تدمج الدراسة التنبؤات المستمدة من التعلم الآلي ( $\hat{p}_j$ ) لأحجام الوظائف في التصميم الخوارزمي. وثمة قيد حاسم تم تقديمه وهو تقليل تعقيد الاستباق (Preemption Complexity). ففي الأنظمة العملية مثل مراكز البيانات، تؤدي عمليات الاستباق المتكررة إلى تكاليف إضافية كبيرة (مثل تبديل السياق، وإبطال ذاكرة التخزين المؤقت). وبينما تحقق خوارزميات الجدولة الحالية المعززة بالتعلم ضمانات قوية لزمن الاستجابة (Latency)، إلا أنها تعتمد غالباً على استباقات "عمياء" أو متكررة (مثل نظام Round-Robin)، متجاهلة المقايضة بين أداء الخوارزمية وتكلفة الاستباق.

تبحث الورقة فيما إذا كان من الممكن تصميم خوارزميات تكون تنافسية ثابتة (Constant-competitive) (قريبة من المثالية) مع تقييد عدد عمليات الاستباق لكل وظيفة بعامل ثابت من الحد النظري الأدنى، وتحديداً عند توفر التنبؤات.

المنهجية

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

1. التغذية الراجعة متعددة المستويات المتوقعة (PMLF)

بالنسبة للآلات المفردة أو المتطابقة، يقوم المؤلفون بتكييف خوارزمية التغذية الراجعة متعددة المستويات (MLF) الكلاسيكية.

الآلية: بدلاً من وضع الوظائف الجديدة في أدنى طابور (كما في MLF القياسي)، يتم وضع الوظائف أولياً في طابور يتوافق مع حجمها المتوقع $\hat{p}_j$ . وتحديداً، تبدأ الوظيفة $j$ في الطابور $Q_k$ حيث $(1+\delta)^k \le \hat{p}_j < (1+\delta)^{k+1}$ .
منطق الاستباق: لا يتم استباق الوظيفة (نقلها إلى طابور أعلى) إلا عندما يصل وقت المعالجة التراكمي لها إلى القوة التالية لـ $(1+\delta)$ .
التعامل مع المبالغة في التقدير: للتعامل مع الحالات التي يكون فيها $\hat{p}_j > p_j$ ، تستخدم الخوارزمية استراتيجية من مرحلتين؛ حيث تشغل PMLF حتى ينخفض عدد الوظائف غير المكتملة إلى عتبة معينة (بناءً على حد أعلى $g$ للوظائف التي تم المبالغة في تقدير حجمها). عند هذه النقطة، يتم إعادة ضبط تنبؤات الوظائف المتبقية إلى حجم المعالجة الحالي، مما يعاملها فعلياً كتقديرات ناقصة لضمان المتانة.

2. التنبؤ التكيفي المحاكي غير المستبق (SNAP)

بالنسبة لـ الآلات غير المرتبطة (حيث تختلف معدلات المعالجة $\lambda_{ij}$ لكل زوج من (وظيفة-آلة))، يقدم المؤلفون خوارፈላ SNAP.

المحاكاة القائمة على الحقبات (Epoch-Based): تعمل الخوارزمية في حقبات. في بداية كل حقبة، تحسب معدلات العدالة النسبية (Proportional Fairness - PF) للوظائف النشطة. تعد PF خوارزمية تنافسية بمقدار $O(1)$ للآلات غير المرتبطة، لكنها عالية الاستباق (كسرية).
نقاط التفتيش (Checkpointing): بدلاً من اتباع جدول PF الكسري بشكل مستمر، تحدد SNAP "نقاط تفتيش" لكل وظيفة بناءً على قوى $(1+\delta)$ بالنسبة لـ $\hat{p}_j$ .
التحويل إلى غير مستبق: تحدد الخوارزمية مدة الحقبة بحيث يصل كسر ثابت ( $\beta$ ) من الوظائف إلى نقطة التفتيش التالية تحت معدلات PF. ثم تقوم بتحويل هذا الجدول الكسري إلى جدول غير مستبق (أو منخفض الاستباق) باستخدام إجراء تقريب غير مستبق (بناءً على [CSV12]). ويتم تنفيذ هذا الجدول طوال مدة الحقبة.
المتانة: على غرار PMLF، تتعامل SNAP مع المبالغة في التقدير عن طريق إعادة ضبط التنبؤات بمجرد انخفاض عدد الوظائف النشطة دون عتبة معينة.

3. الإطار العام لجدولة المتعدد الأوجه (PSP)

يعمم المؤلفون النهج ليشمل جدولة الوظائف القابلة للمطاوعة (Malleable Jobs) وفئة أوسع من مشاكل جدولة المتعدد الأوجه (Polytope Scheduling).

تحليل PF المتين: قدموا نموذج $\beta$ -robust PSP حيث يمكن للمنافس (Adversary) إبطال معدلات المعالجة لكسر $\beta$ من الوظائف. وقد أثبتوا أن PF تظل تنافسية بمقدار $O(1)$ في هذا الإعداد المتين.
التطبيق: من خلال محاكاة سلوك PF المتين هذا وتحويله إلى جدول منخفض الاستباق، يشتقون خوارزميات للوظائف القابلة للمطاوعة تحافظ على تنافسية ثابتة.

المساهمات الرئيسية

أول دراسة منهجية للمقايضة بين الاستباق وزمن الاستجابة: هذا هو العمل الأول الذي يؤصل تحليلياً للمقايضة بين زمن استجابة الوظيفة وتعقيد الاستباق في نموذج الجدولة المعزز بالتعلم.
ضمانات الاستباق المحدودة: يثبت المؤلفون أنه يمكن تحقيق خوارزميات ذات تنافسية ثابتة مع $O(1)$ $O (1)$ من عمليات الاستباق لكل وظيفة (نسبة إلى المعيار $D$ $D$ ) في ظل وجود تنبؤات دقيقة.
- المعيار $D$ : يُعرف بـ $\sum_j (\log_2(p_j/\hat{p}_j) + 1)$ . ويمثل هذا الحد الأدنى من عمليات الاستباق المطلوبة حتى لتظل الخوارزميات غير المتطلعة تنافسية.
النتائج الخوارزمية:
- الآلات المفردة/المتطابقة: خوارزمية تنافسية بمقدار $(2+\epsilon)$ مع $O(\frac{1}{\epsilon} D)$ من عمليات الاستباق.
- الآلات غير المرتبطة: خوارزمية تنافسية بمقدار $14.48(1+\epsilon)$ مع $O(\frac{1}{\epsilon^3} D)$ من عمليات الاستباق.
- الوظائف القابلة للمطاوعة: خوارزمية تنافسية بمقدار $\frac{27e}{e-1}(1+\epsilon)$ مع $O(\frac{1}{\epsilon^3} D)$ من عمليات الاستباق.
التعامل مع المبالغة في التقدير: تم توفير إطار عمل متين يرفع نسبة التنافسية وتكاليف الاستباق لوغاريتمياً مع خطأ التنبؤ، مما يضمن تدهور الأداء بشكل تدريجي وسلس حتى عندما تكون التنبؤات غير دقيقة.

النتائج التجريبية

يتحقق المؤلفون من نتائجهم النظرية من خلال تجارب على نماذج اصطناعية تتضمن 10 آلات و100 وظيفة، بما في ذلك وظائف "خاصة" غير متجانسة.

SNAP مقابل النماذج المرجعية: تتفوق SNAP بشكل كبير على الاستراتيجيات "العمياء" (التي تفترض تنبؤات مثالية) مع زيادة خطأ التنبؤ، بينما تحافظ على الاستقرار في نسبة التنافسية.
كفاءة الاستباق: تستخدم SNAP عمليات استباق أقل بكثير من المعايير الطبيعية مثل "المضاعفة" (Doubling) (التي تضاعف التقديرات عند الخطأ) مع تحسين إجمالي وقت الاكتمال.
النهج الهجين: تُظهر خوارزمية "Hybrid SNAP"، التي تجمع بين الاستراتيجية "العمياء" للأخطاء الصغيرة وSNAP للأخطاء الكبيرة، أفضل ما في العالمين، حيث تتفوق باستمرار أو تضاهي الاستدلالات الأخرى في كل من القيمة المستهدفة وتقليل الاستباق.

الأهمية والادعاءات

تدعي الورقة أنها تسد فجوة كبيرة في أدبيات التعلم المعزز من خلال تجاوز عمليات الاستباق "العمياء". وتوضح أن التنبؤات يمكن استخدامها ليس فقط لتحسين زمن الاستجابة، بل أيضاً لتقليل التكاليف التشغيلية (الاستباق) لخوارزميات الجدولة بشكل جوهري.

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

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