Додому Гігієна Основні поняття систем масового обслуговування. СМО з очікуванням (чергою)

Гігієна

Основні поняття систем масового обслуговування. СМО з очікуванням (чергою)

2.2 Багатоканальна СМО з очікуванням

Система з обмеженою довжиною черги. Розглянемо канальну СМО з очікуванням, яку надходить потік заявок з інтенсивністю ; інтенсивність обслуговування (для одного каналу); кількість місць у черзі.

Стан системи нумерується за кількістю заявок, пов'язаних системою:

немає черги:

Усі канали вільні;

Зайнятий один канал, інші вільні;

Зайняті-каналів, решта немає;

Зайняті всі каналів, вільних немає;

є черга:

Зайняті всі n-каналів; одна заявка стоїть у черзі;

Зайняті всі n-каналів, r-заявок у черзі;

Зайняті всі n-каналів, r-заявок у черзі.

ДСП наведено на рис. 17. У кожної стрілки проставлено відповідні інтенсивності потоків подій. За стрілками зліва направо систему переводить завжди той самий потік заявок з інтенсивністю , по стрілках праворуч наліво систему переводить потік обслуговування, інтенсивність якого дорівнює , помноженому на кількість зайнятих каналів.

Мал. 17. Багатоканальна СМО з очікуванням

Граф типовий для процесів розмноження та загибелі, на яку рішення раніше отримано. Напишемо вирази для граничних ймовірностей станів, використовуючи позначення : (тут використовується вираз для суми геометричній прогресіїзі знаменником).

Отже, всі ймовірності станів знайдено.

Визначимо показники ефективності системи.

Ймовірність відмови. Заявка, що надійшла, отримує відмову, якщо зайняті всі n-каналів і всі m-місць у черзі:

(18)

Відносна пропускна здатність доповнює можливість відмови до одиниці:

Абсолютна пропускна здатність СМО:

(19)

Середня кількість зайнятих каналів. Для СМО з відмовами воно збігалося із середнім числом заявок, що у системі. Для СМО із чергою середня кількість зайнятих каналів не збігається із середнім числом заявок, що знаходяться в системі: остання величина відрізняється від першої на середню кількість заявок, що перебувають у черзі.

Позначимо середню кількість зайнятих каналів. Кожен зайнятий канал обслуговує в середньому -заявок в одиницю часу, а СМО в цілому обслуговує в середньому А-заявок в одиницю часу. Розділивши одне на інше, отримаємо:

Середню кількість заявок у черзі можна обчислити безпосередньо як математичне очікування дискретної випадкової величини:

(20)

Тут знову (вираз у дужках) зустрічається похідна суми геометричної прогресії (див. вище (11), (12) - (14)), використовуючи співвідношення для неї, отримуємо:

Середня кількість заявок у системі:

Середній час очікування заявки у черзі. Розглянемо ряд ситуацій, що відрізняються тим, у якому стані застане систему знову прийшла заявка і скільки часу їй доведеться чекати на обслуговування.

Якщо заявка застане не всі канали зайнятими, їй взагалі не доведеться чекати (відповідні члени математичному очікуваннірівні нулю). Якщо заявка прийде в момент, коли зайняті всі n-каналів, а черги немає, їй доведеться чекати в середньому час, рівний (бо «потік звільнень»-каналів має інтенсивність). Якщо заявка застане всі канали зайнятими і одну заявку перед собою в черзі, їй доведеться в середньому чекати протягом часу (по кожну попереду заявку, що стоїть) і т. д. Якщо заявка застане в черзі -заявок, їй доведеться чекати в середньому протягом часу. Якщо заявка, що знову прийшла, застане в черзі вже m-заявок, то вона взагалі не чекатиме (але й не буде обслужена). Середній час очікування знайдемо, помножуючи кожне із цих значень на відповідні ймовірності:

(21)

Так само, як і у випадку одноканальної СМО з очікуванням, відзначимо, що цей вираз відрізняється від виразу для середньої довжини черги (20) лише множником , тобто.

Середній час перебування заявки в системі, як і для одноканальної СМО, відрізняється від середнього часу очікування на середній час обслуговування, помножений на відносну пропускну здатність:

Системи із необмеженою довжиною черги. Ми розглянули канальну СМО з очікуванням, коли в черзі одночасно можуть бути не більше m-заявок.

Також, як і раніше, при аналізі систем без обмежень необхідно розглянути отримані співвідношення при .

Імовірність станів отримаємо з формул граничним переходом (при ). Зауважимо, що сума відповідної геометричної прогресії сходить при і розходиться при >1. Припустивши, що<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Імовірність відмови, відносна та абсолютна пропускна спроможність. Оскільки кожна заявка рано чи пізно буде обслужена, характеристики пропускної спроможності СМО складуть:

Середню кількість заявок у черзі отримаємо при (20):

а середній час очікування – з (21):

Середня кількість зайнятих каналів, як і раніше, визначається через абсолютну пропускну здатність:

Середня кількість заявок, пов'язаних із СМО, визначається як середня кількість заявок у черзі плюс середня кількість заявок, що знаходяться під обслуговуванням (середня кількість зайнятих каналів):

Приклад 2. Автозаправна станція із двома колонками (n = 2) обслуговує потік машин з інтенсивністю =0,8 (машин на хвилину). Середній час обслуговування однієї машини:

У даному районі немає іншої АЗС, тож черга машин перед АЗС може рости практично необмежено. Знайти властивості СМО.

Оскільки<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

і т.д.

Середня кількість зайнятих каналів знайдемо, розділивши абсолютну пропускну здатність СМО А==0,8 на інтенсивність обслуговування =0,5:

Імовірність відсутності черги біля АЗС буде:

Середня кількість машин у черзі:

Середня кількість машин на АЗС:

Середній час очікування у черзі:

Середній час перебування машини на АЗС:

СМО з обмеженим часом очікування. Раніше розглядалися системи з очікуванням, обмеженим лише довжиною черги (числом m-заявок, що одночасно перебувають у черзі). У такій СМО заявка, що розростала в чергу, не залишає її, доки не дочекається обслуговування. Насправді зустрічаються СМО іншого типу, у яких заявка, почекавши деякий час, може піти з черги (так звані «нетерплячі» заявки).

Розглянемо СМО такого типу, припускаючи, що обмеження часу очікування є випадковою величиною.

Припустимо, що є n-канальна СМО з очікуванням, в якій кількість місць у черзі не обмежена, але час перебування заявки в черзі є деякою випадковою величиною із середнім значенням, таким чином, на кожну заявку, яка стоїть у черзі, діє свого роду пуасонівський. потік доглядів» з інтенсивністю:

Якщо цей пуасонівський потік, то процес, що протікає в СМО, буде марківським. Знайдемо йому ймовірності станів. Нумерація станів системи пов'язується з кількістю заявок у системі - як обслуговуваних, так і стоять у черзі:

немає черги:

Усі канали вільні;

Зайнятий один канал;

Зайнято два канали;

Зайняті всі n-каналів;

є черга:

Зайняті всі n-каналів, одна заявка стоїть у черзі;

Зайняті всі n-каналів, r-заявок стоять у черзі тощо.

Граф станів та переходів системи показаний на рис. 23.

Мал. 23. СМО з обмеженим часом очікування

Розмітимо цей граф, як і раніше; у всіх стрілок, що ведуть зліва направо, стоятиме інтенсивність потоку заявок. Для станів без черги у стрілок, що ведуть з них справа наліво, буде, як і раніше, стояти сумарна інтенсивність потоку обслуговування всіх зайнятих каналів. Що стосується станів з чергою, то у стрілок, що ведуть з них справа наліво, стоятиме сумарна інтенсивність потоку обслуговування всіх n-каналів плюс відповідна інтенсивність потоку відходів з черги. Якщо в черзі стоять r-заявок, то сумарна інтенсивність потоку догляду дорівнюватиме .

Як видно з графа, має місце схема розмноження та загибелі; застосовуючи загальні вирази для граничних ймовірностей станів у цій схемі (використовуючи скорочені позначення, запишемо:

(24)

Зазначимо деякі особливості СМО з обмеженим очікуванням порівняно з раніше розглянутими СМО з «терплячими» заявками.

Якщо довжина черги не обмежена і заявки «терплячі» (не йдуть з черги), то стаціонарний граничний режим існує лише у разі (при відповідній нескінченній геометричній прогресії розходиться, що фізично відповідає необмеженому зростанню черги при ).

Навпаки, в СМО з «нетерплячими» заявками, що йдуть рано чи пізно з черги, режим обслуговування, що встановився, досягається завжди, незалежно від наведеної інтенсивності потоку заявок . Це випливає з того, що ряд для знаменника формули (24) сходиться при будь-яких позитивних значеннях і .

Для СМО з «нетерплячими» заявками поняття «імовірність відмови» не має сенсу – кожна заявка стає в чергу, але може і не дочекатися обслуговування, пішовши раніше.

Відносна пропускна спроможність, середня кількість заявок у черзі. Відносну пропускну здатність q такий СМО можна підрахувати в такий спосіб. Очевидно, обслуговуватимуться всі заявки, окрім тих, які підуть із черги достроково. Підрахуємо, яка в середньому кількість заявок залишає чергу достроково. Для цього обчислимо середню кількість заявок у черзі:

На кожну з цих заявок діє «потік догляду» з інтенсивністю. Значить, із середнього числа -заявок у черзі в середньому йтиме, не дочекавшись обслуговування, -заявок в одиницю часу і всього в одиницю часу в середньому обслуговуватиметься -заявок. Відносна пропускна здатність СМО складатиме:

Середню кількість зайнятих каналів, як і раніше, отримуємо, ділячи абсолютну пропускну здатність А на :

(26)

Середня кількість заявок у черзі. Співвідношення (26) дозволяє обчислити середню кількість заявок у черзі, не підсумовуючи нескінченного ряду (25). З (26) отримуємо:

а середнє число зайнятих каналів, що входить у цю формулу, можна знайти як математичне очікування випадкової величини Z, що приймає значення 0, 1, 2,..., n з ймовірностями ,:

На закінчення зауважимо, що якщо у формулах (24) перейти до межі при (або, що те саме, при ), то при

Черга довжини k, залишається в ній з ймовірністю Pk і не приєднується до черги з ймовірністю gk=1 - Pk,". саме так зазвичай поводяться люди в чергах. величиною (ємність бункера, наприклад), очевидно, це окремий випадок загальної постановки.

У цьому вся параграфі ми розглянемо деякі найпростіші СМО і виведемо висловлювання їх характеристик (показників ефективності). У цьому ми продемонструємо основні методичні прийоми, характерні елементарної, «марківської» теорії масового обслуговування. Ми не гнатимемося за кількістю зразків СМО, для яких будуть виведені кінцеві вирази характеристик; дана книга - не довідник з теорії масового обслуговування (таку роль краще виконують спеціальні керівництва). Наша мета - познайомити читача з деякими «маленькими хитрощами», що полегшують шлях крізь теорію масового обслуговування, яка в низці наявних (навіть претендує на популярність) книг може здатися нескладним набором прикладів.

Всі потоки подій, що переводять СМО зі стану в стан, в даному параграфі ми вважатимемо найпростішими (не обговорюючи це щоразу спеціально). Серед них буде і так званий «потік обслуговувань». Під ним розуміється потік заявок, що обслуговуються одним безперервно зайнятим каналом.

У цьому потоці інтервал між подіями, як і завжди в найпростішому потоці, має показовий розподіл (у багатьох посібниках натомість кажуть: «час обслуговування – показовий», ми й самі надалі користуватимемося таким терміном). У цьому параграфі показовий розподіл часу обслуговування буде зрозуміло, як завжди для «найпростішої» системи.

Характеристики ефективності аналізованих СМО ми будемо вводити під час викладу.

1. n-канальна СМО з відмовами (завдання Ерланга).

Тут ми розглянемо одне з перших часу, «класичних» завдань теорії масового обслуговування; це завдання виникло з практичних потреб телефонії і було вирішено на початку ХХ століття датським математиком Ерлангом. Завдання ставиться так: є каналів (ліній зв'язку), на які надходить потік заявок з інтенсивністю К. Потік обслуговувань має інтенсивність (величина, обернена до середнього часу обслуговування). Знайти фінальні ймовірності станів СМО, а також характеристики її ефективності:

А - абсолютну пропускну спроможність, тобто середня кількість заявок, що обслуговуються в одиницю часу;

Відносну пропускну здатність, тобто середню частку заявок, що прийшли, обслуговуються системою;

Ротк - можливість відмови, т. е. те, що заявка залишить СМО необслуженной;

до - середня кількість зайнятих каналів.

Рішення. Стан системи S (СМО) будемо нумерувати за кількістю заявок, що знаходяться в системі (в даному випадку воно збігається з числом зайнятих каналів):

У СМО немає жодної заявки,

У СМО знаходиться одна заявка (один канал зайнятий, інші вільні),

У СМО знаходиться до заявок каналів зайняті, інші вільні),

У СМО знаходиться заявок (всі канали зайняті).

Граф станів СМО відповідає схемі загибелі та розмноження (рис. 20.1). Розмітимо цей граф - проставимо у стрілок інтенсивності потоків подій, З систему переводить потік заявок з інтенсивністю X (як тільки приходить заявка, система перескакує з ).

Той самий потік заявок переводить систему з будь-якого лівого стану до сусіднього, правого (див. верхні стрілки на рис. 20.1).

Проставимо інтенсивність у нижніх стрілок. Нехай система перебуває у стані (працює один канал). Він здійснює обслуговування в одиницю часу. Тепер уявімо собі, що система перебуває в стані (працюють два канали). Щоб їй перейти в потрібно, щоб закінчив обслуговування перший канал, або другий; сумарна інтенсивність потоків їх обслуговувань дорівнює проставляємо її у відповідної стрілки. Сумарний потік обслуговування, що дається трьома каналами, має інтенсивність до каналів - Проставляємо ці інтенсивності у нижніх стрілок на рис. 20.1.

А тепер, знаючи всі інтенсивності, скористаємося вже готовими формулами (19.7), (19.8) для фінальних ймовірностей у схемі загибелі та розмноження. За формулою (19.8) отримаємо:

Члени розкладання будуть являти собою коефіцієнти при виразах для

Зауважимо, що у формули (20.1), (20.2) інтенсивності Яєць входять не окремо, а лише у вигляді відношення.

і називатимемо величину «наведеної інтенсивністю потоку заявок». Її зміст - середня кількість заявок, що надходить за середній час обслуговування однієї заявки. Користуючись цим позначенням, перепишемо формули (20.1), (20.2) у вигляді:

Формули (20.4), (20.5) для фінальних ймовірностей станів називаються формулами Ерланга – на честь засновника теорії масового обслуговування. Більшість інших формул цієї теорії (сьогодні їх більше, ніж грибів у лісі) не мають жодних спеціальних імен.

Таким чином, фінальні ймовірності знайдено. За ними ми обчислимо показники ефективності СМО. Спочатку знайдемо - ймовірність того, що заявка отримає відмову (не буде обслужена). Для цього потрібно, щоб усі канали були зайняті, отже,

Звідси знаходимо відносну пропускну спроможність - ймовірність того, що заявку буде обслуговано:

Абсолютну пропускну здатність отримаємо, помножуючи інтенсивність потоку заявок X на

Залишилося тільки знайти середню кількість зайнятих каналів до. Цю величину можна було б знайти «прямо», як математичне очікування дискретної випадкової величини з можливими значеннями та ймовірностями цих значень

Підставляючи сюди вирази (20.5) для і виконуючи відповідні перетворення, ми, зрештою, отримали б вірну формулу для до. пропускна спроможність А. Це не що інше, як інтенсивність потоку обслужених системою заявок. Кожен зайнятий канал за одиницю часу обслуговує у середньому заявок. Отже, середня кількість зайнятих каналів дорівнює

І яка частка каналів при цьому простоюватиме?

Тут уже проглядає певний натяк на оптимізацію. Насправді зміст кожного каналу в одиницю часу обходиться в якусь суму. Водночас, кожна обслужена заявка приносить якийсь дохід. Помножуючи цей дохід на середню кількість заявок А, які обслуговуються в одиницю часу, ми отримаємо середній дохід від СМО в одиницю часу. Звісно, зі збільшенням числа каналів цей дохід зростає, але зростають і раеходи, пов'язані зі змістом каналів. Що переважить – збільшення доходів чи витрат? Це залежить від умов операції, від «плати за обслуговування заявки» та вартості змісту каналу. Знаючи ці величини, можна знайти оптимальну кількість каналів, найбільш ефективне економічно. Ми такого завдання вирішувати не будемо, надаючи тому ж «неледачому цікавому читачеві» придумати приклад і вирішити. Взагалі, вигадування завдань більше розвиває, ніж вирішення поставлених кимось.

Системи МО є частиною широкого класу динамічних систем, які іноді називають системами потоків. Системою потоків називається система, у якій деякі предмети переміщаються одним або кількома каналами з обмеженою пропускною здатністю з метою переміщення з однієї точки в іншу. При аналізі систем потоків їх розбивають на два основні класи:

регулярні системи, т. е. системи, у яких потоки поводяться передбачуваним чином (відомі величина потоку та його появи в каналі). У разі, коли канал один, розрахунок системи тривіальний. Очевидно, що між інтенсивністю потоку λ та швидкістю обслуговування зє співвідношення λ < c;

нерегулярні системи, т. е. системи, у яких потоки поводяться непередбачуваним чином.

Цікавішим є випадок регулярного потоку, який розподіляється по мережі каналів. Очевидно, що умова λ < cзберігається для кожного каналу. При цьому виникає складне комбінаторне завдання.

Є сім доріг:

A→B→D→E→F
A→C→B→ E→F
A→C→B→D→E→F
A→C→B→ D→F

Необхідно перевезти вантаж із Ав F. Пропускна спроможність кожного каналу відома. Яка пропускна спроможність мережі та яким шляхом має слідувати потік? Вирішити це можна за допомогою теореми про максимальний потік, яку ми розглядали раніше (рис.6).

До другого класу ставляться випадкові можливі потоки, у яких час надходження вимоги не визначено, кількість вимог непередбачувано. Вирішенням таких завдань і займається теорія масового обслуговування.

У випадку система масового обслуговування то, можливо представлена малюнку 7.

Мал. 7.

Предметом теорії масового обслуговуванняє встановлення залежності між характером потоку заявок, числом каналів, продуктивністю, правильністю роботи та ефективністю.

В якості характеристик ефективностіможуть застосовуватися такі величини та функції:

середня кількість заявок, які може обслужити СМО за одиницю часу;

середня кількість заявок, які отримують відмову та залишають СМО;

ймовірність того, що заявка, що надійшла, негайно буде обслужена;

середній час очікування у черзі;

середня кількість заявок у черзі;

середній дохід СМО в одиницю часу та інші економічні показники СМО.

Аналіз СМО спрощується, якщо у системі протікає марківський процес, тоді систему можна описати звичайними диференціальними рівняннями, а граничні ймовірності – лінійними рівняннями алгебри.

Марківський процес вимагає, щоб усі потоки були пуассонівськими (без післядій), але апарат марківських процесів використовується і тоді, коли процес відмінний від марковського. В цьому випадку характеристики СМО можуть бути оцінені приблизно: чим складніше СМО, тим точніше наближення.

Класифікація систем масового обслуговування

СМО можуть бути двох видів:

СМО із відмовими;

СМО з очікуванням (тобто з чергою).

Обслуговування в системах з чергою може мати різний характер:

обслуговування може бути впорядкованим;

обслуговування у випадковому порядку;

обслуговування з пріоритетом, причому пріоритет може бути з перериванням і без переривання.

Системи з чергою поділяються на:

системи з необмеженим очікуванням, при цьому завдання, що надійшло в СМО, стає в чергу і чекає обслуговування. Рано чи пізно її буде обслужено;

системи з обмеженим очікуванням, при цьому на заявку в черзі накладаються обмеження, наприклад, обмежений час перебування в черзі, довжина черги, загальний час перебування в СМО. Залежно від типу СМО з метою оцінки ефективності можуть бути застосовані різні показники.

Для СМО з відмовами використовуються такі показники ефективності:

абсолютна пропускна спроможність А- Середня кількість заявок, яка може бути обслуговується в одиницю часу;

відносна пропускна спроможність Q- Відносна середня кількість заявок. При цьому відносну пропускну здатність можна знайти за формулою

Де λ – це інтенсивність надходження заявок до СМО.

Для СМО з очікуванням абсолютна пропускна спроможність Аі відносна пропускна спроможність Qвтрачають сенс, але важливими стають інші характеристики:

одиниця часу очікування у черзі;

середня кількість заявок у черзі;

середній час перебування у системі.

Для СМО з обмеженою чергою цікаві обидві групи показників.

Розглянемо n - канальну систему масового обслуговування з очікуванням.

Інтенсивність потоку обслуговування дорівнює μ. Тривалість обслуговування – випадкова величина, підпорядкована показовому закону розподілу. Потік обслуговування є найпростішим пуасонівським потоком подій.

Розмір черги допускає перебування у ній m заявок.

Для знаходження граничних можливостей можна використовувати такі вирази.

(0‑1)

де.

Ймовірність відмови в обслуговуванні заявки(відмова відбудеться у випадку, якщо всі канали зайняті та в черзі знаходяться m заявок):

(0‑2)

Відносна пропускна спроможність.

(0‑3)

Абсолютна пропускна спроможність.

(0‑4)

Середня кількість зайнятих каналів.

Для СМО із чергою середня кількість зайнятих каналів не збігається (на відміну від СМО з відмовими) із середнім числом заявок у системі. Відмінність дорівнює кількості заявок, які чекають у черзі.

Позначимо середню кількість зайнятих каналів. Кожен зайнятий канал обслуговує в середньому μ заявок за одиницю часу, а СМО в цілому – А заявок за одиницю часу. Розділивши А на μ отримаємо

(0‑5)

Середня кількість заявок, що знаходяться в черзі.

Для знаходження середньої кількості заявок, що чекають у черзі, у разі, якщо χ≠1, можна використовувати вираз:

(0‑6)

(0‑7)

де =.

Середня кількість заявок, що знаходяться в системі.

(0‑8)

Середній час очікування заявки у черзі.

Середній час очікування заявки у черзі можна знайти з виразу (χ≠1).

(0‑9)

Середній час перебування заявки у системі.

Так само як і у випадку з одноканальною СМО маємо:

(0‑10)

зміст роботи.

Підготовка інструментарію експерименту .

Виконується відповідно до загальних правил.

Розрахунок на аналітичній моделі .

1. У Microsoft Excel підготуйте таблицю такого вигляду.

Параметри
СМО

Аналітична
Модель

Імітаційна
Модель

Pотк

ніж

Pотк

2. У стовпцях для параметрів СМО таблиці запишіть свої вихідні дані, що визначаються за правилом:

n = 1,2,3

m=1,3,5

Для кожної комбінації ( n, m) необхідно знайти теоретичні та експериментальні значення показників СМО для таких пар значень:

= <порядковый номер в списке группы>

3. У стовпчиках з показниками аналітичної моделі впишіть відповідні формули.

Експеримент на імітаційній моделі.

1. Встановіть режим запуску з експоненційно розподіленим часом обслуговування, задавши значення відповідного параметра рівним 1.

2. Для кожної комбінації n, m, та здійсніть запуск моделі.

Результати запусків внесіть до таблиці.

3. Внесіть у відповідні стовпці таблиці формули розрахунку середнього значення показника Pотк, q і А.

Аналіз результатів .

1. Проаналізуйте результати, отримані теоретичним та експериментальним способами, порівнявши результати між собою.

2. Для однієї з комбінацій (n,m) побудуйте на одній діаграмі графіки залежності Pотк від теоретично та експериментально отриманих даних.

Оптимізація параметрів СМО .

Розв'яжіть задачу оптимізації розміру числа місць у черзі m для двох приладів із середнім часом обслуговування = з погляду отримання максимального прибутку. Як умови завдання візьміть:

- дохід від обслуговування однієї заявки рівним 80 у.о./год.,

- вартість утримання одного приладу - 1у.о./год.,

- вартість утримання одного місця у черзі – 0.2 у.о./год.

1. Для розрахунків доцільно створити таблицю:

Перший стовпець заповнюється значеннями числа приладів n =1.

Другий стовпець заповнюється значеннями чисел натурального ряду (1,2,3…).

Усі клітини третього та четвертого стовпців заповнюються значеннями.

У клітини стовпців з п'ятого до чотирнадцятого переносяться формули для стовпців таблиці розділу 0.

У стовпці з вихідними даними розділів Дохід, Витрата, Прибуток внесіть значення (див. вище).

У стовпцях з значеннями розділів, що обчислюються, Дохід, Витрата, Прибуток запишіть розрахункові формули:

- кількість заявок на одиницю часу

N r =A

- сумарний дохід за одиницю часу

I S = I r *N r

- сумарна витрата в одиницю часу

E S = E s *n + E q *m

- прибуток у одиницю часу

P = I S - E S

де

I r - Дохід від однієї заявки,

E s - Витрата на один прилад,

E q - Витрата на одне місце в черзі

2. Заповніть рядки таблиці для n=2 та n=3.

Знайдіть опт для n = 1,2,3.

3. Побудуйте в одній діаграмі графіки залежності C(m) для n=1,2,3.

Звіт по роботі:

Звіт по роботі повинен включати:

- вихідні дані,

- результати розрахунків та експериментів з програмною моделлю,

Графіки для P отк ,

- таблицю з даними для знаходження найкращого m і значення m опт,

- графіки залежності прибутку в одиницю часу від m для n=1,2,3.

Контрольні питання :

1) Дайте короткий опис багатоканальної моделі СМО з обмеженою чергою.

2) Якими показниками характеризується функціонування багатоканальної СМО з обмеженою чергою?

3) Як розраховуються граничні ймовірності багатоканальної СМО з обмеженою чергою?

4) Як знайти можливість відмови від обслуговування заявки?

5) Як знайти відносну пропускну спроможність?

6) Чому дорівнює абсолютна пропускна спроможність?

7) Як підраховується середня кількість заявок у системі?

8) Наведіть приклади багатоканальної СМО з обмеженою чергою.

Завдання.

1) На автозаправній станції встановлено 3 колонки та майданчик на 3 автомобілі для очікування заправки. У середньому на станцію прибуває одна машина кожні 4 хвилини. Середній час обслуговування однієї машини – 2,8 хв. Визначити характеристики роботи автозаправної станції.

2) На станцію технічного огляду автомобілів, що має 3 оглядові пости, в середньому надходить 1 автомобіль за 0,4 години. Стоянка у дворі вміщує 3 машини. Середній час роботи одного посту – 0,5 години. Визначити характеристики роботи СТО.

3) У магазин здійснюється завезення товарів автомобілями. Протягом дня прибувають у середньому 6 машин. Підсобні приміщення для підготовки товарів до продажу дозволяють обробляти та зберігати товар, привезений двома машинами. У магазині працюють позмінно три фасувальники товарів, кожен з яких у середньому може обробляти товар однієї машини протягом 5 годин. Тривалість робочого дня фасувальників складає 12 годин. Визначити характеристики роботи магазину, а також, якою має бути ємність підсобних приміщень, щоб ймовірність повної обробки товарів була більшою за 0,96.

4) У магазині працюють три каси. Середній час обслуговування одного покупця – 3 хв. Інтенсивність потоку покупців – 7 осіб на хвилину. Число покупців, які стоять у черзі до каси, не може перевищувати 5 осіб. Покупець, який прийшов до магазину, в якому в кожній черзі до каси 5 осіб, не чекає, а йде з магазину. Визначити характеристики роботи магазину.

5) Оптовий склад здійснює відпуск товарів клієнтам. Навантаження автомашини здійснюють три бригади вантажників, кожна з яких складається з чотирьох осіб. Склад одночасно вміщує 5 автомашин і, якщо в цей час прибуває нова автомашина, вона не обслуговується. Інтенсивність вхідного потоку становить 5 машин на годину. Інтенсивність завантаження складає 2 автомашини на годину. Дайте оцінку роботи складу та варіант його реорганізації.

6) Митниця має в своєму розпорядженні три термінали. Інтенсивність потоку автомашин, що перевозять вантажі та підлягають проходженню митного контролю, становить 30 шт. на добу. Середній час митної обробки на терміналі однієї машини становить 3 години. Якщо в черзі на проходження митного контролю стоять 5 автомашин, то автомашини, що приїжджають, їдуть на іншу митницю. Знайти показники ефективності роботи митниці.

7) На будівельний майданчик в середньому через 40 хв прибувають автомобілі з будівельним матеріалом. Середній час розвантаження однієї машини становить 1,8 години. У розвантаженні беруть участь дві бригади вантажників. На території будівельного майданчика може знаходитись у черзі на розвантаження не більше 5 автомашин. Визначити показники ефективності роботи будівельного майданчика.

8) На мийку, що має три робочі місця, в середньому за годину приїжджає 12 автомашин. Якщо в черзі вже знаходиться 6 автомашин, автомобілі, що знову приїжджають, не встають у чергу, а залишають мийку. Середній час миття машини становить 20 хв, середня вартість послуг миття - 150 руб. Визначити показники ефективності роботи миття та середню величину втрати виручки протягом робочого дня (з 9 до 19 години).

9) Інтенсивність потоку автомашин, що перевозять вантажі та підлягають проходженню митного контролю, становить 50 прим. на добу. Середній час митної обробки на терміналі однієї машини становить 2,8 години. Максимальна черга на проходження митного контролю має бути не більше 8 автомашин. Визначити, скільки терміналів треба відкрити на митниці, щоб ймовірність простою автомашин була мінімальна.

Система з обмеженою довжиною черги. Розглянемо канальну СМО з очікуванням, яку надходить потік заявок з інтенсивністю ; інтенсивність обслуговування (для одного каналу); кількість місць у черзі.

Стан системи нумерується за кількістю заявок, пов'язаних системою:

немає черги:

Усі канали вільні;

Зайнятий один канал, інші вільні;

Зайняті каналів, решта немає;

Зайняті всі канали, вільних немає;

є черга:

Зайнято всі n каналів; одна заявка стоїть у черзі;

Зайняті всі n каналів, r заявок у черзі;

Зайнято всі n каналів, mзаявок у черзі.

ДСП наведено на рис. 5.9. У кожної стрілки проставлено відповідні інтенсивності потоків подій. За стрілками зліва направо систему переводить завжди той самий потік заявок з інтенсивністю , по стрілках праворуч наліво систему переводить потік обслуговування, інтенсивність якого дорівнює , помноженому на кількість зайнятих каналів.

Багатоканальна експоненційна СМОвідрізняється від одноканальної наступним. Число каналів у ній більше одного. Заявка, що надходить, стає в чергу, якщо всі канали зайняті. В іншому випадку, заявка займає вільний канал. (5.56)

Напишемо вирази для граничних ймовірностей станів, використовуючи позначення: (див.5.45)

Ймовірність відмови. Заявка, що надійшла, отримує відмову, якщо зайняті всі nканалів і все mмісць у черзі:

(5.57)

Відносна пропускна здатність доповнює можливість відмови до одиниці:

Абсолютна пропускна здатність СМО:

(5.58)

Середня кількість зайнятих каналів. Для СМОз відмовами воно збігалося із середнім числом заявок, що у системі. Для СМОз чергою середня кількість зайнятих каналів не збігається із середнім числом заявок, що у системі: остання величина відрізняється від першої на середнє число заявок, що у черзі.

Позначимо середню кількість зайнятих каналів. Кожен зайнятий канал обслуговує в середньому заявок за одиницю часу, а СМОв цілому обслуговує в середньому Азаявок на одиницю часу. Розділивши одне на інше, отримаємо:

(5.59)

Тут знову (вираз у дужках) зустрічається похідна суми геометричної прогресії (див. вище (5.50), (5.51)-(5.53)), використовуючи співвідношення для неї, отримуємо:

Середня кількість заявок у системі:

Середній час очікування заявки у черзі. Розглянемо ряд ситуацій, що відрізняються тим, у якому стані застане систему знову прийшла заявка і скільки часу їй доведеться чекати на обслуговування.

Якщо заявка застане в повному обсязі канали зайнятими, їй взагалі доведеться чекати (відповідні члени в математичному очікуванні рівні нулю). Якщо заявка прийде в момент, коли всі зайняті пканалів, а черги немає, їй доведеться чекати в середньому час, рівний (бо «потік звільнень» каналів має інтенсивність). Якщо заявка застане всі канали зайнятими і одну заявку перед собою в черзі, їй доведеться в середньому чекати протягом часу (по кожну заявку, що стоїть попереду) і т. д. Якщо заявка застане в черзі заявок, їй доведеться чекати в середньому протягом часу . Якщо заявка, що знову прийшла, застане в черзі вже mзаявок, вона взагалі не чекатиме (але й не буде обслужена).

Середній час очікуваннязнайдемо, помножуючи кожне із цих значень на відповідні ймовірності:

(5.60)

Так само, як і у випадку одноканальної СМО з очікуванням, відзначимо, що цей вираз відрізняється від виразу для середньої довжини черги (5.59) лише множником , тобто.

Середній час перебування заявки у системі, так само, як і для одноканальної СМО, відрізняється від середнього часу очікування на середній час обслуговування, помножений на відносну пропускну здатність:

Системи з необмеженою довжиною черги.

Ми розглянули канальну СМО з очікуванням, коли в черзі одночасно можуть бути не більше mзаявок.

Також, як і раніше, при аналізі систем без обмежень необхідно розглянути отримані співвідношення при .

Імовірність станів отримаємо з формул (5.56) граничним переходом (при ). Зауважимо, що сума відповідної геометричної прогресії сходиться за і розходиться за > 1. Припустивши, що< 1 и устремив в формулах (5.56) величину mдо нескінченності, отримаємо вирази для граничних ймовірностей станів:

(5.61)

Середню кількість заявок в черзі отримаємо при (5.59):

а середній час очікування – з (5.60):

Середня кількість зайнятих каналів, як і раніше, визначається через абсолютну пропускну здатність:

Ускладнення структур і режимів реальних систем ускладнює застосування класичних методів теорії масового обслуговування через зростання розмірності розв'язуваних завдань, що особливо характерно для систем з мережевою структурою. Одним із можливих шляхів подолання розмірності є використання моделей у формі мереж масового обслуговування (СеМО).

СеМОявляє собою сукупність кінцевого числа обслуговуючих вузлів, в якій циркулюють заявки, що переходять відповідно до маршрутної матриці з одного вузла до іншого. Вузол завжди є розімкнутою СМО. При цьому окремі СМО СМО− структуру системи, а вимоги, що циркулюють по СеМО, − складові матеріальних потоків (повідомлення (пакети) у комунікаційній мережі, завдання у мультипроцесорних системах, контейнери вантажопотоків тощо).

В свою чергу, СеМОвикористовують для визначення найважливіших системних характеристик інформаційних систем: продуктивність;часу доставки пакетів; ймовірності втрати повідомлень та блокування у вузлах; області допустимих значень навантаження, у яких забезпечується необхідне якість обслуговування та інших.

В теорії СеМОфундаментальним є поняття стану мережі. Найважливіша характеристика мереж МО− ймовірності їх станів. Для визначення ймовірностей станів СеМОдосліджують випадковий процес, що протікає в мережі. Як моделі протікають у СеМОпроцесів також найчастіше використовують марківські та напівмарківські.

3.3. Система масового обслуговування як модель

1.5. Мережі масового обслуговування

Марківським процесом з безперервним часом описують функціонування експоненційних СеМО.

Мережа називається експоненційною,якщо вхідні потоки вимог до кожної СМО пуассонівські, а часи кожного етапу обслуговування, що реалізується на будь-якій СМОмережі, мають експонентнеРозподіл. Це дозволяє вважати, що етапи обслуговування незалежні між собою і не залежать ні від параметрів вхідного потоку, ні стану мережі, ні від маршрутів дотримання вимог.

Теорія експоненційних СеМОнайбільш розроблена, і її широко застосовують як для дослідження мереж ПД так і для дослідження мультипроцесорних обчислювальних систем (ВС).Розроблено практичні формули розрахунку імовірнісно-тимчасових характеристик (ВВХ) таких мереж та систем.

Спроби глибокого аналізу немарківських моделей мережевих систем наштовхуються на значні труднощі, які зумовлені, зокрема, відсутністю незалежності тривалостей перебування вимог у різних вузлах моделей мережевих систем з нестандартними дисциплінами. Так, наприклад, при досить реалістичному припущенні про те, що довжина вимоги залишається постійною в процесі передачі через вузли мережі, необхідно простежувати шлях кожної вимоги, що унеможливлює аналітичний розрахунок характеристики для мережі з числом вузлів М>2.

Аналіз робіт, присвячених дослідженню або розрахунку немарківських моделей, показує, що рішення, як правило, отримані алгоритмічно шляхом складних чисельних розрахунків з використанням перетворень Лапласа-Стілтьєса, реалізуються програмно, відрізняються великою трудомісткістю, або значними похибками в оцінці показників продуктивності інформаційних систем в області середнього та великого навантаження. Тому для моделювання СеМО,що виходять із класу мультиплікативних, використовують наближені методи.

Порівняльний аналіз наближених методів моделювання СеМОі приклади, наведені в показують, що користуватися наближеними методами розрахунку СеМО необхідно з великою обережністю, що при розрахунку конкретних СеМО, в процесі вирішення різних прикладних завдань є необхідним проведення досліджень з метою оцінки точності та чутливості застосовуваного методу, а також проведення експерименту з імітаційного моделювання вихідний СеМО для досить великої безлічі значень параметрів, що варіюються.

Аналітичні методи розрахунку характеристик ІВ базуються, як правило, на аналізі експоненційних СеМО. З використанням цього математичного апарату вдається отримати аналітичні моделі на вирішення кола завдань дослідження систем. CеМО - це, перш за все, сукупність взаємопов'язаних систем масового обслуговування. Тому слід згадати основні особливості цих систем.

Мережа масового обслуговуванняявляє собою сукупність кінцевого числа Nобслуговуючих вузлів, в якій циркулюють заявки, що переходять відповідно до маршрутної матриці з одного вузла до іншого. Вузол завжди є розімкнутою СМО (причому СМО може бути будь-якого класу). При цьому окремі СМОвідображають функціонально самостійні частини реальної системи, зв'язки між СМО- структуру системи, а вимоги, що циркулюють по СеМО,- складові матеріальних потоків (повідомлення (пакети) у комунікаційній мережі, завдання у мультипроцесорних системах, контейнери вантажопотоків тощо).

Для наочного уявлення СеМОвикористовується граф, вершини якого (вузли) відповідають окремим СМОдуги відображають зв'язки між вузлами.

Перехід заявок між вузлами відбувається миттєво відповідно до перехідних ймовірностей , p ij- ймовірність того, що заявка після обслуговування у вузлі iперейде у вузол j. Звичайно, якщо вузли безпосередньо не пов'язані між собою, то p ij= 0. Якщо з i-го вузла перехід тільки в один якийсь вузол j, то p ij= 1.

СеМОкласифікують за декількома ознаками (рис. 4).

Мережа називається лінійної, якщо інтенсивності потоків заявок у вузлах пов'язані між собою лінійною залежністю

l j= a ij l i,

де a ij- коефіцієнт пропорційності, або щодо джерела

l j= a j l 0 ,.

Коефіцієнт a jназивають коефіцієнтом передачі, він характеризує частку заявок, що надходять у j-й вузол від джерела заявок, або - середня кількість проходжень заявкою через даний вузол під час перебування заявки у мережі.

Якщо інтенсивність потоків заявок у вузлах мережі пов'язана нелінійною залежністю (наприклад, ), то мережа називається нелінійною..

Мережа завжди лінійна, якщо заявки не губляться і не розмножуються.

Розімкненамережа – це така відрита мережа, до якої заявки надходять із довкілля та йдуть після обслуговування з мережі у зовнішнє середовище. Іншими словами, особливістю розімкнутої СеМО(РСеМО) є наявність одного або кількох незалежних зовнішніх джерел, які генерують заявки, що надходять до мережі, незалежно від того, скільки заявок вже знаходиться в мережі. У будь-який момент часу в РСеМОможе бути довільна кількість заявок (від 0 до ¥).

Мал. 4. Класифікація мереж масового обслуговування

У замкнутої СеМО (ЗСеМО)циркулює фіксоване число заявок, а зовнішнє незалежне джерело відсутнє. Виходячи з фізичних міркувань, ЗСеМПро вибирається зовнішня дуга, на якій відзначається псевдонульоваточка, щодо якої можуть вимірюватись тимчасові характеристики.

Комбінованамережа – це мережа, у якій постійно циркулює кілька заявок і є заявки, які від зовнішніх незалежних джерел.

У однорідниймережі циркулюють заявки одного класу І, навпаки, в неоднорідниймережі можуть бути заявки кількох класів. Заявки відносяться до різних класів, якщо вони відрізняються хоча б одним із таких атрибутів:

Законом розподілу тривалості обслуговування у вузлах;

Пріоритетами;

Маршрутами (шляхами руху заявок у мережі).

У експоненційноюмережі тривалості обслуговування у всіх вузлах розподілені за експоненційним законом, і потоки, що надходять у розімкнену мережу, найпростіші (пуассонівські). У решті випадків мережа є неекспоненційною.

Якщо хоча в одному вузлі здійснюється пріоритетне обслуговування, то це – пріоритетнамережа. Пріоритет - це ознака, що визначає черговість обслуговування. Якщо обслуговування заявок у вузлах здійснюється у порядку надходження, то така мережа безпріоритетна.

Таким чином, експоненційною будемо називати СеМО, Що відповідає вимогам:

Вхідні потоки СеМОпуасонівські;

У всіх N СМОчас обслуговування заявок має експоненційну функцію розподілу ймовірностей і заявки обслуговуються в порядку приходу;

Перехід заявки з виходу i-й СМО на вхід j-й є незалежною випадковою подією, що має ймовірність p ij ; p i0- ймовірність відходу заявки з CeМО.

Якщо заявки приходять у мережу і йдуть з неї, то мережа називається розімкнутою. Якщо заявки не приходять до мережі та з неї не йдуть, мережа називається замкнутою. Число заявок у замкненій мережі постійне.