Анотація до роботи:

Скакаліна О.В. Моделі і методи оптимального послідовно-паралельного упорядкування робіт у системах з неідентичними об’єктами. – Рукопис.

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

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

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

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

Головні наукові і практичні результати роботи полягають у наступному.

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

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

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

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

5. Наведено докази коректності розроблених алгоритмів і оцінено часову складність розв’язання кожної задачі.

6. Удосконалено програмний пакет 1plusMmashine, впроваджений у програмне середовище Mathematica, який орієнтований на розв’язання задач з області теорії розкладів.

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

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

Публікації автора:

1. Панишев А.В., Костикова М.В. Скакалина Е.В. Об одном обобщении задачи о назначениях // Радиоэлектроника и информатика. – 1999. – №2(07). - С. 96-101.

2. Панишев А.В., Подоляка О.А., Скакалина Е.В. Эффективный алгоритм распараллеливания работ на неидентичных машинах // Авиационно-космическая техника и технология. - 1999. - Вып. 13. – С. 136-146.

3. Панишев А.В., Скрипина И.В., Скакалина Е.В. Эффективное построение оптимальных решений в задаче о назначении транспортного типа // Автомобильный транспорт: Сб. науч. тр. – Харьков: ХГАДТУ. - 2000. – Вып. 4.– С. 63-65.

4. Скакаліна О.В., Скрипіна І.В. Мінімізація сумарного простою в задачах складання автобусних розкладів // Вісник ЖІТІ. – 2000. - Вип. 15. – С. 40-47.

5. Скакалина Е.В. Эффективное построение множества расписаний с минимальным суммарным временем завершения работ // Радиоэлектроника и информатика. – 2001. - №3(16). – С. 44-46.

6. Подоляка О.О., Подоляка О.М., Скакаліна О.В. Ефективна схема побудови оптимальних за швидкодією розкладів в задачах про призначення двохетапних робіт на неідентичні машини // Авіаційно-космічна техніка і технологія. – 2002. – Вип. 27. – С. 225-231.

7. Панишев А.В., Скакалина Е.В., Скрипина И.В. Эффективное построение множества оптимальных решений в обобщениях задачи о назначениях // Матеріали ІІ Міжнар. конф. "Математичні моделі та інформаційні технології в соціально-економічних та екологічних системах". – Луганськ.:СНУ. – 2001. – С. 171-172.

8. Панишев А.В., Скакалина Е.В., Скрипина И.В. Об одном обобщении задачи о назначениях // Матеріали І всеукраїнської науково-практичної конф. "Україна наукова ’2001" (Дніпропетровськ-Харків-Одеса.). – Дніпропетровськ: Наука і освіта – 2001. – Том 13. – С. 3-5.

9. Панишев А.В., Плечистый Д.Д., Скакалина Е.В. Схема построения локальных оптимальных последовательностей в решении обобщений задачи о назначениях // Матеріали V Міжнар. науково-практичної конф. "Наука і освіта – 2002" (Дніпропетровськ-Донецьк). – Дніпропетровськ: Наука і освіта . - 2002. – С. 54-55.