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

30.05.2020 Терміни

У комерційної діяльностічастіше зустрічаються СМО з очікуванням (чергою).

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

Граф цієї СМО подано на рис. 3.4 та збігається з графом рис. 2.1 описує процес «народження - загибелі», з тією відмінністю, що за наявності тільки одного каналу.

Розмічений граф процесу «народження – загибелі» обслуговування всі інтенсивності потоків обслуговування рівні

Стану СМО можна представити так:

S0 - канал обслуговування вільний,

S, - канал обслуговування зайнятий, але черги немає,

S2-канал обслуговування зайнятий, у черзі стоїть одна заявка,

S3-канал обслуговування зайнятий, у черзі стоять дві заявки,

Sm+1 - канал обслуговування зайнятий, у черзі всі місця зайняті, будь-яка наступна заявка отримує відмову.

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

Вираз для р0 можна в даному випадку записати простіше, користуючись тим, що у знаменнику стоїть геометрична прогресія щодо р, тоді після відповідних перетворень отримуємо:

с= (1- с)

Ця формула справедлива всім р, відмінних від 1, якщо р = 1, то р0 = 1/(т + 2), проте інші ймовірності також дорівнюють 1/(т + 2).

Якщо припустити т = 0, ми переходимо від розгляду одноканальної СМО з очікуванням до вже розглянутої одноканальної СМО з відмовами в обслуговуванні.

Справді, вираз для граничної ймовірності р0 у разі т = 0 має вигляд:

pо = м/(л+м)

І у разі л = м має величину р0 = 1/2.

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

Заявка отримує відмову, якщо вона надходить у момент часу, коли СМО вже перебуває в стані Sm+1 і, отже, всі місця в черзі та зайняті та один канал обслуговує

Тому ймовірність відмови визначається ймовірністю появою

Стан Sm+1:

Pотк = pm+1 = сm+1 * p0

Відносна пропускна здатність, або частка заявок, що обслуговуються, що надходять в одиницю часу, визначається виразом

Q = 1 - pотк = 1 - см + 1 * p0

абсолютна пропускна здатність дорівнює:

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

випадкова величина приймає наступні тільки цілі значення:

1 - у черзі стоїть одна заявка,
2 - у черзі дві заявки,

т-в черзі всі місця зайняті

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

Таблиця 1. Закон розподілу дискретної випадкової величини

Математичне очікування цієї випадкової величини дорівнює:

Lоч = 1 * p2 +2 * p3 + ... + m * pm +1

У випадку при p ?1 цю суму можна перетворити, користуючись моделями геометричної прогресії, до зручнішого виду:

Lоч = p2* 1-pm * (m-m*p+1)* p0

В окремому випадку при р = 1, коли всі ймовірності pk виявляються рівними, можна скористатися виразом для суми членів числового ряду

1+2+3+ m = m(m+1)

Тоді отримаємо формулу

L"оч= m(m+1)* p0 = m(m+1)(p = 1).

Застосовуючи аналогічні міркування та перетворення, можна показати, що середній час очікування обслуговування заявки а черги визначається формулами Літтла

Точ = Lоч / А (при р? 1) і Т1оч = L"оч / А (при р = 1).

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

Заявка, що надійшла до СМО в момент часу, коли всі канали зайняті, отримує відмову, і, отже, час її «очікування» в СМО дорівнює нулю. Це призводить у загальному випадку (при р? 1) до зменшення Точростом л, оскільки частка таких заявок із зростанням л збільшується.

Якщо відмовитися від обмеження довжину черги, тобто. спрямувати m->>?, то випадки р< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

При досить великому до ймовірності pk прагне до нуля. Тому відносна пропускна здатність буде Q = 1, а абсолютна пропускна здатність стане рівною А - л Q - л отже, обслуговуються всі заявки, причому середня довжина черги виявиться рівною:

Lоч = p2 1-p

а середній час очікування за формулою Літтла

Точ = Lоч/А

У межі р<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Граничні ймовірності станів тому неможливо визначити: при Q= 1 вони дорівнюють нулю. Фактично СМО не виконує своїх функцій, оскільки вона не в змозі обслужити всі заявки, що надходять.

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

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

Lсмо= m+1;2

Тсмо = Lсмо;при p?1

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

Тсмо = m+1при p? 1 2м

операції чи ефективності системи масового обслуговування є такі.

Для СМО з відмовами:

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

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

Залежно від мети операції масового обслуговування будь-який із наведених показників (або сукупність показників) може бути обраний як критерій ефективності.

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

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

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

Розглянемо приклади деяких СМО.

2.5.1. Багатоканальна СМО з відмовами

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

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

Опис станів:

Усі інспектори вільні;

Зайнятий один інспектор;

Зайняті два інспектори;

Зайнято трьох інспекторів.

Граф станів системи наведено на рис. 2.11.

Рис. 2.11.

На графі: - Інтенсивність потоку вантажних автомобілів; - Інтенсивність перевірок документів одним автоінспектором.

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

Рішення

Шукана частина ймовірності – ймовірності зайнятості всіх трьох інспекторів. Оскільки граф станів представляє типову схему " загибелі та розмноження " , то знайдемо , використовуючи залежності (2.2).

Пропускну здатність цієї посади автоінспекторів можна характеризувати відносною пропускною здатністю:

Приклад 2.6. Для прийому та обробки донесень від розвідгрупи у розвідвідділі об'єднання призначено групу у складі трьох офіцерів. Очікувана інтенсивність потоку донесень - 15 донесень на годину. Середній час обробки одного повідомлення одним офіцером - . Кожен офіцер може приймати повідомлення від будь-якої розвідгрупи. Офіцер, що звільнився, обробляє останнє з донесень, що надійшли. Донесення, що надходять, повинні оброблятися з ймовірністю не менше 95%.

Визначити, чи достатньо призначеної групи із трьох офіцерів для виконання поставленого завдання.

Рішення

Група офіцерів працює як СМО з відмовами, що складається із трьох каналів.

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

Опис станів та граф станів СМО будуть аналогічні наведеним у прикладі 2.5.

Оскільки граф станів - це схема "загибелі та розмноження", то для неї є готові вирази для граничних ймовірностей стану:

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

У прикладі .

У розглядуваній СМО відмованастає при зайнятості всіх трьох каналів, тобто . Тоді:

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

Таким чином, тільки група з шести офіцерів зможе обробляти донесення, що надходять, з ймовірністю 95 %.

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

Приклад 2.7. На ділянці форсування річки є 15 однотипних переправних засобів. Потік надходження техніки на переправу в середньому становить 1 од./хв, середній час переправи однієї одиниці техніки – 10 хв (з урахуванням повернення назад переправного засобу).

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

Рішення

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

Середня кількість працюючих переправних засобів:

Коефіцієнти використання та простою переправи:

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

Коефіцієнти використання переправи після 50 прогонів практично збігаються: .

Максимальна довжина черги 15 од., середній час перебування у черзі близько 10 хв.

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

Нехай є одноканальна СМО з чергою, на яку не накладено жодних обмежень (ні за довжиною черги, ні за часом очікування). Цю СМО надходить потік заявок з інтенсивністю X; потік обслуговування має інтенсивність, зворотну середньому часу обслуговування заявки Потрібно знайти фінальні ймовірності станів СМО, а також характеристики її ефективності:

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

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

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

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

Імовірність того, що канал зайнятий (ступінь завантаження каналу).

Що стосується абсолютної пропускної спроможності А та відносної Q, то обчислювати їх немає потреби: в силу того, що черга необмежена, кожна заявка рано чи пізно буде обслужена, тому з тієї ж причини

Рішення. Стан системи, як і раніше, будемо нумерувати за кількістю заявок, що знаходяться в СМО:

Канал вільний,

Канал зайнятий (обслуговує заявку), черги немає,

Канал зайнятий, одна заявка стоїть у черзі,

Канал зайнятий, заявок стоять у черзі,

Теоретично кількість станів нічим не обмежена (нескінченно). Граф станів має вигляд, показаний на рис. 20.2. Це - схема загибелі та розмноження, але з нескінченним числом станів. По всіх стрілках потік заявок з інтенсивністю А переводить систему зліва направо, а праворуч наліво - потік обслуговування з інтенсивністю

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

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

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

Ряд у формулі (20.11) є геометричною прогресією. Ми знаємо, що при ряд сходиться - це нескінченно спадна геометрична прогресія зі знаменником. При ряд розходиться (що непрямим, хоча й суворим доказом те, що фінальні ймовірності станів існують лише за ). Тепер припустимо, що ця умова виконана, і підсумовуючи прогресію в (20.11), маємо

(20.12)

Імовірності знайдуться за формулами:

звідки, з урахуванням (20.12), знайдемо остаточно:

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

Знайдемо середню кількість заявок у СМО. Тут доведеться трохи повозитися. Випадкова величина Z – число заявок у системі – має можливі значення з ймовірностями

Її математичне очікування одно

(20.14)

(Сума береться не від 0 до а від 1 до так як нульовий член дорівнює нулю).

Підставимо у формулу (20.14) вираз для

Тепер винесемо за знак суми:

Тут ми знову застосуємо «маленьку хитрість»: є не що інше, як похідна досі від виразу означає,

Змінюючи місцями операції диференціювання та підсумовування, отримаємо:

Але сума у формулі (20.15) є не що інше, як сума нескінченно спадної геометричної прогресії з першим членом і знаменником; ця сума дорівнює а її похідна. Підставляючи цей вираз (20.15), отримаємо:

(20.16)

Ну, а тепер застосуємо формулу Літтла (19.12) та наймемо середній час перебування заявки в системі:

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

Отже, середня кількість заявок під обслуговуванням дорівнює

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

Рис. 6. Одноканальна СМО з необмеженою чергою

Під необмеженою чергою розумітимемо, що кількість заявок, що надійшли на обслуговування, не обмежена і час обслуговування кожної заявки довільний, але всі заявки рано чи пізно будуть обслужені. У цьому випадку немає сенсу говорити про абсолютну пропускну здатність (А = λ) і про відносну пропускну здатність (Q = 1).

Кожна заявка, що знову надійшла, буде переводити СМО в новий стан S зі збільшенням індексу на 1, тобто зліва направо. А кожна обслужена заявка зменшуватиме індекс стану S на 1, тобто переміщення по графу справа наліво. Так як у кожен момент часу обслуговується лише одна заявка (одноканальна СМО), то всі інтенсивності надходження заявок дорівнюють λ і всі інтенсивності обслуговування заявок дорівнюють µ. У спеціальній літературі доводиться, що з необмеженому числі станів СМО фінальні можливості відсутні. Для даного випадкуфінальні ймовірності існують з урахуванням накладених обмежень: усі заявки рано чи пізно будуть обслужені та виконується умова:

Використовуючи формули (10) - (13) та (14), визначимо фінальні ймовірності подій.

Враховуючи, що 1 + ρ + ρ 2 +ρ 3 + ... + ρ m + ... =1/(1-ρ), отримуємо значення фінальної ймовірності події S0:

Ро = 1-ρ. (.21)

Фінальні ймовірності наступних подій будуть визначені як:

P1 = ρP0; р2 = ρ 2 Ро; pз = ρ 3 P0; Pm = pm Pо; (22)

Обчислимо середню кількість заявок до СМО. Оскільки кількість заявок може набувати значень 0, 1, 2, 3, ... , m, ... , то можна записати:

L сист =0P0+1P1+2P2+3P3+…mPm+..=

Застосувавши формулу (17), визначимо час обслуговування заявки

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

Імовірність такої події (зайнятості одного каналу) дорівнюватиме Р зан = 1 – Р0 = ρ. Оскільки СМО обслуговує лише одну заявку, то Lобсл = ρ.

Довжина черги є різниця між загальним числом заявок та заявками, що знаходяться в обслуговуванні, тоді:

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

Усі характеристики одноканальної СМО визначено.

На оптову базу надходять на розвантаження три автомобілі на годину (? = 3). Середній час розвантаження (Тобс) одного автомобіля – 10 хв. Визначити характеристики одноканальної СМО із необмеженою чергою.

Визначимо інтенсивність обслуговування автомобілів

За формулою (23) визначимо середню кількість автомобілів, що обслуговуються:

За формулою (24) визначимо середній час (годину) обслуговування автомобіля:

За формулою (25) визначимо довжину черги (середня кількість автомобілів, які чекають на розвантаження):

L оч = L сист – ρ = 1 – 0,5 = 0,5.

За формулою (26) визначимо середній час очікування у черзі автомобіля.

Розглянемо тепер одноканальну СМО з очікуванням.

Система масового обслуговування має один канал. Вхідний потікзаявок на обслуговування потік має інтенсивність? Інтенсивність потоку обслуговування дорівнює μ (тобто в середньому безперервно зайнятий канал видаватиме μ обслужених заявок). Тривалість обслуговування - випадкова величина, підпорядкована показовому закону розподілу. Заявка, що надійшла в момент, коли канал зайнятий, стає в чергу і чекає на обслуговування.

Розглянемо систему з обмеженою чергою. Припустимо, що незалежно від того, скільки вимог надходить на вхід обслуговуючої системи, дана система(черга + клієнти, що обслуговуються) не може вмістити більше N-вимог (заявок), з яких одна обслуговується, а ( N-1) очікують, що Клієнти, які не потрапили в очікування, змушені обслуговуватися в іншому місці і такі заявки губляться.

Позначимо - ймовірність того, що в системі знаходиться nзаявок. Ця величина обчислюється за такою формулою:

Тут – наведена інтенсивність потоку. Тоді ймовірність того, що канал обслуговування вільний і в системі немає жодного клієнта, дорівнює: .

З огляду на це можна позначити

Визначимо характеристики одноканальної СМО з очікуванням та обмеженою довжиною черги, що дорівнює (N-1):

ймовірність відмови в обслуговуванні заявки:

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

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

А=q∙λ;

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

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

;

середня тривалість перебування клієнта (заявки) у черзі:

W q=W s- 1/μ;

середня кількість заявок (клієнтів) у черзі (довжина черги):

L q=λ(1- P N)W q.

Розглянемо приклад одноканальної СМО з очікуванням.

Приклад 9.2. У зону митного контролюу пункті пропуску автомобілі в'їжджають системою електронної черги. Кожне вікно оформлення прибуття/вибуття є одноканальною СМО. Число стоянок для автомобілів, що чекають на оформлення, обмежено і дорівнює 3, тобто ( N-1) = 3. Якщо всі стоянки зайняті, т. е. в черзі вже три автомобілі, то черговий автомобіль у зону митного контролю не пропускається, тобто. у чергу обслуговування не стає. Потік автомобілів, що прибувають на оформлення має інтенсивність λ =0,85 (автомобіля за годину). Час оформлення автомобіля розподілено за показовим законом і в середньому дорівнює 1,05 год. Потрібно визначити ймовірні характеристики вікна оформлення прибуття/вибуття пункту пропуску, що працює в стаціонарному режимі.

Рішення.

Інтенсивність потоку обслуговувань автомобілів: