الدرس الثاني

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

الفكرة الأساسية

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

الشرح

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

1. خوارزمية القوة المفرطة: تختبر كل الجداول الممكنة باستخدام دالة التباديل $itertools.permutations()$، وتستخرج الجدول الأفضل ذي التباطؤ الكلي الأدنى. ولكن عدد الجداول يتزايد أسيّاً مع زيادة عدد المهام، فحين يكون عدد المهام $N = 5$ يكون الناتج $120$ جدولاً، وعندما يكون $N = 10$ يصل إلى $3,628,800$ جدولاً، مما يجعلها مكلفة جداً للمدخلات الكبيرة.
2. خوارزمية الحل الاستدلالي الجشعة: تستخدم أسلوباً استدلالياً بسيطاً لفرز المهام واتخاذ قرار الترتيب وفقاً له، مثل الفرز حسب الموعد النهائي الأقرب أولاً، أو استخدام دالة استدلالية تأخذ في الاعتبار أوزان المهام.
3. خوارزمية البحث المحلي: تبدأ بحل أولي تم إنشاؤه بواسطة خوارزمية جشعة، ثم تعمل بطريقة تكرارية لفحص الحلول المجاورة عن طريق إجراء تعديلات بسيطة مثل مبادلة مواقع مهمتين، وتقييم جودة الحل الناتج، فإذا كان أفضل فإنه يستبدل الحل الحالي وتستمر العملية حتى يتعذر العثور على حل آخر مجاور أفضل.

مثال محلول خطوة بخطوة

افترض أن لدينا ثلاث مهام بجدول تسليم وأوزان: المهمة الأولى مدتها تتطلب إنجازاً وموعد تسليم وميزان وزن، لنفترض أن لدينا جدولاً بثلاث مهام أوزانها هي $2$ و$1$ و$3$ على الترتيب. إذا أنجزت المهمة رقم $1$ في الموعد المحدد، وستأخر إنجاز المهمة رقم $2$ ثلاث ساعات عن موعد تسليمها، أما المهمة رقم $3$ فستتأخر إنجازها ساعة واحدة عن موعد تسليمها، فإن مجموع التباطؤ الموزون يساوي $3 \times 1 + 1 \times 3 = 6$.

أخطاء شائعة

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

سؤالان للتدريب مع الإجابة

السؤال الأول: كم عدد الجداول الممكنة لنسخة مشكلة التباطؤ الموزون للآلة الواحدة والتي تشتمل على تسع مهام؟ الإجابة: عدد الجداول الممكنة يساوي مضروب عدد المهام $N!$، وبالتالي للـ $9$ مهام يكون الناتج $9! = 362,880$ جدولاً. السؤال الثاني: صف بإيجاز طريقة عمل خوارزمية البحث المحلي. الإجابة: تبدأ الخوارزمية بحل أولي، ثم تقوم بشكل تكراري باكتشاف حلول مجاورة عبر إجراء تعديلات بسيطة مثل مبادلة موقعي مهمتين في الجدول، فإذا كان الحل المجاور الناتج يمتلك تباطؤاً أقل وجودة أفضل، فإنه يستبدل الحل الحالي، وتتكرر العملية حتى يتم الوصول إلى أفضل حل ممكن.