תורת התורים: היסטוריה, מודל, לשם מה היא ודוגמאות - מתמטיקה - 2025

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

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

גופן Pexels

ערכיה משמשים לפרמטריזציה של תהליכים לפני יישומם, ומשמשים כאלמנט ארגוני מרכזי לניהול התכנון הנכון.

הִיסטוֹרִיָה

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

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

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

דגם ואלמנטים

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

-אלמנטים

מקור הכניסה או האוכלוסייה הפוטנציאלית

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

הזנב

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

מערכת הזנב

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

- מנגנון שירות

זהו התהליך שבאמצעותו ניתן השירות לכל משתמש.

-לָקוּחַ

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

קיבולת תור

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

משמעת התור

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

- FIFO: מה ראשי תיבות באנגלית First in first out, המכונה גם FCFS כל הקודם זוכה. שפירושו, בהתאמה, ראשונה ראשונה והחוצה ראשונה שתוגש. בשתי הטפסים מציינים כי הלקוח הראשון שיגיע יהיה הראשון שיוגש.

- LIFO: אחרון ראשון בחוץ, המכונה גם ערימה או LCFS אחרונה. במקום בו מוגש הלקוח שהגיע אחרון.

- RSS: בחירה אקראית של שירות הנקראת גם שירות SIRO בסדר אקראי, שם הלקוחות נבחרים על פי קריטריונים אקראיים או אקראיים.

דגמים

ישנם 3 היבטים השולטים בחשבון את מודל התורים שיש לקחת בחשבון. אלה הם הדברים הבאים:

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

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

שני היבטים אלה יכולים לקחת את הערכים הבאים:

M: חלוקה אקספוננציאלית מעריכית (מרקוביאנה).

D: התפלגות מנוונת (זמנים קבועים).

E _k : חלוקת Erlang עם פרמטר צורה k.

G: חלוקה כללית (כל חלוקה).

- מספר שרתים: שערי שירות פתוחים וזמינים ללקוחות מעבדים. הם חיוניים בהגדרה המבנית של כל מודל תור.

באופן זה מוגדרים דגמי התורים, ראשית לוקחים את ראשי התיבות באותיות גדולות של חלוקת זמן ההגעה וחלוקת זמן השירות. לבסוף, נבדק מספר השרתים.

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

סוגים אחרים של דגמי תורים הם MMs, MG 1, ME 1, DM 1, בין היתר.

סוגי מערכות תורים

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

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

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

- תורים מרובים ושרתים מרובים. ניתן לחלק את המבנה לתהליכים שונים או לשמש ערוץ רחב לכיסוי ביקוש גבוה לשירות משותף.

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

המינוח

- λ: סמל זה (למבדה) מייצג בתורת התורים את הערך הצפוי של התשומות למרווח זמן.

- 1 / λ: מתאים לערך הצפוי בין זמני ההגעה של כל משתמש שנכנס למערכת.

- μ: הסמל Mu מתאים למספר הלקוחות הצפוי שמשלים את השירות ליחידת זמן. זה חל על כל שרת.

- 1 / μ: זמן השירות הצפוי על ידי המערכת.

- ρ: הסמל Rho מציין את גורם השימוש בשרת. הוא משמש למדידת כמה זמן השרת יהיה עסוק בעיבוד משתמשים.

ρ = λ / sμ

אם p> 1, המערכת תהיה חולפת, היא נוטה לצמוח מכיוון שקצב השירות של השרת נמצא מתחת למספר המשתמשים שנכנסים למערכת.

אם p <1 המערכת תישאר יציבה.

לשם מה התיאוריה

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

גופן Pexels

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

אלמנטים קיימים בנוסחאות

- Pn: ערך המתייחס להסתברות שיחידות "n" נמצאות במערכת.

- Lq: אורך התור או הערך הממוצע של המשתמשים בו.

- Ls: ממוצע היחידות במערכת.

- Wq: שיעור המתנה ממוצע בתור.

- Ws: קצב ההמתנה הממוצע במערכת.

- _λ: המספר הממוצע של הלקוחות שנכנסים לשירות.

- Ws (t): ערך המתייחס להסתברות שלקוח נשאר יותר מיחידות "t" במערכת.

- Wq (t): ערך המתייחס להסתברות שלקוח נשאר יותר מיחידות "t" בתור.

דוגמאות

ברישום יש שרת יחיד לעיבוד הדרכונים של המשתמשים המגיעים. בממוצע 35 משתמשים לשעה מגיעים לרישום. לשרת היכולת לשרת 45 משתמשים בשעה. ידוע בעבר שמשתמשים מבלים בממוצע 5 דקות בתור.

אתה רוצה לדעת:

1. זמן ממוצע שכל משתמש מבלה במערכת
2. המספר הממוצע של הלקוחות בתור

יש לנו λ = 35/45 לקוחות / דקות

μ = 45/60 לקוחות / דקות

Wq = 5 דקות

חלק א

ניתן לחשב את הזמן הממוצע במערכת באמצעות Ws

Ws = Wq + 1 / μ = 5 דקות + 1.33 = 6.33 דקות

בדרך זו מוגדרת הזמן הכולל שהמשתמש יהיה במערכת, כאשר 5 דקות יהיו בתור ו- 1.33 דקות עם השרת.

חלק ב

Lq = λ x Wq

Lq = (0.78 דקות דקות) x (5 דקות) = 3.89 לקוחות

יכולים להיות יותר משלושה לקוחות בתור בו זמנית.

הפניות

1. ניהול תפעול. מערכת Vértice, 16 באפריל. 2007
2. תיאוריה של תורים או קו המתנה. ז'רמן אלברטו קורדובה ברהונה. פונטיפיאה אוניברסידד ג'בריאנה, 2002
3. תורת המערכות פתרה בעיות. רוברטו סנצ'יס לופיס. פרסומי אוניברסיטת ג'ומא הראשון, 2002
4. שיטות כמותיות של ארגון תעשייתי II. ג'ואן בפטיסטה פונולוסה גרדיאט, חוסה מריה סאלאן חוקים, אלברט סוני טורנטים. אוניברסיטת פוליטק. מקטלוניה, 2009
5. תורת המלאי ויישומה. עריכה פאקס-מקסיקו, 1967