Методи теорії імовірності розв’язку задач в автоматизованих системах; теорія масового обслуговування

В теорії масового обслуговування розглядаються задачі планування і управління робіт по задоволенню потоку вимог, що виникають випадково та вимагають різного, зараннє точно непередбаченого часу для їх задоволення. Типовими виробничими задачами такого роду є роботи по ремонту та наладці обладнання. Інші приклади задач: обслуговування покупців у магазині, медичне обслуговування, продаж квитків, організація інформаційно-довідкової служби, телефонний та телеграфний зв’язок і т.п.

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

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

Важливою характеристикою довільного потоку вимог є час Т між моментом виникнення одної та безпосередньо наступної за ним вимоги. Ця величина випадкова і характеризується деяким законом розподілу. Для пуасоновського потоку з інтенсивністю ймовірність того, що час Т замкнений в границях від х до х+ dх з точністю до безкінечно малих вищих порядків дорівнює еdx. Таким чином, ймовірність РT A того, що Т А, дорівнює

e-xdx =1- е.

Отже, ймовірність того, що Т А є е. Це так званий показовий закон розподілу.

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

РN = k = -е.

Це – є так званий розподіл Пуасона, за ім’ям якого і названий відповідний потік.

(РN= k є ймовірність того, що на протязі часу t буде отримано k вимог).

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

Показовий розподіл достатньо добре описує розподіл тривалості телефонних розмов і ряд інших прикладів.

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

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

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

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

Існує два основних методи:

Метод математичного моделювання.

Аналітичні методи.

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

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

___________________________________________________

0 1 2 3 4 5 Довжина черги

Із гістограми видно, що довжина черги, що дорівнює нулю, зустрічалась 10 разів, а довжина черги, рівна трьом – 25 разів, що відповідає експериментальним ймовірностям

Р0 = = .1 та Р3 = = .25.

Середнє значення довжини черги

n0 = 0P0 + 1P1 +2P2 + 3P3 + 4P4 + 5P5 = 0 + .2 +.6 +.75