מודל תורים

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

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

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

סימון

הסימון המתמטי הנפוץ ביותר למודל תורים נקרא סימון קנדל (Kendall) הקרוי על שם ממציאו הבריטי ובנוי לכל היותר משישה סימונים עוקבים המציינים את תכונות התור במודל:

A/B/S/K/N/Disc

כאשר:

• A - התפלגות משך הזמן שבין ההגעה של שני לקוחות עוקבים
• B - התפלגות משך השירות שניתן ללקוח על ידי השרת
• S - מספר השרתים נותני השירות בתור (הומוגניים, כלומר בעלי אותה התפלגות משך השירות)
• K - קיבולת המערכת (סכום מספר המקומות בתור ומספר מקבלי השירות)
• N - גודל אוכלוסיית מבקשי השירות
• Disc - שיטת השירות (FCFS עבור First Come First Served, כלומר מגיע ראשון-מקבל שירות ראשון וכדומה)

על פי רוב משמיטים את שלושת הסימונים האחרונים בהנחה ש-K ו-N הם אינסוף, ו-Disc הוא FCFS (מגיע ראשון מקבל שירות ראשון). ההתפלגויות הנפוצות ביותר עבור A ו-B הן התפלגות מעריכית (M), התפלגות ארלנג עם k כפרמטר (Ek), התפלגות מנוונת כלומר דטרמיניסטית (D) והתפלגות כללית כלשהי (G).

שיטות שירות

קיימות מספר שיטות שירות עיקריות הממומשות במודל תורים:

• מגיע ראשון מקבל שירות ראשון, מסומן FCFS (מאנגלית: First Come First Served). זוהי השיטה הנפוצה ביותר וגם הדומה ביותר לזו שנהוגה בדרך כלל בתורים: הראשון בתור יקבל שירות ראשון ברגע שיתפנה שרת. יש לדייק ולומר FCFS ולא נכנס ראשון יוצא ראשון על אף הדמיון שבין השניים, שכן בתור רב שרתים המממש FCFS ייתכן שלקוח נכנס לקבלת שירות לפני לקוח אחר אך סיים אחריו בשל אקראיות זמן השירות.
• מגיע אחרון מקבל שירות ראשון, מסומן LCFS (מאנגלית: Last Come First Served). השיטה המקבילה לנכנס אחרון יוצא ראשון, ברגע שהשרת מתפנה האחרון שהצטרף לתור מקבל שירות. שיטה זו נהוגה בעיקר כאשר מדובר במבני תור מסוג מחסנית, שבו הפריטים הממתינים לשירות נערמים זה על גבי זה.
• שירות אקראי, מסומן SIRO (מאנגלית: Service in Random Order), מקבל השירות הבא נבחר אקראית מבין אלו הממתינים.
• תור עדיפויות, מסומן PNPN (מאנגלית: Priority service), תור שבו מקבלי השירות מסודרים לפי עדיפויות. תחת הגדרה זו קיימים שני סוגי שירות שונים:
  • עדיפות עם הפקעה (preemptive priorities), כך שברגע שמגיע לקוח עם עדיפות גבוהה מזו של מקבל השירות הנוכחי - השרת מפסיק את השירות ועובר לשרת את הלקוח עם העדיפות הגבוהה ביותר.
  • עדיפות ללא הפקעה (non-preemptive priorities), כך ששרת מקבל בכל פעם את הלקוח בעל העדיפות הגבוהה ביותר אך לא מפסיק את השירות אם הצטרף לתור לקוח בעל עדיפות גבוהה יותר.
• שיתוף שרת, מסומן PS (מאנגלית: Processor Sharing), שיטה בה כל הלקוחות הממתינים מחלקים ביניהם את השרת.

הגדרה וניתוח

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

לאחר זיהוי המצבים נהוג לשרטט דיאגרמת שינויים שמייצגת את המעברים האפשריים בין המצבים השונים של המערכת. אם ההתפלגויות A ו-B הן מעריכיות, אזי מתקבלת שרשרת מרקוב למצב שיווי המשקל. את התפלגות ההסתברות לכל אחד ממצבי המערכת ניתן לחשב באמצעות פתרון שרשרת מרקוב שנבנתה קודם לכן, באמצעות משוואות שיווי משקל בין הקצב הנכנס לקצב היוצא ומשוואת נורמליזציה לסכום כל ההסתברויות.

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

מודלים נפוצים

ערכים מורחבים – תור M/M/1, תור M/M/c

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.

רשת תורים

רשת תורים היא מערכת המכילה מספר סופי של תורים כאשר בתום קבלת שירות משרת אחד לקוח עובר לתור אחר. רשת תורים פתוחה היא רשת בה לקוחות חדשים מצטרפים למערכת וגם רשאים לעזוב אותה ורשת תורים סגורה היא רשת שלקוחות לעולם לא עוזבים וממשיכים לעבור משרת לשרת כך שמספר הלקוחות נותר קבוע. רשתות מורכבות יותר אף מאפשרות מחלקות שונות של לקוחות המצריכות טיפול שונה בכל אחד מהשרתים. מצבה של רשת בעלת m תורים מתואר על פי רוב באמצעות וקטור $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$, כאשר k_i מציין את מספר הלקוחות הממתינים בתור ה-i. לדוגמה, ניתן לחשוב על פארק שעשועים כעל רשת תורים סגורה, שבה הלקוחות הם המבקרים והשרתים הם המתקנים השונים. המבקרים עוברים מתור לתור ומקבלים שירות בכל אחד מהמתקנים, אך בזמן השיא של הפרק תנועת המבקרים החדשים והעוזבים היא דלילה ביותר ועל כן זניחה. התוצאה המשמעותית הראשונה שהתקבלה בתחום רשתות התורים מכונה משפט ג'קסון שחל על רשתות המכונות רשתות ג'קסון, עבורן ניתן לחשב בקלות יחסית את התפלגות המצבים של הרשת ומשם את שאר המדדים הנפוצים לאפיון מודל תורים.

הערות שוליים

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

21681844מודל תורים