עבודה בקורס

"סימולציה של המערכת הִזדַנְבוּת»

בקורס "מחקר מבצעים"

מבוא

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

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

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

– מוחלט תפוקהמערכות ( א

ש

- ההסתברות לסירוב למתן שירות לבקשה ();

ק);

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

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

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

1. מאפיינים עיקריים של CMO ואינדיקטורים ליעילותם

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

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

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

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

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

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

זרם של אירועים הוא רצף של אירועים הומוגניים הבאים בזה אחר זה בזמנים אקראיים.

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

זרם של אירועים נקרא קבוע אם אירועים עוקבים בזה אחר זה במרווחי זמן קבועים.

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

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

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

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

1.2 משוואות קולמוגורוב

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

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

לדוגמה, עבור גרף המדינה המוצג באיור. 1, למשוואות קולמוגורוב יש את הצורה:

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

,

,

לכן, אחת מהמשוואות של המערכת ניתן לבטל ולהחליף במשוואה (1.2.1).

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

1.3 הסתברויות סופיות וגרף מצב של QS

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

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

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

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

אורז. 2. גרף של מצבים במודלים של QS

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

המערכת מתקבלת מ ( נ +1) משוואה, שנפתרת בשיטת האלימינציה. שיטה זו מורכבת מכך שכל ההסתברויות של המערכת מתבטאות ברציפות באמצעות ההסתברות.

,

.

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

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

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

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

הוא התפוקה היחסית ( ש), כלומר. החלק הממוצע של הבקשות שהתקבלו בשירות המערכת;

היא ההסתברות לכישלון (), כלומר. ההסתברות שהאפליקציה תשאיר את ה-QS ללא הגשה;

הוא המספר הממוצע של ערוצים עסוקים ( ק);

- המספר הממוצע של יישומים ב-QS ();

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

- המספר הממוצע של יישומים בתור () - אורך התור;

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

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

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

– מידת טעינת הערוץ (), כלומר. ההסתברות שהערוץ תפוס;

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

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

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

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

(1.4.1)

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

נוסחאות לחישוב מדדי ביצועים ניתנות בטבלה. 1.

שולחן 1.

אינדיקטורים	QS חד ערוצי עם תור מוגבל	QS רב ערוצי עם תור מוגבל
סופי הסתברויות
הִסתַבְּרוּת
תפוקה מוחלטת יְכוֹלֶת
תפוקה יחסית יְכוֹלֶת
מספר פניות ממוצע לכל
מספר ממוצע של בקשות מתחת שֵׁרוּת
מספר יישומים ממוצע במערכת

1.5 מושגי יסוד של סימולציה

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

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

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

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

תן להיות מימוש של משתנה אקראי , מופץ באופן אחיד על המרווח , ותן להיות מימוש זמן השירות האקראי של בקשה אחת המתאימה לו. לאחר מכן, לפי (1.5.1)

1.6 בניית דגמי סימולציה

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

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

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

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

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

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

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

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

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

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

, , כלומר , איפה

שונות מתוקנת, ,

נ- מספר ריצות תוכנית, - אמינות, .

2. מידול אנליטי של QS

2.1 גרף מצב של המערכת ומשוואת קולמוגורוב

שקול מערכת תורים דו-ערוצית (n=2) עם תור מוגבל השווה לשישה (m=4). ה-QS מקבל את הזרימה הפשוטה ביותר של יישומים עם עוצמה ממוצעת λ = 4.8 וחוק אקספוננציאלי של התפלגות זמן בין הגעת יישומים. זרימת הבקשות המוגשות במערכת היא הפשוטה ביותר עם עוצמה ממוצעת μ = 2 וחוק אקספוננציאלי של חלוקת זמן השירות.

למערכת זו 7 מצבים, אנו מציינים אותם:

S 0 - המערכת חינמית, אין בקשות;

S 1 - 1 בקשת שירות, התור ריק;

S 2 - 2 בקשות לשירות, התור ריק;

S 3 - 2 בקשות לשירות, בקשה אחת בתור;

S 4 - 2 בקשות לשירות, 2 בקשות בתור;

S 5 - 2 בקשות לשירות, 3 בקשות בתור;

S 6 - 2 בקשות לשירות, 4 בקשות בתור;

ההסתברויות של המערכת להיכנס למצבים S 0 , S 1 , S 2 , …, S 6 שוות בהתאמה ל- Р 0 , Р 1 , Р 2 , …, Р 6 .

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

אורז. 3. גרף של מצבים של QS דו-ערוצי

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

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

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

שיטת אוילר

איפה - במקרה שלנו, אלו הם החלקים הנכונים של משוואות קולמוגורוב, n=6.

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

הערכים של הסתברויות QS ב- שווים ל:

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

P0

P5

P4

P3

P2

P1

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

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

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

בואו נפתור את המערכת הזו משוואות ליניאריותבאמצעות חבילת התוכנה מייפל 11 (ראה נספח 1).

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

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

הָהֵן. קטן מספיק. זה מאשר את נכונות התוצאות שהתקבלו.

2.3 חישוב מדדי ביצועי המערכת לפי הסתברויות סופיות

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

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

1) ההסתברות לסירוב למתן שירות לבקשה, כלומר. ההסתברות שהלקוח יעזוב את המערכת ללא שירות. במקרה שלנו, הלקוח נמנע משירות אם כל 2 הערוצים תפוסים והתור מלא במקסימום (כלומר 4 אנשים בתור), זה מתאים למצב של המערכת S 6 . כי ההסתברות שהמערכת תיכנס למצב S 6 היא P 6, אם כן

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

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

3. דוגמנות סימולציה של QS

3.1 אלגוריתם של שיטת הדמיית QS (גישה צעד אחר צעד)

שקול מערכת תורים דו-ערוצים (n=2) עם אורך תור מקסימלי של שישה (m=4). ה-QS מקבל את הזרימה הפשוטה ביותר של יישומים עם עוצמה ממוצעת λ = 4.8 וחוק אקספוננציאלי של התפלגות זמן בין הגעת יישומים. זרימת הבקשות המוגשות במערכת היא הפשוטה ביותר עם עוצמה ממוצעת μ = 2 וחוק אקספוננציאלי של חלוקת זמן השירות.

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

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

איפה (3.1.1)

בהתבסס על תנאי (3.1.1), אנו קובעים את שלב הזמן .

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

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

זה נעשה בתוכנית מבוקש () . ניקח את מרווח הזמן הקבוע ושווה ל-0.0001, אז היחס יהיה שווה ל-10000. אם הבקשה מתקבלת, אז היא לוקחת את הערך "true", אחרת הערך הוא "false".

bool isRequested()

double r = R.NextDouble();

אם (ר< (timeStep * lambda))

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

כפול GetServiceTime()

double r = R.NextDouble();

return(-1/mu*Math. Log(1-r, Math.E));

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

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

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

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

3.2 תרשים זרימה של התוכנית

דיאגרמת הבלוק של התוכנית המיישמת את האלגוריתם המתואר מוצג באיור. 5.

אורז. 5. תרשים זרימה של התוכנית

בואו נכתוב כמה בלוקים ביתר פירוט.

בלוק 1. הגדרת הערכים ההתחלתיים של הפרמטרים.

אקראי ר; // מחולל מספר אקראי

public uint maxQueueLength; // אורך תור מקסימלי

public unit channelCount; // מספר ערוצים במערכת

למבדה זוגית ציבורית; // עוצמת זרימת הבקשות הנכנסות

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

זמן כפול ציבורי; // שלב זמן

public timeOfFinishProcessingReq כפול; // שעת הסיום של שירות הבקשה בכל הערוצים

זמן כפול ציבורי בתור; // זמן השהות של ה-QS במדינות עם תור

זמן עיבוד כפול ציבורי; // זמן ריצת המערכת

ציבורי כפול totalProcessingTime; // זמן כולל לבקשות שירות

public uint requestEntryCount; // מספר הבקשות שהתקבלו

public uint declinedRequestCount; // מספר הבקשות שנדחו

public uint acceptedRequestCount; // מספר הבקשות שהוגשו

uint queueLength; // אורך התור //

סוג המתאר מצבי QS

enum SysCondition(S0, S1, S2, S3, S4, S5, S6);

SysCondition currentSystemCondition; // המצב הנוכחי של המערכת

הגדרת מצבי מערכת.בואו נפרט 7 מצבים שונים עבור מערכת 2 ערוצים זו: S 0 , S 1 . S 6 . QS נמצא במצב S 0 כאשר המערכת פנויה; S 1 - ערוץ אחד לפחות בחינם; במצב S 2 כאשר כל הערוצים תפוסים ויש מקום בתור; במצב S 6, כל הערוצים תפוסים והתור הגיע לאורך המקסימלי (queueLength = 4).

אנו קובעים את המצב הנוכחי של המערכת באמצעות הפונקציה GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

עבור (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

(p_currentCondit++;)

החזר p_currentCondit + (int) QueueLength;

שינוי בזמן השהייה של QS במדינות עם אורך תור של 1, 2,3,4.זה מיושם על ידי הקוד הבא:

if (אורך תור > 0)

timeInQueue += timeStep;

if (אורך תור > 1)

(timeInQueue += timeStep;)

ישנה פעולה כמו הצבת בקשת שירות בערוץ חינמי. כל הערוצים נסרקים, החל מהראשון, כאשר מתקיים התנאי timeOfFinishProcessingReq [ אני ] <= 0 (הערוץ חינמי), מוגשת אליו בקשה, כלומר. מופקת שעת הסיום למתן שירות לבקשה.

עבור (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i]<= 0)

timeOfFinishProcessingReq[i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq[i];

שירות יישומים בערוצים מעוצב על ידי הקוד:

עבור (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

timeOfFinishProcessingReq[i] -= timeStep;

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

3.3 חישוב מדדי ביצועים של QS מבוססים על תוצאות הסימולציה שלו

האינדיקטורים החשובים ביותר הם:

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

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

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

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

5) הזמן הממוצע שאפליקציה מבלה בתור נקבע על פי הנוסחה של ליטל

6) המספר הממוצע של ערוצים תפוסים מוגדר כדלקמן:

7) אחוז הבקשות שסורבו בשירות נמצא לפי הנוסחה

8) אחוז הבקשות המטופלות נמצא לפי הנוסחה

3.4 עיבוד סטטיסטי של תוצאות והשוואתם לתוצאות של מידול אנליטי

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

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

, איפה

תוחלת מתמטית (ערך ממוצע), נמצאת על ידי הנוסחה

שונות מתוקנת,

,

נ =20 - מספר ריצות

- מהימנות. ב ו נ =20 .

התוצאה של התוכנית מוצגת באיור. 6.

אורז. 6. סוג התוכנית

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

שולחן 2.

אינדיקטורים יעילות QS	תוצאות אנליטיים דוּגמָנוּת	תוצאות דוגמנות סימולציה (שלב אחרון)	תוצאות סימולציה
			שורה תחתונה נאמנות הַפסָקָה	גבול עליון נאמנות הַפסָקָה
הסתברות כישלון		0,174698253017626	0,158495148639101	0,246483801571923
רוחב פס יחסי		0,825301746982374	0,753516198428077	0,841504851360899
רוחב פס מוחלט		3,96144838551539	3,61687775245477	4,03922328653232
אורך תור ממוצע		1,68655313447018	1,62655862750852	2,10148609204869
הזמן הממוצע שאפליקציה מבלה בתור	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
ערוצים תפוסים ממוצעים		1,9807241927577	1,80843887622738	2,01961164326616

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

סיכום

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

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

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

התוצאות המתקבלות במהלך דוגמנות סימולציה תואמות את התוצאות של דוגמנות אנליטית.

סִפְרוּת

1. Wentzel E.S. חקר תפעול. – M.: Bustard, 2004. – 208 p.

2. Volkov I.K., Zagoruiko E.A. חקר תפעול. - M .: הוצאה לאור של MSTU im. נ.ע. באומן, 2002. - 435 עמ'.

3. Volkov I.K., Zuev S.M., Tsvetkova G.M. תהליכים אקראיים. - M .: הוצאה לאור של MSTU im. נ.ע. באומן, 2000. - 447 עמ'.

4. גמורמן V.E. מדריך לפתרון בעיות בתורת ההסתברות ובסטטיסטיקה מתמטית. - מ.: בית ספר תיכון, 1979. - 400 עמ'.

5. איבניצקי ו.ל. תיאוריה של רשתות בתור. – מ.: פיזמטלית, 2004. – 772 עמ'.

6. פעולות מחקר במשק / עורך. נ.ש. קרמר. - מ.: אחדות, 2004. - 407 עמ'.

7. טכא ח.א. מבוא לחקר תפעול. - מ.: הוצאה לאור "וויליאמס", 2005. - 902 עמ'.

8. Kharin Yu.S., Malyugin V.I., Kirlitsa V.P. וחב' יסודות סימולציה ומידול סטטיסטי. - Minsk: Design PRO, 1997. - 288 עמ'.

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

במודלים של QS, האובייקטים הבאים נחשבים:

1) בקשות שירות (עסקאות);

2) התקני שירות (OA), או התקנים.

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

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

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

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

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

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

פרמטרי הפלט החשובים ביותר של ה-QS

ביצועים

רוחב פס

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

זמן שירות ממוצע;

מקדם עומס ציוד (OA).

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

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

דגמי QS הפשוטים ביותר

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

M o d e l o n s e r e n t e r e s s e n c a t i o n (איור 5.1)

אורז. 5.1. דגם QS עם כשלים:

0 - מקור בקשה;

1 - מכשיר שירות;

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

Vהוא זרם הפלט של בקשות שירות;

עםהוא זרם הפלט של בקשות שלא הוגשו.

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

מודלים ותכנים (איור 5.2)

אורז. 5.2. דגם QS עם ציפייה

(N– 1) - מספר האפליקציות שיכולות להתאים למצבר

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

מודל שירות לזמן מוגבל

w i d a n y (איור 5.3)

אורז. 5.4. מודל QS רב ערוצי עם כשלים:

נ- מספר התקני השירות (התקנים) זהים

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

עם זה (איור 5.5)

אורז. 5.6. דגם QS רב ערוצי עם OA המתנה ושחזור:

ה- מכשירי שירות שאינם תקינים;

ו– רכבי שירות משוחזרים

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

M i n o n a l m o l l Q O

OA זמן המתנה והתאוששות (איור 5.7)

אורז. 5.7. דגם QS רב ערוצי עם זמן המתנה מוגבל ושחזור OA

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

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

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

כל SMO כולל ארבעה אלמנטים: זרם נכנס, תור, שרת, זרם יוצא.

דְרִישָׁה(לקוח, אפליקציה) ב-QS היא כל בקשה פרטנית לביצוע כל עבודה.

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

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

SMOs מסווגים לפי קריטריונים שונים..

1. לפי מספר ערוצי השירות, QS מחולקים לערוץ חד-ערוצי ורב-ערוצי.

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

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

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

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

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

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

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

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

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

ניתן לטפל בבקשות לפי סדר קבלתן, באופן אקראי או על סמך סדרי עדיפויות שנקבעו.

4. QS יכול להיות חד פאזי ורב פאזי.

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

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

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

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

שיטות ומודלים ללימוד QS ניתנים לחלוקה מותנית לניתוח וסטטיסטי (סימולציה של מודלים של תהליכי תור).

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

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

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

עבור הזרימה הפשוטה ביותר, תדירות קבלת הדרישות למערכת מצייתת לחוק Poisson, כלומר, ההסתברות להגיע בזמן t שווה ל-k דרישות ניתנת על ידי הנוסחה:

כאשר λ הוא פרמטר הזרימה (ראה להלן).

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

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

יַצִיבשקוראים לו זְרִימָה, שעבורו הציפייה המתמטית למספר התביעות הנכנסות למערכת ליחידת זמן (מסומן ב-λ) אינה משתנה בזמן. לפיכך, ההסתברות של מספר מסוים של תביעות להיכנס למערכת במהלך מרווח זמן נתון Δt תלויה בערכו ואינה תלויה במקורו בציר הזמן.

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

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

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

F(t) \u003d 1 - e -μt,

הָהֵן. ההסתברות שזמן השירות לא יעלה על ערך מסוים t נקבעת על ידי הנוסחה (1 - e -μt), כאשר μ הוא הפרמטר של החוק האקספוננציאלי של זמן השירות של הדרישות במערכת - ההדדיות של הממוצע זמן שירות, כלומר. .

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

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

הצהרת הבעיה הכללית היא כדלקמן.

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

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

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

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

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

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

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

1. ההסתברות שיש k דרישות במערכת, בתנאי שמספרן לא יעלה על מספר התקני השירות n:

P k = α k P 0 , (1 ≤ k ≤ n),

איפה

λ הוא התדירות (העוצמה) של קבלת דרישות למערכת ממקור אחד;

משך השירות הממוצע של דרישה אחת;

m - המספר הגדול ביותר האפשרי של דרישות שנמצאות במערכת ההגשה בו זמנית;

n הוא מספר התקני השירות;

P 0 - ההסתברות שכל מכשירי השירות פנויים.

2. ההסתברות שיש k דרישות במערכת, בתנאי שמספרן גדול ממספר התקני השירות:

P k = α k P 0 , (n ≤ k ≤ m),

איפה

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

לָכֵן,

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

5. יחס זמן השבתה דרישה בהמתנה לשירות:

6. ההסתברות שכל מכשירי השירות תפוסים:

7. מספר הדרישות הממוצע במערכת השירות (מוגשת וממתינה לשירות):

8. היחס בין זמן ההשבתה הכולל של דרישות שירות והמתנה לשירות:

9. זמן סרק ממוצע של תביעה בתור שירות:

10. מספר ממוצע של משתתפים בחינם:

11. יחס זמני השבתה של רכבי שירות:

12. ההסתברות שמספר הלקוחות הממתינים לשירות גדול ממספר B כלשהו (ההסתברות שיש יותר מ-B לקוחות בתור השירות):

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

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

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

אורז. 6.2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 באוקטובר 2013 בשעה 02:22

Squeak: Modeling Queuing Systems

• תִכנוּת,
• אוף,
• תכנות מקביל

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

כמה מילים על סקוויק

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

<объект> <сообщение>

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

מערכות תורים

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

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

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

קצת מתמטיקה

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

זְמַן טבין שני אירועים λ(t) = const = λמופץ על פי חוק:
צפיפות התפלגות של משתנה אקראי טנראה כמו:
להשיג רצפי פואסון פסאודו אקראיים של מרווחי זמן אניפתור את המשוואה:
איפה אניהוא מספר אקראי המחולק באופן אחיד על פני המרווח.
במקרה שלנו זה נותן את הביטוי:

על ידי יצירת מספרים אקראיים, אתה יכול לכתוב כרכים שלמים. כאן, כדי ליצור מספרים שלמים המחולקים באופן אחיד על פני המרווח, אנו משתמשים באלגוריתם הבא:
איפה ר i- עוד מספר שלם אקראי;
ר- מספר ראשוני גדול כלשהו (למשל 2311);
ש- מספר שלם - הגבול העליון של המרווח, לדוגמה, 2 21 = 2097152;
rem- פעולת השגת השארית מחלוקת המספרים השלמים.

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

שיעור רנד

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

Float variableWordSubclass: #Rand "שם מחלקה" instanceVariableNames: "" "משתני מופע" classVariableNames: "R" "משתני מחלקה" poolDictionaries: "" "מילונים נפוצים" קטגוריה: "לדוגמה" "שם קטגוריה"
שיטות:

"אתחול" init R:= Time totalSeconds.next "המספר הפסאודו-אקראי הבא" הבא R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
כדי להגדיר את המצב ההתחלתי של החיישן, שלח הודעה ראנד איניט.
כדי לקבל עוד מספר אקראי, שלח רנד הבא.

תוכנית לעיבוד בקשות

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

קוד חריקת

"הכרזה על משתנים זמניים" | proc1 proc2 t1 t2 s1 s2 sysPriority תור המשך r | "הגדרות משתנה ראשוניות" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. להמשיך:=נכון. sysPriority:= מעבד פעיל עדיפות תהליך. תור "עדיפות נוכחית": = סמפור חדש. "מודל תור תביעה" "יצירת תהליך - דגם ערוץ 1" s1:= s1 + 1. proc1 suspend."השעיית תהליך בהמתנה לסיום שירות" ].proc1:= nil."הסר הפניה לתהליך 1" ]priority: (sysPriority + 1)) קורות חיים. "עדיפות חדשה גדולה מהרקע" "יצירת תהליך - מודל ערוץ 2" .proc2:= אפס.] עדיפות: (sysPriority + 1)) חידוש. "תיאור המשך של התהליך הראשי ומודל המקור" בעוד אמת: [ r:= (Rand next * 10) מעוגל. (r = 0) ifTrue: . ((SysTime rem: r) = 0) ifTrue: . "שלח בקשה" "מתג תהליך שירות" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "זמן הדגם מתקתק" ]. "הצג את מצב מונה הבקשות" PopUpMenu inform: "proc1: ",(s1 printString),", proc2: ",(s2 printString). להמשיך:= שקר.

בעת ההפעלה, אנו רואים שתהליך 1 הצליח לעבד 31 בקשות, ותהליך 2 רק 11: