הצגת המקור של הדף "תור M/M/c"

ב[[תורת התורים]], '''תור M/M/c''' (גם '''M/M/k''', '''M/M/m''', '''M/M/s''') הוא [[מודל תורים]] [[מודל מתמטי|מתמטי]] ו[[תהליך סטוכסטי|סטוכסטי]] למערכת בעלת תור אחד ללא מגבלה ו-''c'' שרתים הזהים בפעולתם ובקצב עבודתם, כאשר ''c'' הוא [[מספר טבעי]] השונה מ[[0 (מספר)|אפס]]. המודל מהווה הכללה ל[[תור 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>) או סכום של פונקציות קמורות. לכן גם הן קמורות.
{{הערה|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, [http://www.jstor.org/stable/3213606 Stable Link]}}

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

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