תור M/M/c
בתורת התורים, תור M/M/c (גם M/M/k, M/M/m, M/M/s) הוא מודל תורים מתמטי וסטוכסטי למערכת בעלת תור אחד ללא מגבלה ו-c שרתים הזהים בפעולתם ובקצב עבודתם, כאשר c הוא מספר טבעי השונה מאפס. המודל מהווה הכללה לתור M/M/1 שמשמש כמודל למערכת בעלת תור אחד ללא מגבלה ושרת יחיד. הסימון M/M/c מייצג על פי סימון קנדל מערכת כלהלן:
- תהליך ההגעה של הלקוחות הוא תהליך פואסון (ועל כן משך הזמן שבין הגעה להגעה הוא בעל התפלגות מעריכית)
- זמני השירות בכל שרת הם בעלי התפלגות מעריכית גם הם, ותוחלת זמן השירות בכל השרתים זהה.
- קיימים c שרתים זהים במערכת
- קיבולת התור שבו הלקוחות ממתינים הוא אינסופי
- הלקוחות נגזרים מאוכלוסייה אינסופית של מבקשי שירות פוטנציאליים
- שיטת השירות היא FCFS, כלומר מגיע ראשון מקבל שירות ראשון. מאחר שמדובר בשרתים רבים אין הדבר גורר בהכרח נכנס ראשון יוצא ראשון.
תור M/M/c כתהליך לידה ומוות
אם נגדיר את מספר הלקוחות במערכת k כמשתנה המצב, תור M/M/c ניתן לייצוג כתהליך לידה ומוות (Birth-death process) שבו קצב הלידה (הגעת לקוח חדש לתור) קבוע עבור כל המצבים, אך קצב המוות (סיום שירות ויציאה מהמערכת) משתנה בהתאם למספר השרתים הפעילים. יהי λ קצב הגעת הלקוחות ו-μ קצב השירות של שרת יחיד אזי קצב השירות וקצב המוות בכל מצב k של המערכת ניתנים באמצעות:
- $ \lambda _{k}=\lambda ,\ \forall k $
- $ \mu _{k}={\begin{cases}k\mu ,&{\mbox{if }}0\leq k\leq c\\c\mu ,&{\mbox{if }}c\leq k\end{cases}} $
קל לראות שרק עבור $ \rho ={\frac {\lambda }{c\mu }}<1 $ המערכת תתכנס בטווח הרחוק ותהיה יציבה, שכן אחרת התור יילך ויגדל לאינסוף.
תוצאות שיווי המשקל
נהוג להגדיר את היחס בין הקצבים כפרמטר של המערכת: $ \scriptstyle \rho \,=\,{\tfrac {\lambda }{c\mu }}. $, וכאמור, המערכת תגיע לשיווי משקל רק עבור $ \rho <1 $. פתרון תהליך הלידה והמוות מניב את ההסתברות שהמערכת תהיה במצב k, כלומר שבמערכת כולה יהיו k לקוחות, והיא:
- $ \pi _{k}={\begin{cases}\pi _{0}{\dfrac {(c\rho )^{k}}{k!}},&{\mbox{if }}0\leq k\leq c\\[10pt]\pi _{0}{\dfrac {\rho ^{k}c^{c}}{c!}},&{\mbox{if }}c\leq k\end{cases}} $
כאשר $ \pi _{0} $ היא ההסתברות שבמערכת יהיו אפס לקוחות, והיא נתונה על ידי:
- $ \pi _{0}=\left[\sum _{k=0}^{c-1}{\frac {(c\rho )^{k}}{k!}}+{\frac {(c\rho )^{c}}{c!}}{\frac {1}{1-\rho }}\right]^{-1} $
ההסתברות שלקוח חדש ייאלץ להמתין בתור למשך זמן כלשהו, כלומר שברגע הגעתו לא יהיה אף שרת פנוי היא:
- $ P[K\geq c]=\pi _{c+}=\sum _{k=c}^{\infty }\pi _{k}={\frac {(c\rho )^{c}}{c!(1-\rho )}}\pi _{0} $
נוסחה זו להסתברות מכונה "נוסחת ההשהיה של ארלנג" (The Erlang delay formula) או "נוסחת ארלנג C" והיא מתארת את ההסתברות שלקוח טלפוניה יצטרך להמתין לקבלת קו טלפון לצורך שיחה בהינתן c שרתים.
מספר הלקוחות הממוצע במערכת בשיווי משקל נתון על ידי:
- $ {\overline {L}}=c\rho +{\frac {\rho }{1-\rho }}\pi _{c+} $
ומספר הלקוחות הממוצע הממתינים בתור נתון על ידי:
- $ {\overline {L}}_{Q}={\frac {\rho }{1-\rho }}\pi _{c+} $
באמצעות חוק ליטל ניתן לחשב מכאן את משך הזמן הממוצע שלקוח יבלה במערכת:
- $ {\overline {W}}={\frac {\overline {L}}{\lambda }}={\frac {1}{\mu }}+{\frac {\rho }{\lambda (1-\rho )}}\pi _{c+} $
ואת משך הזמן הממוצע שלקוח ימתין בתור:
- $ {\overline {W}}_{Q}={\frac {{\overline {L}}_{Q}}{\lambda }}={\frac {\rho }{\lambda (1-\rho )}}\pi _{c+} $
קמירות
במאמר מאת האו ליונג לי ומוריס כהן הוכיחו השניים כי נוסחת ההשהיה של ארלנג היא פונקציה קמורה ומונוטונית עולה ממש ב-$ \rho $ כאשר $ \rho <1 $ ו- $ 0<\rho $. להוכחה זו השפעות מרחיקות לכת מבחינת היכולת להגיע לאופטימיזציה מתמטית של הפונקציה, בעיקר בשל היכולת להשתמש באופטימיזציה קמורה. שאר המדדים, דהיינו $ {\overline {L}},{\overline {L}}_{Q},{\overline {W}},{\overline {W}}_{Q} $, נגזרים מנוסחה זו וכל אחד ניתן לייצוג כמכפלה של שתי פונקציות עולות ממש וקמורות (שאחת מהן היא $ \pi _{c+} $) או סכום של פונקציות קמורות. לכן גם הן קמורות. [1]
הערות שוליים
- ↑ A Note on the Convexity of Performance Measures of M/M/c Queueing Systems, Hau Leung Lee and Morris A. Cohen, Journal of Applied Probability, Vol. 20, No. 4 (Dec., 1983), pp. 920-923, Published by: Applied Probability Trust, Stable Link
שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] תור M/M/c19286925