Дослідження систем обслуговування з поверненням заявок при неекспоненціальному розподілі часу перебування на орбіті - Автореферат

Ця теорія на протязі кількох останніх десятиріч здобула чільне місце у питаннях моделювання систем з дискретними подіями. За такий клас у нашому дослідженні взято системи обслуговування з поверненням заявок (повторенням викликів), що слугують адекватними моделями систем доступу в компютерних мережах, систем телефонного звязку, процесів управління повітряним рухом. математичний стохастичний ергодичність У класичній теорії масового обслуговування, в створення якої основоположний внесок зробила, зокрема, школа академіка Б.В.Гнєденка, розглядають системи без блокування заявок; таким чином, при наявності вільного каналу заявка, що є в системі, спрямовується в нього негайно. У більшості реальних моделей, особливо тих, що описують роботу компютерних мереж, заявка блокується від обслуговування до моменту, коли створюються умови для її обслуговування, навіть у випадку, коли канал вільний. Участь автора у цих науково-дослідних темах полягала у розробці моделей мереж з урахуванням повторних викликів, дослідженні умов ергодичності спеціального вигляду систем, розробці та реалізації алгоритмів стохастичного моделювання систем з повторними викликами, порівняльного аналізу результатів моделювання.У вступі обґрунтовується актуальність теми дисертаційної роботи, формулюється мета і задачі дослідження, викладено короткий зміст дисертації і отриманих у ній результатів, виділено їх наукову новизну і практичну цінність. У першому розділі дано огляд літератури за темою дисертації і визначено напрямки досліджень. У другому розділі запропоновано класифікацію типових систем з поверненням заявок і поставлено основні задачі їх дослідження, а також дано мотивацію їх актуальності для системного аналізу.У додатку А зібрано необхідні відомості з теорії ймовірностей на строгому аксіоматичному рівні. Так, маючи на увазі процеси масового обслуговування з додатковими компонентами, ми означаємо розподіли ймовірностей на звязках (обєднаннях) евклідових просторів різної розмірності.У дисертаційній роботі розроблено новий науковий напрямок у математичному моделюванні систем масового обслуговування, а саме, розроблено методи дослідження стійкості та ергодичності систем обслуговування з поверненням заявок (з повторенням викликів) при неекспоненціальному розподілі часу перебування на орбіті та досліджено широке коло таких систем. Основна змінна інтерпретуються, як величина черги у момент надходження n-ої заявки або закінчення n-го обслуговування; - вектор додаткових змінних, що вказують на час до реалізації або час від реалізації тієї чи іншої події. З цією метою зауважено, що для типових систем з поверненням заявок існують моменти очистки, коли система є вільною від вимог, та моменти відновлення, коли майбутня поведінка системи не залежить від попередньої історії. Значно узагальнено систему Ласло Лакатоша з T-поверненням заявок та дисципліною обслуговування в порядку черги: ми дослідили загальний рекурентний потік заявок, загальний розподіл часу обслуговування та часу перебування на орбіті. Для системи PRIOR типу GI/D/m автор виводить достатню умову ергодичності системи, яку істотно покращити неможливо.

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

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

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

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

Вироблено узагальнену схему типових систем з поверненням заявок.

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

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

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

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. Результати дисертації можна застосовувати для тестування алгоритмів та програм статистичного моделювання значно складніших систем з поверненням заявок, ніж ті, що ми їх розглянули. Зокрема, типовим є випадок, коли при спрощенні моделі реального процесу або за умови малого навантаження модель стає подібною до деякої типової моделі, яку можна дослідити аналітичним методом.

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

РОБОТИ АВТОРА ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Коба Е.В. О системе обслуживания GI/G/1 с повторением заявок при обслуживании в порядке очереди // Доповіді НАН України. - 2000. - №6. - С. 101-103.

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.

Коба Е.В. Условие эргодичности обобщенной модели обслуживания типа Л.Лакатоша // Доповіді НАН України. - 2004. - №11. - С. 70-74.

Коваленко И.Н., Коба Е.В. Три системы обслуживания с повторными вызовами, отражающие некоторые особенности процесса посадки воздушных судов // Проблемы управления и информатики. - 2002. - №2. - C. 78-82.

Коба Е.В. Системы обслуживания с ограниченным снизу временем возвращения заявок // Проблемы управления и информатики. - 2004. - №3. - С. 153-157.

Коба Е.В. Достаточное условие эргодичности системы М/D/1 с Т-возвращением и приоритетом задержанных заявок // Доповіді НАН України. - 2003. - №5. - С. 17-20.

Коба О.В. Достатня умова стійкості системи обслуговування GI/D/m з Т-поверненням і пріоритетом затриманих заявок // Доповіді НАН України. - 2004. - №9. - С. 65-70.

Коба О.В. Умова стійкості системи обслуговування GI/G/1 з Т-поверненням заявок // Системні дослідження та інформаційні технології. - 2005. - №1. - C.39-43.

Коба О.В., Михалевич К.В. Порівняння систем типу M/M/1 з швидким поверненням заявок при різних дисциплінах обслуговування // Системні дослідження та інформаційні технології. - 2003. - №2. - С. 59-68.

Коба О.В., Коваленко І.М. Умова ергодичності для системи M/G/1 з повторенням викликів при негратчастому розподілі циклу на орбіті // Доповіді НАН України. - 2004. - №8. - С. 70-77.

Коба Е.В. Условия устойчивости некоторых типовых систем обслуживания с возвращением заявок // Кибернетика и системный анализ. - 2005. - №1. - C. 124-127.

Коба Е.В. О производительности замкнутой сети с показательным временем обслуживания и периодически повторяющимися заявками абонентов // Кибернетика и системный анализ. - 2000. - №3. - С. 176-179.

Коба Е.В. О производительности процессора, обслуживающего двух абонентов, при постоянном времени повторения заявки // Доповіді НАН України. - 2000. - №10. - С. 104-106.

Коба Е.В. Система обслуживания M/D/1 с заявками, повторяющимися через постоянное время, при частичной синхронизации входящего потока // Кибернетика и системный анализ. - 2000. - №6. - С. 177-180.

Коваленко И.Н., Коба Е.В. О двусторонней оценке распределения числа циклов на орбите для одной системы обслуживания с повторением заявок // Доповіді НАН України. - 2000. - №9. - С. 109-112.

Коба Е.В. Об условии устойчивости системы обслуживания M/D/1 с повторяющимися заявками и ограниченным временем ожидания // Кибернетика и системный анализ. - 2000. - №2. - С. 184-186.

Коба Е.В. Вероятность потери заявки в замкнутой и разомкнутой системах обслуживания типа M/D/1 с ограниченным временем ожидания // Доповіді НАН України. -2002. - №5. - С. 72-76.

Коба Е.В. Ободной системе обслуживания с повторением и выталкиванием заявок // Проблемы управления и информатики. - 2001. - №1. - С. 58-62.

Коба Е.В. Вероятность потери заявки в системе обслуживания M/D/1 с постоянным временем возвращения // Доповіді НАН України. - 2002. - №4. - С. 61-66.

Коба Е.В. Система обслуживания пуассоновского потока сдвоенных заявок // Доповіді НАН України. - 1995. - №3. - С. 9-11.

Коба Е.В. Исследование эргодичности систем обслуживания с возвращением заявок методом статистического моделирования // Проблемы управления и информатики. - 2004. - №6. - С. 106-115.

Коба О.В. Стаціонарні характеристики системи масового обслуговування GI/G/1 із Т-поверненням при обслуговуванні в порядку черги // Вісник Національного авіаційного ун-ту. - 2003. - №1. - С. 122-125.

Коба О.В. Системи обслуговування з повторенням заявок при детермінованому часі перебування на орбіті // Вісник Національного авіаційного ун-ту. - 2002. - №3. - С. 69-73.

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.

Коба О.В., Михалевич К.В. Ефект швидкого повернення з орбіти в системах типу M/M/1 з FCFS дисципліною обслуговування // Матеріали V Міжнародної науково-технічної конференції АВІА-2003. - Київ. - 2003. - С. 14.83-14.86.

Коба О.В. Дослідження системи GI/G/1 з довільною орбітою і FCFS дисципліною обслуговування // Матеріали V Міжнародної науково-технічної конференції АВІА-2003. - Київ. - 2003. - С. 14.79-14.82.

Коба Е., Михалевич К. Сравнение систем обслуживания типа M/G/1 с повторением при быстром возвращении с орбиты // Материалы международной научной конференции “Современные математические методы анализа и оптимизации телекоммуникационных сетей”. - 2003. - Гомель. - С. 136-138.

Коба О.В. Системи масового обслуговування з повторенням заявок і складною дисципліною обслуговування // Матеріали VI Міжнародної науково-технічної конференції АВІА-2004. - Київ. - 2004. - С. 13.85-13.88.

Коба Е.В., Михалевич К.В. Исследование систем обслуживания с циклическим временем ожидания // Матеріали міжнародної науково-технічної конференції, присвяченої 90-річчю від дня народження академіка НАН України О.І.Кухтенка. В сб. Проблемы информатизации и управления. - 2004. - №11. - С. 131-134.