Near-optimal scheduling with general service times and IHR abandonment times

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

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

هذه الورقة البحثية، التي كتبها سامولي ألتو (Samuli Aalto)، تتناول النسخة الفوضوية والواقعية من هذه المشكلة. فبدلاً من افتراض أنماط بسيطة ومتوقعة، يسمح المؤلف بأي نوع من أوقات الخدمة (مثل "لاتيه" معقد يستغرق وقتاً طويلاً جداً) ونوع محدد من نفاد الصبر يسمى "معدل الخطر المتزايد" (IHR). و IHR هو طريقة منمقة للقول بأنك كلما انتظرت أكثر، زاد احتمال أن تفقد صبرك وتغادر — تمامًا مثل البشر الحقيقيين الذين يزداد غضبهم كلما تحرك الطابور ببطء. تستخدم الورقة أداة رياضية ذكية تسمى "مؤشر ويتل" (Whittle Index) لتحديد الترتيب الأمثل لخدمة الناس. والنتيجة الرئيسية هي أن هذه الطريقة الجديدة، التي تتعامل مع هذه السيناريوهات المعقدة والواقعية، تتفوق باستمرار على القاعدة التقليدية القديمة (المعروفة باسم قاعدة $c\mu/\theta$) في عمليات المحاكاة الحاسوبية. لقد أثبت المؤلف أن صيغته الجديدة سليمة رياضيًا للنسخة المبسطة من المشكلة، ثم أظهر من خلال المحاكاة أنها توفر المزيد من المال وتحافظ على سعادة المزيد من الزبائن مقارنة بالطرق الأفضل السابقة.

قصة الطابور النافد الصبر

تخيل طابور أمن مطار فوضويًا. لديك فريق من ضباط الأمن (الخادمين) وتدفق من المسافرين (الزبائن). لكل مسافر ساعتان غير مرئيتين تعملان: ساعة تعد تنازليًا لـ وقت الخدمة — وهو الوقت الذي يستغرقه فحص حقيبته والتحقق من هويته. والساعة الأخرى تعد تنازليًا لـ وقت الصبر — وهو الوقت الذي هو مستعد فيه للوقوف قبل أن يقرر تخطي الرحلة والعودة إلى منزله.

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

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

الصيغة السحرية: مؤشر ويتل

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

1. كم من الوقت انتظر بالفعل (x).
2. كم من الخدمة تلقاها بالفعل (y).
3. كم يكلف إبقاؤه في حالة انتظار (تكلفة الانتظار).
4. كم يكلف إذا غادر (عقوبة التخلي).

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

ثم تأخذ الورقة بطاقة التسجيل هذه وتكيفها للواقع المستمر حيث يصل الناس باستمرار. الصيغة الناتجة، $W_k(x, y)$، قد تبدو مخيفة عند النظر إليها، لكنها في الأساس تسأل: "إذا خدمت هذا الشخص لفترة وجيزة من الوقت، فكم من المال سأوفر مقارنة بخطر مغادرته؟"

المواجهة: الجديد مقابل القديم

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

• الفئة 1: مهام قصيرة (فحص سريع) ولكن بمستويات صبر متفاوتة.
• الفئة 2: مهام طويلة (فحص معقد) مع مستويات صبر مختلفة.

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

كانت النتائج واضية. تفوقت سياسة مؤشر ويتل الجديدة بشكل منهجي على القاعدة القديمة المعروفة باسم قاعدة $c\mu/\theta$.

• في سيناريو "المنتظم-المنتظم" (حيث يكون الجميع قابلين للتوقع نوعًا ما)، وفرت السياسة الجديدة حوالي 12% إلى 19% أكثر في التكاليف من القاعدة القديمة.
• في سيناريو "المنتظم-باريتو" (حيث يستغرق بعض الأشخاص أوقات خدمة طويلة وغير متوقعة)، اتسعت الفجوة. وفرت السياسة الجديدة 33% إلى 42% أكثر من القاعدة القديمة.
• حتى في السيناريوهات الأكثر تعقيدًا، كانت السياسة الجديدة أفضل باستمرار، وأحيانًا بنسبة تصل إلى 52%.

كما قارنت الورقة الطريقة الجديدة باستراتيجيات شائعة أخرى مثل "الخدمة حسب ترتيب الوصول" (First-Come-First-Served - خدمة أقدم شخص أولاً) و"مشاركة المعالج" (Processor-Sharing - تقسيم وقت الخادم بالتساوي بين الجميع). وقد هزمت سياسة مؤشر ويتل الجديدة جميعها.

لماذا هذا مهم؟

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