ВСТУП ТА ОСНОВНИЙ ЗМІСТ РОБОТИ
Національна академія наук України
Інститут кібернетики імені В.М. Глушкова
Коба Олена Вікторівна
УДК 519.872
Дослідження систем обслуговування з поверненням заявок
при неекспоненціальному розподілі часу перебування на орбіті
01.05.02 – математичне моделювання та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
доктора фізико-математичних наук
Київ – 2005
Дисертацією є рукопис.
Робота виконана в Інституті комп’ютерних технологій Національного авіаційного університету.
Науковий консультант: академік НАН України, доктор фізико-математичних наук, доктор технічних наук, професор
Коваленко Ігор Миколайович,
Інститут кібернетики ім. В.М. Глушкова НАН України,
завідувач відділу математичних методів
теорії надійності складних систем.
Офіційні опоненти: доктор фізико-математичних наук, професор
Єлейко Ярослав Іванович,
Львівський національний університет ім. І.Франка,
завідувач кафедри теоретичної та прикладної статистики,
доктор фізико-математичних наук, професор
Кнопов Павло Соломонович,
Інститут кібернетики ім. В.М. Глушкова НАН України,
завідувач відділу математичних методів дослідження операцій,
доктор технічних наук, професор
Тоценко Віталій Георгійович,
Інститут проблем реєстрації інформації НАН України,
завідувач відділу надійності і технічної діагностики систем реєстрації і обробки інформації.
Провідна установа: Київський національний університет ім. Т.Шевченка, факультет кібернетики.
Захист відбудеться ”28” жовтня 2005 року об 11 годині
на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: 03680,
м. Київ – 187, проспект академіка Глушкова, 40.
З дисертацією можна ознайомитись у науково-технічному архіві
Інституту кібернетики ім. В.М. Глушкова.
Автореферат розісланий ”22” вересня 2005 року.
Вчений секретар
спеціалізованої вченої ради В.Ф.Синявський
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Задачі дослідження ефективності великомасштабних систем – таких, як мережа телефонного зв’язку, злітно-посадкова система аеропорту, система організації черг у мережах обміну інформацією тощо – потребують створення математичних моделей з урахуванням стохастичного характеру відповідних процесів. Для побудови моделі того чи іншого явища або системи потрібно виходити з певного класу випадкових процесів. Саме на теорії випадкових процесів ґрунтується теорія масового обслуговування. Ця теорія на протязі кількох останніх десятиріч здобула чільне місце у питаннях моделювання систем з дискретними подіями. Це пояснюється тим, що методами цієї науки принципово можливо досліджувати широке коло випадкових факторів. Один із творців теорії О.Я.Хінчин наголошував, що на противагу іншим математичним моделям, де стохастика виступає лише як мале збурення детермінованого процесу, у моделях обслуговування випадковість – це головне. Б.В.Гнєденко зауважував, що формули теорії масового обслуговування (наприклад, вираз для середнього часу чекання заявки) принципово неможливо замінити розрахунком через самі середні значення.
Величезних застосувань до моделювання реальних явищ набули дискретні марковські моделі. Це пояснюється насамперед їхньою простотою, наочністю та можливістю виводити прозорі аналітичні вирази для потрібних дослідникові характеристик систем. Нехай A(x) – функція розподілу часу між надходженням до системи заявок, B(x) – функція розподілу часу обслуговування заявки. Дискретна марковська модель ґрунтується на гіпотезі експоненціальності обох розподілів.
Чи можна вживати формули, що їх отримано в експоненціальних припущеннях, у тому випадку, коли A(x) або B(x) – неекпоненціальна функція? Така проблема має велике теоретичне та практичне значення. У рамках класичних моделей теорії систем та мереж обслуговування багатьма дослідниками створено теорію нечутливості (інваріантності) характеристик систем (переважно з відмовами) до виду розподілів A(x) та B(x). Слід відзначити піонерську роль у цих дослідженнях відомих учених: Б.О.Севастьянова; учнів Б.В.Гнєденка – І.М.Коваленка, Т.П.Мар’яновича, Т.І.Насірової та інших; В.А. та О.В.Івницьких; О.М.Дудіна, В.І.Кліменок, Ю.В.Маленковича та деяких інших. В останніх статтях І.М.Коваленка та його співавторів розвинуто новий напрямок – так звану асимптотичну нечутливість – light-traffic insensitivity.
У випадку, коли нечутливість не має місця, потрібно розв’язати такі задачі:
– віднайти умови ергодичності або принаймні стохастичної обмеженості процесу обслуговування;
– вивести аналітичну формулу для актуальної характеристики процесу, якщо це можливо;
– розробити алгоритм стохастичного моделювання для досить загальної математичної схеми та методологію перевірки адекватності моделі.
Напевне, неможливо в окремому дослідженні розв’язати усі ці задачі для найзагальнішої схеми стохастичних мереж. З огляду на складність проблеми, виправданим є створення методу дослідження ергодичності процесу обслуговування для окремого, але досить широкого і практично обґрунтованого, класу стохастичних моделей. За такий клас у нашому дослідженні взято системи обслуговування з поверненням заявок (повторенням викликів), що слугують адекватними моделями систем доступу в комп’ютерних мережах, систем телефонного зв’язку, процесів управління повітряним рухом.
Теорія систем з повторенням заявок активно розвивається, починаючи з 80-х років 20-го століття. У класичній теорії масового обслуговування, в створення якої основоположний внесок зробила, зокрема, школа академіка Б.В.Гнєденка, розглядають системи без блокування заявок; таким чином, при наявності вільного каналу заявка, що є в системі, спрямовується в нього негайно. Очевидно, такі моделі являють собою ідеалізовану картину реальних процесів. У більшості реальних моделей, особливо тих, що описують роботу комп’ютерних мереж, заявка блокується від обслуговування до моменту, коли створюються умови для її обслуговування, навіть у випадку, коли канал вільний. Одним із важливих типів систем з блокуванням є системи з поверненням (повторенням) заявок. Так, у звичайному телефонному зв’язку, почувши часті гудки, абонент повторює виклик через випадковий час . Під час посадки повітряного судна (ПС) у випадку зайнятості злітно-посадкової смуги аеропорту (або з інших причин) ПС спрямовується в зону чекання, щоб повернутися через сталий (в достатньому наближенні) час T. Подібна ж ситуація має місце і в системах доступу в мережах ЕОМ.
Автором запропоновано узагальнену модель функціонування системи обслуговування з поверненням заявок, що охоплює відомі в літературі моделі, та розроблено метод дослідження ергодичності відповідних випадкових процесів. Виведено цілу низку аналітичних виразів для характеристик систем з поверненням заявок. Розроблено алгоритм статистичного моделювання та підхід до порівняння різновидів систем при тому самому навантаженні кожного з них.
Проаналізувавши літературу, ми впевнилися в актуальності нашого дослідження, оскільки в наявних роботах, за винятком окремих робіт Л.Г.Афанасьєвої, А.А.Borovkov і Е.Altman, L.Lakatos, зазвичай розглядається окремий випадок закону повернення заявок, а саме, експоненціальний закон (див., напр., роботи Г.І.Фаліна, О.М.Дудіна, В.І.Кліменок, В.В.Анісімова, А.А.Назарова, Д.Ю.Кузнєцова, J.G.C. Templeton, J.R.Artalejo, V.G.Kulkarni, J.Keilson, J.Cozzolino, H.Young, K.Farahmand, N.H.Smith, M.Martin, C.Fricker). Натомість у нашому дослідженні ми майже всюди досліджуємо немарковський закон: час повернення заявки (час перебування на орбіті) має або загальну функцію розподілу D(x), або є детермінованим.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась в Інституті комп’ютерних технологій Національного авіаційного університету (НАУ). ЇЇ результати отримано, зокрема, при виконанні науково-дослідних робіт за темами:
– “Провести дослідження та аналіз методів і засобів побудови інформаційно-комп’ютерних систем на основі інтранет-технологій” (реєстраційний №0103U000692);
– “Стохастичний аналіз бездротових комунікаційних мереж” (міжнародний проект ADLON, реєстраційний №М/418-2003).
Участь автора у цих науково-дослідних темах полягала у розробці моделей мереж з урахуванням повторних викликів, дослідженні умов ергодичності спеціального вигляду систем, розробці та реалізації алгоритмів стохастичного моделювання систем з повторними викликами, порівняльного аналізу результатів моделювання.
Завершальний етап дисертаційної роботи виконувався у докторантурі НАУ (2001-2004).
Мета і завдання дослідження. Метою дослідження є розробка узагальненої моделі широкого класу систем обслуговування з поверненням заявок та здобуття умов їх стохастичної обмеженості та ергодичності. Завданнями, що випливають з цієї мети, є:
– розробка моделі, що охоплює найвідоміші випадки систем з повторенням заявок, у нових, загальніших за відомі, припущеннях про потік, обслуговування та час повернення;
– математична схематизація критеріїв якості роботи системи як функціоналів від випадкового процесу або послідовності;
– обрання математичного апарату для дослідження ергодичності систем;
– віднайдення умов ергодичності типових систем з поверненням заявок;
– здобуття аналітичних формул для характеристик систем для низки конкретних моделей;
– обрання методів статистичного моделювання систем з поверненням заявок з урахуванням параметрів системи, проведення статистичного експерименту та аналізу його результатів.
Об’єкт дослідження – системи масового обслуговування з поверненням заявок при загальних припущеннях щодо процесу надходження заявок, розподілу часу обслуговування та розподілу часу повернення.
Предмет дослідження – математичні моделі систем з поверненням заявок, їх стійкість та ергодичність.
Методи дослідження – теорія ланцюгів Маркова у метричному просторі станів, методи теорії відновлення та теорії неоднорідних випадкових блукань.
Наукова новизна одержаних результатів. У дисертаційній роботі побудовано теорію аналізу ергодичності систем обслуговування з поверненням заявок при неекспоненціальному законі повернення (часу перебування на орбіті). У межах цієї теорії одержано такі результати:
– уперше схематизовано широкий клас типових систем з поверненням заявок при загальному рекурентному потоці заявок, загальному розподілі часу обслуговування та неекспоненціальному законі повернення з орбіти;
– узагальнено відому модель Лакатоша та до кінця досліджено умову її ергодичності, а також виведено формули для її характеристик у стаціонарному випадку;
– досліджено системи з T-поверненням та з -поверненням, що виникли з аналізу процесів управління повітряним рухом, та віднайдено оцінки області їх ергодичності;
– уперше введено поняття системи з пріоритетом затриманих заявок та дано непокращуванну у деякому сенсі умову її ергодичності;
– уперше отримано формули та оцінки основних характеристик низки систем з поверненням заявок та складним характером обслуговування (обмежений час очікування, обмежене число повернень заявки тощо);
– уперше аналітично порівняно одну з характеристик ефективності для двох різновидів систем при швидкому поверненні заявок з орбіти;
– розроблено підхід до статистичного моделювання системи з поверненням заявок, проведено статистичний експеримент та порівняно різновиди системи.
Практичне значення одержаних результатів полягає насамперед у тому, що при проектуванні систем замість моделі експоненціального повернення заявок можна обирати точнішу неекспоненціальну модель, що значно покращить адекватність і отже точність розрахунків. При дослідженні складних систем типу авіаційних єдиним універсальним методом є статистичне моделювання; водночас при спрощенні системи, тобто “відрубанні” деяких логічних гілок процесу, ми отримаємо таку систему, для якої існує аналітична формула (скажімо, розподілу часу чекання заявки). На такій спрощеній моделі можна перевірити результати моделювання. Але найголовніше те, що ми розробили підхід, який можна наслідувати при дослідженні багатьох складніших систем з різними особливостями обслуговування.
Отримані результати можуть бути ефективно використані при досліджені ймовірнісних характеристик телекомунікаційних мереж і комп’ютерних систем.
Результати дисертації також впроваджено в навчальний процес Інституту комп’ютерних технологій НАУ.
Особистий внесок здобувача. Усі результати дисертаційної роботи отримано особисто або за участю автора. У роботах, написаних у співавторстві, здобувачу належать такі результати:
[4] – вироблено схему з -поверненням заявок та алгоритм оцінки розподілу часу чекання;
[9] – сформульовано принцип порівняння характеристик двох систем з поверненням заявок та отримано якісний результат порівняння у випадку малого навантаження;
[10] – отримано умову ергодичності системи RQ типу M/G/1 (співавторові належить доведення леми 2);
[15] – отримано асимптотичну оцінку числа циклів заявки на орбіті для системи RQ типу M/D/1 (співавторові належить уточнення оцінок).
Апробація результатів дисертації. Основні положення дисертації доповідалися та обговорювалися на конференціях: Міжнародна наукова конференція, присвячена 90-річчю від дня народження академіка Б.В.Гнєденка (Київ, 2002), Міжнародна наукова конференція “Современные математические методы анализа и оптимизации телекоммуникационных сетей” (Білорусь, Гомель, 2003), Міжнародна науково-технічна конференція, присвячена 90-річчю від дня народження академіка О.І.Кухтенка (Київ, 2004), Міжнародні науково-технічні конференції : АВІА-1999 (Київ, 1999), АВІА-2003 (Київ, 2003), АВІА-2004 (Київ-2004), а також на наукових семінарах у НАУ, НТУУ “КПІ”, Інституті кібернетики ім. В.М.Глушкова НАН України.
Публікації. За результатами дисертаційної роботи опубліковано 29 наукових праць, з них: статей у фахових журналах, затверджених ВАК України, – 21 (17 без співавторів), статей у збірниках наукових праць – 2, матеріалів конференцій – 6.
Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, 7 розділів, висновків, списку використаних джерел, двох додатків. Повний об’єм дисертації – 395 сторінок, з них: основний текст – 306 сторінок, ілюстрації (33 рисунки і 1 таблиця) – 23 сторінки, додатки – 34 сторінки, список використаних джерел, що включає 302 найменування, – 32 сторінки.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовується актуальність теми дисертаційної роботи, формулюється мета і задачі дослідження, викладено короткий зміст дисертації і отриманих у ній результатів, виділено їх наукову новизну і практичну цінність.
У першому розділі дано огляд літератури за темою дисертації і визначено напрямки досліджень.
У другому розділі запропоновано класифікацію типових систем з поверненням заявок і поставлено основні задачі їх дослідження, а також дано мотивацію їх актуальності для системного аналізу. Відзначено, що у дуже широкому класі випадків стохастична послідовність, що описує поведінку системи, являє собою регенеруючий процес. Ця властивість спрощує аналіз.
У розділі запропоновано деякий легко досяжний для розуміння клас типових систем з поверненням заявок, який має практичне значення і значно загальніший, ніж ті, що їх досліджено в літературі.
Розділ 3 присвячено узагальненню моделі Лакатоша та дослідженню відповідних ергодичних та аналітичних властивостей.
Розділ 4 присвячено доведенню ергодичних теорем для систем з T-поверненням при знятті умови обслуговування в порядку черги, а також системи з -поверненням.
У розділі 5 досліджується умова ергодичності класичної системи з поверненням типу M/G/1 при негратчастому розподілі часу заявки на орбіті.
У розділі 6 розглянуто вісім різних модифікацій систем з поверненням заявок. Усі ці моделі відображають певні особливості реальних процесів.
Розділ 7 присвячений статистичному моделюванню систем з поверненням заявок.
У додатку А зібрано необхідні відомості з теорії ймовірностей на строгому аксіоматичному рівні. Відомі результати належним чином “препаровано” для використання в основному тексті. Так, маючи на увазі процеси масового обслуговування з додатковими компонентами, ми означаємо розподіли ймовірностей на зв’язках (об’єднаннях) евклідових просторів різної розмірності. Для відповідних просторів станів викладаються елементи ланцюгів Маркова. Викладено теорему про умови, достатні для ергодичності ланцюга Маркова з довільною множиною станів та виділеним “нульовим” станом. Наведено також необхідні факти з теорії відновлення.
Додаток Б – це довідки про впровадження результатів дисертації.
ВИСНОВКИ
У дисертаційній роботі розроблено новий науковий напрямок у математичному моделюванні систем масового обслуговування, а саме, розроблено методи дослідження стійкості та ергодичності систем обслуговування з поверненням заявок (з повторенням викликів) при неекспоненціальному розподілі часу перебування на орбіті та досліджено широке коло таких систем.
Отримані автором результати дозволяють підвищити адекватність та точність математичних моделей, використовуваних у дослідженні таких процесів, як функціонування злітно-посадової смуги, організація доступу у мережах ЕОМ тощо, відмовившись від традиційного припущення, що час повторення заявки розподілений за експоненціальним законом.
Основними науковими результатами дисертаційної роботи є такі:
1.
Проаналізовано велику кількість літературних джерел, включаючи найновіші джерела світової літератури, що стосуються систем з повторними викликами. Виявилося, що майже всі автори обмежуються розглядом систем з експоненціальним розподілом часу повернення заявки (часу на орбіті) – не існувало загального підходу до дослідження систем з неекспоненціальним розподілом. Водночас вивчення прикладних систем свідчить про те, що розгляд неекспоненціальної орбіти є досить актуальним.
2.
Вироблено узагальнену схему типових систем з поверненням заявок.
3.
Вироблено загальний підхід до побудови випадкового процесу, що описує дію системи обслуговування з поверненням заявок. Таким процесом є ланцюг Маркова
, де
– основна змінна,
– додаткова змінна. Основна змінна інтерпретуються, як величина черги у момент надходження n-ої заявки або закінчення n-го обслуговування;
– вектор додаткових змінних, що вказують на час до реалізації або час від реалізації тієї чи іншої події.
4.
Для моделювання найважливіших показників якості обслуговування у різних реальних системах дано схему функціоналів від процесу
. Визначено поняття “стійкості”, стохастичної обмеженості та ергодичності системи по відношенню до того чи іншого функціоналу.
5.
Віднайдено загальний підхід до встановлення стохастичної обмеженості ланцюга Маркова
. З цією метою зауважено, що для типових систем з поверненням заявок існують моменти очистки, коли система є вільною від вимог, та моменти відновлення, коли майбутня поведінка системи не залежить від попередньої історії. Ергодичну теорему, сформульовано у вигляді, який найзручніший у застосуванні до систем з поверненням заявок.
6. Значно узагальнено систему Ласло Лакатоша з T-поверненням заявок та дисципліною обслуговування в порядку черги: ми дослідили загальний рекурентний потік заявок, загальний розподіл часу обслуговування та часу перебування на орбіті. Окремо досліджено випадки, коли розподіл часу перебування на орбіті гратчастий та негратчастий. В обох випадках віднайдено умову ергодичності, яку істотно покращити неможливо.
Цей результат узагальнено на систему типу Лакатоша, в якій інтервали між заявками, часи обслуговування та перебування на орбіті залежать від ергодичного ланцюга Маркова зі скінченною множиною станів.
7. Віднайдено достатню умову ергодичності одноканальної системи з -поверненням.
8. Для системи PRIOR типу GI/D/m автор виводить достатню умову ергодичності системи, яку істотно покращити неможливо.
9. Віднайдено універсальну непокращуванну умову ергодичності системи RQ з Т-поверненням типу GI/G/1.
10. Порівняно дві системи з поверненням заявок типу M/M/1.
Досліджено умову ергодичності системи RQ типу M/G/1 за умови, що D(x) – негратчаста функція розподілу.
Досліджено вісім різних модифікацій систем з поверненням заявок. Усі ці моделі відображають певні особливості реальних процесів.
11. Розроблено алгоритм статистичного моделювання типових систем у межах періоду зайнятості, що ґрунтується на рекурентному алгоритмі локальних змін випадкового процесу.
12. Для статистичної оцінки критичного значення навантаження типових систем з поверненням заявок застосовано метод прямого моделювання.
13. З усієї сукупності результатів дисертації випливає, що неекспоненціальність розподілу часу на орбіті призводить до інших характеристик процесу обслуговування, ніж ті, що спостерігаються в експоненціальному випадку. Це є пересторогою для дослідників щодо застосування відомих “експоненціальних” формул. Водночас ми вказуємо досить загальний метод аналізу систем з “неекспоненціальною” орбітою.
14. Результати дисертації можна застосовувати для тестування алгоритмів та програм статистичного моделювання значно складніших систем з поверненням заявок, ніж ті, що ми їх розглянули. Зокрема, типовим є випадок, коли при спрощенні моделі реального процесу або за умови малого навантаження модель стає подібною до деякої типової моделі, яку можна дослідити аналітичним методом.
Результати дисертації можна також використовувати в учбовому процесі для викладання теорії систем масового обслуговування, їх моделювання та проектування.
РОБОТИ АВТОРА ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.
Коба Е.В. О системе обслуживания GI/G/1 с повторением заявок при обслуживании в порядке очереди // Доповіді НАН України. – 2000. – №6. – С. 101-103.
2.
Koba E.V. On a GI/G/1 retrial queueing system with a FIFO queueing discipline // Theory of Stochastic Processes. – 2002. – 24, №8. – Р. 201-207.
3.
Коба Е.В. Условие эргодичности обобщенной модели обслуживания типа Л.Лакатоша // Доповіді НАН України. – 2004. – №11. – С. 70-74.
4.
Коваленко И.Н., Коба Е.В. Три системы обслуживания с повторными вызовами, отражающие некоторые особенности процесса посадки воздушных судов // Проблемы управления и информатики. – 2002. – №2. – C. 78-82.
5.
Коба Е.В. Системы обслуживания с ограниченным снизу временем возвращения заявок // Проблемы управления и информатики. – 2004. – №3. – С. 153-157.
6.
Коба Е.В. Достаточное условие эргодичности системы М/D/1 с Т-возвращением и приоритетом задержанных заявок // Доповіді НАН України. – 2003. – №5. – С. 17-20.
7.
Коба О.В. Достатня умова стійкості системи обслуговування GI/D/m з Т-поверненням і пріоритетом затриманих заявок // Доповіді НАН України. – 2004. – №9. – С. 65-70.
8.
Коба О.В. Умова стійкості системи обслуговування GI/G/1 з Т-поверненням заявок // Системні дослідження та інформаційні технології. – 2005. – №1. – C.39-43.
9.
Коба О.В., Михалевич К.В. Порівняння систем типу M/M/1 з швидким поверненням заявок при різних дисциплінах обслуговування // Системні дослідження та інформаційні технології. – 2003. – №2. – С. 59-68.
10.
Коба О.В., Коваленко І.М. Умова ергодичності для системи M/G/1 з повторенням викликів при негратчастому розподілі циклу на орбіті // Доповіді НАН України. – 2004. - №8. – С. 70-77.
11.
Коба Е.В. Условия устойчивости некоторых типовых систем обслуживания с возвращением заявок // Кибернетика и системный анализ. – 2005. – №1. – C. 124-127.
12.
Коба Е.В. О производительности замкнутой сети с показательным временем обслуживания и периодически повторяющимися заявками абонентов // Кибернетика и системный анализ. – 2000. – №3. – С. 176-179.
13.
Коба Е.В. О производительности процессора, обслуживающего двух абонентов, при постоянном времени повторения заявки // Доповіді НАН України. – 2000. – №10. – С. 104-106.
14.
Коба Е.В. Система обслуживания M/D/1 с заявками, повторяющимися через постоянное время, при частичной синхронизации входящего потока // Кибернетика и системный анализ. – 2000. – №6. – С. 177-180.
15.
Коваленко И.Н., Коба Е.В. О двусторонней оценке распределения числа циклов на орбите для одной системы обслуживания с повторением заявок // Доповіді НАН України. – 2000. – №9. – С. 109-112.
16.
Коба Е.В. Об условии устойчивости системы обслуживания M/D/1 с повторяющимися заявками и ограниченным временем ожидания // Кибернетика и системный анализ. – 2000. – №2. – С. 184-186.
17.
Коба Е.В. Вероятность потери заявки в замкнутой и разомкнутой системах обслуживания типа M/D/1 с ограниченным временем ожидания // Доповіді НАН України. –2002. – №5. – С. 72-76.
18.
Коба Е.В. Об одной системе обслуживания с повторением и выталкиванием заявок // Проблемы управления и информатики. – 2001. – №1. – С. 58-62.
19.
Коба Е.В. Вероятность потери заявки в системе обслуживания M/D/1 с постоянным временем возвращения // Доповіді НАН України. – 2002. – №4. – С. 61-66.
20.
Коба Е.В. Система обслуживания пуассоновского потока сдвоенных заявок // Доповіді НАН України. – 1995. – №3. – С. 9-11.
21.
Коба Е.В. Исследование эргодичности систем обслуживания с возвращением заявок методом статистического моделирования // Проблемы управления и информатики. – 2004. – №6. – С. 106-115.
22.
Коба О.В. Стаціонарні характеристики системи масового обслуговування GI/G/1 із Т-поверненням при обслуговуванні в порядку черги // Вісник Національного авіаційного ун-ту. – 2003. – №1. – С. 122-125.
23.
Коба О.В. Системи обслуговування з повторенням заявок при детермінованому часі перебування на орбіті // Вісник Національного авіаційного ун-ту. – 2002. – №3. – С. 69-73.
24.
Koba O.V. Stability and ergodicity conditions for a GI/G/1 retrial queueing system with FIFO queueing discipline // Abstracts of the International Gnedenko Conference. – 2002. – Kyiv. – P.51.
25.
Коба О.В., Михалевич К.В. Ефект швидкого повернення з орбіти в системах типу M/M/1 з FCFS дисципліною обслуговування // Матеріали V Міжнародної науково-технічної конференції АВІА-2003. – Київ. – 2003. – С. 14.83-14.86.
26.
Коба О.В. Дослідження системи GI/G/1 з довільною орбітою і FCFS дисципліною обслуговування // Матеріали V Міжнародної науково-технічної конференції АВІА-2003. – Київ. – 2003. – С. 14.79-14.82.
27.
Коба Е., Михалевич К. Сравнение систем обслуживания типа M/G/1 с повторением при быстром возвращении с орбиты // Материалы международной научной конференции “Современные математические методы анализа и оптимизации телекоммуникационных сетей”. – 2003. – Гомель. – С. 136-138.
28.
Коба О.В. Системи масового обслуговування з повторенням заявок і складною дисципліною обслуговування // Матеріали VI Міжнародної науково-технічної конференції АВІА-2004. – Київ. – 2004. – С. 13.85-13.88.
29.
Коба Е.В., Михалевич К.В. Исследование систем обслуживания с циклическим временем ожидания // Матеріали міжнародної науково-технічної конференції, присвяченої 90-річчю від дня народження академіка НАН України О.І.Кухтенка. В сб. Проблемы информатизации и управления. – 2004. – №11. – С. 131-134.
АНОТАЦІЇ
Коба О.В. Дослідження систем обслуговування з поверненням заявок при неекспоненціальному розподілі часу перебування на орбіті. – Рукопис.
Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Інститут кібернетики ім. В.М.Глушкова НАН України, Київ, 2005.
Головною проблемою, на вирішення якої спрямоване дослідження, є віднайдення умов стохастичної обмеженості та ергодичності випадкової послідовності, що описує функціонування систем з поверненням заявок при неекспоненціальному розподілі часу перебування заявки на орбіті. Складність математичної задачі спричиняється необхідністю вивчати багатовимірні випадкові послідовності (процеси з додатковими змінними), якщо відмовитися від звичайного припущення, що час повернення заявки – експоненціально розподілена величина. Саме на аналізі цього складного випадку зосереджено дослідження здобувача.
Автором вироблено узагальнену стохастичну модель типових систем з поверненням заявок. Ця модель характеризується: числом каналів, рекурентним потоком заявок з ф.р. (функцією розподілу) інтервалу між заявками, ф.р. часу обслуговування заявки, ф.р. часу повернення (повторення) заявки, а також додатковими ознаками, пов’язаними з дисципліною доступу заявок до каналу та певними часовими обмеженнями. Виділено системи: – чиста система з поверненням заявок, – система типу Лакатоша, в якій обслуговування відбувається в порядку черги, – система, в якій надається пріоритет затриманим заявкам перед тими, що надходять вперше, а також системи з -поверненням, -поверненням, з обмеженим числом повернень заявки. Виділено також багато інших різновидів систем.
Розвинуто загальний підхід до побудови ланцюга Маркова у метричному просторі, що описує функціонування системи, та дослідження його ергодичності. Віднайдено умови стохастичної обмеженості та ергодичності відповідних ланцюгів Маркова для типових систем. Віднайдено низку аналітичних формул для характеристик систем. Розвинуто метод статистичного моделювання.
Ключові слова: спеціальні випадкові процеси, системи обслуговування з повторними викликами, стійкість систем обслуговування, ергодичність систем обслуговування, управління повітряним рухом, статистичне моделювання систем.
Koba O.V. Investigation of retrial queueing systems with non-exponential orbit time. – Manuscript.
Thesis for a doctor’s degree in physics and mathematics, speciality 01.05.02 – mathematical modeling and numerical methods. – V.M.Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, 2005.
Our work is directed towards the main problem of the development of a mathematical method for the investigation of system stability. This problem can be formulated in a rigorous way as a search for conditions of stochastic boundnedness and ergodicity of a random sequence describing the system behaviour. The complexity of the mathematical problem is due to the necessity of the studying of a multidimensional random sequence (a process with supplementary variables) as long as one violates a common-used assumption of the exponentiality of the retrial time distribution. Just this hard case, that of a non-exponential retrial time, is analyzed in the thesis.
The author is carried out a generalized stochastic model of typical retrial queueing systems. The model is characterized by: a number m of channels; the d.f. (hereinafter distribution function) A(x) of the inter-arrival time; d.f. B(x) of the service time; d.f. D(x) of the retrial time, and also some extra characteristics relating the access discipline and time restrictions. A practically important situation if the retrial time equals a constant T, is called as “T-retrial”. We consider such most typical systems: RQ – a system with “pure” retrial; L – Lakatos type retrial system in which the FCFS discipline is admitted; PRIOR – the retrial queue in which delayed customers possess a priority upon newly arriving ones; (=T)-retrial system in which the waiting time of a delayed customer is at least T; a system with a bounded number of retrials of a customer. A number of other modifications are considered, as well.
We developed a general approach to the construction of a Markov chain in a metric space for the description of the system evolution and the investigation of its stability. There are derived stochastic boundedness and ergodicity conditions of appropriate Markov chains for typical systems. A number of analytical expressions for system parameters is also derived. Appropriate simulation procedures are developed.
Key words: special stochastic processes, retrial queues, stability of queues, ergodicity of queues, air control, system simulation.
Коба Е.В. Исследование систем обслуживания с возвращением заявок при неэкспоненциальном распределении времени пребывания на орбите. – Рукопись.
Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Институт кибернетики им. В.М.Глушкова НАН Украины, Киев, 2005.
Объектами исследования являются системы массового обслуживания с возвращением заявок (с повторными вызовами), теория которых развита, начиная с 80-х гг. ХХ ст. в ответ на запросы моделирования реальных процессов в коммуникационных системах, авиации и т.п. Данному классу систем посвящены исследования Г.И.Фалина, А.А.Боровкова, Л.Г.Афанасьевой, Д.Ю.Кузнецова, А.А.Назарова, А.Н.Дудина, В.М.Клименок, В.В.Анисимова, L.Lakatos, J.G.C. Templeton, J.R.Artalejo, V.G.Kulkarni и многих других авторов.
Следует заметить, что только отдельные работы (Л.Г.АфанасьеваАфанасьєва Л.Г. Об условии эргодичности систем обслуживания с повторными вызовами // Труды семинара ВНИИСИ: Устойчивость стохастических сиcтем. – Москва, 1991. – С., Altman E, Borovkov Altman E, Borovkov A.A. On the stability of retrial queues // Baltzer Journals. – 1996-1997. – P.1-19., Lakatos Cм. цикл работ периода 1994-2005 гг.) посвящены исследованию систем с неэкспоненциальным распределением времени возвращения заявки. Основной проблемой, на решение которой направлено исследование, является построение математического метода изучения устойчивости системы, строго формулируемое как отыскание условий стохастической ограниченности и эргодичности случайной последовательности, описывающей функционирование системы. Сложность математической задачи объясняется необходимостью изучения многомерной случайной последовательности (процесса с дополнительными переменными), если отказаться от обычного предположения, что время возвращения заявки – экспоненциально распределенная величина. Именно на анализе этого сложного случая сосредоточено исследование автора.
Нами разработана обобщенная стохастическая модель типовых систем с возвращением заявок. Эта модель характеризуется: числом каналов, рекуррентным потоком заявок с ф.р. (функцией распределения) интервала между заявками, ф.р. времени обслуживания заявки, ф.р. времени возвращения (повторения) заявки, а также дополнительными признаками, касающимися дисциплины доступа заявок в канал и теми или иными временными ограничениями. Важный в приложениях случай, когда время возвращения заявки равно постоянной , назван “-возвращением”. Выделена система (чистая система с возвращением); – система типа Лакатоша, в которой обслуживание происходит в порядке очереди; – система, в которой дается приоритет задержанным заявкам по отношению к вновь поступающим заявкам; система с -возвращением, в которой задержанная заявка может поступить в канал через время, не меньшее ; система с ограниченным числом возвращений. Выделено также много других разновидностей систем.
Развит общий подход к построению цепи Маркова в метрическом пространстве, описывающей функционирование системы, и исследованию ее эргодичности. Ключом к доказательству эргодических теорем является использование моментов очистки и следующих за ними моментов обновления системы, а также свойств суперпозиции большого числа процессов восстановления с запаздыванием. Найдены условия стохастической ограниченности и эргодичности соответствующих цепей Маркова для типовых систем. Выведен ряд аналитических формул для характеристик систем. Развит метод статистического моделирования.
Обозначим через время между поступлением заявок, – среднее время обслуживания заявки, . Система типа устойчива, если , распределение нерешетчато и выполняется некоторое техническое условие. Система с -возвращением типа устойчива, если , причем эта оценка неулучшаема в терминах . Система с -возвращением типа устойчива, если . Система с -возвращением типа устойчива, если , причем в случае эта оценка неулучшаема в терминах .
Задачу об условии эргодичности системы типа Лакатоша удалось решить исчерпывающим образом; при этом выведено уравнение для распределения времени ожидания заявки, обобщающее известное уравнение Линдли.
Развит метод статистического моделирования для вычисления вероятности того, что заявка будет направлена на орбиту более раз, а также эмпирического определения критического значения параметра в типичных системах типа с -возвращением, такого, что система устойчива при и неустойчива при .
Ключевые слова: специальные случайные процессы, системы обслуживания с повторными вызовами, устойчивость систем обслуживания, эргодичность систем обслуживания, управление воздушным движением, статистическое моделирование систем.
