תור 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 של המערכת ניתנים באמצעות:

$$\begin{gathered} {\lambda }_k=\lambda , \\ \mathrm{\forall }k \end{gathered}$$

${\mu }_k=\{\begin{array}{ll}k\mu ,& \text{if }0\le k\le c\\ c\mu ,& \text{if }c\le k\end{array}$

קל לראות שרק עבור $\rho =\frac{\lambda }{c\mu }<1$ המערכת תתכנס בטווח הרחוק ותהיה יציבה, שכן אחרת התור ילך ויגדל לאינסוף.

תוצאות שיווי המשקל

נהוג להגדיר את היחס בין הקצבים כפרמטר של המערכת: $\rho =\frac{\lambda }{c\mu }.$, וכאמור, המערכת תגיע לשיווי משקל רק עבור $\rho <1$. פתרון תהליך הלידה והמוות מניב את ההסתברות שהמערכת תהיה במצב k, כלומר שבמערכת כולה יהיו k לקוחות, והיא:

${\pi }_k=\{\begin{array}{ll}{\pi }_0\frac{(c\rho {)}^k}{k!},& \text{if }0\le k\le c\\ {\pi }_0\frac{{\rho }^k{c}^c}{c!},& \text{if }c\le k\end{array}$

כאשר ${\pi }_0$ היא ההסתברות שבמערכת יהיו אפס לקוחות, והיא נתונה על ידי:

${\pi }_0={[\sum _{k=0}^{c-1}\frac{(c\rho {)}^k}{k!}+\frac{(c\rho {)}^c}{c!}\frac{1}{1-\rho }]}^{-1}$

ההסתברות שלקוח חדש ייאלץ להמתין בתור למשך זמן כלשהו, כלומר שברגע הגעתו לא יהיה אף שרת פנוי היא:

$P[K\ge c]={\pi }_{c+}=\sum _{k=c}^{\mathrm{\infty }}{\pi }_k=\frac{(c\rho {)}^c}{c!(1-\rho )}{\pi }_0$

נוסחה זו להסתברות מכונה "נוסחת ההשהיה של ארלנג" (The Erlang delay formula) או "נוסחת ארלנג C" והיא מתארת את ההסתברות שלקוח טלפוניה יצטרך להמתין לקבלת קו טלפון לצורך שיחה בהינתן c שרתים.

מספר הלקוחות הממוצע במערכת בשיווי משקל נתון על ידי:

$\bar{L}=c\rho +\frac{\rho }{1-\rho }{\pi }_{c+}$

ומספר הלקוחות הממוצע הממתינים בתור נתון על ידי:

${\bar{L}}_Q=\frac{\rho }{1-\rho }{\pi }_{c+}$

באמצעות חוק ליטל ניתן לחשב מכאן את משך הזמן הממוצע שלקוח יבלה במערכת:

$\bar{W}=\frac{\bar{L}}{\lambda }=\frac{1}{\mu }+\frac{\rho }{\lambda (1-\rho )}{\pi }_{c+}$

ואת משך הזמן הממוצע שלקוח ימתין בתור:

${\bar{W}}_Q=\frac{{\bar{L}}_Q}{\lambda }=\frac{\rho }{\lambda (1-\rho )}{\pi }_{c+}$

קמירות

במאמר מאת האו ליונג לי ומוריס כהן הוכיחו השניים כי נוסחת ההשהיה של ארלנג היא פונקציה קמורה ומונוטונית עולה ממש ב-$\rho$ כאשר $\rho <1$ ו- $0<\rho$. להוכחה זו השפעות מרחיקות לכת מבחינת היכולת להגיע לאופטימיזציה מתמטית של הפונקציה, בעיקר בשל היכולת להשתמש באופטימיזציה קמורה. שאר המדדים, דהיינו $\bar{L},{\bar{L}}_Q,\bar{W},{\bar{W}}_Q$, נגזרים מנוסחה זו וכל אחד ניתן לייצוג כמכפלה של שתי פונקציות עולות ממש וקמורות (שאחת מהן היא ${\pi }_{c+}$) או סכום של פונקציות קמורות. לכן גם הן קמורות.