نموذج الطابور

في نظرية الطابور، يُستخدم نموذج الطابور لتقريب حالة أو نظام طابور حقيقي، وذلك يمكننا من تحليل سلوك الطابور رياضياً. وتتيح لنا نماذج الطوابير أن نحدد مقاييس الأداء لعدد من الحالات المستقرة المستخدمة، بما في ذلك:

• متوسط العدد داخل الطابور أو النظام.
• متوسط الوقت الذي يُقضى في الطابور أو النظام.
• التوزيع الاحتمالي لهذه الأعداد أو الأوقات.
• احتمال امتلاء الطابور أو بقائه فارغاً.
• احتمال وجود النظام في حالة معينة.

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

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

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

يمكن تمثيل نماذج الطوابير باستخدام ترقيم كندال: A/B/S/K/N/Disk بحيث أن:

• A هو توزيع الأوقات الفاصلة بين القدوم.
• B يُمَثِّل توزيع أوقات الخدمة.
• S يُمَثِّل عدد الخوادم.
• K يُمَثِّل سعة النظام.
• N يُمَثِّل عدد النداءات.
• Disk يُمَثِّل طريقة الخدمة المفترضة.

في أحيان كثيرة تحذف آخر المتغيرات، وبالتالي فإن الترقيم يصبح A/B/S مع افتراض أن $K={\infty }$ و$N={\infty }$ وDisk=FIFO (FIFO من يدخل أولاً يخرج أولاً).

وهنا بعض الترقيمات القياسية للتوزيعات (A أو B):

• M تدل على التوزيع الماركوفي (أو الأسّي).
• Ek توزيع ايرلانج مع عدد k من المراحل.
• D توزيع انحرافي (أو مُحَدَّد) (ثابت).
• G توزيع عام (عشوائي).
• PH التوزيع حسب نوع المرحلة.

النماذج

البناء والتحليل

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

الطريقة العامة لبناء وتحليل النظام الطابوري هي:

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

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

طابور الخادم الواحد

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

الخدمة والقدوم على طريقة بويسون

$M/M/1/{\infty }/{\infty }$ تمثل خادماً واحداً لديه طابور غير محدود السعة وعدد لانهائي من النداءات، القدوم والخدمة كلاهما على طريقة بويسون (أو عمليات عشوائية)، وهذا يعني بأن التوزيع الإحصائي لكل من أوقات الخدمة والأوقات الفاصلة بين القدوم يتبعان التوزيع الأسِّي. وبسبب الطبيعة الرياضية للتوزيع الأسّي، فهناك عدد من العلاقات البسيطة للغاية قابلة لأن تُشتقَّ لمقاييس أداء متعددة وذلك بناء على معرفة معدلات القدوم والخدمة.

وهذا من حسن الحظ لأن نظام الـ M/M/1 الطابوري قابل لأن يستخدم لتقريب الكثير من حالات الطوابير.

الخدمة العامة والقدوم على طريقة بويسون

$M/G/1/{\infty }/{\infty }$ تمثل خادماً واحداً لديه طابور غير محدود السعة وعدد لانهائي من النداءات. في حين أن القدوم ما زال على طريقة بويسون، أي أن التوزيع الإحصائي للأوقات الفاصلة بين القدوم ما زال يتبع التوزيع الأسِّي، إلا أن توزيع وقت الخدمة لايتبع ذلك. فتوزيع وقت الخدمة قد يتبع أي توزيع إحصائي عام وليس فقط التوزيع الأسِّي. أما بالنسبة للعلاقات فهي ما زالت قابلة لأن تُشتقَّ لعددٍ (محدود) من مقاييس الأداء إذا كنا نعلم معدل القدوم والمتوسط والفرق لمعدل الخدمة. ومع ذلك فهذه الاشتقاقات عموماً أكثر تعقيداً.

إن عدداً من الحالات الخاصة منM/G/1 تقدم حلولاً محددة تعطي نظرة أعمق للنموذج الأفضل للاختيار لحالاتٍ محددة من الطوابير لأنها تسمح بالمقارنة بين هذه الحلول وأداء نموذج الـ M/M/1.

طابور الخوادم المتعددة

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

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

وكمثال بسيط لإثبات الحقيقة السابقة: لنفترض نظاماً بـ 8 خطوط إدخال وطابور وحيد و8 خوادم، وخط الإخراج بسعة 64 كيلوبت/ثانية. ولنفرض معدل القدوم في كل خط إدخال هو حزمتين/ثانية. إذاً فمعدل القدوم الكلي هو 16 حزمة/ثانية. وبمعدل 2000 بت لكل حزمة، سيكون معدل الخدمة 64 كيلوبت/ثانية/2000 بت = 32 حزمة/ثانية. وهنا، فمعدل وقت استجابة النظام هو:

1/(μ - λ) = 1/(32 - 16) = 0.0667 ثانية

والآن لنفترض نظاماً آخر بـ 8 طوابير، واحداً لكل خادم. وكل واحد من خطوط الإخراج الثمانية بسعة 8 كيلوبت/ثانية. وبالحسابات سيتضح لنا أن وقت استجابة النظام هو:

1/(μ - λ) = 1/(4 - 2) = 0.5 ثانية

ومعدل وقت الانتظار في الطابور في الحالة الأولى هو:

ρ/(1 - ρ)μ = 0.25

بينما في الحالة الثانية يصبح 0.03125

العدد اللانهائي من الخوادم

بينما لانجد هذه الحالة فعلياً في الواقع، فنموذج العدد اللانهائي من الخوادم (مثل $M/M/{\infty }$) هو نموذج نظري مريح للحالات التي تنطوي على تخزين أو تأخير، مثل مواقف السيارات والمستودعات وحتى التحولات الذرية. في هذه النماذج لاتوجد طوابير، فكلُ قادمٍ يتلقى الخدمة مباشرة. وحين ننظر له من الخارج، فالنموذج يبدو وكأنه يؤخر أو يحفظ كل عميل لبعض الوقت.