ملخص قوائم الانتظار (الطوابير): نمذجة وقت الانتظار وطول الطابور — أولى ثانوي

مقدمة

الوحدة الحادية عشرة: المحاكاة — الموضوع 11-4

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

أهداف التعلم

أن تعرّف قائمة الانتظار (الطابور).
أن تحسب وقت بدء الخدمة ووقت انتهائها ووقت الانتظار لكل عميل.
أن تقرأ مخطط تغير الطابور وتستخرج منه أطول وقت انتظار وأطول طابور.
أن تذكر تطبيقات للطوابير في الحاسوب.

شرح الدرس

مفهوم قائمة الانتظار

قائمة الانتظار (Queue): خط يتكون عندما ينتظر العملاء الحصول على خدمة، مثل الطابور أمام خزينة السوبر ماركت أو لعبة في مدينة الملاهي. ويُخدم العملاء بترتيب وصولهم: من يصل أولًا يُخدم أولًا.

معادلات الطابور (لخزينة واحدة)

1) وقت بدء الخدمة:

إذا لم يكن عند الخزينة عميل (لا يوجد طابور): وقت بدء الخدمة = وقت وصول العميل.
إذا كان هناك عميل سابق يُخدم: وقت بدء الخدمة = وقت انتهاء خدمة العميل السابق.

أي أن وقت بدء الخدمة هو الأكبر من بين: وقت وصول العميل، ووقت انتهاء خدمة العميل السابق.

2) وقت انتهاء الخدمة = وقت بدء الخدمة + مدة الخدمة

3) وقت الانتظار = وقت بدء الخدمة − وقت الوصول

فوقت الانتظار يتحدد بترتيب الوصول ومدة الخدمة.

تطبيقات في الحاسوب

لا يقتصر نموذج الطابور على البشر؛ فالحاسوب يستخدمه في:

معالجة المهام في وحدة المعالجة المركزية (CPU)؛ حيث تنتظر البرامج دورها.
طابور الطباعة؛ حيث تُطبع المستندات بترتيب إرسالها إلى الطابعة.

أمثلة وتطبيقات

مثال: خزينة واحدة، ومدة خدمة كل عميل 10 دقائق. أوقات الوصول (بالدقائق من وصول العميل الأول):

العميل	وقت الوصول	بدء الخدمة	انتهاء الخدمة	وقت الانتظار
1	0	0	10	0
2	5	10	20	5
3	12	20	30	8
4	40	40	50	0

طريقة الحل:

العميل 1 وجد الخزينة فارغة، فبدأ فورًا عند 0 وانتهى عند $0 + 10 = 10$ .
العميل 2 وصل عند 5 والخزينة مشغولة حتى 10؛ فبدأ عند 10، وانتظر $10 - 5 = 5$ دقائق.
العميل 3 وصل عند 12 والخزينة مشغولة حتى 20؛ فانتظر $20 - 12 = 8$ دقائق.
العميل 4 وصل عند 40 بعد انتهاء العميل 3 عند 30؛ فلم ينتظر.

قراءة النتائج:

أطول وقت انتظار: العميل 3 (8 دقائق).
من وصول العميل 3 حتى انتهاء خدمته: $30 - 12 = 18$ دقيقة.
أطول طابور: في الفترة من 12 إلى 20 دقيقة كان العميل 3 ينتظر بينما يُخدم العميل 2 (وقبلها من 5 إلى 10 كان العميل 2 ينتظر). يمكن تمثيل ذلك بمخطط أفقي يُظلل فيه وقت الخدمة بلون ووقت الانتظار بلون آخر لكل عميل.

ملاحظات مهمة

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

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

الطابور: خط انتظار يُخدم فيه العملاء بترتيب وصولهم.
وقت بدء الخدمة = وقت الوصول (لا طابور) أو وقت انتهاء السابق (يوجد طابور).
وقت انتهاء الخدمة = وقت البدء + مدة الخدمة.
وقت الانتظار = وقت البدء − وقت الوصول.
تطبيقات حاسوبية: جدولة المهام في CPU وطابور الطباعة.

ملخص الدرس

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

أسئلة للتدريب

عرّف قائمة الانتظار، واذكر مثالين من الحياة ومثالًا من الحاسوب.
اكتب معادلتي وقت انتهاء الخدمة ووقت الانتظار.
خزينة واحدة ومدة الخدمة 6 دقائق، وصل العملاء عند 0 و2 و4 دقائق. احسب وقت انتظار كل عميل.
في المثال السابق، متى تنتهي خدمة العميل الثالث؟
عميل وصل عند الدقيقة 30 وكانت الخزينة فارغة منذ الدقيقة 25. كم دقيقة ينتظر؟ ولماذا؟