Дослідження систем обслуговування з обмеженою чергою

Размещено на http://www.allbest.ru/

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико - математичних наук

01.05.04 - системний аналіз і теорія оптимальних рішень

ДОСЛІДЖЕННЯ СИСТЕМ ОБСЛУГОВУВАННЯ З ОБМЕЖЕНОЮ ЧЕРГОЮ

БРАТІЙЧУК АНДРІЙ МИКОЛАЙОВИЧ

Київ -2008

Дисертацією є рукопис.

Робота виконана на кафедрі прикладної статистики факультету кібернетики Київського національного університету імені Тараса Шевченка.

Науковий керівник: доктор фізико - математичних наук, професор

Лебєдєв Євген Олександрович,

Київський національний університет імені Тараса Шевченка, завідувач кафедри прикладної статистики факультету кібернетики.

Офіційні опоненти: доктор фізико-математичних наук, доцент

Коба Олена Вікторівна,

Інститут кібернетики НАН України, провідний науковий співробітник відділу математичної теорії надійності складних систем;

кандидат фізико-математичних наук,

Самойленко Ігор Валерійович,

Інститут математики НАН України, науковий співробітник відділу фрактального аналізу.

Захист відбудеться 19 червня 2008 р. о 14.00 годині на засіданні спеціалізованої вченої ради Д 26.001.35 в Київському національному університеті ім. Тараса Шевченка за адресою: 03680, м. Київ - просп. академіка Глушкова, 2, корпус 6, факультет кібернетики, ауд. 24

З дисертацією можна ознайомитись у науковій бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01033, м. Київ, вул. Володимирська, 58.

Автореферат розісланий "14" травня 2008 року.

Вчений секретар спеціалізованої вченої ради П.М. Зінько

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Становлення та розвиток теорії систем обслуговування стимулювались практичними задачами різних галузей науки і техніки і, в першу чергу, спробами наукового аналізу роботи телефонних станцій. Саме роботи відомого датського вченого А.К. Ерланга (1878-1929), який був співробітником Копенгагенської телефонної компанії, фактично привели до виникнення та становлення нової галузі науки - теорії масового обслуговування. Пізніше виявилось, що подібні задачі постають у фізиці, економіці, транспорті, військовій справі, організації виробництва та багатьох інших галузях науки і техніки. З часів, коли були опубліковані перші результати Ерланга (1908-1922), теорія систем масового обслуговування стала одним з головних підрозділів теорії ймовірностей та математичної статистики. Бурхливий розвиток обчислювальної техніки в останні роки привів до появи нового важливого підрозділу цієї теорії - теорії стохастичних мереж. Різні аспекти теорії масового обслуговування знайшли своє відображення в працях А.Я. Хінчина, О.О. Боровкова, Б.В. Гнеденка, І.М. Коваленка, Г.П. Клімова, В.А. Каштанова, В.С. Королюка, А.Ф. Турбіна, І.І. Єжова, Takacs L., Saati T., Syski R., Smith W., Rise O., Kendall D., Renyi A. та багатьох інших авторів. Найбільш загальні та цікаві результати як з теоретичної, так і практичної точок зору були отримані для систем з необмеженою чергою та пуассонівським вхідним потоком замовлень (а також для випадку експоненціального часу обслуговування).

Як відомо, більшість систем обслуговування, які зустрічаються на практиці, не можуть мати необмежену чергу. Цим і пояснюється зростання інтересу до таких систем. Треба також взяти до уваги той факт, що математичний апарат, який успішно працює у випадку необмеженої черги, виявляється непридатним для систем з обмеженою чергою. Тому дослідження систем з обмеженою чергою створили самостійний підрозділ загальної теорії. Крім уже згадуваних вище авторів, в цій області активно працювали Г.П. Башарин, І.Т. Бокучава, П.П. Бочаров, Takagi H., Miller L., Truslove A. Особлива увага при вивченні систем з обмеженою чергою приділяється обчислювальним алгоритмам для таких характеристик як ергодичний розподіл, період зайнятості, віртуальний стаціонарний час чекання, оскільки ці характеристики використовуються для розв'язку оптимізаційних задач, пов'язаних з роботою таких систем.

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

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконувалась відповідно до плану наукових досліджень кафедри прикладної статистики факультету кібернетики Київського національного університету імені Тараса Шевченка в рамках науково - дослідної теми № 06БФ015-06 "Розробка теорії і програмного забезпечення стохастичних моделей, теорії алгебраїчних систем та аналіз перспектив їх застосувань. Розробка та впровадження інформаційних технологій в освіті" (№ держреєстрації 0106U004353), а також пов'язана з тематикою DFG проекту "Асимптотичний аналіз випадкових потоків та мереж" № 436 UKR 113/94.

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

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

*провести аналіз стаціонарного режиму в системі та побудувати апроксимативний розподіл для довжини черги в стаціонарному режимі при ;

*вивчити головні функціонали від процесу обслуговування (період зайнятості, віртуальний час чекання, розподіл довжини черги) в системі ;

*дослідити сумісний розподіл періоду зайнятості та кількості замовлень, обслужених за цей період у системі ;

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

Об'єкт дослідження -- системи типу , а також системи типу

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

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

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

Наукова новизна одержаних результатів. Всі основні результати дисертаційної роботи є новими і опубліковані у фахових журналах. Основні результати дисертації:

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

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

-знайдено точні оцінки швидкості збіжності розподілу довжини черги до стаціонарного в системах ;

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

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

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

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

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

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

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

Апробація результатів дисертації. Матеріали дисертації доповідались та обговорювались на міжнародних конференціях:

-XXI Seminar on Stability Problems of Stochastic Models, Eger,Hungary, 2001;

-"Problems of Decision Making under Uncertainties" (Бердянськ, 11-17 вересня, 2005);

-"Problems of Decision Making under Uncertainties" (Алушта, 18-23 вересня, 2006);

-"Problems of Decision Making under Uncertainties" (Новий Світ, 17-24 вересеня, 2007),

а також на наукових семінарах факультету кібернетики Київського національного університету імені Тараса Шевченка та Львівського національного університету імені Івана Франка.

Публікації. За темою дисертації опубліковано 7 наукових праць, де викладені основні результати дисертації, опубліковані у фахових журналах, які затверджено ВАК України.

Структура та обсяг роботи. Робота складається зі вступу, трьох розділів, розділених на підрозділи, висновків, списку використаних джерел та додатку. Повний обсяг дисертаційної роботи становить 128 стор., вміщує 7 рисунків, 6 таблиць, 1 додаток на 3-x сторінках та список літературних джерел з 65 найменувань(7 стор.).

ОСНОВНИЙ ЗМІСТ

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

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

Позначимо:

-- кількість замовлень у системі в момент часу ;

-- довжина першого періоду зайнятості;

()-- позначає умовне математичне сподівання (умовна ймовірність) при умові, що в початковий момент часу в ній знаходиться замовлень;

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

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

-кількість замовлень у системі в момент часу ;

-довжина першого періоду зайнятості;

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

-віртуальний час чекання.

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

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

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

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

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

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

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

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

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

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

В підрозділі 2.3 запропоновано алгоритм для обчислення ергодичного розподілу кількості замовлень в системі типу. Наведено приклади реалізації цього алгоритму за допомогою пакету МАТЕМАТИКА 5. Вказано на переваги нашого алгоритму перед вже відомими.

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

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

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

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

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

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

У підрозділі 3.4 отримано зображення для перетворення Лапласа віртуального часу чекання. Наведемо лише результат для стаціонарного віртуального часу чекання.

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

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

У Додатку наведено програми на мові пакету МАТЕМАТИКА 5, які були розроблені на основі формул, отриманих у попередніх розділах.

ВИСНОВКИ

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

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

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

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

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

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

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

*Розроблено ефективні обчислювальні алгоритми для ергодичного розподілу довжини черги для системи типу , а також для розв'язування задач синтезу і оптимізації таких систем. На базі пакету МАТЕМАТИКА 5 продемонстровано ефективність цих алгоритмів для конкретних систем.

СПИСОК ОПУБЛІКОВАНИХ НАУКОВИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

*Братійчук А.М. Система з відновлюючим рівнем вхідного потоку// Вісник Київського університету.Серія: фіз.-мат. науки.-- 2007.-- № 1.-- С.114-121.

*Братійчук А.М. Граничні теореми для систем типу з відновлюючим рівнем вхідного потоку// УМЖ.-- 2007.-- Т. 59, №7.-- С. 884-890.

*Братійчук А.М. Швидкість збіжності до ергодичного розподілу довжини черги в системах типу // УМЖ.-- 2007.-- T. 59, №9.-- C. 1169-1178.

*Братійчук А.М. Точні зображення для характеристик системи з відновлюючим рівнем вхідного потоку// Вісник Київського університету.Серія: фіз.-мат. науки.-- 2007.-- № 2.-- С.114-120.

* Bratiychuk M.S., Bratiychuk A.M. Some results for the queueing system with losses// Abstracts of XXI Seminar on Stability Problems of Stochastic Models.-- Eger,Hungary, 2001.-- p.54-55.

* Bratiychuk А.М. queues with a resume level// International conference "Problems of Decision Making under Uncertаinties." Abstracts. -- Alushta, September 18-23, 2006.--P. 14.

* Bratiychuk А.М. Ergodic distribution and convergence rate for systems with finite waiting room // International conference "Problems of Decision Making under Uncertаinties." Abstracts. -- Berdyansk, September 11-17, 2006.--P. 12.

АНОТАЦІЇ

Братійчук А.М. Дослідження систем обслуговування з обмеженою чергою.- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.04 - системний аналіз і теорія оптимальних рішень. - Київський національний університет імені Тараса Шевченка, Київ,2008.

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

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

Братийчук А.Н. Исследования систем обслуживания с ограниченной очередью. - Рукопись.

Дисcертация на соискание ученой степени кандидата физико - математических наук по специальности 01.05.04 - системный анализ и теория оптимальных решений. - Киевский национальный университет имени Тараса Шевченко, Киев,2008.

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

Рассматривается также обобщение таких систем путем введения восстановительного уровня входного потока заявок. Другими словами, предполагается, что когда количество заявок в системе достигнет уровня , то их поступление блокируется и возобновляется только тогда, когда длина очереди достигнет некоторого уровня. Такие системы обозначаются символом а соответствующие функционалы снабжены дополнительным индексом . В диссертации впервые проведено систематическое изучение таких сиcтем.

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

Метод исследования интересующих нас характеристик основан на модификации метода потенциала Королюка. Предложенный метод позволил не только получить представления для преобразований Лапласа функционалов, изучаемых в диссертации с помощью стандартного подхода, а также дал возможность написать вычислительные алгоритмы и программы для стационарных характеристик, которые имеют существенные преимущества перед известными. Эти алгоритмы используются для решения оптимизационных задач, а также для синтеза систем с наперед заданными характеристиками. Так для эргодического распределения числа требований в системе получено следующее представление

Здесь обозначает потенциал (в терминологии В.С. Королюка) непрерывного снизу случайного блуждания, распределение величины скачков которого определяется последовательностью, а последовательность определяется так:

Это представление послужило основой для построения алгоритмов и программ для вычисления эргодического распределения. Аналогичный результат получен и для систем с восстановительным уровнем.

Получены оригинальные представления для преобразований Лапласа основных функционалов, а также проведен асимптотический анализ их распределений при увеличении длины очереди. Для систем с восстановительным уровнем входного потока доказаны предельные теоремы для периода занятости и числа требований, обслуженных за этот период.

Ключевые слова: система обслуживания, метод потенциала, период занятости, виртуальное время ожидания, эргодическое распределение, синтез систем, целевая функция.

Bratiichuk A.M. Investigation of the queueing systems with finite waiting space. - Manuscript.

Thesis for the degree of candidate of phisical and mathematical sciences, speciality 01.05.04 - system analysis and theory of optimal decisions. -Kyiv Taras Shevchenko national university , Kyiv,2008.

The thesis deals with queueing systems with Poisson input, general service time distribution and limited queue. Group arrival of the customers is allowed. A generalization of these systems by adding some resume level for the input stream are considered as well. To study these systems the modification of the Koroluyk's potential methods is proposed. The method proposed allowed not only to obtain the formulae for Laplace transforms functions of the functionals we are interested in by the standard approach but enables to write down the computational algorithms and programs for ergodic characteristics of the systems which have the essential advantages over known ones. These algorithms are used to study the optimization problems and to synthesize the queueing systems with characteristics given in advance. The original formulae for Laplace transform of the main functionals are obtained, and the asymptotic analysis of their distributions are performed as the queue length tends to infinity. For the systems with a resume level the limit theorems for busy period and the number of customers served during this period are obtained.

Key words: queuing system, potential method, busy period, virtual waiting time, ergodic distribution, synthesis of the systems, aim function.

Размещено на Allbest.ru