Лекція 10: Часткові випадки організації смо



Скачати 191.51 Kb.
Дата конвертації30.04.2017
Розмір191.51 Kb.

Лекція 10: Часткові випадки організації СМО




Основні питання


1. Характеристика часткових випадків організації СМО-системи з: обмеженим за довжиною черги; невпорядкованою чергою; обмеженням за часом обслуговування заявки; обмеженням за часом знаходження заявки у системі; неординарним вхідним потоком заявок; нерівноцінними каналами обслуговування.

2. Характерні особливості даних систем.

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

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



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

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

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

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

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

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

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

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

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

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

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

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

Характеристиками потоків є: однорідність, ординарність, стаціонарність, післядія, інтенсивність. Розкриємо зміст цих понять.

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



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

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



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

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

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



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

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

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

, (1)

або


, (2)

де - момент настання i-го події потоку ;



- інтервал часу між і подією потоку .

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

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



, , (3)

де позначення ті ж, що й у (1). Тимчасова діаграма можливої реалізації процесу (3), що відповідає потокові (1) і (2), зображена на мал.2.



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

. (4)

Таким чином, обидві форми (1) і (3) завдання потоку подій рівносильні.

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

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

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

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

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

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






Рис.1.На мал.1 приведений фрагмент тимчасової діаграми можливої реалізації потоку





Рис.2.Тимчасова діаграма можливої реалізації процесу, що відповідає різним потокам

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

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

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

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

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

Кожна подія потоку у цьому випадку характеризується моментом часу tj, у котрий вона настає.

Якщо потік однорідних події є цілком детермінованим, то необхідно задати послідовність tj одним з можливих способів: перерахувати їх, вказати відношення, що описує tj як функцію індексу j, або, нарешті, привести рекурентні залежності, що дозволяють визначити поточне значення tj за попередніми.

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

Звичайно буває зручним замість величин t1, t2, ..., tт розглядати випадкові величини ζ1, ζ2, ..., ζт що є довжинами часу між послідовними моментами tj,



(1.1)

Сукупність випадкових величин ζj вважається заданою, якщо визначена спільна функція розподілу



(1.2)

Звичайно розглядають тільки безперервні випадкові величини ζі, тому часто користаються відповідної (1.2) функцією щільності f(z1, z2, …, zk).

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



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

Очевидно, що для потоків з обмеженою післядією сумісна функція щільності f(z1, z2, …, zk) представляється у вигляді





(1.3)

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

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

Більш того: потік однорідних подій називається стаціонарним, якщо імовірність появи k подій за проміжок часу (t0,t0+t) не залежить від t0, а залежить тільки від t та k.

Для стаціонарних потоків з обмеженою післядією має місце співвідношення





(1.4)

Це значить, що при j>1 інтервали ζі однаково розподілені.

Розглянемо математичне очікування μ випадкової величини ζі при j>1.








Величина μ має смисл середньої довжини інтервалу між послідовними заявками.

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





(1.5)

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

У якості приклада стаціонарного потоку з обмеженою післядією можна привести потік з рівномірним розподілом інтервалів часу між заявками. Функція щільності f(z) у цьому випадку має вигляд





(1.6)

Оскільки математичне очікування величини ζ дорівнює b/2, то щільність потоку, задаваємого функцією щільності (1.6), дорівнює



(1.7)

Для стаціонарних потоків з обмеженою післядією має місце співвідношення (формула Пальма), що зв’язує функції щільності f1(z1) та f(z):



(1.8)

Використовуючи (1.8), можна отримати функцію щільності f1(z1) для різних стаціонарних потоків з обмеженою післядією. Наприклад, для потоку з рівномірним розподілом інтервалів

або




(1.9)

Легко бачити, що математичне очікування першого інтервалу ζ1 для потоку (1.6) дорівнює



(1.10)

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

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








У дослідженнях іноді доводиться мати справу із задачами, пов’язаними з обслуговуванням групових замовлень, що створюють згустки подій, тобто розглядати неординарні потоки однорідних подій. Для того, щоб описати неординарні потоки, необхідно, окрім моментів tj, задати розподіл кількості заявок, що надходять у кожний з моментів часу tj. В окремому випадку, коли кількість подій, які настають, є випадковою величиною, незалежною від моментів tj, достатньо задати імовірність pk того, що у довільний момент tj наступає рівно k подій.

Випадковий потік однорідних подій з обмеженою післядією може бути потоком без післядії, якщо відсутня імовірностна залежність наступного ходу подій у потоці від попереднього. Точніше, потік однорідних подій називається потоком без післядії, якщо імовірність настання k подій за проміжок часу (t, t0+t) не залежить від ходу подій до моменту t0 і дорівнює безумовній імовірності тієї ж події.



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

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

Можна строго довести, що для найпростішого потоку імовірність pk(t) настання k подій за інтервал часу довжини t виражається законом розподілу Пуассона





(2.1)

Тому часто найпростіший потік називають пуассоновським потоком.

З (2.1) випливає, що функція щільності f(z) випадкової величини ζj при j>0 простішого потоку має вигляд показового розподілу з параметром λ





(2.2)

де λ – інтенсивність (щільність) потоку.

У відповідності з формулою Пальма (1.8) можна знайти функцію щільності f1(z1) для першого інтервалу ζ1:



або




(2.3)

Таким чином, у випадку найпростішого потоку f1(z1)=f(z). Як легко бачити з попереднього прикладу, у загальному випадку це невірно.

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



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

Потоком Ерланга порядку m називається ординарний стаціонарний потік з обмеженою післядією, для якого



(2.4)

Щільність (інтенсивність) цього потоку







Легко визначити, що інтервали ζj при j>0 потоку Ерланга порядку m можна подати у вигляді суми m незалежних випадкових величин, що мають показовий розподіл з параметром λ*.

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

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

У загальному випадку для m доданків



(2.5)

Для випадку двох доданків




(2.6)

Інтенсивність такого потоку λ може бути обчислена за формулою:



(2.7)

Розподіл довжини першого інтервалу ζ1 має вид:



(2.8)

Аналогічно для випадку трьох доданків




(2.9)



(2.10)



(2.11)

Інше узагальнення потоку Ерланга виглядає наступним чином.

Нехай інтервали ζj при j>0 є сумами незалежних випадкових величин, рівномірно розподілених у інтервалах (0, bj), відповідно.



Наприклад, у випадку двох доданків з параметрами b1 та b2 при b12 отримаємо функцію щільності f(z) у виді



(2.12)

Інтенсивність потоку такого типу




(2.13)

Розподіл довжини першого інтервалу ζ1



(2.14)

Для розв”язку ряду прикладних задач буває необхідним аналізувати потоки, у яких інтервали ζі є сумами постійної а та випадкової величини ξ.

У випадку, коли ξ має показовий розподіл з параметром λ*, маємо




(2.15)



(2.16)



(2.17)

Якщо ξ має рівномірний розподіл у інтервалі довжиною b–a, то



(2.18)



(2.19)



(2.20)

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

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

,

(2.21)

де



(2.22)

Змінна Λ(t0, t) є математичним очікуванням числа подій, що виникають за інтервал часу (t0, t0+t).

Функція λ(t0) є функцією миттєвої щільності потоку у момент t0, а величина – середньою щільністю потоку у інтервалі часу (t0, t0+t).

Виходячи з (2.21), легко знайти закон розподілу довжини інтервалу часу між довільним моментом t та моментом настання чергової події. Насправді,



(2.23)

Диференціюючи (2.23) по u, отримаємо функцію щільності



(2.24)

Помітимо, що функція щільності f1(z) для першого інтервалу буде мати вигляд

,

(2.25)

а у випадку довільного інтервалу виражається співвідношенням (2.24).

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

У загальному випадку система масового обслуговування може складатися з n ліній, здатних одночасно та незалежно один від одного обслуговувати заявки. У будь-який момент часу лінія знаходиться в одному з двох станів – лінія вільна або лінія зайнята.



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


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка