תור M/M/1

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
תרשים תור M/M/1

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

  • תהליך מופע הלקוחות הוא תהליך פואסון (ועל כן משך הזמן שבין הופעה להופעה הוא בעל התפלגות מעריכית)
  • זמני השירות בעלי התפלגות מעריכית גם הם
  • קיים שרת יחיד במערכת
  • קיבולת התור שבו הלקוחות ממתינים הוא אינסופי
  • הלקוחות נגזרים מאוכלוסייה אינסופית של מבקשי שירות פוטנציאליים
  • שיטת השירות היא FCFS, כלומר מגיע ראשון מקבל שירות ראשון. מאחר שמדובר בשרת יחיד הדבר שקול לנכנס ראשון יוצא ראשון.

ההכללה של תור M/M/1 למערכת בעלת מספר כלשהו של שרתים מכונה תור M/M/c.

תור M/M/1 כתהליך לידה ומוות[עריכת קוד מקור | עריכה]

אם נגדיר את מספר הלקוחות במערכת, k, כמשתנה המצב, תור M/M/1 הוא תהליך לידה ומוות (Birth-death process) מהפשוטים ביותר, שבו קצב הלידה (הגעת לקוח חדש לתור) וקצב המוות (סיום שירות ויציאה מהמערכת) קבועים עבור כל המצבים למעט מצב הקצה שבו אין לקוחות במערכת (במצב הקצה קצב המוות הוא אפס). יהי λ קצב מופע הלקוחות ו-μ קצב השירות, שניהם קבועים כאמור עבור כל המצבים למעט מצב האפס.

מכאן אפשר לנסח את משוואות המצב הדיפרנציאליות המתארות את הסתברות המערכת להיות במצב k בזמן t:

p_0^\prime(t)=\mu_1 p_1(t)-\lambda_0 p_0(t)
p_k^\prime(t)=\lambda_{k-1} p_{k-1}(t)+\mu_{k+1} p_{k+1}(t)-(\lambda_k +\mu_k) p_k(t)

במצב שיווי המשקל הנגזרות מתאפסות ועל כן קצב הכניסה למצב מסוים שווה לקצב היציאה ממנו, כך שמתקבלות המשוואות הבאות:

\lambda_0 p_0(t)=\mu_1 p_1(t)
(\lambda_k +\mu_k) p_k(t)=\lambda_{k-1} p_{k-1}(t)+\mu_{k+1} p_{k+1}(t)

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

\sum_{k=0}^\infty p_k = 1

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

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

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

\mbox{Prob}(q=k)=\pi_k=(1-\rho)\rho^k.\,

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

\overline L=\frac{\rho}{1-\rho}
\sigma^2_L = \frac{\rho}{(1 - \rho)^2}.
  • תוחלת מספר הלקוחות הממתינים בתור (כלומר לקוחות שממתינים ואינם מקבלים שירות):
\overline L_Q = \frac{\rho^2}{1 - \rho}
  • תוחלת מספר הלקוחות המקבלים שירות בכל רגע (במקרה של שרת יחיד גם שקול לניצולת השרת, כלומר ממוצע החלק היחסי מהזמן שהוא משרת לקוחות):
\overline L_S = \lambda \overline x = \rho
  • תוחלת משך השהייה במערכת (המתנה בתור וקבלת שירות יחד) ניתנת לחישוב באופן מיידי באמצעות חוק ליטל:
W= \frac{\overline L}{\lambda} =\frac{1}{\mu-\lambda}
  • תוחלת משך ההמתנה בתור (לא כולל זמן קבלת השירות) ניתנת גם היא לחישוב באמצעות חוק ליטל:
W_Q = \frac{\overline L_Q}{\lambda} = W - \overline x = W - \frac{1}{\mu} = \frac{\rho}{\mu - \lambda}