نظرية الأرتال

نظرية الطابور

معلومات عامة

صنف فرعي من	نظرية الاحتمال
يدرس	طابور
يدرسه	رياضياتي business operations manager (en)
نظام تصنيف حوسبة رابطة مكائن الحوسبة (2012)	10003689

نظرية الأرتال أو نظرية الطابور أو نظرية صفوف الانتظار أو نظرية الاِصْطِفاف (بالإنجليزية: Queuing theory)‏ هي دراسة رياضية لصفوف الانتظار (أو الطوابير).

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

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

التهجئة

تأتي كلمة queue من اللغة الفرنسية عن كلمة cauda اللاتينية والتي تعني «الذيل». ويفضل معظم الباحثين في هذا المجال كتابتها كـ "queueing" أكثر من "queuing"، على الرغم من أن الأخيرة أكثر شيوعاً إلى حدٍ ما في سياقاتٍ أخرى.

التاريخ

قام «أغنر كراروب إرلانغ» -وهو مهندس دانمركي يعمل في مقسم للهاتف في كوبنهاغن- بنشر أول ورقة عن نظرية الطابور عام 1909م. و من ثُمّ قدّم «ديفيد كيندال» طريقة A/B/C لترقيم الطابور في 1953م. أما أهم العمل على نظرية الطابور والذي يستخدم في شبكات تبديل الحزم الحديثة فقد أنجزها «ليونارد كلينروك» في أوائل الستينات في القرن الحالي.

طريقة الترقيم

ستجد المزيد من التفاصيل عن هذا الترقيم في مقالة نموذج الطابور

اقترح ديفيد كندال في عام 1953م طريقة ترقيم لوصف الخصائص المميزة لنموذج الطابور. وقَدَّم كندال طريقة A/B/C للترقيم، والتي نجدها في كل الأعمال القياسية الحديثة في نظرية الطابور، مثل تيجيمس.

ترقيم A/B/C يُحدد بعض خصائص نظام الطابور، بحيث أن A تُمثِّل توزيع الأوقات الفاصلة للقدوم و B هي توزيع وقت الخدمة و C تُمثِّل عدد الخوادم. فعلى سبيل المثال: G/D/1 يشير إلى طريقة وصول عامة (ربما أي شيء) ووقت محدد لعملية الخدمة (وقت ثابت) وخادم واحد.

تطبيقاته في الاتصالات الهاتفية

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

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

انضباط الطابور هو الذي يقرر الطريقة التي تتعامل بها مع الدعوات القادمة من العميل. وتحدد الطريقة التي ستتم خدمتهم بها (طريقة ترتيبهم حتى تتم خدمتهم) والطريقة التي تقسم بها الموارد على العملاء أو الزبائن. وهنا تفاصيل لثلاثة أنواع من الطوابير:

• من يدخل أولاً يخرج أولاً:

ينص هذا المبدأ على أن العملاء يُخدمون واحداً واحداً. والعميل الذي انتظر مدةً أطول يُخدم أولاً.

• من يدخل أخيراً يخرج أولاً:

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

• تَقَاسُم المعالج:

جميع العملاء يُخدمون على حدٍّ سواء. فسعة الشبكة ستكون مشتركة بين العملاء، ولهم جميعاً نفس التأخير.

• الأولوية:

العملاء ذوو الأولوية العليا سَيُخدمون أولاً.

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

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

تنطوي نظرية الطابور الكلاسيكية على الحسابات المعقدة لتحديد وقت انتظار المكالمات ووقت الخدمة ومدى فاعلية الخادم والكثير من المقاييس الأخرى التي تستخدم لقياس أداء الطابور.

شبكات الطوابير

يمكن جمع الطوابير لتصبح شبكة من السلاسل بحيث أن المغادرون من أحد الطوابير يدخلون على الطابور التالي. ويمكن تصنيف شبكات الطوابير إلى فئتين:

• شبكات الطوابير المفتوحة: حيث تكون مُدخلاتها خارجية ومُخرجاتها أيضاً خارجية.
• شبكات الطوابير المغلقة: وتكون مغلقة تماماً بحيث أن الزبائن يدورون داخل الشبكة ولا يغادرونها أبداً.

دور عملية بواسون والتوزيعات الأُسِّية

النموذج المفيد من الطابور هو الذي:

• يمثل نظام الحياة الواقعية بدقة كافية.
• وقابل للتحليل.

حين يكون نموذج الطابور معتمداً على عملية بويسون ومرافقه التوزيع الاحتمالي الأُسِّي فإنه في كثير من الأحيان يجمع هذان المتطلبان.

عملية بويسون: تمثل الأحداث العشوائية (مثل وصول عميل أو طلب لأمر ما من خادم الشبكة أو الانتهاء من الإجراءات المطلوبة من خادم الشبكة) حيث أنها تعتبر عملية بدون ذاكرة (أي أنها تُنسى بمجرد الانتهاء منها).

و على هذا فإن طول الفترة الزمينة الفاصلة بين الوقت الحالي ووقت حدوث الحدث المقبل لاتعتمد على وقت وقوع الحدث الأخير. فيسجل الملاحظ عدداً من أحداث توزيع بواسون التي تحدث في فترة لها طول ثابت. يسجل الملاحظ الفترة للأحداث المتتالية في توزيع الاحتمال الأُسِّي (السلبي). فالعملية في كليهما تكون بدون ذاكرة (أي بمجرد الانتهاء منها لا يحتفظ بها).

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

بالإضافة إلى أن شكل حل النماذج يستند إلى عملية بواسون وغالباً ما يقدم نظرة ثاقبة لشكل حلول مشاكل الطابور والتي غالباً ما تُحاكى بشكلٍ سيء. ونتيجة لذلك فإنه كثيراً ما تكون نماذج الطوابير على شكل البواسون من خلال استخدام التوزيع الأسِّي.

قيود الطريقة الرياضية

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

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

تم وضع الوسائل البديلة للتحليل من أجل تقديم فكرة عن المشاكل التي لا تندرج تحت النطاق الرياضي لنظرية الطابور، رغم أنها في كثير من الأحيان ذات سيناريو محدد لأنها عامةً تتكون من المحاكاة الحاسوبية أو/و تحليل البيانات التجريبية.