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

הערות שוליים[עריכת קוד מקור | עריכה]

  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