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

משימה 1.קונסולת השיגור מקבלת זרימת בקשות, שהיא זרימת Erlang מסדר שני. עוצמת זרימת האפליקציות היא 6 אפליקציות בשעה. אם השולח עוזב את הקונסולה ברגע אקראי, אז בבקשה הראשונה הבאה עליו לחזור לקונסולה. מצא את צפיפות ההתפלגות של זמן ההמתנה לבקשה הבאה ושרטט את הגרף שלה. חשב את ההסתברות שהשולח יכול להיעדר בין 10 ל-20 דקות. פִּתָרוֹן. מכיוון שזרימת Erlang מהסדר השני היא זרימה נייחת עם אפקט לוואי מוגבל, אז הנוסחה של Palm תקפה עבורה

איפה f1(θ)- צפיפות התפלגות ההסתברות לזמן ההמתנה של האירוע הקרוב הראשון;
λ - עוצמת זרימה;
- סדר זרימה;
(θ) היא פונקציית התפלגות ההסתברות עבור הזמן בין שני אירועים סמוכים של זרימת הסדר של ארלנג (E).
ידוע שלפונקציית ההתפלגות עבור הזרימה E יש את הצורה

. (2)

לפי תנאי הבעיה, זרימת האפליקציות היא Erlang בסדר גודל =2. ואז מ-(1) ו-(2) נקבל
.
מהיחס האחרון עבור λ=6 יהיה לנו

f1(θ)=3е-6θ(1+6θ), θ≥0. (3)

בואו נשרטט את הפונקציה f1(θ) . בְּ θ <0 יש לנו f1(θ) =0 . בְּ θ =0 , f1(0)=3. קחו בחשבון את הגבול

בעת חישוב הגבול לחשיפת אי בהירות סוג, נעשה שימוש בכלל L'Hopital. על סמך תוצאות המחקר, אנו בונים גרף של הפונקציה f1(θ) (איור 1).

נשים לב לממדי הזמן בטקסט המשימה: לעוצמה, מדובר באפליקציות לשעה, לזמן, לדקות. נעבור ליחידת זמן אחת: 10 דקות = 1/6 שעה, 20 דקות = 1/3 שעה. עבור ערכים אלה, אפשר לחשב f1(θ) ולחדד את אופי העקומה

אורדינאטות אלו מסומנות בגרף מעל נקודות העקומה המתאימות.
ממהלך תורת ההסתברות ידוע כי ההסתברות לפגיעה במשתנה מקרי איקסלתוך המקטע [α, β] שווה מספרית לשטח מתחת לעקומת צפיפות ההסתברות f(x). אזור זה מתבטא באמצעות אינטגרל מובהק

לכן, ההסתברות הרצויה שווה ל

ניתן לחשב את האינטגרל הזה בקלות לפי חלקים אם נשים
U=1+6θו dV=e-6θdθ. לאחר מכן dU=6dθו V= .
שימוש בנוסחה אנחנו מקבלים

תשובה: ההסתברות שהשולח יכול להיעדר בין 10 ל-20 דקות היא 0.28.

משימה 2.בחדר התצוגה 5 תצוגות. זרימת המשתמשים היא הפשוטה ביותר. מספר המשתמשים הממוצע המבקרים בחדר התצוגה ביום הוא 140. זמן עיבוד המידע על ידי משתמש אחד בתצוגה אחת מופץ על פי חוק אקספוננציאלי ועומד בממוצע על 40 דקות. קבע אם יש מצב פעולה נייח של האולם; ההסתברות שהמשתמש ימצא את כל התצוגות תפוסות; מספר ממוצע של משתמשים בחדר התצוגה; מספר ממוצע של משתמשים בתור; זמן תצוגה סרק ממוצע; הזמן הממוצע שהמשתמש מבלה בחדר התצוגה. פִּתָרוֹן.ה-QS שנחשב בבעיה שייך למחלקה של מערכות רב-ערוציות עם תור בלתי מוגבל. מספר ערוצים = 5. הבה נמצא את עוצמת ה-λ של זרימת הבקשות: איפה (שעות) - הזמן הממוצע בין שני יישומים עוקבים של זרימת המשתמשים הנכנסת. לאחר מכן משתמש/שעה

בואו נמצא - את עוצמת זרימת השירות: , כאשר M[T service]=40 דקות=0.67 שעות - זמן שירות ממוצע למשתמש אחד עם תצוגה אחת,

לאחר מכן משתמש/שעה

לפיכך, למסווג של מערכת זו יש את הצורה CMO (5, ∞; 5.85; 1.49).
חשב את מקדם העומס QS . זה ידוע כי עבור QS של מחלקה זו, מצב נייח קיים אם היחס בין מקדם העומס של המערכת למספר הערוצים הוא פחות מאחד. למצוא את הקשר הזה
.
לכן, המשטר הנייח קיים. התפלגות ההסתברות של המצב המגביל מחושבת על ידי הנוסחאות

מאז =5, יש לנו

בוא נחשב את P* - ההסתברות שהמשתמש ימצא את כל התצוגות תפוסות. ברור שזה שווה לסכום ההסתברויות של אירועים כאלה: כל התצוגות תפוסות, אין תור (p5); כל התצוגות תפוסות, משתמש אחד בתור (p6); כל התצוגות תפוסות, שני משתמשים נמצאים בתור (p7), וכן הלאה. מכיוון שלקבוצה שלמה של אירועים סכום ההסתברויות של אירועים אלה שווה לאחד, אזי השוויון

P * \u003d p5 + p6 + p7 + ... \u003d 1 - ro - p1 - p2 - p3 - p4.

בואו נמצא את ההסתברויות האלה: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
אם מוציאים את הגורם המשותף מהסוגריים, אנחנו מבינים
P*=1-0.0148*(1+3.93+7.72+10.12+9.94)=1-0.014*32.71=1-0.46=0.54.
משתמש בנוסחאות לחישוב מדדי ביצועים? למצוא:

• 1. מספר ממוצע של משתמשים בתור

2. מספר משתמשים ממוצע בחדר התצוגה

3. זמן המתנה ממוצע לתצוגה בחינם

4. זמן השהות הממוצע של המשתמש בחדר התצוגה

תשובה: אופן הפעולה הנייח של חדר התצוגה קיים ומאופיין במדדים הבאים R*=0.54; מִשׁתַמֵשׁ; מִשׁתַמֵשׁ; ; .

משימה 3.למערכת דו-ערוצית הִזדַנְבוּת(QS) עם כשלים, מגיעה זרימת פואסון נייחת של יישומים. הזמן בין הגעות של שתי בקשות רצופות מחולק לפי החוק האקספוננציאלי עם הפרמטר λ=5 בקשות לדקה. משך הטיפול בכל בקשה הוא 0.5 דקות. באמצעות שיטת מונטה קרלו, מצא את המספר הממוצע של בקשות מטופלות למשך זמן של 4 דקות. רמז: בצע שלוש בדיקות. פִּתָרוֹן.הבה נתאר את המודל הסטטיסטי של הפעולה של QS נתון באמצעות דיאגרמות זמן. הבה נציג את הסימון הבא עבור צירי זמן:
Vx- זרימת יישומים נכנסת, כאן ti- רגע קבלת הבקשות; טי- מרווחי זמן בין שני יישומים עוקבים. זה ברור ש ti=ti-1 +Tאני.
K1 - ערוץ השירות הראשון;
ערוץ שירות K2 שניות; כאן, הקווים העבים על ציר הזמן מייצגים מרווחי עמוס של ערוץ. אם שני הערוצים פנויים, אז הבקשה מקבלת שירות בערוץ K1, אם הוא תפוס, הבקשה מטופלת על ידי ערוץ K2.
אם שני הערוצים תפוסים, הבקשה משאירה את ה-QS ללא הגשה.
Out OB - זרימה יוצאת של בקשות מטופלות.
Out PT הוא הזרם היוצא של בקשות שאבדו עקב כשלים ב-QS (שני הערוצים תפוסים).
בדיקה סטטיסטית נמשכת לפרק זמן. ברור, כל שעות נוספות tmaxכרוך בהחזרת הבקשה לזרם היוצא Out PT. אז באיור. 3 בקשה מס' 10 שנכנסה אז למערכת t10, אין זמן להגיש עד הרגע tmax, כי t10+Tmont.>tmax. לכן, הוא אינו מתקבל על ידי הערוץ החינמי K1 לשירות והוא מאופס ל-Out PT, מקבל סירוב.

אורז. 3

מתוך דיאגרמות התזמון, ניתן לראות כי יש צורך ללמוד כיצד לדגמן מרווחים טאני. אנו מיישמים את השיטה של ​​פונקציות הפוכות. מאז המשתנה האקראי טימופץ לפי החוק האקספוננציאלי עם הפרמטר λ =5, אז לצפיפות ההתפלגות יש את הצורה ו(τ)=5е-5τ. ואז הערך F(Ti)פונקציית התפלגות ההסתברות נקבעת על ידי האינטגרל

.

ידוע שטווח התפלגות פונקציה ו(ט) יש חתך. אנו בוחרים מספר מטבלת המספרים האקראיים וקובעים טאנימשוויון , מנין . לעומת זאת, אם . לכן, אתה יכול מיד לקבל יישומים מטבלת המספרים האקראיים. כתוצאה מכך,
e-5Tאני= ri, או -5Tאני= אינרי, איפה . נוח להזין את תוצאות החישובים בטבלה.
למבחן מס' 1 נלקחו מספרים אקראיים מתוך נספח 2, החל מהמספר הראשון של השורה הראשונה. דגימה נוספת בוצעה לפי שורות. בוא נעשה עוד שני מבחנים.
שימו לב לבחירת המספרים האקראיים מהטבלה של נספח 2, אם במבחן מס' 1 המספר האקראי האחרון לבקשה מס' 16 היה 0.37 (המספר האקראי הראשון בשורה השנייה), אזי מבחן מס' 2 מתחיל ב המספר האקראי הבא 0.54. ניסיון מס' 2 מכיל את המספר האקראי האחרון 0.53 (המספר החמישי בשורה השלישית). לכן, המבחן השלישי יתחיל במספר 0.19. באופן כללי, בתוך אותה סדרת בדיקות נבחרים מספרים אקראיים מהטבלה ללא פערים והוספות בסדר מסוים, למשל בשורות.

טבלה 1. מבחן מס' 1

בקשה מס. אני	Sl. מספר ri		-ברי טי	רגע קבלת הבקשה ti=ti-1+Ti	זמן סיום השירות. ti+0.50		מונה יישומים
					K1

טבלה 2 מבחן מס' 2

בקשה מס. אני	Sl. מספר ri		-ברי טאני	רגע קבלת הבקשה ti=ti-1+Ti	זמן סיום השירות. ti+0.50		מונה יישומים

טבלה מס' 3 מבחן מס' 3

בקשה מס. אני		Sl. מספר ri		-ברי טאני	רגע קבלת הבקשה ti=ti-1+Ti	זמן סיום השירות. ti+0.50		מונה יישומים
						K1

לפיכך, על פי התוצאות של שלוש בדיקות, מספר האפליקציות שקיבלו שירות היה בהתאמה: x1=9, x2=9, x3=8. מצא את המספר הממוצע של בקשות לטיפול:

תשובה: מספר הבקשות הממוצע שהוגשו על ידי ה-QS ב-4 דקות הוא 8.6(6).

מטרות

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

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

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

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

לאחר השלמת המשימות בפרק זה, תוכל להגדיר ולהשתמש במושגים הבאים לניתוח כלכלי:

מערכת תורים;

תור;

שיעור קבלת הבקשות;

קצב השירות;

הזמן הממוצע שהאפליקציה מבלה בתור;

אורך תור ממוצע;

הזמן הממוצע שהאפליקציה מבלה במערכת השירות;

מספר לקוחות ממוצע במערכת השירות;

עלויות תפקוד מערכת השירות;

עלויות המתנה.

דגמים

תכונות סיווג של מערכות תורים.

במערכות תורים, ישנם שלושה שלבים עיקריים שכל אפליקציה עוברת:

1) הופעת אפליקציה בכניסה למערכת;

2) העברת התור;

3) תהליך השירות, שלאחריו האפליקציה עוזבת את המערכת.

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

מפרטי קלט:

1) מספר הבקשות בכניסה (גודל אוכלוסייה);

2) אופן קבלת פניות במערכת השירות;

3) התנהגות לקוחות.

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

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

אופן קבלת פניות במערכת השירות.אפליקציות יכולות להיכנס למערכת השירות לפי לוח זמנים מסוים (לדוגמה מטופל אחד לרופא השיניים כל 15 דקות, רכב אחד על פס הייצור כל 20 דקות) או באופן אקראי. ביקורי לקוחות נחשבים אַקרַאִי,אם הם בלתי תלויים זה בזה ובדיוק בלתי צפויים. לעתים קרובות בבעיות תור, ניתן להעריך את מספר ההתרחשויות ליחידת זמן באמצעות התפלגות הסתברות של Poisson. בקצב כניסה נתון (לדוגמה, שני לקוחות לשעה או ארבע משאיות לדקה) הפצה בדידה Poisson מתואר בנוסחה הבאה:

איפה P(x) -הסתברות להתקבל איקספניות ליחידת זמן;

איקס -מספר הפניות ליחידת זמן;

L הוא מספר הבקשות הממוצע ליחידת זמן (שיעור קבלת הבקשות);

ההסתברויות המתאימות P(x)קל לקבוע באמצעות טבלת התפלגות Poisson. אם, למשל, הקצב הממוצע של קבלת בקשות הוא שני לקוחות לשעה, אז ההסתברות שלא ייכנסו פניות למערכת תוך שעה היא 0.135, ההסתברות לבקשה אחת היא בערך 0.27, ושתיים הן גם בערך 0.27, שלוש טענות עשויות להופיע בהסתברות של 0.18, ארבע בהסתברות של כ-0.09 וכן הלאה.ההסתברות ש-9 תביעות או יותר ייכנסו למערכת תוך שעה קרובה לאפס.

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

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

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

מאפייני תור:

2) כלל שירות.

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

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

מאפייני תהליך השירות:

1) תצורת מערכת השירות (מספר הערוצים ומספר שלבי השירות);

2) מצב תחזוקה.

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

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

על איור. 1 מציג מערכות שירות של תצורות שונות.

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

F(ט ) = P(ט< t) =1 – e–tm, שבו R (ט< t) היא ההסתברות שהזמן בפועל טבקשת השירות לא תחרוג מהערך שצוין t;

M - מספר הבקשות הממוצע שהוגשו ליחידת זמן;

E \u003d 2.7182 - הבסיס של הלוגריתם הטבעי.

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

להלן הנפוצים ביותר מפרטים:

1) הזמן הממוצע שלקוח מבלה בתור;

2) האורך הממוצע של התור;

3) הזמן הממוצע שלקוח מבלה במערכת השירות (זמן המתנה פלוס זמן שירות);

4) מספר הלקוחות הממוצע במערך השירות;

5) ההסתברות שמערכת השירות תהיה בטלה;

6) ההסתברות למספר מסוים של לקוחות במערכת.

בין מאפיינים כלכליים המעניינים ביותר הם הבאים:

1) עלות ההמתנה בתור;

2) עלויות המתנה במערכת;

3) עלויות תחזוקה.

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

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

א) התפלגות Poisson של ההסתברות לקבלת בקשות;

ב) התנהגות סטנדרטית של לקוחות;

ב) כלל שירות FIFO(כל הקודם זוכה);

ד) השלב היחיד של השירות.

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

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

1. הגשת הבקשות מוגשת על בסיס כל הקודם זוכה (FIFO)יתרה מכך, כל לקוח ממתין לתור שלו עד הסוף, ללא קשר לאורך התור.

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

3. תהליך קבלת הבקשות מתואר על ידי הפצת Poisson, והאפליקציות מגיעות מסט בלתי מוגבל.

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

5. שיעור השירות גבוה משיעור קבלת הבקשות.

תן l להיות מספר היישומים ליחידת זמן;

M הוא מספר הלקוחות המוגשות ליחידת זמן;

פ -מספר האפליקציות במערכת.

אז מערכת התורים מתוארת על ידי המשוואות המפורטות להלן.

נוסחאות לתיאור מערכת M/M/ 1:

- מספר לקוחות ממוצע במערכת;

זמן שירות ממוצע ללקוח במערכת (זמן המתנה פלוס זמן שירות);

מספר לקוחות ממוצע בתור;

זמן המתנה ממוצע ללקוח בתור;

מאפייני עומס המערכת (שיעור הזמן שבו המערכת עסוקה בטיפול);

ההסתברות להיעדר יישומים במערכת;

ההסתברות שהמערכת מכילה יותר מ קיישומים.

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

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

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

הזמן שבו האפליקציה הייתה בתור;

זמן שהאפליקציה משקיעה במערכת.

III. דגם C- דגם עם זמן שירות קבוע M/ד/ 1.

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

נוסחאות המתארות את דגם C:

- אורך תור ממוצע;

- זמן המתנה ממוצע בתור;

מספר לקוחות ממוצע במערכת;

זמן המתנה ממוצע במערכת.

IV. דֶגֶם ד - מודל עם אוכלוסיה מוגבלת.

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

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

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

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

מאפיינים השוואתיים של מודלים שונים של מערכות תורים ניתנים בטבלה הבאה.

אובייקט מתמטי (מופשט), שמרכיביו הם (איור 2.1):

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

בַּקָשָׁה(בקשה, דרישה, שיחה, לקוח, הודעה, חבילה) - אובייקט שנכנס ל-QS ודורש שירות במכשיר. מערך האפליקציות הרצופות המופץ בצורת זמן זרימת קלט של יישומים.

אורז. 2.1.

מכשיר שירות(מכשיר, מכשיר, ערוץ, קו, כלי, רכב, נתב וכו') - אלמנט QS, שמטרתו לתת שירות לאפליקציות.

שֵׁרוּת- עיכוב של הבקשה במכשיר השירות למשך זמן מה.

משך השירות- זמן עיכוב (שירות) של האפליקציה במכשיר.

מכשיר אחסון(buffer, input buffer, output buffer) - סט מקומות להמתנה לאפליקציות מול מכשיר ההגשה. מספר מקומות המתנה - נפח אחסון.

בקשה שהתקבלה על ידי ה-CMO יכולה להיות בשתי מדינות:

• 1) שֵׁרוּת(במכשיר);
• 2) ציפיות(במצבר), אם כל המכשירים עסוקים בטיפול בבקשות אחרות.

התביעות בטופס מצבר וממתינים תוריישומים. מספר האפליקציות בשירות הממתין לצבר - אורך התור.

משמעת חציצה(משמעת בתור) - הכלל להזנת יישומים נכנסים לכונן (מאגר).

משמעת שירות- הכלל לבחירת בקשות מהתור לשירות במכשיר.

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

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

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

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

במערכות IM, בעת יישום QS, ההגבלות וההנחות הבאות מתקבלות:

• אפליקציה שהוכנסה למערכת באופן מיידינכנס לשירות אם אין בקשות בתור והמכשיר פנוי;
• במכשיר לתחזוקה בכל עת יכול להיות רק אחדבַּקָשָׁה;
• לאחר סיום השירות של כל בקשה במכשיר, הבקשה הבאה נבחרת מהתור למתן שירות מיידי, כלומר, המכשיר אינו מתבטלאם יש לפחות אפליקציה אחת בתור;
• קבלת פניות ב-QS ומשך השירות שלהן אינם תלויים במספר הבקשות שכבר נמצאות במערכת, או בכל גורם אחר;
• משך בקשות השירות אינו תלוי בעוצמת הבקשות הנכנסות למערכת.

הבה נתעכב על כמה אלמנטים של QS ביתר פירוט.

זרימת קלט (נכנסת) של יישומים. שטף האירועיםנקרא רצף של אירועים הומוגניים העוקבים בזה אחר זה ומתרחשים בחלקם, באופן כללי, אַקרַאִינקודות זמן. אם האירוע מורכב ממראית עין של טענות, יש לנו זרימת יישום.כדי לתאר את זרימת היישומים ב מקרה כללייש צורך להגדיר מרווחי זמן t = ט ק - t k-1בין רגעים סמוכים ט ק _ קו ט קקבלת בקשות עם מספרים סידוריים ל - 1 ו לבהתאמה (ל - 1, 2, ...; t 0 - 0 - רגע זמן ראשוני).

המאפיין העיקרי של זרימת האפליקציה הוא שלה X עוצמה- המספר הממוצע של יישומים המגיעים לקלט QS ליחידת זמן. ערך t = 1/Xמגדיר מרווח הזמן הממוצע בין שני פקודות עוקבות.

הזרימה נקראת דטרמיניסטיתאם מרווחי זמן לא לבין בקשות סמוכות לקבל קבוע מראש ערכים ידועים. אם המרווחים זהים (x ל= t עבור כולם k = 1, 2, ...), ואז נקרא הזרם רגיל.ל תיאור מלאעבור זרימה קבועה של יישומים, זה מספיק כדי להגדיר את עוצמת הזרימה איקסאו הערך של המרווח t = 1/X.

זרם שבו מרווחי זמן x kבין יישומים סמוכים יש משתנים אקראיים, הנקראים אַקרַאִי.לתיאור מלא של זרימה אקראית של יישומים במקרה הכללי, יש צורך להגדיר את חוקי ההפצה F fc (x fc) עבור כל אחד ממרווחי הזמן x k, k = 1,2,....

זרם אקראי שבו כל מרווחי הזמן x b x 2,... בין לקוחות עוקבים סמוכים משתנים אקראיים בלתי תלויים המתוארים על ידי פונקציות הפצה FjCij), F 2 (x 2), ... בהתאמה, נקרא זרימה עם אפקט לוואי מוגבל.

זרם אקראי נקרא חוזר ונשנה,אם כל מרווחי הזמן x ב t 2, ... מופץ בין יישומים לפי אותו חוק F(t). יש הרבה זרמים חוזרים. כל חוק הפצה מייצר זרימה חוזרת משלו. זרמים חוזרים ידועים גם כנחלי דקל.

אם העוצמה איקסוחוק ההפצה F(t) של מרווחים בין בקשות עוקבות לא משתנה עם הזמן, ואז זרימת הבקשות נקראת יַצִיבאחרת, זרימת היישום היא לא נייח.

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

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

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

מרווחי הזמן t בין בקשות בזרימה הפשוטה ביותר מתחלקים לפי אקספוננציאלי (מוֹפְתִי) חוֹק:עם פונקציית התפלגות F(t) = 1 - ה~ מ;צפיפות הפצה/(f) = חח~"ל,איפה X > 0 - פרמטר הפצה - עוצמת זרימת האפליקציות.

הזרימה הפשוטה ביותר נקראת לעתים קרובות פויסון.השם בא מהעובדה שעבור זרימה זו ההסתברות P fc (At) להתרחשות בדיוק לבקשות למרווח זמן מסוים נקבעת חוק פואסון:

יש לציין שזרימת הפואסון, שלא כמו הפשוטה ביותר, יכולה להיות:

• יַצִיב,אם עוצמה איקסאינו משתנה עם הזמן;
• לא נייח,אם קצב הזרימה תלוי בזמן: איקס= >.(t).

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

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

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

סְכוּם נזרימות רגילות נייחות עצמאיות עם עוצמות x x x 2 ,..., XNיוצר את הזרימה הפשוטה ביותר בעוצמה

X=Y,^iבתנאי שלזרימות שנוספו יש יותר או

השפעה קטנה באותה מידה על הזרימה הכוללת. בפועל, הזרימה הכוללת קרובה לפשוטה ביותר בשעה N > 5. אז כאשר מסכמים את הזרימות הפשוטות ביותר, הזרימה הכוללת תהיה הפשוטה ביותרלכל ערך שהוא נ.

• 2. הסתברות נדירה של הזרימה. הסתברותי(אבל לא דטרמיניסטי) נדירות הזרימה הפשוטה ביותריישומים, שבהם כל יישום באופן אקראי עם סבירות מסוימת ראינו נכלל מהזרימה ללא קשר לשאלה אם יישומים אחרים אינם נכללים או לא, מוביל להיווצרות הזרימה הפשוטה ביותרבעוצמה איקס* = pX,איפה איקס- עוצמת הזרימה הראשונית. זרימת יישומים שלא נכללים בעוצמה X** = (1 - p) X- גם פרוטוזואהזְרִימָה.
• 3. יעילות. אם ערוצי הגשה (מכשירים) מיועדים לזרימה הפשוטה ביותר של בקשות בעוצמה איקס,אז שירות סוגים אחרים של זרימות (באותה עוצמה) יינתן ביעילות לא פחותה.
• 4. פשטות. ההנחה של זרימת האפליקציות הפשוטה ביותר מאפשרת למודלים מתמטיים רבים להשיג בצורה מפורשת את התלות של מדדי QS בפרמטרים. המספר הגדול ביותרהתקבלו תוצאות אנליטיות עבור הזרימה הפשוטה ביותר של יישומים.

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

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

מאפיין חשוב של זרם הקלט הוא מקדם השונות

כאשר t int - ציפייה מתמטית לאורך המרווח; על אודות- ממוצע סטיית תקןאורך מרווח x int (משתנה מקרי) .

עבור הזרימה הפשוטה ביותר (a = -, m = -) יש לנו v = 1. לרוב

זרימות אמיתיות 0

ערוצי שירות (מכשירים). המאפיין העיקרי של הערוץ הוא משך השירות.

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

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

איפה ג - עוצמת השירות,כאן p = _--; t 0 bsl - מתמטיקה-

זמן המתנה טיק לשירות.

בנוסף להתפלגות האקספוננציאלית, קיימות התפלגויות Erlang /c, התפלגויות היפר-אקספוננציאליות, התפלגויות משולשות ועוד כמה. זה לא צריך לבלבל אותנו, שכן הוכח שהערך של קריטריוני היעילות של QS תלוי מעט בצורת חוק חלוקת זמן השירות.

בלימוד QS, מהות השירות, איכות השירות, יוצאת מהשיקול.

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

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

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

• חציצה;
• שֵׁרוּת.

ניתן לסווג דיסציפלינות חציצה ותחזוקה לפי הקריטריונים הבאים:

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

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

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

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

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

אורז. 2.2.

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

• עקירה מקרית;
• אי הכללת הצו האחרון, כלומר. נכנס למערכת מאוחר יותר מכולם;
• דחיקת הזמנה "ארוכה", כלומר. ממוקם בצובר זמן רב יותר מכל הבקשות שהתקבלו בעבר.

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

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

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

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

• מצב יחיד;
• מצב קבוצתי;
• מצב משולב.

אורז. 2.3.

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

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

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

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

לא בעדיפות(לאפליקציות אין הרשאות שירות מוקדם - לכידת משאבים):

• שירות כל הקודם זוכה FIFO (ראשון ב -ראשון החוצה,ראשון נכנס - ראשון יוצא)
• שירות הפוך- האפליקציה נבחרה מהתור במצב LIFO (אחרון פנימה - ראשון החוצה,נכנס אחרון, יוצא ראשון)
• שירות אקראי- האפליקציה נבחרה מהתור במצב רנד (אַקרַאִי- באופן אקראי);
• שירות מחזורי- יישומים נבחרים בתהליך של סקר מחזורי של כוננים ברצף 1, 2, חמ ח- מספר הכוננים), שלאחריו חוזר הרצף שצוין;

עדיפות(לאפליקציות יש הרשאות לשירות מוקדם - לכידת משאבים):

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

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

בקשות המתקבלות ב-CMO מחולקות לכיתות. ב-QS, שהוא תקציר מודל מתמטי, יישומים שייכים למחלקות שונותבמקרה שהם שונים במערכת האמיתית המדומה לפחות באחת מהתכונות הבאות:

• משך השירות;
• סדרי עדיפויות.

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

לתיאור מתמטי של דיסציפלינות שירות עם סדרי עדיפויות מעורבים, אנו משתמשים מטריצת עדיפות,מייצגים מטריצה ​​מרובעת Q = (ש, ;), אני, י - 1,..., I, I - מספר מחלקות האפליקציות הנכנסות למערכת.

אֵלֵמֶנט q(jמטריצה ​​קובעת את העדיפות של בקשות המחלקה אניביחס ליישומים כיתתיים; ויכול לקחת את הערכים הבאים:

• 0 - אין עדיפות;
• 1 - עדיפות יחסית;
• 2 - עדיפות מוחלטת.

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

• q n= 0, מכיוון שלא ניתן להגדיר עדיפויות בין בקשות מאותה מחלקה;
• אם q (j = 1 או 2 אז ש^ = 0, שכן אם יישומי מחלקה אניעדיפות על פני בקשות כיתתיות י,אזי האחרונים אינם יכולים לקבל עדיפות על פני תביעות ייצוגיות אני (i,j = 1, ..., I).

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

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

במערכות מחשב IM יש בהכרח אלמנט בודד (אובייקט) שדרכו ורק דרכו מוזנות בקשות למודל. כברירת מחדל, כל האפליקציות שהוזנו אינן עדיפות. אבל יש אפשרויות להקצאת עדיפויות ברצף 1, 2, ..., כולל במהלך ביצוע המודל, כלומר. בדינמיקה.

זרם יוצאהוא זרימת בקשות השירות היוצאות מה-QS. במערכות אמיתיות, יישומים עוברים מספר QS: תקשורת מעבר, צינור ייצור וכו'. במקרה זה, הזרם היוצא הוא הזרם הנכנס עבור ה-QS הבא.

הזרם הנכנס של ה-QS הראשון, לאחר שעבר דרך QSs עוקבים, מעוות, וזה מסבך את המודלים האנליטיים. עם זאת, יש לזכור זאת עם זרם הקלט הפשוט ביותר ושירות אקספוננציאלי(הָהֵן. במערכות Markov) זרם הפלט הוא גם הפשוט ביותר.אם לזמן השירות יש התפלגות לא אקספוננציאלית, אז הזרם היוצא הוא לא רק לא פשוט, אלא גם לא חוזר.

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

ב-QS, בנוסף לזרימה היוצאת של בקשות שירות, יכולות להיות זרם של בקשות שלא הוגשו.אם QS כזה מקבל זרימה חוזרת, והשירות הוא אקספוננציאלי, אז גם הזרימה של לקוחות לא מוגשת היא חוזרת.

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

כפי שציינו קודם לכן, באובייקטים אמיתיים, בקשות מטופלות ברצף במספר QSs.

קבוצה סופית של QSs מחוברים ברצף שמעבדים יישומים שמסתובבים בהם נקראת רשת בתור (סמו) (איור 2.4, א).

אורז. 2.4.

SEMO נקרא גם QS רב-פאזי.

נשקול דוגמה לבניית QEMO IM מאוחר יותר.

המרכיבים העיקריים של QS הם צמתים (U) ומקורות (מחוללים) של בקשות (G).

קשררשתות הן מערכת תורים.

מָקוֹר- מחולל יישומים הנכנסים לרשת ודורשים שלבי שירות מסוימים בצמתי הרשת.

גרף משמש לתמונה פשוטה של ​​QEMO.

הרוזן סמו- גרף מכוון (דיגרף), שקודקודיו תואמים לצמתי QEM, והקשתות מייצגות את מעברי היישומים בין הצמתים (איור 2.4, ב).

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

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

זה נדרש כדי לפתור בעיות 1-3. הנתונים הראשוניים ניתנים בטבלה. 2-4.

סימון כלשהו המשמש בתורת התורים לנוסחאות:

n הוא מספר הערוצים ב-QS;

λ - עוצמת הזרימה הנכנסת של יישומים P in;

v - עוצמת הזרימה היוצאת של יישומים P out;

μ - עוצמת זרימת השירות P בערך;

ρ - מחוון עומס מערכת (תנועה);

מ' - המספר המרבי של מקומות בתור, המגביל את אורך תור הבקשות;

i - מספר מקורות יישום;

p to - ההסתברות למצב ה-k של המערכת;

p about - ההסתברות לזמן סרק של המערכת כולה, כלומר ההסתברות שכל הערוצים פנויים;

p syst - ההסתברות לקבל בקשה במערכת;

p otk - ההסתברות לסירוב לבקשה בקבלתה למערכת;

p about - ההסתברות שהבקשה תוגש;

A הוא התפוקה המוחלטת של המערכת;

Q הוא התפוקה היחסית של המערכת;

och - המספר הממוצע של יישומים בתור;

o - המספר הממוצע של בקשות בשירות;

syst - המספר הממוצע של יישומים במערכת;

pt - זמן המתנה ממוצע לאפליקציה בתור;

o - זמן ההגשה הממוצע של הבקשה, המתייחס לבקשות המוגשות בלבד;

sys - זמן השהייה הממוצע של האפליקציה במערכת;

exp - זמן ממוצע המגביל את ההמתנה לאפליקציה בתור;

מספר ממוצע של ערוצים עמוסים.

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

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

בעת פתרון בעיות תור, יש צורך להקפיד על הרצף הבא:

1) קביעת סוג ה-QS לפי טבלה. 4.1;

2) בחירת נוסחאות בהתאם לסוג ה-QS;

3) פתרון בעיות;

4) גיבוש מסקנות על הבעיה.

1. תכנית מוות ורבייה.

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

לגרף המדינה עבור ערכת המוות והרבייה יש את הצורה המוצגת באיור. 19.1. המוזרות של גרף זה היא שניתן לצייר את כל מצבי המערכת לשרשרת אחת, שבה כל אחד מהמצבים הממוצעים ( ס 1 , ש 2 , …, ש n-1) מחובר על ידי חץ קדימה ואחורה עם כל אחד מהמדינות השכנות - ימין ושמאל, והמצבים הקיצוניים (ס 0 , שנ) - עם מדינה שכנה אחת בלבד. המונח "תכנית מוות ורבייה" מקורו בבעיות ביולוגיות, כאשר שינוי בגודל האוכלוסייה מתואר על ידי תכנית כזו.

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

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

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

למדינה הראשונה ס 0 יש לנו:

(19.1)

למדינה השנייה S1:

בשל (19.1), השוויון האחרון מצטמצם לטופס

איפה קלוקח את כל הערכים מ-0 עד פ.אז ההסתברויות הסופיות p0, p1,..., p n מספקים את המשוואות

(19.2)

בנוסף, עלינו לקחת בחשבון את מצב הנורמליזציה

ע 0 + ע 1 + ע 2 +…+ ע n=1. (19.3)

בואו נפתור את מערכת המשוואות הזו. מהמשוואה הראשונה (19.2) אנו מבטאים ע 1 דרך ר 0 :

ע 1 = ע 0. (19.4)

מהשני, בהתחשב (19.4), אנו מקבלים:

(19.5)

מהשלישי, תוך התחשבות (19.5),

(19.6)

ובכלל, לכל ק(מ-1 עד נ):

(19.7)

הבה נשים לב לנוסחה (19.7). המונה הוא המכפלה של כל העוצמות בחצים המובילים משמאל לימין (מההתחלה עד מדינה נתונה ס k), והמכנה הוא המכפלה של כל העוצמות בחצים המובילים מימין לשמאל (מההתחלה עד Sk).

לפיכך, כל ההסתברויות של המדינה ר 0 , עמ' 1 , ..., р נבא לידי ביטוי באמצעות אחד מהם ( ר 0). הבה נחליף ביטויים אלה בתנאי הנורמליזציה (19.3). אנחנו מסתדרים באמצעות סוגריים ר 0:

מכאן אנו מקבלים את הביטוי עבור ר 0 :

(העלינו את הסוגריים בחזקת -1 כדי לא לכתוב שברים דו-קומתיים). כל ההסתברויות האחרות מתבטאות במונחים של ר 0 (ראה נוסחאות (19.4)-(19.7)). שימו לב שהמקדמים עבור ר 0 בכל אחד מהם הם לא יותר מחברים עוקבים בסדרה אחרי היחידה בנוסחה (19.8). אז, בחישוב ר 0 , כבר מצאנו את כל המקדמים הללו.

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

2. נוסחה קטנה.

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

הבה ניקח בחשבון כל QS (ערוץ אחד, רב-ערוצי, מרקוביאן, לא מרקוביאן, עם תור בלתי מוגבל או מוגבל) ושני זרמים של אירועים הקשורים אליו: זרימת הלקוחות המגיעים ל-QS וזרם הלקוחות היוצאים מה-QS. QS. אם נקבע משטר מגביל, נייח במערכת, אזי המספר הממוצע של יישומים המגיעים ל-QS ליחידת זמן שווה למספר היישומים הממוצע היוצאים ממנו: לשני הזרמים יש אותה עוצמה λ.

לציין: X(t) -מספר הבקשות שהגיעו ל-CMO לפני הרגע ט. י(ט) — מספר הבקשות שיצאו מה-CMO

עד הרגע ט.שתי הפונקציות הן אקראיות ומשתנות בפתאומיות (מוגברת באחת) ברגע הגעת הבקשות (איקס(ט)) ויציאות של בקשות (Y(t)).סוג הפונקציות X(t) ו-Y(t)מוצג באיור. 19.2; שני הקווים מדורגים, העליון הוא X(t),נמוך יותר- Y(t).ברור, לכל רגע טההבדל שלהם ז(ט)= X(t) - Y(t)אינו אלא מספר היישומים ב-QS. כאשר הקווים X(t)ו Y(t)מיזוג, אין בקשות במערכת.

קחו בחשבון פרק זמן ארוך מאוד ט(ממשיכים נפשית את הגרף הרבה מעבר לשרטוט) ומחשבים עבורו את מספר האפליקציות הממוצע ב-QS. זה יהיה שווה לאינטגרל של הפונקציה Z T)על מרווח זה חלקי באורך המרווח ת:

ל syst. = . (19.9) o

אבל האינטגרל הזה אינו אלא השטח של הדמות המוצלת באיור. 19.2. בואו נסתכל היטב על הציור הזה. הדמות מורכבת ממלבנים שלכל אחד מהם גובה שווה לאחד, ובסיס השווה לזמן השהייה במערכת של הסדר המקביל (הראשון, השני וכו'). בואו נציין את הזמנים האלה t1, t2,...נכון, בסוף המרווח טכמה מלבנים ייכנסו לדמות המוצללת לא לגמרי, אלא חלקית, אבל עם דמות גדולה מספיק טהדברים הקטנים האלה לא יהיו חשובים.

(19.10)

כאשר הסכום חל על כל הבקשות שהתקבלו במהלך הזמן ט.

בואו נפריד בין הימין לבין צד שמאל(.19.10) באורך המרווח ט.אנו משיגים, תוך התחשבות (19.9),

ל syst. = . (19.11)

מחלקים ומכפילים צד ימין(19.11) לעוצמה X:

ל syst. = .

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

ל syst. = λ W syst. ,

W syst. = . (19.12)

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

בדיוק באותו אופן, נגזרת הנוסחה השנייה של ליטל, המתייחסת לזמן הממוצע שהאפליקציה מבלה בתור ^ ו וומספר הפניות הממוצע בתור ל och:

W och = . (19.13)

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

הנוסחאות של ליטל (19.12) ו- (19.13) ממלאות תפקיד חשוב בתורת התורים. לרוע המזל, ברוב המדריכים הקיימים, נוסחאות אלו (הוכחו ב השקפה כלליתיחסית לאחרונה) אינם ניתנים 1).

מערכות התורים הפשוטות ביותר ומאפייניהן

בסעיף זה, נשקול כמה מה-QS הפשוטים ביותר ונגזר ביטויים עבור המאפיינים שלהם (מדדי ביצועים). במקביל, נדגים את הטכניקות המתודולוגיות העיקריות האופייניות לתיאוריה היסודית, ה"מרקוביאנית" של עמידה בתור.

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

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

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

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

נציג את מאפייני היעילות של ה-QS הנבחנים במהלך המצגת.

1. פ- ערוץ QS עם כשלים(בעיית ארלנג). כאן אנו רואים את אחת הבעיות ה"קלאסיות" הראשונות בזמן של תורת העמידה בתור; בעיה זו נבעה מהצרכים המעשיים של הטלפוניה ונפתרה בתחילת המאה שלנו על ידי המתמטיקאי הדני ארלנט. המשימה מוגדרת כך: יש פערוצים (קווי תקשורת), המקבלים זרימה של יישומים בעוצמה λ. לזרימת השירות יש עוצמה μ (ההדדיות של זמן השירות הממוצע טעל אודות).

מצא את ההסתברויות הסופיות של מצבי ה-QS, כמו גם את המאפיינים של היעילות שלו:

^ א -תפוקה מוחלטת, כלומר, המספר הממוצע של יישומים שהוגשו ליחידת זמן;

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

^ ר אוטק- ההסתברות לכישלון, כלומר העובדה שהבקשה תשאיר את ה-QS ללא הגשה;

ק -מספר ממוצע של ערוצים עמוסים.

פִּתָרוֹן. מצבי מערכת ^S(QS) ימוספרו בהתאם למספר הבקשות במערכת (במקרה זה, זה עולה בקנה אחד עם מספר הערוצים העסוקים):

S 0 -אין יישומים ב-CMO,

S 1 -יש בקשה אחת ב-QS (ערוץ אחד תפוס, השאר בחינם),

Sk —ב-SMO הוא קיישומים ( קהערוצים עמוסים, השאר בחינם),

S n -ב-SMO הוא פיישומים (כולם נהערוצים עמוסים).

גרף מצב ה-QS מתאים לתכנית המוות ברבייה (איור 20.1). בואו נסמן את הגרף הזה - הניחו את עוצמת זרימות האירוע ליד החצים. מ ס 0 אינץ' S1המערכת מועברת על ידי זרימת בקשות בעוצמה λ (ברגע שמגיעה בקשה, המערכת קופצת מ S0ב S1).אותה זרימת בקשות מעבירה את המערכת מכל מצב שמאל למצב הימני השכן (ראה את החצים העליונים באיור 20.1).

בואו נניח את עוצמת החצים התחתונים. תן למערכת להיות במדינה ^S 1 (ערוץ אחד עובד). הוא מייצר μ שירותים ליחידת זמן. שמנו למטה ליד החץ ס 1 →סעוצמה 0 μ. עכשיו דמיינו שהמערכת נמצאת במדינה S2(שני ערוצים עובדים). כדי שהיא תלך אליה S 1,יש צורך שהערוץ הראשון או השני יסיים את השירות; העוצמה הכוללת של זרימות השירות שלהם היא 2μ; שים אותו בחץ המתאים. זרימת השירות הכוללת שניתנת על ידי שלושת הערוצים היא בעוצמה של 3μ, קערוצים - ק"מ.הנחנו את העוצמות הללו בחצים התחתונים באיור. 20.1.

ועכשיו, כשאנחנו יודעים את כל העוצמות, נשתמש בנוסחאות המוכנות (19.7), (19.8) להסתברויות הסופיות בסכימה של מוות ורבייה.

לפי הנוסחה (19.8) נקבל:

מונחי פירוק יהיו המקדמים עבור p 0בביטויים עבור p1

שימו לב שנוסחאות (20.1), (20.2) אינן כוללות את העוצמות λ ו-μ בנפרד, אלא רק כיחס λ/μ. לציין

λ/μ = ρ (20.3)

ונכנה את הערך של p "העוצמה המופחתת של זרימת היישומים". המשמעות שלו היא המספר הממוצע של בקשות המגיעות במשך זמן השירות הממוצע של בקשה אחת. באמצעות סימון זה, אנו משכתבים נוסחאות (20.1), (20.2) בצורה:

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

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

ר otk = ר n = . (20.6)

מכאן אנו מוצאים את התפוקה היחסית - ההסתברות שהבקשה תוגש:

ש = 1 - פלִפְתוֹחַ = 1 - (20.7)

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

A = λQ = λ. (20.8)

נותר רק למצוא את המספר הממוצע של ערוצים עסוקים ק.ניתן למצוא ערך זה "ישירות", כציפייה מתמטית למשתנה אקראי בדיד עם ערכים אפשריים 0, 1, ..., פוההסתברויות של ערכים אלו p 0 p 1 , ..., p n:

ק = 0 · p 0 +אחד · p 1 + 2 · p 2 + ... + n · P n .

מחליף כאן ביטויים (20.5) עבור רק , (ק = 0, 1, ..., P)וביצוע הטרנספורמציות המתאימות, נשיג בסופו של דבר את הנוסחה הנכונה עבורה ק.אבל נפיק את זה הרבה יותר קל (הנה זה, אחד ה"טריקים הקטנים"!) ואכן, אנחנו יודעים את התפוקה המוחלטת אבל.אין זו אלא עוצמת זרימת האפליקציות שמשרתת המערכת. כל מועסק ביחידת זמן משרת בממוצע |1 בקשות. אז המספר הממוצע של ערוצים עמוסים הוא

k = A/μ, (20.9)

או, נתון (20.8),

k = (20.10)

אנו מעודדים את הקורא לעבד את הדוגמה בעצמו. יש תחנת תקשורת עם שלושה ערוצים ( נ= 3), עוצמת זרימת היישומים λ = 1.5 (יישומים לדקה); זמן שירות ממוצע לכל בקשה ט v = 2 (דקות), כל זרימות האירועים (כמו בכל הפסקה הזו) הן הפשוטות ביותר. מצא את הסתברויות המצב הסופי ואת מאפייני הביצועים של ה-QS: א, ש, פאוקיי, ק.ליתר בטחון, הנה התשובות: ע 0 = 1/13, ע 1 = 3/13, ע 2 = 9/26, עמ' 3 = 9/26 ≈ 0,346,

אבל≈ 0,981, ש ≈ 0,654, פפתוח ≈ 0.346, k ≈ 1,96.

ניתן לראות מהתשובות, אגב, שה-QS שלנו עמוס במידה רבה: מתוך שלושה ערוצים, בממוצע, כשניים עמוסים, וכ-35% מהאפליקציות הנכנסות נותרות ללא שירות. אנו מזמינים את הקורא, אם הוא סקרן ולא עצלן, לברר: כמה ערוצים יידרשו על מנת לספק לפחות 80% מהפניות הנכנסות? ואיזה חלק מהערוצים יהיה בטל בו זמנית?

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

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

QS חד ערוץ עם תור בלתי מוגבל.

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

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

נדרש למצוא את ההסתברויות הסופיות של מצבי ה-QS, כמו גם את המאפיינים של יעילותו:

ל syst. — מספר יישומים ממוצע במערכת,

W syst. הוא זמן השהייה הממוצע של בקשה במערכת,

^ ל אוך- המספר הממוצע של יישומים בתור,

W och — הזמן הממוצע שאפליקציה מבלה בתור,

פזאן — ההסתברות שהערוץ תפוס (מידת הטעינה של הערוץ).

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

בשל העובדה שהתור אינו מוגבל, כל בקשה תוגש במוקדם או במאוחר, לפיכך A \u003d λ,מאותה הסיבה ש= 1.

פִּתָרוֹן. מצבי המערכת, כבעבר, ימוספרו לפי מספר האפליקציות ב-QS:

ס 0 — הערוץ בחינם

ס 1 - הערוץ תפוס (משרת את הבקשה), אין תור,

ס 2 - הערוץ תפוס, בקשה אחת נמצאת בתור,

ס k - הערוץ תפוס, ק - 1 יישומים נמצאים בתור,

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

קודם כל, הבה נשאל את עצמנו, האם יש הסתברויות סופיות במקרה הזה? אחרי הכל, מספר המצבים של המערכת הוא אינסופי, ובאופן עקרוני, ב t → ∞התור יכול לגדול ללא הגבלת זמן! כן, זה נכון: ההסתברויות הסופיות ל-QS כזה לא תמיד קיימות, אלא רק כשהמערכת לא עמוסה. ניתן להוכיח שאם ρ הוא בהחלט פחות מאחד (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при ט→ ∞ גדל ללא הגבלה.

עובדה זו נראית "בלתי מובנת" במיוחד עבור ρ = 1. נראה כי אין דרישות בלתי אפשריות למערכת: במהלך השירות של בקשה אחת, בממוצע, מגיעה בקשה אחת, והכל צריך להיות מסודר, אבל במציאות זה לא. עבור ρ = 1, ה-QS מתמודד עם זרימת הבקשות רק אם זרימה זו היא סדירה, וגם זמן השירות אינו אקראי, שווה למרווח בין בקשות. במקרה ה"אידיאלי" הזה, לא יהיה תור ב-QS כלל, הערוץ יהיה עמוס באופן רציף ויוציא באופן קבוע בקשות שירות.

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

אבל בואו נחזור ל-QS החד-ערוץ שלנו עם תור בלתי מוגבל. למהדרין, הנוסחאות להסתברויות הסופיות בסכימה של מוות ורבייה נגזרו על ידינו רק למקרה של מספר סופי של מצבים, אבל בואו ניקח חירויות - נשתמש בהן למספר אינסופי של מצבים. הבה נחשב את ההסתברויות הסופיות של מצבים לפי נוסחאות (19.8), (19.7). במקרה שלנו, מספר האיברים בנוסחה (19.8) יהיה אינסופי. אנחנו מקבלים ביטוי עבור p 0:

ע 0 \u003d -1 \u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

הסדרה בנוסחה (20.11) היא התקדמות גיאומטרית. אנחנו יודעים את זה עבור ρ< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ...קיים רק עבור r<1).

כעת נניח שתנאי זה מתקיים ו- ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

ע 0 = 1 - עמ'. (20.12)

הסתברויות p 1 , p 2 , ..., p k ,... ניתן למצוא לפי הנוסחאות:

p1 = ρ p 0, p 2= ρ2 p 0 ,…,p k = ρ p0, ...,

מאיפה, בהתחשב (20.12), אנו מוצאים לבסוף:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ ק(1 - p), . . .(20.13)

כפי שאתה יכול לראות, ההסתברויות p0, p1, ..., p k,...יוצרים התקדמות גיאומטרית עם המכנה p. באופן מוזר, הגדול שבהם p 0 -ההסתברות שהערוץ יהיה בחינם בכלל. לא משנה עד כמה המערכת עמוסה בתור, אם רק היא יכולה בכלל להתמודד עם זרימת היישומים (ρ<1), самое вероятное число заявок в системе будет 0.

מצא את המספר הממוצע של יישומים ב-QS ^L syst. . כאן אתה צריך להתעסק קצת. ערך אקראי Z-מספר בקשות במערכת - יש ערכים אפשריים 0, 1, 2, .... ק,...עם הסתברויות p0, p 1 , p 2 , ..., p k , ...הציפייה המתמטית שלו היא

למערכת = 0? p 0 + 1 ? ע 1 + 2 ? ע 2 +…+ק ? ע k +…= (20.14)

(הסכום נלקח לא מ-0 ל-∞, אלא מ-1 ל-∞, שכן איבר האפס שווה לאפס).

אנו מחליפים לנוסחה (20.14) את הביטוי עבור p k (20.13):

ל syst. =

כעת נוציא את הסימן של הסכום ρ (1-ρ):

ל syst. = ρ(1-ρ)

כאן אנו מיישמים שוב את "הטריק הקטן": קρ ק-1 אינו אלא הנגזרת ביחס ל- ρ של הביטוי ρ ק; אומר,

ל syst. = ρ(1-ρ)

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

ל syst. = ρ (1-ρ) (20.15)

אבל הסכום בנוסחה (20.15) אינו אלא סכום של התקדמות גיאומטרית פוחתת אינסופית עם האיבר הראשון ρ והמכנה ρ; כמות זו

שווה ל , והנגזרת שלו היא . החלפת ביטוי זה ב-(20.15), נקבל:

למערכת = . (20.16)

ובכן, עכשיו בואו ניישם את הנוסחה של ליטל (19.12) ונמצא את זמן השהייה הממוצע של אפליקציה במערכת:

W syst = (20.17)

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

מספר הבקשות בשירות יכול להיות אפס (אם הערוץ פנוי) או אחד (אם הוא תפוס). התוחלת המתמטית של משתנה אקראי כזה שווה להסתברות שהערוץ תפוס (סימנו את זה רזאן). מובן מאליו, ר zan שווה לאחד פחות ההסתברות p 0שהערוץ בחינם:

רזאן = 1 - ר 0 = p. (20.18)

לכן, המספר הממוצע של בקשות בשירות שווה ל

^L בערך= ρ, (20.19)

ל och = ל syst - ρ =

ולבסוף

ל pt = (20.20)

באמצעות הנוסחה של ליטל (19.13), אנו מוצאים את הזמן הממוצע שהאפליקציה מבלה בתור:

(20.21)

לפיכך, נמצאו כל המאפיינים של יעילות QS.

הבה נציע לקורא לפתור דוגמה בעצמו: QS חד ערוצית היא חצר תיווך רכבת, המקבלת את הזרימה הפשוטה ביותר של רכבות בעוצמה של λ = 2 (רכבות לשעה). שירות (פירוק)

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

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

לבסוף, מצא את סך הקנס היומי W, אותו תצטרך התחנה לשלם עבור ירידת מרץ של רכבות על מסילות חיצוניות, אם התחנה משלמת קנס a (רובל) עבור שעה אחת של ירידת מרץ של רכבת אחת. ליתר בטחון, הנה התשובות: ל syst. = 2 (הרכב), W syst. = 1 (שעה), לנקודות = 4/3 (הרכב), W pt = 2/3 (שעות), לחיצוני = 16/27 (הרכב), Wחיצוני = 8/27 ≈ 0.297 (שעות). העונש היומי הממוצע W על המתנה לרכבות על מסילות חיצוניות מתקבל על ידי הכפלת מספר הרכבות הממוצע המגיעות לתחנה ביום, זמן ההמתנה הממוצע לרכבות על מסילות חיצוניות וקנס שעתי. א: W ≈ 14.2 א.

ערוץ מחדש של QS עם תור בלתי מוגבל.

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

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

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

נניח שהתנאי ρ/ נ < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0תהיה סדרה של איברים המכילים פקטוריאלים, בתוספת סכום של התקדמות גיאומטרית פוחתת אינסופית עם המכנה ρ/ נ. לסכם את זה, אנחנו מוצאים

(20.22)

עכשיו בואו נמצא את המאפיינים של יעילות QS. מבין אלה, הכי קל למצוא את המספר הממוצע של ערוצים תפוסים ק= λ/μ, = ρ (זה נכון בדרך כלל עבור כל QS עם תור בלתי מוגבל). מצא את המספר הממוצע של יישומים במערכת למערכת ומספר האפליקציות הממוצע בתור ל och. מבין אלה, קל יותר לחשב את השני, לפי הנוסחה

ל och =

ביצוע הטרנספורמציות המתאימות לפי המדגם של בעיה 2

(עם בידול של הסדרה), אנו מקבלים:

ל och = (20.23)

הוספת אליו את המספר הממוצע של אפליקציות בשירות (זה גם המספר הממוצע של ערוצים עסוקים) k =ρ, נקבל:

למערכת = ל och + ρ. (20.24)

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

(20.25)

עכשיו בואו נפתור דוגמה מעניינת. משרד כרטיסי רכבת עם שני חלונות הוא QS דו-ערוצי עם תור בלתי מוגבל שמתבסס מיד לשני חלונות (אם חלון אחד פנוי, הנוסע הבא בתור לוקח אותו). הקופה מוכרת כרטיסים בשתי נקודות: A ו בְּ.עוצמת זרם האפליקציות (נוסעים שרוצים לקנות כרטיס) לשתי הנקודות א' וב'זהה: λ A = λ B = 0.45 (נוסע לדקה), ובסך הכל הם יוצרים זרימה כללית של יישומים בעוצמה של λ A + λB = 0.9. קופאי משקיע בממוצע שתי דקות בשירות נוסע.

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

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

אפשרות I (קיימת). QS דו-ערוצי מקבל זרימה של יישומים בעוצמה של λ = 0.9; עוצמת זרימת תחזוקה μ = 1/2 = 0.5; ρ = λ/μ = l.8. מאז ρ/2 = 0.9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0.0525. הממוצע, מספר האפליקציות בתור נמצא לפי הנוסחה (20.23): L och ≈ 7.68; הזמן הממוצע של הלקוח בתור (לפי הראשונה מהנוסחאות (20.25)), שווה ל- Wנקודות ≈ 8.54 (דקות).

אפשרות II (מוצע). יש צורך לשקול שני ערוץ QS אחד (שני חלונות מיוחדים); כל אחד מקבל זרימת בקשות בעוצמה λ = 0.45; μ . עדיין שווה ל-0.5; ρ = λ/μ = 0.9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) ל och = 8.1.

הנה אחד בשבילך! אורך התור, מסתבר, לא רק שלא ירד, אלא גדל! אולי זמן ההמתנה הממוצע בתור ירד? בוא נראה. דליה לנקודות על λ = 0.45, נקבל Wנקודות ≈ 18 (דקות).

זה הרציונליזציה! במקום לרדת, גם אורך התור הממוצע וגם זמן ההמתנה הממוצע בו גדלו!

בואו ננסה לנחש למה זה קרה? לאחר שחשבנו על המוח שלנו, הגענו למסקנה: זה קרה בגלל שבגרסה הראשונה (דו-ערוצי QS) חלקיק הזמן הממוצע שבו כל אחת משתי הקופאיות בטלה הוא פחות: אם הוא לא עסוק בשירות נוסע אשר קונה כרטיס ל אבל,הוא יכול לדאוג לנוסע שקונה כרטיס לנקודה בְּ,ולהיפך. בגרסה השנייה, אין אפשרות להחלפה כזו: קופאית לא מאוכלסת פשוט יושבת בחיבוק ידיים...

- נו , בסדר, הקורא מוכן להסכים, ניתן להסביר את העלייה, אבל למה היא כל כך משמעותית? האם יש כאן טעות בחישוב?

ונשיב על השאלה הזו. אין שגיאה. העובדה , שבדוגמה שלנו, שני ה-QS עובדים על גבול היכולות שלהם; אם תגדיל מעט את זמן השירות (כלומר, תפחית את μ), הם לא יוכלו יותר להתמודד עם זרימת הנוסעים, והתור יתחיל לגדול ללא הגבלת זמן. ו"זמן השבתה נוסף" של הקופאי במובן מסוים שווה לירידה בתפוקה שלו μ.

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

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

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

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

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

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

יש צורך למצוא את ההסתברויות הסופיות של מצבים (אגב, הם קיימים בבעיה זו עבור כל ρ - אחרי הכל, מספר המצבים הוא סופי), ההסתברות לכישלון ר otk, רוחב פס מוחלט אבל,ההסתברות שהערוץ תפוס ר zan, אורך תור ממוצע ל och, המספר הממוצע של בקשות ב-CMO ל syst , זמן המתנה ממוצע בתור W och , זמן שהייה ממוצע של בקשה ב-CMO W syst. כשמחשבים את מאפייני התור, אפשר להשתמש באותה טכניקה שהשתמשנו בבעיה 2, עם ההבדל שיש צורך לסכם לא התקדמות אינסופית, אלא סופית.

לולאה סגורה QS עם ערוץ אחד ו Mמקורות יישומים.למען הקונקרטיות, בואו נקבע את המשימה בצורה הבאה: עובד אחד משרת טמכונות, שכל אחת מהן דורשת התאמה (תיקון) מעת לעת. עוצמת זרימת הביקוש של כל מכונה עובדת שווה ל- λ . אם המכונה לא תקינה ברגע שהעובד פנוי, הוא ניגש מיד לשירות.

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

שימו לב שב-QS זה, הסתברויות סופיות יתקיימו גם עבור כל ערכים של λ ו-μ = 1/ ט o, מכיוון שמספר המצבים של המערכת הוא סופי.

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

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

דוגמאות למערכות תורים הן:

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

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

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

אורז. אחד

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

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

1. תור - מצבר בקשה. ייתכן שהתור לא קיים.
2. צומת שירות מורכב ממספר סופי של ערוצי שירות. לכל ערוץ יש 3 מצבים: פנוי, תפוס, סרק. אם כל הערוצים תפוסים, אז אתה יכול להמציא אסטרטגיה למי להעביר את האפליקציה.
3. סֵרוּב משירות מתרחש אם כל הערוצים תפוסים (ייתכן שחלקם לא יפעלו).

בנוסף לאלמנטים הבסיסיים הללו ב-QS, חלק מהמקורות מבחינים גם ברכיבים הבאים:

מסיים - משמיד עסקאות;

מחסן - אחסון משאבים ומוצרים מוגמרים;

חשבון הנהלת חשבונות - לביצוע פעולות מסוג "רישום";

מנהל - מנהל משאבים;

סיווג CMO

החלוקה הראשונה (על ידי נוכחות של תורים):

• CMO עם כשלים;
• CMO עם תור.

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

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

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

אז, למשל, השאלות הבאות נחשבות:

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

ניתן לשלב סוגי הגבלת תור.

סיווג נוסף מחלק את ה-CMO לפי מקור הבקשות. המערכת עצמה או סביבה חיצונית כלשהי הקיימת ללא תלות במערכת יכולה ליצור יישומים (דרישות).

מטבע הדברים, זרימת הבקשות שתיווצר על ידי המערכת עצמה תהיה תלויה במערכת ובמצבה.

בנוסף, SMOs מחולקים ל לִפְתוֹחַ CMO ו סָגוּר SMO.

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

דוגמה למערכת סגורה: הוצאת שכר על ידי קופאי במפעל.

לפי מספר הערוצים, QS מחולקים ל:

• ערוץ יחיד;
• רב ערוצי.

מאפייני מערכת התורים

המאפיינים העיקריים של מערכת תורים מכל סוג הם:

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

זרם קלט דרישות

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

א i- זמן הגעה בין דרישות - משתנים אקראיים מפוזרים זהים באופן בלתי תלוי;

E(A)הוא זמן ההגעה הממוצע (MO);

λ=1/E(A)- עוצמת קבלת הדרישות;

מאפייני זרם קלט:

1. חוק הסתברותי הקובע את רצף הרגעים של קבלת דרישות השירות.
2. מספר הבקשות בכל הגעה הבאה לזרימות ריבוי שידור.

משמעת בתור

תור - סט דרישות הממתינות לטיפול.

לתור יש שם.

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

• כל הקודם זוכה;

ראשון נכנס ראשון יוצא (FIFO)

הסוג הנפוץ ביותר של תור.

איזה מבנה נתונים מתאים לתיאור תור כזה? המערך גרוע (מוגבל). אתה יכול להשתמש במבנה LIST.

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

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

רשימת פעולות:

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

מבנה המכונה STACK. ניתן לתאר על ידי מערך או מבנה רשימה;

• בחירה אקראית של יישומים;
• בחירת בקשות לפי קריטריון עדיפות.

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

מאפייני תור

• הַגבָּלָהזמן המתנהרגע התרחשות השירות (יש תור עם זמן המתנה מוגבל לשירות, הקשור למושג "אורך תור קביל");
• אורך התור.

מנגנון שירות

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

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

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

סִי- זמן שירות אניהדרישה ה';

E(S)- זמן שירות ממוצע;

μ=1/E(S)- מהירות דרישות השירות.

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

גורם ניצול QS

נμ – קצב שירות במערכת כאשר כל מכשירי השירות תפוסים.

ρ=λ/( נμ) נקרא גורם ניצול QS , מראה כמה משאבי מערכת נמצאים בשימוש.

מבנה מערכת השירות

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

דוגמא. קופות רושמות בחנות.

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

דוגמא. הועדה הרפואית.

שירות משולב - טיפול בהפקדות בקופת החיסכון: קודם הבקר, אחר כך הקופאית. ככלל, 2 בקרים לכל קופאי.

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

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

הקריטריונים העיקריים לאפקטיביות תפקוד ה-QS

כפי ש הקריטריונים העיקריים לאפקטיביות התפקוד של מערכות התורים בהתאם לאופי הבעיה הנפתרת, ייתכן שיש:

• ההסתברות לשירות מיידי של הבקשה שהתקבלה (P service =K obs /K post);
• ההסתברות לדחיית שירות של הבקשה שהתקבלה (P otk =K otk /K post);

ברור ש-R obl + P otk =1.

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

לְעַכֵּב – אחד מקריטריוני השירות של QS, הזמן שבו לקחה הבקשה לקראת השירות.

ד i- עיכוב בתור הבקשות אני;

W i \u003d D i + S i- זמן שהייה במערכת הדרישה אני.

(עם הסתברות 1) הוא האיחור הממוצע שנקבע של בקשה בתור;

(עם הסתברות 1) הוא הזמן הממוצע במצב יציב שהדרישה מבלה ב-QS (המתנה).

ש(ט) -מספר הבקשות בתור בכל פעם t;

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

ואז אקספוננטים (אם יש)

(עם הסתברות 1) הוא המספר הממוצע בזמן של מצב יציב של בקשות בתור;

(עם הסתברות 1) הוא מספר הזמן הממוצע של בקשות במערכת.

שימו לב ש- ρ<1 – обязательное условие существования d, w, Qו לבמערכת התורים.

אם נזכור ש-ρ= λ/( נμ), אז ברור שאם עוצמת קבלת הבקשות גדולה מ נμ, ואז ρ>1, וזה טבעי שהמערכת לא תוכל להתמודד עם זרימת יישומים כזו, ולכן, אי אפשר לדבר על d, w, Qו ל.

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

יש לציין כי הקריטריונים לעיל להערכת ביצועי המערכת ניתנים לחישוב אנליטי עבור מערכות תורים M/M/N(נ>1), כלומר, מערכות עם זרימות מרקוב של לקוחות ושירות. ל M/G/אני לכל הפצה גולכמה מערכות אחרות. באופן כללי, התפלגות הזמן בין כניסות, התפלגות זמן השירות או שניהם חייבים להיות אקספוננציאליים (או מעין התפלגות Erlang מעריכית מסדר ה-K) כדי שפתרון אנליטי יהיה אפשרי.

בנוסף, אתה יכול גם לדבר על מאפיינים כגון:

• תפוקה מוחלטת של המערכת - שירות А=Р *λ;
• תפוקה יחסית של המערכת -

עוד דוגמה מעניינת (וממחישה) לפתרון אנליטי – חישוב של עיכוב תור ממוצע במצב יציב עבור מערכת תור M/G/ 1 לפי הנוסחה:

.

ברוסיה, נוסחה זו ידועה בשם נוסחת פולצק. – חינצ'ין, בחו"ל נוסחה זו קשורה בשמו של רוס.

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

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

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