תור 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}.\,$

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

• תוחלת ושונות מספר הלקוחות במערכת, שנהוג לסמן כ-L:

${\overline {L}}={\frac {\rho }{1-\rho }}$

$\sigma _{L}^{2}={\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 }}$

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

22368478תור M/M/1