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

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

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

تعود جذور نظرية الطوابير إلى أبحاث أجراها أغنر كراروب إرلانغ ، الذي ابتكر نماذج لوصف نظام المكالمات الواردة في شركة كوبنهاغن لتبادل الهاتف. [ 1 ] وقد شكلت هذه الأفكار ركيزة أساسية في مجال هندسة حركة الاتصالات ، وشهدت منذ ذلك الحين تطبيقات في الاتصالات السلكية واللاسلكية ، وهندسة المرور ، والحوسبة ، [ 2 ] وإدارة المشاريع ، ولا سيما الهندسة الصناعية ، حيث تُطبق في تصميم المصانع والمتاجر والمكاتب والمستشفيات. [ 3 ] [ 4 ]

وصف

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

عقدة طابور واحدة

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

صندوق أسود. تصل المهام إلى قائمة الانتظار وتغادرها.

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

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

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

عملية الولادة والوفاة

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

ينتقل النظام بين قيم k عن طريق الولادات والوفيات ، والتي تحدث بمعدلات الوصول .λأنا{\displaystyle \lambda _{i}}ومعدلات المغادرةμأنا{\displaystyle \mu _{i}}لكل وظيفةأنا{\displaystyle i}بالنسبة لطابور الانتظار، تُعتبر هذه المعدلات عمومًا ثابتة بغض النظر عن عدد المهام في الطابور، لذا يُفترض معدل وصول/مغادرة متوسط ​​واحد لكل وحدة زمنية. وبناءً على هذا الافتراض، يكون معدل وصول هذه العملية هوλ=متوسط(λ1،λ2،...،λك){\displaystyle \lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})}ومعدل مغادرة قدرهμ=متوسط(μ1،μ2،...،μك){\displaystyle \mu ={\text{avg}}(\mu _{1},\mu _{2},\dots ,\mu _{k})}.

عملية ولادة وموت. تمثل القيم الموجودة في الدوائر حالة النظام، والتي تتطور بناءً على معدلات الوصول λ i ومعدلات المغادرة μ i .
طابور به خادم واحد، ومعدل وصول λ ومعدل مغادرة μ

موازنة المعادلات

معادلات الحالة المستقرة لعملية الولادة والوفاة، والمعروفة بمعادلات التوازن ، هي كما يلي.Pن{\displaystyle P_{n}}يشير إلى احتمالية الحالة المستقرة للتواجد في الحالة n .

μ1P1=λ0P0{\displaystyle \mu _{1}P_{1}=\lambda _{0}P_{0}}
λ0P0+μ2P2=(λ1+μ1)P1{\displaystyle \lambda _{0}P_{0}+\mu _{2}P_{2}=(\lambda _{1}+\mu _{1})P_{1}}
λن-1Pن-1+μن+1Pن+1=(λن+μن)Pن{\displaystyle \lambda _{n-1}P_{n-1}+\mu _{n+1}P_{n+1}=(\lambda _{n}+\mu _{n})P_{n}}

المعادلتان الأوليان تعنيان

P1=λ0μ1P0{\displaystyle P_{1}={\frac {\lambda _{0}}{\mu _{1}}}P_{0}}

و

P2=λ1μ2P1+1μ2(μ1P1-λ0P0)=λ1μ2P1=λ1λ0μ2μ1P0{\displaystyle P_{2}={\frac {\lambda _{1}}{\mu _{2}}}P_{1}+{\frac {1}{\mu _{2}}}(\mu _{1}P_{1}-\lambda _{0}P_{0})={\frac {\lambda _{1}}{\mu _{2}}}P_{1}={\frac {\lambda _{1}\lambda _{0}}{\mu _{2}\mu _{1}}}P_{0}}.

بالاستقراء الرياضي،

Pن=λن-1λن-2⋯λ0μنμن-1⋯μ1P0=P0∏أنا=0ن-1λأناμأنا+1// _{i}}{\mu _{i+1}}}}.

الحالة∑ن=0∞Pن=P0+P0∑ن=1∞∏أنا=0ن-1λأناμأنا+1=1{\displaystyle \sum _{n=0}^{\infty}P_{n}=P_{0}+P_{0}\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}=1}يؤدي إلى

P0=11+∑ن=1∞∏أنا=0ن-1λأناμأنا+1{\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}}}

والتي، بالإضافة إلى معادلةPن{\displaystyle P_{n}}(ن≥1){\displaystyle (n\geq 1)}، يصف بشكل كامل احتمالات الحالة المستقرة المطلوبة.

تدوين كيندال

تُوصَف عقد الانتظار الفردية عادةً باستخدام ترميز كيندال على الصورة A/S/ c ، حيث يصف A توزيع المدد الزمنية بين كل وصول إلى قائمة الانتظار، وS توزيع أوقات خدمة المهام، و c عدد الخوادم في العقدة. [ 6 ] [ 7 ] كمثال على هذا الترميز، تُعد قائمة انتظار M/M/1 نموذجًا بسيطًا حيث يخدم خادم واحد مهامًا تصل وفقًا لعملية بواسون (حيث تتوزع المدد الزمنية بين الوصولات توزيعًا أُسّيًا ) ولها أوقات خدمة موزعة أُسّيًا (يشير M إلى عملية ماركوف ). في قائمة انتظار M/G/1 ، يرمز G إلى "عام" ويشير إلى توزيع احتمالي عشوائي لأوقات الخدمة.

تحليل نموذجي لطابور M/M/1

لنفترض وجود طابور بخادم واحد وبالخصائص التالية:

  • λ{\displaystyle \lambda }معدل الوصول (مقلوب الوقت المتوقع بين وصول كل عميل، على سبيل المثال 10 عملاء في الثانية)
  • μ{\displaystyle \mu }: مقلوب متوسط ​​وقت الخدمة (العدد المتوقع لعمليات إكمال الخدمة المتتالية لكل وحدة زمنية، على سبيل المثال لكل 30 ثانية)
  • n : المعامل الذي يحدد عدد العملاء في النظام
  • Pن{\displaystyle P_{n}}: احتمال وجود n عميل في النظام في حالة الاستقرار

علاوة على ذلك، دعهـن{\displaystyle E_{n}}يمثل عدد مرات دخول النظام في الحالة n ، ولن{\displaystyle L_{n}}يمثل عدد مرات خروج النظام من الحالة n . ثم|هـن-لن|∈{0،1}{\displaystyle \left\vert E_{n}-L_{n}\right\vert \in \{0,1\}}لكل n . أي أن عدد مرات خروج النظام من حالة معينة يختلف بمقدار 1 على الأكثر عن عدد مرات دخوله تلك الحالة، لأنه سيعود إلى تلك الحالة في وقت ما في المستقبل (هـن=لن{\displaystyle E_{n}=L_{n}}) أو لا (|هـن-لن|=1{\displaystyle \left\vert E_{n}-L_{n}\right\vert =1}).

عندما يصل النظام إلى حالة مستقرة، يجب أن يكون معدل الوصول مساوياً لمعدل المغادرة.

وبالتالي معادلات التوازن

μP1=λP0{\displaystyle \mu P_{1}=\lambda P_{0}}
λP0+μP2=(λ+μ)P1{\displaystyle \lambda P_{0}+\mu P_{2}=(\lambda +\mu )P_{1}}
λPن-1+μPن+1=(λ+μ)Pن{\displaystyle \lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_{n}}

يعني

Pن=λμPن-1، ن=1،2،...{\displaystyle P_{n}={\frac {\lambda }{\mu }}P_{n-1},\ n=1,2,\ldots }

حقيقة أنP0+P1+⋯=1{\displaystyle P_{0}+P_{1}+\cdots =1}يؤدي ذلك إلى صيغة التوزيع الهندسي

Pن=(1-ρ)ρن{\displaystyle P_{n}=(1-\rho )\rho ^{n}}

أينρ=λμ<1{\displaystyle \rho ={\frac {\lambda }{\mu }}<1}.

طابور بسيط بمعادلتين

يُنسب نظام الطوابير الأساسي الشائع إلى إرلانج ، وهو تعديل لقانون ليتل . بمعلومية معدل وصول λ ، ومعدل تسرب σ ، ومعدل مغادرة μ ، يُعرَّف طول الطابور L على النحو التالي:

ل=λ-σμ{\displaystyle L={\frac {\lambda -\sigma }{\mu }}}.

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

μλ=هـ-دبليوμ{\displaystyle {\frac {\mu }{\lambda }}=e^{-W{\mu }}}

تُعاد كتابة المعادلة الثانية عادةً على النحو التالي:

دبليو=1μلنλμ{\displaystyle W={\frac {1}{\mu }}\mathrm {ln} {\frac {\lambda }{\mu }}}

يُعد نموذج الصندوق الواحد ذو المرحلتين شائعًا في علم الأوبئة . [ 8 ]

تاريخ

في عام 1909، نشر أغنر كراروب إرلانغ ، وهو مهندس دنماركي كان يعمل في مقسم كوبنهاغن للهاتف، أول ورقة بحثية حول ما يُعرف الآن بنظرية الطوابير. [ 9 ] [ 10 ] [ 11 ] وقد وضع نموذجًا لعدد المكالمات الهاتفية الواردة إلى المقسم باستخدام عملية بواسون ، وحلّ طابور M/D/1 في عام 1917 ونموذج طابور M/D/ k في عام 1920. [ 12 ] باستخدام ترميز كيندال:

  • يرمز الحرف M إلى ماركوف أو عديم الذاكرة ، ويعني أن عمليات الوصول تحدث وفقًا لعملية بواسون.
  • يرمز الحرف D إلى الحتمية ، ويعني أن الوظائف التي تصل إلى قائمة الانتظار تتطلب مقدارًا ثابتًا من الخدمة
  • يصف k عدد الخوادم في عقدة الانتظار ( k = 1، 2، 3، ...)

إذا كان لدى العقدة وظائف أكثر من الخوادم، فستقوم الوظائف بالانتظار في قائمة الانتظار للحصول على الخدمة.

تم حل مشكلة طابور الانتظار M/G/1 بواسطة فيليكس بولاتشيك في عام 1930، [ 13 ] وهو حل أعيد صياغته لاحقًا بعبارات احتمالية بواسطة ألكسندر خينشين ، ويُعرف الآن باسم صيغة بولاتشيك-خينشين . [ 12 ] [ 14 ]

بعد أربعينيات القرن العشرين، أصبحت نظرية الطوابير مجالًا بحثيًا ذا أهمية بالغة لعلماء الرياضيات. [ 14 ] في عام 1953، حلّ ديفيد جورج كيندال طابور GI/M/ k [ 15 ] وقدّم الترميز الحديث للطوابير، المعروف الآن باسم ترميز كيندال . في عام 1957، درس بولاتشيك طابور GI/G/1 باستخدام معادلة تكاملية . [ 16 ] وقدّم جون كينغمان صيغة لحساب متوسط ​​وقت الانتظار في طابور G/G/1 ، تُعرف الآن باسم صيغة كينغمان . [ 17 ]

عمل ليونارد كلاينروك على تطبيق نظرية الطوابير على تبديل الرسائل في أوائل الستينيات وتبديل الحزم في أوائل السبعينيات. وكانت مساهمته الأولى في هذا المجال أطروحته للدكتوراه في معهد ماساتشوستس للتكنولوجيا عام 1962، والتي نُشرت في كتاب عام 1964. وقد أرست أعماله النظرية التي نُشرت في أوائل السبعينيات الأساس لاستخدام تبديل الحزم في شبكة أربانت ، وهي شبكة رائدة للإنترنت.

أتاحت طريقة الهندسة المصفوفية وطرق التحليل المصفوفي إمكانية دراسة الطوابير ذات التوزيعات المرحلية بين أوقات الوصول وأوقات الخدمة. [ 18 ]

تُعد الأنظمة ذات المدارات المترابطة جزءًا مهمًا في نظرية الطوابير في تطبيقها على الشبكات اللاسلكية ومعالجة الإشارات. [ 19 ]

يتناول التطبيق الحديث لنظرية الطوابير، من بين أمور أخرى، تطوير المنتجات حيث تتمتع المنتجات (المادية) بوجود مكاني وزماني، بمعنى أن للمنتجات حجماً معيناً ومدة زمنية معينة. [ 20 ]

لا تزال مشاكل مثل مقاييس الأداء لطابور M /G/ k مشكلة مفتوحة. [ 12 ] [ 14 ]

تخصصات الخدمة

يمكن استخدام سياسات جدولة متنوعة في عقد الانتظار:

أسبقية الدخول، أسبقية الخروج
مثال على قائمة انتظار "الأول في الأول خارج" (FIFO)
يُعرف هذا المبدأ أيضاً باسم "الأسبقية لمن يأتي أولاً" (FCFS)، [ 21 ] وينص على أنه يتم خدمة العملاء واحداً تلو الآخر، وأن العميل الذي انتظر أطول مدة يتم خدمته أولاً. [ 22 ]
آخر الداخلين، أول الخارجين
يُطبَّق هذا المبدأ أيضاً على العملاء فرداً فرداً، ولكن يُخدَم العميل الذي لديه أقصر وقت انتظار أولاً. [ 22 ] يُعرف أيضاً باسم "التكديس" .
مشاركة المعالج
يتم توزيع سعة الخدمة بالتساوي بين العملاء. [ 22 ]
الخدمة بترتيب عشوائي (SIRO)
ويطلق على هذا النظام أيضًا اسم الترتيب العشوائي للخدمة (ROS)، وينص على أن المهمة التالية التي يتم خدمتها يتم اختيارها عشوائيًا من بين المهام المنتظرة في قائمة الانتظار.
أولوية
يُخدَم العملاء ذوو الأولوية العالية أولاً. [ 22 ] يمكن أن تكون قوائم الانتظار ذات الأولوية من نوعين: غير قابلة للمقاطعة (حيث لا يمكن مقاطعة مهمة قيد التنفيذ) وقابلة للمقاطعة (حيث يمكن مقاطعة مهمة قيد التنفيذ بواسطة مهمة ذات أولوية أعلى). لا تُفقد أي أعمال في أي من النموذجين. [ 23 ]
ابدأ بأقصر مهمة
المهمة التالية التي يجب إنجازها هي المهمة ذات الحجم الأصغر. [ 24 ]
البدء بأقصر المهام أولاً
المهمة التالية التي يجب إنجازها هي تلك التي لها أصغر حجم أصلي. [ 25 ]
أقصر وقت معالجة متبقٍ
المهمة التالية التي يجب إنجازها هي تلك التي تتطلب أقل قدر من المعالجة المتبقية. [ 26 ]
مرفق الخدمة
  • خادم واحد: يصطف الزبائن ولا يوجد سوى خادم واحد
  • عدة خوادم متوازية (طابور واحد): يصطف العملاء في طابور، وهناك عدة خوادم.
  • عدة خوادم متوازية (عدة طوابير): يوجد العديد من العدادات ويمكن للعملاء اختيار الطابور الذي يرغبون في الانتظار فيه
خادم غير موثوق

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

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

يُعرف العملاء الذين يصلون ولا يتم خدمتهم (إما لعدم وجود مساحة كافية في الطابور، أو بسبب امتناعهم أو تراجعهم) باسم "المتسربين" . ويُعدّ متوسط ​​معدل التسربات مؤشراً هاماً لوصف الطابور.

شبكات الانتظار

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

بالنسبة للشبكات المكونة من m عقدة، يمكن وصف حالة النظام بواسطة متجه ذي m بُعد (x1، x2 ، ... ، xm ) حيث يمثل xi عدد العملاء في كل عقدة .

تُسمى أبسط شبكات الطوابير غير التافهة بالطوابير المتتالية . [ 28 ] كانت أولى النتائج المهمة في هذا المجال هي شبكات جاكسون ، [ 29 ] [ 30 ] التي تتميز بتوزيع ثابت فعال على شكل حاصل ضرب ، ويمكن حساب تحليل القيمة المتوسطة لها [ 31 ] (الذي يسمح بحساب متوسط ​​المقاييس مثل الإنتاجية وأوقات الإقامة). [ 32 ] إذا ظل العدد الإجمالي للعملاء في الشبكة ثابتًا، تُسمى الشبكة شبكة مغلقة ، وقد ثبت أن لها أيضًا توزيعًا ثابتًا على شكل حاصل ضرب باستخدام نظرية جوردون-نيويل . [ 33 ] تم توسيع هذه النتيجة لتشمل شبكة BCMP ، [ 34 ] حيث تبين أن الشبكة ذات أوقات الخدمة العامة جدًا، والأنظمة، وتوجيه العملاء، تُظهر أيضًا توزيعًا ثابتًا على شكل حاصل ضرب. يمكن حساب ثابت التطبيع باستخدام خوارزمية بوزن ، التي طُرحت عام 1973. [ 35 ]

كما تمّت دراسة شبكات العملاء، مثل شبكات كيلي ، حيث يختبر عملاء من فئات مختلفة مستويات أولوية مختلفة في نقاط خدمة مختلفة. [ 36 ] وهناك نوع آخر من الشبكات هو شبكات G ، التي اقترحها إيرول جيلينبي لأول مرة عام 1993: [ 37 ] ولا تفترض هذه الشبكات توزيعات زمنية أسية مثل شبكة جاكسون الكلاسيكية.

خوارزميات التوجيه

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

حدود المجال المتوسط

تأخذ نماذج المجال المتوسط ​​في الاعتبار السلوك الحدي للمقياس التجريبي (نسبة الطوابير في حالات مختلفة) عندما يقترب عدد الطوابير m من اللانهاية. ويتم تقريب تأثير الطوابير الأخرى على أي طابور معين في الشبكة بمعادلة تفاضلية. ويتقارب النموذج الحتمي إلى نفس التوزيع الثابت للنموذج الأصلي. [ 39 ]

تقريب الازدحام المروري/الانتشار الكثيف

في نظام ذي معدلات إشغال عالية (استخدام يقارب 1)، يمكن استخدام تقريب حركة المرور الكثيفة لتقريب عملية طول الطابور بواسطة حركة براونية منعكسة ، [ 40 ] أو عملية أورنستين-أولينبيك ، أو عملية انتشار أكثر عمومية . [ 41 ] عدد أبعاد العملية البراونية يساوي عدد عقد الطابور، مع اقتصار الانتشار على الجزء غير السالب من الفضاء الإقليدي .

حدود السوائل

تُعدّ نماذج الموائع نظائر حتمية مستمرة لشبكات الانتظار، تُستخلص بأخذ النهاية عند تغيير مقياس العملية في الزمان والمكان، مما يسمح بوجود عناصر غير متجانسة. يتقارب هذا المسار المُقاس إلى معادلة حتمية تُتيح إثبات استقرار النظام. من المعروف أن شبكة الانتظار قد تكون مستقرة، ولكن لها حدّ مائع غير مستقر. [ 42 ]

تطبيقات إدارة قوائم الانتظار

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

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

تتناول نظرية الطوابير مفاهيم أساسية متعددة، حيث تُعدّ عملية الوصول وعملية الخدمة محوريتين فيها. تصف عملية الوصول كيفية انضمام الكيانات إلى الطابور بمرور الوقت، وغالبًا ما تُنمذج باستخدام عمليات عشوائية مثل عمليات بواسون. تُقاس كفاءة أنظمة الطوابير من خلال مؤشرات أداء رئيسية، تشمل متوسط ​​طول الطابور، ومتوسط ​​وقت الانتظار، وإنتاجية النظام. توفر هذه المؤشرات رؤى ثاقبة حول وظائف النظام، مما يُساعد في اتخاذ القرارات الرامية إلى تحسين الأداء وتقليل أوقات الانتظار. [ 43 ] [ 44 ] [ 45 ]

انظر أيضاً

مراجع

  1. 1 2 3 سوندارابانديان، ف. (2009). "7. نظرية الطوابير". الاحتمالات والإحصاء ونظرية الطوابير . دار نشر PHI Learning. ISBN 978-81-203-3844-9.
  2. ↑ لورانس دبليو. داودي، فيرجيلو إيه إف ألميدا، دانيال إيه. ميناسكي. "الأداء بالتصميم: تخطيط سعة الحاسوب من خلال الأمثلة" . مؤرشف من الأصل بتاريخ 2016-05-06 . تم الاطلاع عليه بتاريخ 2009-07-08 .
  3. ↑ شليختر، كيرا (2 مارس 2009). "مركز هيرشي الطبي يفتتح غرفة طوارئ مُعاد تصميمها" . صحيفة ذا باتريوت نيوز . مؤرشف من الأصل في 29 يونيو 2016. تم الاطلاع عليه في 12 مارس 2009 .
  4. ↑ مايهيو، ليس؛ سميث، ديفيد (ديسمبر 2006). استخدام نظرية الطوابير لتحليل أوقات الإنجاز في أقسام الحوادث والطوارئ في ضوء هدف الحكومة المتمثل في 4 ساعات . كلية كاس للأعمال . ISBN 978-1-905752-06-5أُرشف من الأصل في 7 سبتمبر 2021. تم الاطلاع عليه بتاريخ 20 مايو 2008 .
  5. 1 2 3 تايلور، برنارد و. (2019). مقدمة في علم الإدارة ( الطبعة الثالثة عشرة). نيويورك: بيرسون. ISBN  978-0-13-473066-0.
  6. ↑ تيمز، إتش سي، التحليل الخوارزمي للطوابير ، الفصل 9 في كتاب "مقدمة في النماذج العشوائية"، وايلي، تشيتشستر، 2003
  7. ↑ كيندال، د. ج. (1953). "العمليات العشوائية التي تحدث في نظرية الطوابير وتحليلها باستخدام طريقة سلسلة ماركوف المضمنة" . حوليات الإحصاء الرياضي . 24 (3): 338-354 . doi : 10.1214/aoms/1177728975 . JSTOR 2236285 . 
  8. ↑ هيرنانديز-سواريز، كارلوس (2010). "تطبيق نظرية الطوابير على نماذج الأوبئة SIS وSEIS" . الرياضيات الحيوية . 7 (4): 809-823 . doi : 10.3934/mbe.2010.7.809 . PMID 21077709 . 
  9. ↑ "أجنر كراروب إرلانغ (1878-1929) | plus.maths.org" . Pass.maths.org.uk. 30 أبريل 1997. مؤرشف من الأصل في 7 أكتوبر 2008. تم الاطلاع عليه في 22 أبريل 2013 .
  10. ^ أسموسن، ريال. بوكسما، الجريدة الرسمية (2009). “مقدمة التحرير”. أنظمة الانتظار . 63 ( 1– 4): 1– 2. دوى : 10.1007/s11134-009-9151-8 . S2CID 45664707 . 
  11. ↑ إرلانغ، أغنر كراروب (1909). "نظرية الاحتمالات والمحادثات الهاتفية" (ملف PDF) . مجلة الرياضيات الجديدة ب . 20 : 33-39 . مؤرشف من الأصل (ملف PDF) بتاريخ 1 أكتوبر 2011.
  12. كينغمان ، جيه إف سي ( 2009 ). "القرن الأول لإرلانج - والقرن التالي". أنظمة الانتظار . 63 ( 1-4 ): 3-4 . doi : 10.1007/s11134-009-9147-4 . S2CID 38588726 . 
  13. ^ Pollaczek، F.، Ueber eine Aufgabe der Wahrscheinlichkeitstheorie، Math. ز. 1930
  14. 1 2 3 ويتل، ب. (2002). "الاحتمالات التطبيقية في بريطانيا العظمى" . بحوث العمليات . 50 (1): 227-239 . doi : 10.1287/opre.50.1.227.17792 . JSTOR 3088474 . 
  15. ↑ كيندال، دي جي: العمليات العشوائية التي تحدث في نظرية الطوابير وتحليلها بطريقة سلسلة ماركوف المضمنة، حوليات الإحصاء الرياضي 1953
  16. ^ Pollaczek، F.، مشاكل Stochastiques التي تطرحها ظاهرة تشكيل قائمة الانتظار
  17. ↑ كينغمان، جيه إف سي ؛ عطية (أكتوبر 1961). "طابور الخادم الواحد في حالة الازدحام الشديد". وقائع الجمعية الفلسفية في كامبريدج الرياضية . 57 (4 ) : 902. Bibcode : 1961PCPS...57..902K . doi : 10.1017/S0305004100036094 . JSTOR 2984229. S2CID 62590290 .  
  18. ↑ راماسوامي، ف. (1988). "علاقة تكرارية مستقرة لمتجه الحالة المستقرة في سلاسل ماركوف من النوع m/g/1". الاتصالات في الإحصاء. النماذج العشوائية . 4 : 183-188 . doi : 10.1080/15326348808807077 .
  19. ↑ موروزوف، إي. (2017). "تحليل استقرار نظام إعادة محاكمة متعدد الفئات مع طوابير مدارية مقترنة". وقائع ورشة العمل الأوروبية الرابعة عشرة . سلسلة محاضرات في علوم الحاسوب. المجلد 17. الصفحات 85-98 . doi : 10.1007/978-3-319-66583-2_6 . ISBN   978-3-319-66582-5.
  20. ↑ كارلسون، إي سي؛ فيلدر، آر إم (1992). "محاكاة ونمذجة شبكة الانتظار لحملات إنتاج منتج واحد" . الحوسبة والهندسة الكيميائية . 16 (7): 707-718 . doi : 10.1016/0098-1354(92)80018-5 .
  21. 1 2 مانويل، لاجونا (2011). نمذجة عمليات الأعمال ومحاكاتها وتصميمها . بيرسون للتعليم الهند. ص 178. ISBN  978-81-317-6135-9تم الاطلاع عليه بتاريخ 6 أكتوبر 2017 .
  22. 1 2 3 4 Penttinen A., الفصل 8 – أنظمة الانتظار ، ملاحظات المحاضرة: S-38.145 - مقدمة في نظرية حركة المرور عن بعد.
  23. ↑ هارتشول-بالتر، م. (2012). "الجدولة: سياسات غير استباقية قائمة على الحجم". نمذجة الأداء وتصميم أنظمة الحاسوب . ص 499-507 . doi : 10.1017/CBO9781139226424.039 . ISBN  978-1-139-22642-4.
  24. ↑ أندرو س. تانينباوم؛ هربرت بوس (2015). أنظمة التشغيل الحديثة . بيرسون. ISBN 978-0-13-359162-0.
  25. ↑ هارتشول-بالتر، م. (2012). "الجدولة: سياسات استباقية قائمة على الحجم". نمذجة الأداء وتصميم أنظمة الحاسوب . ص 508-517 . doi : 10.1017/CBO9781139226424.040 . ISBN  978-1-139-22642-4.
  26. ↑ هارتشول-بالتر، م. (2012). "الجدولة: جدولة التكرار المتسلسل للوقت والإنصاف". نمذجة الأداء وتصميم أنظمة الحاسوب . ص 518-530 . doi : 10.1017/CBO9781139226424.041 . ISBN  978-1-139-22642-4.
  27. ↑ ديميتريو، آي. (2019). "نظام إعادة محاكمة متعدد الفئات مع مدارات مقترنة وانقطاعات الخدمة: التحقق من شروط الاستقرار". وقائع مؤتمر FRUCT 24. 7 : 75-82 .
  28. ↑ "المحاضرة 13: طوابير M/M/1 وشبكات الطوابير" (ملف PDF) . مؤرشف (PDF) من الأصل بتاريخ 29-03-2017 . تم الاطلاع عليه بتاريخ 02-08-2018 .
  29. ↑ جاكسون، الابن (1957). "شبكات خطوط الانتظار". بحوث العمليات . 5 (4): 518-521 . doi : 10.1287/opre.5.4.518 . JSTOR 167249 . 
  30. ↑ جاكسون، جيمس ر. (أكتوبر 1963). "أنظمة الانتظار الشبيهة بأنظمة ورش العمل". مجلة علوم الإدارة . 10 (1): 131-142 . doi : 10.1287/mnsc.1040.0268 . JSTOR 2627213 . 
  31. ↑ ريزر، م.؛ لافنبرغ، س.س. (1980). "تحليل القيمة المتوسطة لشبكات الانتظار متعددة السلاسل المغلقة" . مجلة ACM . 27 (2): 313. doi : 10.1145/322186.322195 . S2CID 8694947 . 
  32. ↑ فان دايك، ن.م. (1993). "حول نظرية الوصول لشبكات الاتصالات" . شبكات الحاسوب وأنظمة ISDN . 25 (10): 1135-2013 . doi : 10.1016/0169-7552(93)90073-D . S2CID 45218280. مؤرشف من الأصل بتاريخ 24-09-2019 . تم الاسترجاع بتاريخ 24-09-2019 . 
  33. ↑ غوردون، دبليو جيه؛ نيويل، جي إف (1967). "أنظمة الانتظار المغلقة مع خوادم أسية". بحوث العمليات . 15 (2): 254. doi : 10.1287/opre.15.2.254 . JSTOR 168557 . 
  34. ↑ باسكت، ف.؛ تشاندي، ك.؛ ماني ؛ مونتز، ر. ر.؛ بالاسيوس، ف. ج. (1975). "شبكات طوابير مفتوحة ومغلقة ومختلطة مع فئات مختلفة من العملاء" . مجلة ACM . 22 (2): 248-260 . doi : 10.1145/321879.321887 . S2CID 15204199 . 
  35. ↑ بوزين، جيه بي (1973). "خوارزميات حسابية لشبكات الانتظار المغلقة ذات الخوادم الأسية" ( ملف PDF) . مجلة اتصالات رابطة مكائن ​​الحوسبة . 16 (9): 527-531 . doi : 10.1145/362342.362345 . S2CID 10702. مؤرشف (ملف PDF) من الأصل بتاريخ 13 مايو 2016. تم الاطلاع عليه بتاريخ 1 سبتمبر 2015 . 
  36. ↑ كيلي، ف. ب. (1975). " شبكات الطوابير ذات العملاء من أنواع مختلفة". مجلة الاحتمالات التطبيقية . 12 (3): 542-554 . doi : 10.2307/3212869 . JSTOR 3212869. S2CID 51917794 .  
  37. ↑ جيلينبي، إيرول (سبتمبر 1993). " شبكات G مع حركة العملاء المُحفَّزة". مجلة الاحتمالات التطبيقية . 30 (3): 742-748 . doi : 10.2307/3214781 . JSTOR 3214781. S2CID 121673725 .  
  38. ↑ نيويل، جي إف (1982). تطبيقات نظرية الطوابير . doi : 10.1007/978-94-009-5970-5 . ISBN 978-94-009-5972-9.
  39. ↑ بوبيو، أ.؛ غريباودو، م.؛ تيليك، م.س. (2008). "تحليل الأنظمة التفاعلية واسعة النطاق باستخدام طريقة المجال المتوسط". المؤتمر الدولي الخامس للتقييم الكمي للأنظمة ، 2008. ص 215. doi : 10.1109/QEST.2008.47 . ISBN  978-0-7695-3360-5. S2CID 2714909 . 
  40. ↑ تشين، هـ.؛ ويت، و. (1993). "تقريبات الانتشار لشبكات الانتظار المفتوحة مع انقطاعات الخدمة". أنظمة الانتظار . 13 (4): 335. doi : 10.1007/BF01149260 . S2CID 1180930 . 
  41. ↑ يامادا، ك. (1995). "تقريب الانتشار لشبكات الانتظار المفتوحة المعتمدة على الحالة في حالة الازدحام الشديد" . حوليات الاحتمالات التطبيقية . 5 (4): 958-982 . doi : 10.1214/aoap/1177004602 . JSTOR 2245101 . 
  42. ↑ برامسون، م. (1999). "شبكة انتظار مستقرة مع نموذج سائل غير مستقر" . حوليات الاحتمالات التطبيقية . 9 (3): 818-853 . doi : 10.1214/aoap/1029962815 . JSTOR 2667284 . 
  43. ↑ غروس، د.، وهاريس، سي إم (1998). أساسيات نظرية الطوابير . جون وايلي وأولاده.
  44. ↑ كلاينروك، ل. (1976). أنظمة الانتظار: المجلد الأول - النظرية . وايلي.
  45. ↑ كوبر، بي إف، وميتراني، آي. (1985). شبكات الانتظار: منهج أساسي . جون وايلي وأولاده.

للمزيد من القراءة