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

מדדי ביצועים של QS

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

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

• P obs - ההסתברות למתן שירות לאפליקציה,
• t syst הוא הזמן שבו הבקשה נשארת במערכת.

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

• λ בהוא התפוקה המוחלטת של המערכת (מספר הבקשות הממוצע המוגשות ליחידת זמן),
• P obs הוא התפוקה היחסית של המערכת,
• k z - מקדם עומס מערכת.

ראה גם פרמטרים של עלות-תועלת של קופות חולים

משימה . מרכז המחשוב לשימוש משותף עם שלושה מחשבים מקבל הזמנות ממפעלים לעבודת מחשוב. אם כל שלושת המחשבים פועלים, ההזמנה החדשה הנכנסת אינה מתקבלת, והארגון נאלץ לפנות למרכז מחשבים אחר. זמן העבודה הממוצע בהזמנה אחת הוא 3 שעות עוצמת זרימת האפליקציות היא 0.25 (1/h). מצא את ההסתברויות המגבילות של מצבים ומחווני ביצועים של מרכז המחשבים.
פִּתָרוֹן. לפי תנאי n=3, λ=0.25(1/h), t rev. =3 (ח). עוצמת זרימת השירותים μ=1/t vol. =1/3=0.33. עוצמת עומס המחשב לפי נוסחה (24) ρ=0.25/0.33=0.75. הבה נמצא את ההסתברויות המגבילות של המצבים:
על פי הנוסחה (25) p 0 \u003d (1 + 0.75 + 0.75 2 / 2! + 0.75 3 / 3!) -1 \u003d 0.476;
לפי הנוסחה (26) p 1 =0.75∙0.476=0.357; p 2 \u003d (0.75 2 / 2!) ∙ 0.476 \u003d 0.134; p 3 \u003d (0.75 3 / 3!) ∙ 0.476 \u003d 0.033 כלומר. במצב נייח של מרכז המחשבים, בממוצע, 47.6% מהמקרים אין אפליקציה אחת, 35.7% - יש אפליקציה אחת (מחשב אחד תפוס), 13.4% - שתי אפליקציות (שני מחשבים), 3.3% מהזמן - שלושה יישומים (שלושה מחשבים תפוסים).
ההסתברות לכשל (כאשר כל שלושת המחשבים תפוסים), לפיכך, P otk. \u003d p 3 \u003d 0.033.
לפי נוסחה (28), התפוקה היחסית של המרכז היא Q = 1-0.033 = 0.967, כלומר. בממוצע, מתוך כל 100 פניות, מרכז המחשבים משרת 96.7 פניות.
לפי נוסחה (29), התפוקה המוחלטת של המרכז היא A= 0.25∙0.967 = 0.242, כלומר. 0.242 בקשות מוגשות בממוצע לשעה.
לפי נוסחה (30), המספר הממוצע של מחשבים מועסקים k = 0.242/0.33 = 0.725, כלומר. כל אחד משלושת המחשבים יעסוק בשירות יישומים בממוצע של 72.5/3 בלבד = 24.2%.
בהערכת יעילות מרכז המחשבים יש להשוות את ההכנסה מביצוע בקשות להפסדים מהשבתת מחשבים יקרים (מצד אחד יש לנו תפוקה גבוהה של ה-QS, ומצד שני. , זמן השבתה משמעותי של ערוצי השירות) ולבחור בפתרון פשרה.

משימה . בנמל יש עגינה אחת לפריקת אוניות. עוצמת זרימת הכלים היא 0.4 (כלים ליום). הזמן הממוצע לפריקת כלי שיט אחד הוא יומיים. ההנחה היא שהתור יכול להיות באורך בלתי מוגבל. מצא את מדדי הביצועים של המעגן, כמו גם את ההסתברות שלא יותר מ-2 כלי שיט ממתינים לפריקה.
פִּתָרוֹן. יש לנו ρ = λ/μ = μt כרך. =0.4∙2=0.8. מאז ρ = 0.8 < 1, אז התור לפריקה לא יכול לגדול ללא הגבלת זמן ויש הסתברויות מגבילות. בואו נמצא אותם.
ההסתברות שהמעגן פנוי, לפי (33) p 0 = 1 - 0.8 = 0.2, וההסתברות שהוא תפוס, P zan. = 1-0.2 = 0.8. לפי נוסחה (34), ההסתברויות ש-1, 2, 3 ספינות נמצאות בעגינה (כלומר, 0, 1, 2 ספינות ממתינות לפריקה) שוות ל-p 1 = 0.8 (1-0.8) = 0, 16 ; p 2 \u003d 0.8 2 ∙ (1-0.8) \u003d 0.128; p 3 \u003d 0.8 3 ∙ (1-0.8) \u003d 0.1024.
ההסתברות שלא יותר מ-2 ספינות ממתינות לפרוק היא

לפי נוסחה (40), מספר הספינות הממוצע הממתינות לפריקה

וזמן ההמתנה הממוצע לפריקה לפי הנוסחה (15.42)
(יְוֹם).
לפי נוסחה (36), מספר הספינות הממוצע במעגן, L syst. = 0.8/(1-0.8) = 4 (ימים) (או קל יותר לפי (37) L syst. = 3.2+0.8 = 4 (ימים), וזמן השהייה הממוצע של הספינה במעגן לפי הנוסחה ( 41) T syst = 4/0.8 = 5 (ימים).
ברור שהיעילות של פריקת אוניות נמוכה. כדי להגדיל אותו, יש צורך להקטין את הזמן הממוצע של פריקת כלי השיט t בערך או להגדיל את מספר המקומות n.

משימה . בסופרמרקט, זרם לקוחות מגיע לצומת ההתנחלות בעוצמה של λ = 81 איש. תוך שעה. משך השירות הממוצע על ידי הבקר-קופאית של קונה אחד לא כ-2 דקות. לְהַגדִיר:
א. המספר המינימלי של בקרים-קופאים p min,שבו התור לא יגדל עד אינסוף, ומאפייני השירות המתאימים עבור n=n min.
ב. המספר האופטימלי של n opt. בקרים-קופאים, שבהם הערך היחסי של עלויות C rel., הקשורות לעלויות אחזקת ערוצי שירות והישארות בתור של הקונים, בהינתן, למשל, כמו , יהיה מינימלי, וישווה את מאפייני השירות ב-n=n min ו-n=n opt.
ב. ההסתברות שלא יהיו יותר משלושה קונים בתור.
פִּתָרוֹן.
א. לפי תנאי l = 81(1/h) = 81/60 = 1.35 (1/דקה). לפי הנוסחה (24) r = l / m = lt rev = 1.35 × 2 = 2.7. התור לא יגדל ללא הגבלת זמן בתנאי r/n< 1, т.е. при n >r = 2.7. לפיכך, המספר המינימלי של בקרים-קופאים n min = 3.
תן לנו למצוא את מאפייני שירות QS עבור פ= 3.
ההסתברות שאין קונים בצומת ההתיישבות, לפי נוסחה (45) p 0 = (1+2.7+2.7 2 /2!+2.7 3 /3!+2.7 4 /3!(3 -2.7)) - 1 = 0.025, כלומר. ממוצע של 2.5% בקרי זמן-קופאים יהיו בטלים.
ההסתברות שיהיה תור בצומת החישוב, לפי (48) P och. = (2.7 4 /3!(3-2.7))0.025 = 0.735
המספר הממוצע של קונים בתור, לפי (50) L נקודות. \u003d (2.7 4 / 3 3! (1-2.7 / 3) 2) 0.025 \u003d 7.35.
זמן המתנה ממוצע בתור לפי (42) T נקודות. = 7.35/1.35 = 5.44 (דקות).
מספר הקונים הממוצע בצומת החישוב לפי (51) L syst. = 7.35+2.7 = 10.05.
הזמן הממוצע של הקונים בצומת החישוב לפי (41) T syst. = 10.05/1.35 = 7.44 (דקות).
שולחן 1

מאפיין שירות	מספר בקרים-קופאים
	3	4	5	6	7
הסתברות לקופאיות סרק p 0	0,025	0,057	0,065	0,067	0,067
המספר הממוצע של קונים בתור T och.	5,44	0,60	0,15	0,03	0,01
ערך יחסי של עלויות С rel.	18,54	4,77	4,14	4,53	5,22

המספר הממוצע של בקרים-קופאים העוסקים בשירות לקוחות, לפי (49) k = 2.7.
יחס (חלק) של בקרי קופאים המועסקים בשירות
= ρ/n = 2.7/3 = 0.9.
תפוקה מוחלטת של צומת החישוב א = 1.35 (1/דקה), או 81 (1/h), כלומר. 81 קונים לשעה.
ניתוח של מאפייני השירות מצביע על עומס יתר משמעותי של צומת ההתיישבות בנוכחות שלושה בקרים-קופאים.
ב. עלות יחסית עבור n = 3
ג רל. = = 3/1.35+3∙5.44 = 18.54.
חשב את הסכום היחסי של עלויות עבור ערכים אחרים פ(שולחן 1).
כפי שניתן לראות מהטבלה. 2, העלויות המינימליות מתקבלות ב-n = n opt. = 5 בקרים-קופאים.
הבה נקבע את מאפייני השירות של צומת החישוב עבור n = n opt. =5. אנחנו מקבלים P och. = 0.091; ל = 0.198; ט ו. = 0.146 (דקה); מערכת L = 2.90; ט סנסט. = 2.15 (דקות); k = 2.7; k 3 \u003d 0.54.
כפי שאתה יכול לראות, ב-n = 5, בהשוואה ל-n = 3, ההסתברות לתור P och. , אורך תור L נקודות. וזמן השהות הממוצע בתור T och. ובהתאם, המספר הממוצע של קונים מערכת L. והזמן הממוצע שהושקע בצומת החישוב T sist., כמו גם שיעור הבקרים המועסקים בשירות k 3. אבל המספר הממוצע של בקרים-קופאים המועסקים בטיפול ב-k והתפוקה המוחלטת של צומת החישוב A כמובן לא. שינוי.
ב. ההסתברות שלא יהיו יותר מ-3 לקוחות בתור מוגדרת כ
= 1-P och. + p 5+1 + p 5+2 + p 5+3 , כאשר כל איבר נמצא על ידי נוסחאות (45) – (48). נקבל עבור n=5:

(שימו לב שבמקרה של n=3 בקרים-קופאים, אותה הסתברות קטנה משמעותית: P(r ≤ 3) =0.464).

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

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

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

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

דוגמאות ל-SMOs הן:

עמדות תחזוקה לרכב;

עמדות לתיקון רכב;

משרדי ביקורת ועוד.

המייסד של תורת התורים, בפרט, תורת התורים, הוא המדען הדני המפורסם A.K. Erlang (1878-1929), שחקר את תהליכי השירות במרכזיות הטלפונים.

מערכות שבהן מתרחשים תהליכי שירות נקראות מערכות תורים (QS).

כדי לתאר מערכת תורים, עליך לציין:

- זרימת קלט של יישומים;

- משמעת שירות;

- זמן שירות

- מספר ערוצי השירות.

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

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

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

הגיע אחרון - הוגש ראשון; (קופסה לכדורי טניס, ערימה בטכניקה)

בחירה אקראית של יישומים;

בחירת בקשות לפי קריטריון עדיפות.

זמן שירותיישומים ב-QS הוא משתנה אקראי. חוק ההפצה הנפוץ ביותר הוא החוק האקספוננציאלי.  - מהירות שירות. =מספר בקשות שירות/יחידות. זְמַן.

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

המבנה הכללי של ה-QS מוצג באיור.

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

בעיות עיצוב QS.

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

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

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

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

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

2). יש צורך לקבוע את הקריטריון ליעילות התפקוד QS, תוך התחשבות בעלות הפסדי זמן הן מצד האפליקציות והן מצד השירות.

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

1. מדדים ליעילות השימוש ב-QS.

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

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

משך הזמן הממוצע של תקופת העסקתו של ה-SMO.

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

2. אינדיקטורים לאיכות יישומי השירות.

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

זמן שהייה ממוצע של בקשה ב-CMO.

ההסתברות לסירוב לבקשה ללא המתנה.

ההסתברות שבקשה נכנסת תתקבל מיד לשירות.

חוק חלוקת זמן המתנה לפנייה בתור.

חוק חלוקת הזמן של בקשה ב-QS.

המספר הממוצע של פניות בתור.

מספר הבקשות הממוצע ב-CMO.

3. אינדיקטורים ליעילות התפקוד של צמד "QS - צרכן".

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

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

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

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

1. על פי אופי השירות, ניתן להבחין בין סוגי ה-QS הבאים:

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

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

מערכות עם תור מוגבל. (תיקון מוסך)

מערכות עם כשלים. כל הבקשות שהגיעו במועד הטיפול בבקשה נדחות. (GTS)

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

2. לפי מספר ערוצי השירות, QS מחולקים לקבוצות הבאות.

ערוץ יחיד QS.

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

3. על פי מגוון החפצים המטופלים, מבדילים שני סוגים.

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

פתחו CMOs.

4. לפי מספר שלבי השירות, מבדילים QS חד פאזיים ורב פאזיים.

שלב בודד QS הן מערכות הומוגניות שמבצעות את אותה פעולת שירות.

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

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

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

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

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

אורז. 6.2.

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

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

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

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

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

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

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

QSs גם שונים במספר הדרישות שיכולות להיות בו זמנית במערכת ההגשה. לְהַקְצוֹת:

• 1) מערכות עם זרימה מוגבלת של דרישות;
• 2) מערכות עם זרימה בלתי מוגבלת של דרישות.

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

• 1) מערכות עם שירות מוזמן;
• 2) מערכות עם שירות מופרע.

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

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

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

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

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

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

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

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

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

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

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

הרעיון של תהליך סטוכסטי של מרקוב

תהליך העבודה של ה-SMO הוא תהליך אקראי.

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

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

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

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

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

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

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

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

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

פִּתָרוֹן.מצבים אפשריים של המערכת: - שני הצמתים פועלים; - הצומת הראשון בתיקון, השני ניתן לשירות; - הצומת השני בתיקון, הראשון ניתן לשירות; שתי היחידות נמצאות בתיקון. הגרף של המערכת מוצג באיור. אחד.

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

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

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

זרמי אירועים

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

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

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

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

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

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

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

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

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

שעבורו התוחלת המתמטית של משתנה מקרי שווה לשונות שלו:.

בפרט, ההסתברות ששום אירוע לא יתרחש במהלך הזמן שווה ל

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

בהתאם ל(2), ההסתברות שאף אחד מהאירועים הבאים לא יופיע במרווח הזמן שווה ל

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

צפיפות ההסתברות של משתנה אקראי היא הנגזרת של פונקציית ההתפלגות שלו (איור 3), כלומר.

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

ולהיפך לפי גודל עוצמת הזרימה.

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

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

עבור הזרימה הפשוטה ביותר עם עוצמה, ההסתברות להכות

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

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

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

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

תורת התורים– קטע מיוחד בתורת המערכות הוא קטע בתורת ההסתברות בו לומדים מערכות תורים באמצעות מודלים מתמטיים.

מערכת תורים (QS)- זהו מודל הכולל: 1) זרימה אקראית של דרישות, שיחות או לקוחות הזקוקים לשירות; 2) האלגוריתם ליישום שירות זה; 3) ערוצים (התקנים) לתחזוקה.

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

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

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

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

כפי ש מאפייני QSנחשב:

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

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

3.1 מודלים של מערכות תורים.

ניתן לאפיין כל QS על ידי הביטוי: (א ב ג ד ה ו) , איפה

א - הפצה של זרימת הקלט של יישומים;

ב - הפצה של זרימת הפלט של יישומים;

ג - תצורה של מנגנון השירות;

ד – משמעת בתור;

ה – בלוק המתנה;

ו הוא הקיבולת של המקור.

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

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

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

הגדרות מערכתמרמז על המספר הכולל של ערוצים וצמתי שירות. SMO עשוי להכיל:

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

לפיכך, ניתן להבחין בין QS חד ורב ערוצי.

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

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

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

1. PERPPO (כל הקודם זוכה) הוא הסוג הנפוץ ביותר;
2. POSPPO (כל הקודם זוכה);
3. SOP (בחירה אקראית של יישומים) - ממאגר הנתונים.
4. יחסי ציבור - שירות עדיפות.

אורך התוראולי

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

בלוק המתנה– "קיבולת" המערכת - סך כל האפליקציות במערכת (בתור ובשירות). בדרך זו, e=c+ד.

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

מספר דגמי QS מתאים למספר השילובים האפשריים של רכיבים אלו.

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

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

זרימת הבקשות נקראת יַצִיב, אם חוק ההפצה אינו תלוי בנקודה הראשונית של המרווח א, אך תלוי רק באורך המרווח הנתון ט. למשל, זרימת האפליקציות למרכזית הטלפון במהלך היום ( ט\u003d 24 שעות) לא יכול להיחשב נייח, אבל בין 13 ל 14 שעות ( ט\u003d 60 דקות) - אתה יכול.

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

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

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

משפט ראשי.אם הזרימה היא הפשוטה ביותר, אז ה-r.v. X [ א . + ט] מופץ לפי חוק Poisson, כלומר. .

מסקנה 1. הזרימה הפשוטה ביותר נקראת גם זרימת Poisson.

תוצאה 2. M(איקס)= M(איקס [ א , א + ט ] )= לט, כלומר בְּמַהֲלָך ט לטיישומים. לכן, ליחידת זמן אחת המערכת מקבלת בממוצע ליישומים. ערך זה נקרא עָצמָהזרם קלט.

שקול דוגמה .

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

פִּתָרוֹן.

לפי המשימה, ל=3, ט=2 ימים, זרם קלט Poisson, נ ³5. בעת פתרון, נוח להציג את האירוע ההפוך, המורכב מכך שבמהלך הזמן טיתקבלו פחות מ-5 בקשות. לכן, לפי נוסחת הפואסון, אנחנו מקבלים

^

3.3 מצב המערכת. מטריצה ​​וגרף של מעברים.

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

ה 0 - כל הערוצים בחינם;

ה 1 - ערוץ אחד תפוס;

ה נ- כל הערוצים תפוסים;

ה נ +1 - כל הערוצים תפוסים ובקשה אחת נמצאת בתור;

ה נ + M– כל הערוצים וכל המקומות בתור תפוסים.

מערכת דומה עם כשלים יכולה להיות במדינות ה 0 – ה נ .

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

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

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

איור 3.1 - גרף מעבר

Comp.	E 0	E 1	E 2
E 0	P 0.0	P 0.1	P 0.2
E 1	P 1.0	R 1.1	R 1.2
E 2	R 2.0	R 2.2	R 2.2

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

מאז המערכת תעבור בהכרח מאחד

מצב לאחר, אז סכום ההסתברויות בכל שורה תמיד שווה לאחד.

3.4 QS חד ערוץ.

3.4.1 QS חד ערוצי עם כשלים.

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

(P/E/1):(–/1/¥) . נניח גם שזמן השירות של לקוח אינו תלוי במספר הלקוחות הנכנסים למערכת. כאן ולמטה, "P" אומר שזרימת הקלט מופצת לפי חוק Poisson, כלומר. הפשוטה ביותר, "E" אומר שזרימת הפלט מופצת באופן אקספוננציאלי. גם כאן ולהלן, הנוסחאות העיקריות ניתנות ללא הוכחה.

עבור מערכת כזו, שני מצבים אפשריים: ה 0 - המערכת חינמית ו ה 1 - המערכת תפוסה. בואו ניצור מטריצת מעבר. בוא ניקח דטהוא כמות אינסופית של זמן. תן לאירוע א' להיות מורכב מהעובדה שבמערכת במהלך הזמן דטקיבל בקשה אחת. אירוע ב' מורכב מכך שבמהלך הזמן דטבקשה אחת הוגשה. מִקרֶה אבל אני , ק- במהלך דטהמערכת תעבור מהמדינה ה אנילתוך מדינה ה ק. כי להיא עוצמת זרימת הקלט, ואז במהלך הזמן דטנכנס למערכת בממוצע l*Dטדרישות. כלומר, ההסתברות לקבלת תביעה אחת P(A)=אני* דט, וההסתברות לאירוע ההפוך Р(А)=1-l*Dט.P(B)=ו(דט)= פ(ב< ד ט)=1- ה - M ד ט = M דט- ההסתברות למתן שירות לבקשה בזמן דט. לאחר מכן A 00 - הבקשה לא תתקבל או תתקבל אלא תוגש. A 00 \u003d Ā + A * V. R 00 \u003d 1 - l*Dט. (לקחנו את זה בחשבון (דט) 2 הוא ערך אינפיניטסימלי)

א 01 - הבקשה תתקבל אך לא תוגש. A 01 = A * . R 01 = l*Dט.

ו-10 - הבקשה תוגש ולא תהיה חדשה. A 10 \u003d B * א. R 10 = m*Dט.

ו-11 - הבקשה לא תוגש או שתגיע חדשה שטרם הוגשה. A 11 = +V * A. R 01 = 1- m*Dט.

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

Comp.	E 0	E 1
E 0	1-l * Dt	ל * Dt
E 1	M * Dt	1-מ' * Dt

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

הבה נמצא כעת את ההסתברות שהמערכת נמצאת במצב ה 0 בכל נקודת זמן ט(הָהֵן. ר 0 ( ט) ). גרף פונקציות
מוצג באיור 3.2.

האסימפטוטה של ​​הגרף היא קו ישר
.

ברור, מנקודה מסוימת ט,

1

איור 3.2

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

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

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

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

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

פִּתָרוֹן.לפי המשימה, ל=5, M y =5/6. אנחנו צריכים למצוא את ההסתברות ר 1 היא ההסתברות לכשל במערכת.
.

3.4.2 QS חד ערוצי עם אורך תור בלתי מוגבל.

נשקול מערכות שעומדות בדרישות: (Р/Е/1):(d/¥/¥). המערכת יכולה להיות באחת המדינות ה 0 , …, ה ק, ... הניתוח מראה כי לאחר זמן מה מערכת כזו מתחילה לפעול במצב נייח, אם עוצמת זרימת הפלט עולה על עוצמת זרימת הקלט (כלומר, מקדם העומס של המערכת קטן מאחד). בהתחשב בתנאי זה, אנו מקבלים את מערכת המשוואות

פתרון שאנו מוצאים ש. לפיכך, בתנאי ש y<1, получим
סוף כל סוף,
ו
היא ההסתברות שה-QS יהיה במדינה ה קבנקודת זמן אקראית.

מאפיינים ממוצעים של המערכת.

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

• נ – מספר הדרישות ב-QS (בתור ובשירות);
• v - אורך התור;
• w - זמן המתנה לתחילת השירות;
• w 0 הוא הזמן הכולל ששהה במערכת.

נתעניין מאפיינים ממוצעים(כלומר, אנחנו לוקחים את הציפייה המתמטית של המשתנים האקראיים הנחשבים, וזוכרים את זה y<1).

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

הוא אורך התור הממוצע.

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

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

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

פִּתָרוֹן. ל=5, M=60 דקות/10 דקות = 6. מקדם עומס y =5/6. לאחר מכן מספר המכוניות הממוצע במערכת
, אורך תור ממוצע
, זמן ההמתנה הממוצע לתחילת השירות
שעות = 50 דקות, ולבסוף זמן השהייה הממוצע במערכת
שָׁעָה.

3.4.3 QS חד ערוצי מסוג מעורב.

נניח שאורך התור הוא Mדרישות. ואז, לכל ס£ M, ההסתברות למצוא את ה-QS במדינה ה 1+ ס, מחושב לפי הנוסחה
, כלומר בקשה אחת מוגשת ואחרת סיישומים נמצאים בתור.

ההסתברות להשבתת מערכת היא
,

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

שלוש מערכות חד ערוציות ניתנות, עבור כל אחת ל=5, M =6. אבל המערכת הראשונה היא עם כשלים, השנייה היא עם המתנה טהורה, והשלישית היא עם אורך תור מוגבל, M=2. מצא והשווה את ההסתברויות לזמן השבתה של שלוש המערכות הללו.

פִּתָרוֹן.לכל המערכות מקדם עומס y=5/6. למערכת עם כשלים
. למערכת עם ציפייה טהורה
. למערכת עם אורך תור מוגבל
. המסקנה ברורה: ככל שיש יותר יישומים בתור, כך הסבירות להשבתת מערכת קטנה יותר.

3.5 QS רב ערוצי.

3.5.1 QS רב ערוצי עם כשלים.

נשקול מערכות (Р/Е/s):(-/s/¥) בהנחה שזמן השירות אינו תלוי בזרם הקלט וכל הקווים פועלים באופן עצמאי. ניתן לאפיין מערכות רב-ערוציות, בנוסף למקדם העומס, גם במקדם
, איפה ס– מספר ערוצי שירות. בחינת QS רב-ערוצית, אנו משיגים את הנוסחאות הבאות (נוסחאות Erlang) עבור ההסתברות שהמערכת תהיה במצב ה קבזמן אקראי:

, k=0, 1, …

פונקציית עלות.

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

כדי למצוא את האפשרות האופטימלית, עליך למצוא (ואפשר לעשות זאת) את הערך המינימלי של פונקציית העלות: מ(ס) = עם 1* ל * ע ס +c 2*, שהגרף שלו מוצג באיור 3.3:

איור 3.3

החיפוש אחר הערך המינימלי של פונקציית העלות הוא שאנו מוצאים את ערכיה תחילה ס =1, ואז עבור ס =2, ואז עבור ס =3 וכו'. עד שבשלב מסוים הערך של הפונקציה С( ס) לא יהיה גדול יותר מהקודם. זה אומר שהפונקציה הגיעה למינימום שלה והתחילה לגדול. התשובה היא מספר ערוצי השירות (ערך ס) שעבורו פונקציית העלות היא מינימלית.

דוגמא .

כמה קווי שירות צריכים להכיל QS עם כשלים, אם ל\u003d 2 ריב / שעה, M\u003d 1reb / ​​שעה, העונש על כל כישלון הוא 7,000 רובל, עלות השבתה עבור שורה אחת היא 2,000 רובל. תוך שעה?

פִּתָרוֹן. y = 2/1=2. עם 1 =7, עם 2 =2.

הבה נניח של-QS יש שני ערוצי שירות, כלומר. ס =2. לאחר מכן
. כתוצאה מכך, C(2) = ג 1 *ל*ע 2 +c 2 *(2- י*(עמוד אחד 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

בואו נעמיד פנים כך ס =3. לאחר מכן
, C(3) = ג 1 *ל*ע 3 +c 2 *
=5.79.

נניח שיש ארבעה ערוצים, כלומר. ס =4. לאחר מכן
,
, C(4) = ג 1 *ל*ע 4 +c 2 *
=5.71.

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

3.5.2 QS רב ערוצי עם תור.

נשקול מערכות (Р/Е/s):(d/d+s/¥) בהנחה שזמן השירות אינו תלוי בזרימת הקלט וכל הקווים פועלים באופן עצמאי. נאמר שהמערכת הותקנה פעולה נייחת, אם המספר הממוצע של תביעות נכנסות קטן ממספר התביעות הממוצע שהוגשו בכל קווי המערכת, כלומר. ל

P(w>0) האם ההסתברות להמתין לתחילת השירות,
.

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

דוגמא .

SMO - תחנת אמבולנס של מיקרו-מחוז קטן. ל=3 שיחות לשעה, ו M= 4 שיחות לשעה לצוות אחד. כמה צוותים חייבים להיות בתחנה כדי שהסבירות להמתין ליציאה תהיה פחות מ-0.01?

פִּתָרוֹן.גורם עומס מערכת y =0.75. נניח שיש שני צוותים זמינים. תן לנו למצוא את ההסתברות לחכות שהשירות יתחיל ב- ס =2.
,
.

נניח שיש שלוש חטיבות, כלומר. ס=3. לפי הנוסחאות, אנחנו מקבלים את זה ר 0 =8/17, P(w>0)=0.04>0.01 .

נניח שיש ארבעה צוותים בתחנה, כלומר. ס=4. ואז נקבל את זה ר 0 =416/881, P(w>0)=0.0077<0.01 . לכן צריכות להיות ארבע חטיבות בתחנה.

3.6 שאלות לשליטה עצמית

1. הנושא והמטלות של תורת העמידה בתור.
2. QS, הדגמים והייעודים שלהם.
3. זרם קלט דרישות. עוצמת זרם הקלט.
4. מצב המערכת. מטריצה ​​וגרף של מעברים.
5. QS חד ערוצי עם כשלים.
6. QS חד ערוצי עם תור. מאפיינים.
7. מצב פעולה נייח. גורם עומס מערכת.
8. QS רב ערוצי עם כשלים.
9. אופטימיזציה של פונקציית עלות.
10. QS רב ערוצי עם תור. מאפיינים.

3.7 תרגילים לעבודה עצמאית

1. למזנון בתחנת הדלק יש דלפק אחד. מכוניות מגיעות לפי חלוקת Poisson, עם ממוצע של 2 מכוניות ל-5 דקות. בממוצע, 1.5 דקות מספיקות להשלמת הזמנה, אם כי משך השירות מחולק על פי חוק אקספוננציאלי. מצא: א) את ההסתברות שהדוכן יהיה סרק; ב) ביצועים ממוצעים; ג) ההסתברות שמספר המכוניות המגיעות יהיה לפחות 10.
2. מכשיר רנטגן מאפשר לך לבדוק בממוצע 7 אנשים בשעה. עוצמת המבקרים היא 5 אנשים בשעה. בהנחה של פעולה נייחת, קבע את המאפיינים הממוצעים.
3. זמן השירות ב-QS מציית לחוק אקספוננציאלי,
   M = 7 דרישות לשעה. מצא את ההסתברות שא) זמן השירות הוא בין 3 ל-30 דקות; ב) התביעה תוגש תוך שעה. השתמש בטבלת ערכי פונקציות ה איקס .
4. ישנו עגינה אחד בנמל הנהר, עוצמת זרימת הקלט היא 5 כלי שיט ביום. עוצמת פעולות ההעמסה והפריקה היא 6 ספינות ביום. תוך התחשבות במצב הפעולה הנייח, קבע את כל המאפיינים הממוצעים של המערכת.
5. ל=3, M=2, העונש על כל תקלה הוא 5, ועלות ההשבתה לשורה היא 2?
6. מהו המספר האופטימלי של ערוצי שירות ש-QS צריך להיות אם ל=3, M =1, העונש על כל תקלה הוא 7, ועלות ההשבתה לשורה היא 3?
7. מהו המספר האופטימלי של ערוצי שירות ש-QS צריך להיות אם ל=4, M=2, העונש על כל תקלה הוא 5, ועלות ההשבתה לשורה היא 1?
8. קבע את מספר מסלולי ההמראה למטוסים, בכפוף לדרישה שהסתברות להמתנה חייבת להיות קטנה מ-0.05. יחד עם זאת, עוצמת זרימת הקלט היא 27 מטוסים ביום, ועוצמת השירות שלהם היא 30 מטוסים ביום.
9. כמה קווי מסוע עצמאיים שוות ערך צריכה להיות לבית מלאכה כדי להבטיח את קצב העבודה, שבהם ההסתברות להמתנה לעיבוד המוצרים חייבת להיות פחות מ-0.03 (כל מוצר מיוצר על ידי קו אחד). ידוע כי עוצמת קבלת ההזמנות היא 30 מוצרים בשעה, ועוצמת עיבוד מוצר בקו אחד היא 36 מוצרים לשעה.
10. משתנה אקראי רציף X מופץ לפי חוק מעריכי עם הפרמטר l=5. מצא את פונקציית ההתפלגות, המאפיינים וההסתברות לפגיעה ב-r.v. X בטווח שבין 0.17 ל-0.28.
11. המספר הממוצע של שיחות המגיעות למרכזייה בדקה אחת הוא 3. בהנחה שהזרימה היא Poisson, מצא את ההסתברות שתוך 2 דקות יהיו: א) שתי שיחות; ב) פחות משתי שיחות; ג) לפחות שתי שיחות.
12. יש 17 חלקים בקופסה, מתוכם 4 פגומים. ההרכב מצייר 5 חלקים באקראי. מצא את ההסתברות שא) כל החלקים שחולצו הם באיכות גבוהה; ב) בין החלקים שחולצו 3 פגומים.
13. כמה ערוצים צריכים להיות ל-QS עם כשלים אם ל\u003d 2 ריב / שעה, M\u003d 1reb / ​​שעה, העונש על כל כישלון הוא 8,000 רובל, עלות השבתה עבור שורה אחת היא 2,000 רובל. תוך שעה?