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

:: <math>\lambda_k = \lambda,\ \forall k</math>

:: <math>\mu_k = \begin{cases} 
 k\mu, & \mbox{if }0 \le k \le c \\
 c\mu, & \mbox{if } c \le k 
\end{cases}</math>

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

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

:: <math>\pi_k = \begin{cases} 
 \pi_0\dfrac{(c\rho)^k}{k!}, & \mbox{if }0 \le k \le c \\[10pt]
 \pi_0\dfrac{\rho^k c^c}{c!}, & \mbox{if } c \le k 
\end{cases}</math>

כאשר <math>\pi_0</math> היא ההסתברות שבמערכת יהיו אפס לקוחות, והיא נתונה על ידי:

: <math>\pi_0 = \left[\sum_{k=0}^{c-1}\frac{(c\rho)^k}{k!} + \frac{(c\rho)^c}{c!}\frac{1}{1-\rho}\right]^{-1}</math>

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

:: <math>P[K \ge c] = \pi_{c+} = \sum^\infty_{k=c} \pi_{k} = \frac{(c\rho)^c}{c!(1-\rho)}\pi_0</math>

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

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

:: <math>\overline L = c\rho + \frac{\rho}{1-\rho}\pi_{c+}</math>

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

:: <math>\overline L_Q = \frac{\rho}{1 - \rho}\pi_{c+}</math>

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

:: <math>\overline W = \frac{\overline L}{\lambda} = \frac{1}{\mu} + \frac{\rho}{\lambda(1 - \rho)}\pi_{c+}</math>

ואת משך הזמן הממוצע שלקוח ימתין בתור:
:: <math>\overline W_Q = \frac{\overline L_Q}{\lambda} = \frac{\rho}{\lambda(1 - \rho)}\pi_{c+}</math>

==קמירות==
במאמר מאת האו ליונג לי ומוריס כהן הוכיחו השניים כי נוסחת ההשהיה של ארלנג היא פונקציה קמורה ומונוטונית עולה ממש ב-<math>\rho</math> כאשר <math> \rho < 1 </math> ו- <math> 0 < \rho </math>. להוכחה זו השפעות מרחיקות לכת מבחינת היכולת להגיע לאופטימיזציה מתמטית של הפונקציה, בעיקר בשל היכולת להשתמש באופטימיזציה קמורה. שאר המדדים, דהיינו <math>\overline L, \overline L_Q, \overline W, \overline W_Q</math>, נגזרים מנוסחה זו וכל אחד ניתן לייצוג כמכפלה של שתי פונקציות עולות ממש וקמורות (שאחת מהן היא <math>\pi_{c+}</math>) או סכום של פונקציות קמורות. לכן גם הן קמורות.

==הערות שוליים==

קטגוריה:תהליכים סטוכסטיים
קטגוריה:תורת התורים