תור 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 \le k \le c \\
  c\mu, & \mbox{if } c \le k 
\end{cases}

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

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

:: \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}

כאשר \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 \ge c] = \pi_{c+} = \sum^\infty_{k=c} \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  ו-  0 . להוכחה זו השפעות מרחיקות לכת מבחינת היכולת להגיע לאופטימיזציה מתמטית של הפונקציה, בעיקר בשל היכולת להשתמש באופטימיזציה קמורה. שאר המדדים, דהיינו \overline L, \overline L_Q, \overline W, \overline W_Q, נגזרים מנוסחה זו וכל אחד ניתן לייצוג כמכפלה של שתי פונקציות עולות ממש וקמורות (שאחת מהן היא \pi_{c+}) או סכום של פונקציות קמורות. לכן גם הן קמורות.

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

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