У дисертаційній роботі розроблено новий науковий напрямок у математичному моделюванні систем масового обслуговування, а саме, розроблено методи дослідження стійкості та ергодичності систем обслуговування з поверненням заявок (з повторенням викликів) при неекспоненціальному розподілі часу перебування на орбіті та досліджено широке коло таких систем. Отримані автором результати дозволяють підвищити адекватність та точність математичних моделей, використовуваних у дослідженні таких процесів, як функціонування злітно-посадової смуги, організація доступу у мережах ЕОМ тощо, відмовившись від традиційного припущення, що час повторення заявки розподілений за експоненціальним законом. Основними науковими результатами дисертаційної роботи є такі: Проаналізовано велику кількість літературних джерел, включаючи найновіші джерела світової літератури, що стосуються систем з повторними викликами. Виявилося, що майже всі автори обмежуються розглядом систем з експоненціальним розподілом часу повернення заявки (часу на орбіті) – не існувало загального підходу до дослідження систем з неекспоненціальним розподілом. Водночас вивчення прикладних систем свідчить про те, що розгляд неекспоненціальної орбіти є досить актуальним. Вироблено узагальнену схему типових систем з поверненням заявок. На переконання автора, це схема досить загальна, щоб описувати багато реальних процесів обслуговування, і водночас не переобтяжена включенням складних алгоритмів організації черг та інших особливостей. Пропонована схема включає деяке число каналів обслуговування, рекурентний потік заявок з функцією розподілу інтервалу між надходженням заявок, загальний розподіл часу обслуговування заявки та загальний розподіл часу перебування заявки на орбіті. Якщо цей час дорівнює сталому , таку систему ми називаємо системою з -поверненням. Ми розглядаємо також систему, яку ми назвали системою з -поверненням. У ній заявки обслуговуються таким чином, що при неможливості спрямувати заявку до каналу обслуговування негайно, вона спрямовується до орбіти, але в цьому разі час її чекання не менший від сталої .
Продовжуючи класифікацію, автор виділяє типові системи з поверненням заявок, а саме: систему , або узагальнену систему Лакатоша, в якій обслуговування заявок відбувається в порядку їх надходження до системи, тобто за дисципліною ; систему , в якій обслуговування відбувається в порядку надходження заявок до каналу (з орбіти чи первинного потоку); систему , у якій час обслуговування кожної заявки визначає диспетчер у момент надходження цієї заявки; нова заявка може надійти до каналу лише в тому випадку, коли вона не заважає обслуговуванням, що їх уже заплановано. Упродовж нашої роботи досліджено також багато систем більш складної структури, але автор вважає недоцільним включати їх до переліку типових систем. Вироблено загальний підхід до побудови випадкового процесу, що описує дію системи обслуговування з поверненням заявок. Таким процесом є ланцюг Маркова , де – основна змінна, – додаткова змінна. Основна змінна інтерпретуються, як величина черги у момент надходження -ої заявки або закінчення -го обслуговування; – вектор додаткових змінних, що вказують на час до реалізації або час від реалізації тієї чи іншої події. Для всіх типових систем з поверненням заявок побудову послідовності виконано з усіма необхідними подробицями. Для моделювання найважливіших показників якості обслуговування у різних реальних системах дано схему функціоналів від процесу . Визначено поняття “стійкості”, стохастичної обмеженості та ергодичності системи по відношенню до того чи іншого функціоналу. Віднайдено загальний підхід до встановлення стохастичної обмеженості ланцюга Маркова . З цією метою зауважено, що для типових систем з поверненням заявок існують моменти очистки, коли система є вільною від вимог, та моменти відновлення, коли майбутня поведінка системи не залежить від попередньої історії. Наявність таких моментів значно полегшує доведення потрібних властивостей, виходячи з феллерівської теорії рекурентних подій. Ергодичну теорему, яка, щоправда, не потребує нових математичних підходів, сформульовано у вигляді, який, на погляд автора, найзручніший у застосуванні до систем з поверненням заявок. Значно узагальнено систему Ласло Лакатоша з -поверненням заявок та дисципліною обслуговування : ми дослідили загальний рекурентний потік заявок, загальний розподіл часу обслуговування та часу перебування на орбіті. Окремо досліджено випадки, коли розподіл часу перебування на орбіті гратчастий та негратчастий. В обох випадках віднайдено умову ергодичності, яку істотно покращити неможливо. Так, у негратчастому випадку доведено, що достатньою умовою ергодичності послідовності часів очікування є нерівність
, де – середній час між надходженням заявок, – середній час обслуговування, та – відповідно, перший та другий моменти часу перебування на орбіті. Цей результат узагальнено на систему типу Лакатоша, в якій інтервали між заявками, часи обслуговування та перебування на орбіті залежать від ергодичного ланцюга Маркова зі скінченною множиною станів. Віднайдено достатню умову ергодичності одноканальної системи з -поверненням, а саме: якщо при довільному , тобто інтервал між заявками може бути як завгодно великий, то за умови, що середній час обслуговування менший за середній час між заявками, відповідний ланцюг Маркова ергодичний. Для системи типу автор виводить достатню умову ергодичності системи, а саме,
, де – час обслуговування, – середній час між заявками, – число каналів, за умови, що при будь-якому та . Цей результат не можна істотно покращити, а саме, за умови при деякому існує такий розподіл , що стійкість системи відсутня. Віднайдено універсальну непокращуванну умову ергодичності системи з Т-поверненням типу , а саме,
. Однак потрібно зазначити, що умова ергодичності для конкретних систем (наприклад, типу ) в дисертаційній роботі не досліджувалась. Проведений нами статистичний експеримент свідчить на користь гіпотези Л.Г.Афанасьєвої (Московський державний університет ім. М.В.Ломоносова), що за умови система з Т-поверненням ергодична. Порівняно дві системи з поверненням заявок типу , в яких час повернення заявок експоненціальний з параметром , параметр потоку заявок , параметр обслуговування , . Припустимо, що очікування заявки на протязі часу пов’язане з витратами , де . Тоді при досить великому , тобто при швидкому поверненні з орбіти, система вигідніша від системи . Цей висновок може знайти практичне застосування. Досліджено умову ергодичності системи типу за умови, що – негратчаста функція розподілу. Нехай також виповнюється умова
при деяких додатних та і довільному . Тоді умова , де – параметр потоку, – середній час обслуговування, достатня для ергодичності деякого марковського процесу, що описує поведінку системи. Досліджено вісім різних модифікацій систем з поверненням заявок. Усі ці моделі відображають певні особливості реальних процесів. Так, наприклад, часто час чекання заявки обмежений: це характерно для повітряного судна, що потребує вільної смуги для посадки через обмеженість запасу пального. У системах обробки інформації часто операція обслуговування заявки складається з низки станів неоднозначної ваги; наприклад, спочатку йде етап пересилання найціннішої інформації, далі – другорядний етап; тому можлива дисципліна динамічного пріоритету: нова заявка спроможна виштовхнути з каналу обслуговування ту, яка там перебуває. Для стохастичних мереж (наприклад, центрального процесора, що обслуговує деяке число периферійних пристроїв) часто кожне джерело вимог посилає їх через певний час після того, як попередня заявка цього джерела одержала обслуговування або застала канал у зайнятому стані. Далі, у стохастичних мережах часто має місце синхронізація потоку заявок: заявки надходять до системи лише в дискретні моменти часу. Це явище може спричинити розщеплення систем з поверненням заявок на кілька самостійних систем. Звичайно, переліченими особливостями не вичерпується різновиди реальних систем з поверненням заявок. Проте, досліджуючи ці вісім моделей, ми мали на меті розвинути певний підхід, що його можна використати й для багатьох інших моделей систем з поверненням заявок.
Зокрема, досліджено систему з -поверненням типу , у котрій кожна заявка може повертатися на орбіту не більше, ніж разів; якщо після -го повернення система зайнята, то заявку буде втрачено. Доведено ергодичну теорему для відповідного процесу з додатковими змінними. Для такої системи за умови, що час обслуговування , ймовірність втрати заявки має асимптотичний вигляд , де константа обчислюється за деякою формулою. Розроблено алгоритм статистичного моделювання типових систем у межах періоду зайнятості, що ґрунтується на рекурентному алгоритмі локальних змін випадкового процесу. Від оцінок, одержаних для періоду зайнятості, робиться перехід до глобальних параметрів: ймовірності того, що заявка потребує принаймні двічі побувати на орбіті, та граничного значення навантаження системи – такого, що при система ергодична, а при – не ергодична. Оцінка глобального параметра дається через осереднення відповідних величин, отриманих з незалежних реалізацій періоду зайнятості. Для статистичної оцінки критичного значення навантаження типових систем з поверненням заявок застосовано метод прямого моделювання.
До статистичного моделювання досліджуваних систем застосовано, зокрема, метод розшарованої вибірки, що істотно зменшує дисперсію оцінки такого параметру, як, наприклад, ймовірність того, що в системі заявка побуває на орбіті принаймні двічі (це важливий показник в задачах управління повітряним рухом). З усієї сукупності результатів дисертації випливає, що неекспоненціальність розподілу часу на орбіті призводить до інших характеристик процесу обслуговування, ніж ті, що спостерігаються в експоненціальному випадку. Це є пересторогою для дослідників щодо застосування відомих “експоненціальних” формул. Водночас ми вказуємо досить загальний метод аналізу систем з “неекспоненціальною” орбітою. Результати дисертації можна застосовувати для тестування алгоритмів та програм статистичного моделювання значно складніших систем з поверненням заявок, ніж ті, що ми їх розглянули. Зокрема, типовим є випадок, коли при спрощенні моделі реального процесу або за умови малого навантаження модель стає подібною до деякої типової моделі, яку можна дослідити аналітичним методом.
Результати дисертації можна також використовувати в учбовому процесі для викладання теорії систем масового обслуговування, їх моделювання та проектування. |
