Класифікація СМО

Назва роботи: Класифікація СМО

Предметна область: Інформатика, кібернетика та програмування

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

Дата завантаження: 2013-08-17

Розмір файлу: 34.33 KB

Роботу завантажили: 19 чол.

1. Класифікація СМО.

Системи масового обслуговування взагалі може бути двох типів.

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

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

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

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

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

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

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

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

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

2. Математична модель процесу «загибелі та розмноження». Граф, система рівнянь.

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

Процес (або схема) розмноження та загибелі описується графом станів, наведеним на рис. 1.

Число станів дорівнює m + 1. З кожного стану w k , k = 1, 2, …, m− 1, можливі переходи тільки в сусідні стани w k-1 і w k +1 . Перехід w k → w k+1 (k = 0, 1, 2, …, m−1) означає народження деякого об'єкта, а перехід w k → w k-1 (k = 1, 2, …, m) його загибель. Отже, індекс k у позначенні w k показує кількість об'єктів, що у системі.

Мал. 1. Граф станів схеми розмноження та загибелі

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

Марківський процес відноситься до випадкових процесів з дискретними станами та безперервним часом, тобто перебування в станах та переходи між ними відбуваються у безперервному часі. Перехід із стану w i у стан w j за досить малий проміжок часу ∆t описується ймовірністю:

де λ ij ¦ параметр, званий інтенсивністю переходу w i →w j в безперервному часі, o(∆t) ¦ нескінченно мала величина більш високого порядку малості порівняно з ∆t при ∆t→0. Якщо інтенсивності не залежать від часу, процес буде однорідним, а ймовірності p ij (∆t) залежатимуть тільки від w i , w j і довжини ∆t і не залежатимуть від положення проміжку ∆t на осі часу. Для однорідного марківськогоПроцес часу перебування у кожному стані розподілено за показовим законом.

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

де ρj параметр, рівний відношенню інтенсивності переходу w j → w j + 1 до інтенсивності переходу w j + 1 → w j .

Можна сформулювати правило обчислення граничної ймовірності стану w k (k = 1, 2, …, m): ймовірність стану ≠ k дорівнює добутку параметрів ρ j для всіх переходів лівіше стану w k , помноженому на ймовірність крайнього лівого стану ≠ 0 . Слід зазначити, що з ∞ k =0 має місце процес чистого розмноження.

Один з найбільш розроблених додатків схеми розмноження та загибелі – це її використання для моделювання систем масового обслуговування.