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

 
 

קל לראות שרק עבור   המערכת תתכנס בטווח הרחוק ותהיה יציבה, שכן אחרת התור יילך ויגדל לאינסוף.

תוצאות שיווי המשקלעריכה

נהוג להגדיר את היחס בין הקצבים כפרמטר של המערכת:  , וכאמור, המערכת תגיע לשיווי משקל רק עבור  . פתרון תהליך הלידה והמוות מניב את ההסתברות שהמערכת תהיה במצב k, כלומר שבמערכת כולה יהיו k לקוחות, והיא:

 

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

 

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

 

נוסחה זו להסתברות מכונה "נוסחת ההשהיה של ארלנג" (The Erlang delay formula) או "נוסחת ארלנג C" והיא מתארת את ההסתברות שלקוח טלפוניה יצטרך להמתין לקבלת קו טלפון לצורך שיחה בהינתן 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