2025-11-14T12:46:11.790924

Minimizing the Weighted Makespan with Restarts on a Single Machine

Amouzandeh, Jansen, Pirotton et al.
We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it has to be run again from the start instead of resuming at the point of interruption later. The objective is to minimize the weighted makespan, defined as the maximum weighted completion time of jobs. We establish a lower bound of 1.4656 on the competitive ratio achievable by deterministic online algorithms. For the case where all jobs have identical processing times, we design and analyze a deterministic online algorithm that improves the competitive ratio to better than 1.3098. Finally, we prove a lower bound of 1.2344 for this case.
academic

تقليل أقصى وقت إنجاز مرجح مع إعادة التشغيل على آلة واحدة

المعلومات الأساسية

  • معرّف الورقة: 2510.09589
  • العنوان: Minimizing the Weighted Makespan with Restarts on a Single Machine
  • المؤلفون: Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton, Rob van Stee, Corinna Wambsganz
  • التصنيف: cs.DS (هياكل البيانات والخوارزميات)
  • تاريخ النشر: 10 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.09589

الملخص

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

الخلفية البحثية والدافع

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

المشكلة الأساسية المدروسة في هذه الورقة هي تقليل أقصى وقت إنجاز مرجح في جدولة آلة واحدة، المسجلة كـ 1|rj, online, restart|WCmax. لكل مهمة j الخصائص التالية:

  • وقت المعالجة pj
  • وقت الوصول rj
  • الوزن wj

دالة الهدف هي WCmax = max{wjCj}، حيث Cj هو وقت إنجاز المهمة j.

أهمية البحث

  1. الأهمية النظرية: تقليل أقصى وقت الإنجاز هي مشكلة أساسية في نظرية الجدولة، وذات قيمة نظرية مهمة
  2. التطبيقات العملية: في الحوسبة السحابية وجدولة مهام أنظمة التشغيل، قد يتم مقاطعة المهام وإعادة تشغيلها بسبب وصول مهام ذات أولوية أعلى
  3. ابتكار النموذج: نموذج إعادة التشغيل يتوافق بشكل أفضل مع بعض سيناريوهات التطبيق العملي مقارنة بنموذج الاستيلاء-الاستئناف التقليدي

قيود الطرق الموجودة

  • أنشأ Li 12 حداً أدنى لنسبة المنافسة بمقدار 2 للمشكلة على آلة واحدة، وقدم خوارزمية على الإنترنت بنسبة منافسة 3
  • حسّن Chai وآخرون 4 نسبة المنافسة للمشكلة على آلة واحدة إلى 2
  • بالنسبة لحالة أوقات المعالجة المتساوية، اقترح Li خوارزمية بنسبة منافسة مثلى تبلغ (√5+1)/2
  • درس Liang وآخرون 13 المشكلة تحت قيد إعادة تشغيل واحدة، لكن هذا يختلف عن نموذج إعادة التشغيل غير المحدود في هذه الورقة

المساهمات الأساسية

  1. تحديد الحد الأدنى للحالة العامة: إثبات أن أي خوارزمية حتمية على الإنترنت يجب أن تكون نسبة منافستها على الأقل R₁ ≈ 1.4656، حيث R₁ هو الجذر الحقيقي للمعادلة R₁³ - R₁² - 1 = 0
  2. تصميم خوارزمية محسّنة: اقتراح خوارزمية Limited Largest Weight (LLW) لحالة أوقات المعالجة الموحدة، بنسبة منافسة أقل من 1.3098
  3. توفير تحليل دقيق: إثبات الحد الأدنى R₂ ≈ 1.2344 لحالة أوقات المعالجة الموحدة، حيث R₂ هو الجذر الحقيقي للمعادلة 4R₂³ - R₂² - 6 = 0
  4. تحسين الإطار النظري: توفير طريقة تحليل منهجية لمشاكل الجدولة مع إعادة التشغيل

شرح الطريقة

تعريف المهمة

الإدخال: سلسلة من المهام التي تصل على الإنترنت، لكل مهمة j وقت وصول rj، وقت معالجة pj، ووزن wj الإخراج: خطة جدولة تقلل أقصى وقت إنجاز مرجح WCmax = max{wjCj} القيود: يمكن إعادة تشغيل المهام (من البداية)، لكن لا يمكن استئناف التنفيذ من نقطة المقاطعة

الخوارزمية الأساسية: Limited Largest Weight (LLW)

الفكرة الأساسية لخوارزمية LLW هي إيجاد التوازن بين الإستراتيجية الجشعة (معالجة المهام الثقيلة أولاً) والكفاءة الزمنية. قواعد الخوارزمية كالتالي:

  1. المرحلة الأولية: تبدأ المهمة الأولى التي تصل فوراً
  2. قاعدة القرار:
    • إذا بدأت مهمة في الوقت t ≥ (2-R)/(R-1) ≈ 2.2279، قم بتشغيل خوارزمية LW بدون السماح بالمقاطعة
    • إذا بدأت مهمة في الوقت t < (2-R)/(R-1)، قم بتشغيل خوارزمية LW مع السماح بالمقاطعة حتى الوقت t' = (t+2)/R - 1
  3. مفهوم LW-phase: بالنسبة للمهام التي تبدأ في الوقت t < (2-R)/(R-1)، يُسمى الفاصل الزمني (t, t') بـ LW-phase
  4. تحديث المقاطعة: إذا حدثت مقاطعة في الوقت ti، يتم تحديث t := ti وإعادة حساب t'

نقاط الابتكار التقني

  1. تصميم الحد الزمني: تحديد نقطة زمنية حرجة (2-R)/(R-1) من خلال التحليل الرياضي، يُسمح بالمقاطعة قبلها وتُحظر بعدها
  2. تعديل الحد الديناميكي: وقت انتهاء LW-phase يتم تعديله ديناميكياً حسب وقت المقاطعة
  3. تحليل نسبة المنافسة: تحليل منهجي لنسبة منافسة الخوارزمية من خلال مفهوم "good set"

التحليل النظري

طريقة إثبات الحد الأدنى

الحد الأدنى للحالة العامة (النظرية 1): بناء مثال معاكس:

  • الوقت 0: وصول المهمة 1، w₁=1, p₁=1
  • الوقت r₂ = 1/(R₁(R₁-1)) - 1: وصول المهمة 2، w₂=1/(R₁-1), p₂=0

إثبات من خلال تحليل الحالات أن نسبة منافسة أي خوارزمية تبلغ على الأقل R₁ ≈ 1.4656.

الحد الأدنى لحالة الوقت الموحد (النظرية 3): بناء مثال معاكس أكثر تعقيداً يتضمن سلسلة من 4 مهام، إثبات أن نسبة المنافسة تبلغ على الأقل R₂ ≈ 1.2344.

طريقة إثبات الحد الأعلى

يستخدم إثبات النظرية 2 طريقة الاستدلال بالتناقض وتحليل الحالات:

  1. افتراض وجود أصغر مثال معاكس
  2. تعريف مفهوم "good set"
  3. استبعاد جميع أنماط الجدولة الممكنة من خلال 5 خصائص رئيسية

تتضمن الخصائص الرئيسية:

  • الخاصية 1: وصول المهمة 1 في الوقت s₁ وبدء التنفيذ فوراً
  • الخاصية 2: وجود مهام مقاطعة تحقق قيوداً زمنية محددة
  • الخصائص 3-5: تقييد تدريجي لأنماط الجدولة الممكنة

إعداد التجارب

طريقة التحقق النظري

هذه الورقة عمل نظري بشكل أساسي، تستخدم الإثبات الرياضي بدلاً من التحقق التجريبي:

  1. بناء الحد الأدنى: من خلال بناء أمثلة معاكسة وتحسين المعاملات
  2. المساعدة الحاسوبية: استخدام الحاسوب لتحسين معاملات الأمثلة المعاكسة
  3. التحليل الدقيق: الحصول على حدود نسبة المنافسة الدقيقة من خلال حل أنظمة المعادلات

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

  • R₁ ≈ 1.4656: الحد الأدنى لنسبة المنافسة للحالة العامة
  • R ≈ 1.3098: نسبة منافسة خوارزمية LLW لحالة أوقات المعالجة الموحدة
  • R₂ ≈ 1.2344: الحد الأدنى لنسبة المنافسة لحالة أوقات المعالجة الموحدة

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

ملخص نتائج نسبة المنافسة

متغير المشكلةالحد الأدنىالحد الأعلى (الخوارزمية)الفجوة
الحالة العامة1.4656--
أوقات المعالجة الموحدة1.23441.3098 (LLW)0.0754

المقارنة مع الأعمال الموجودة

  • مدى التحسين: مقارنة بنتائج Li، تحسن من (√5+1)/2 ≈ 1.618 إلى 1.3098 لحالة أوقات المعالجة الموحدة
  • المساهمة النظرية: أول تحليل دقيق لنموذج إعادة التشغيل

ضمانات أداء الخوارزمية

تضمن خوارزمية LLW:

  • نسبة منافسة أقل بدقة من 1.3098
  • أن هذا الحد دقيق (توجد حالات تحقق هذه النسبة)

الأعمال ذات الصلة

أساسيات نظرية الجدولة

  • وضع Graham وآخرون 9 نظام التدوين ثلاثي المجالات لمشاكل الجدولة
  • تمت دراسة مشكلة أقصى وقت الإنجاز الكلاسيكية على نطاق واسع

بحث أقصى وقت إنجاز مرجح

  • اعتبر Feng و Yuan 16 أولاً مشكلة أقصى وقت إنجاز مرجح على آلة واحدة
  • أنشأ Li 12 حداً أدنى بمقدار 2 وحداً أعلى بمقدار 3 للنسخة على الإنترنت
  • حسّن Chai وآخرون 4 نسبة المنافسة إلى 2

بحث نموذج إعادة التشغيل

  • قدم Shmoys وآخرون 17 مفهوم إعادة التشغيل لأول مرة
  • ثبت أن نموذج إعادة التشغيل يحسّن أداء الخوارزميات على الإنترنت تحت دوال هدف متعددة 1,2,11,18
  • درس Liang وآخرون 13 متغير مع تقييد عدد إعادات التشغيل

الخلاصة والمناقشة

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

  1. الحدود النظرية: تحديد حدود نسبة المنافسة لمشكلة أقصى وقت إنجاز مرجح مع إعادة التشغيل
  2. تصميم الخوارزمية: تحقيق خوارزمية LLW تحسناً كبيراً لحالة أوقات المعالجة الموحدة
  3. طريقة التحليل: توفير إطار عمل منهجي لتحليل نسبة المنافسة

القيود

  1. وجود فجوة: لا تزال هناك فجوة حوالي 0.075 بين الحد الأعلى والأدنى لحالة أوقات المعالجة الموحدة
  2. الحالة العامة: توفير حد أدنى فقط للحالة العامة مع نقص خوارزمية حد أعلى متطابقة
  3. التطبيق العملي: نقص التحقق من التطبيقات العملية الفعلية للتحليل النظري

الاتجاهات المستقبلية

  1. تقليل الفجوة: تحسين الخوارزمية أو رفع الحد الأدنى لتقليل الفجوة النظرية
  2. خوارزمية الحالة العامة: تصميم خوارزمية للحالة العامة بنسبة منافسة قريبة من 1.4656
  3. توسيع النموذج: النظر في بيئات جدولة أكثر تعقيداً مثل الآلات المتعددة والمعالجة الدفعية المتوازية

التقييم المتعمق

المزايا

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

أوجه القصور

  1. التوجه النظري: نقص التحقق من التطبيقات العملية والتقييم التجريبي
  2. فجوة كبيرة نسبياً: نقص خوارزمية حد أعلى للحالة العامة
  3. التعقيد: عملية الإثبات معقدة نسبياً، وقابلية القراءة تحتاج إلى تحسين

التأثير

  1. المساهمة النظرية: توفير أساس نظري مهم لنموذج إعادة التشغيل في نظرية الجدولة
  2. قيمة المنهجية: يمكن تعميم طريقة التحليل على مشاكل جدولة أخرى
  3. الإمكانية العملية: لها آفاق تطبيق في الحوسبة السحابية والأنظمة الفعلية

السيناريوهات المناسبة

  1. الحوسبة السحابية: جدولة الآلات الافتراضية مع إعادة تشغيل المهام
  2. الأنظمة الفعلية: جدولة المهام ذات الأولوية العالية بشكل استباقي
  3. أنظمة التشغيل: آليات جدولة العمليات مع تقسيم الوقت

المراجع

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

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