Задача мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями
Вантажиться...
Дата
2018
Автори
Годна, Анастасія Вікторівна
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Магістерська дисертація: 117 с., 32 рис., 23 табл., 1 додаток, 125 джерел.
Актуальність. Теорія розкладів і календарне планування утворюють одне з важливих і цікавих напрямків в області оптимізації та в даний час переживають період бурхливого розвитку. Це пов'язано, перш за все, з появою принципово нових видів продукції, технологій, інтенсифікацією виробництва, його безперервним оновленням і вдосконаленням. Стрімкий розвиток систем зв'язку, інтернету, логістичних структур ставить перед математиками нові завдання, в тому числі в області теорії розкладів. На практиці виникає безліч різноманітних завдань календарного планування виробництва і збуту продукції, ефективного використання обладнання та інших ресурсів, узгодження роботи різних служб і так далі.
Різноманітність математичних моделей і методів складання розкладів зазвичай ставить перед прикладними математиками й програмістами неминучу проблему побудови швидких алгоритмів і їх ефективної програмної реалізації з урахуванням особливостей вирішуваної задачі.
Більшість задач теорії розкладів і календарного планування є NP-складними, і виникають серйозні труднощі при їх вирішенні, так як побудова оптимального розкладу вимагає великих затрат часу навіть при порівняно невеликих розмірностях вхідних даних. У такій ситуації необхідно проводити більш глибокі дослідження задач в рамках теорії складності.
У зв’язку з цим актуальною є розробка програмного продукту для складання календарних планів виконання завдань паралельними пристроями, який допоможе мінімізувати сумарне відхилення від директивних строків.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках теми «Ефективні методи розв’язання задач теорії розкладів» (номер держреєстрації 0117U000919).
Мета дослідження – підвищення якості розв’язку задач календарного планування за рахунок побудови оптимального чи близького до оптимального розкладу, що дозволяє мінімізувати сумарний час відхилення від директивних строків.
Для досягнення мети необхідно виконати наступні завдання:
провести аналіз відомих результатів з розв’язання поставленої в рамках роботи задачі;
розробити алгоритм створення календарного плану виконання завдань паралельними пристроями, що мінімізує сумарне відхилення моментів завершення завдань від директивних строків;
виконати програмну реалізацію розробленого алгоритму;
дослідити ефективність алгоритму при різних вхідних даних шляхом проведення обчислювальних експериментів;
Об’єкт дослідження – процес календарного планування виконання завдань.
Предмет дослідження – моделі та методи розв’язання задач календарного планування з метою мінімізації сумарного відхилення виконання завдань від директивних строків паралельними пристроями.
Методи дослідження. Для виконання поставлених завдань у роботі було використано методи: теорії розкладів, дослідження операцій та теорії складності (при розробленні методів розв’язання задач складання розкладів).
Наукова новизна отриманих результатів.
Розроблено трьохетапний евристичний алгоритм розв‘язання задачі мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями.
Набув подальшого розвитку метод розв’язання задачі задачі мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями та має статистично сталі високі показники роботи.
Публікації. Матеріали роботи представлено у науковій статті міжнародного наукового журналу «Науковий огляд» [123] (свідоцтво про державну реєстрацію КВ № 20878-10678Р), опубліковані в тезах наукової конференції студентів, магістрантів та аспірантів «Інформатика та обчислювальна техніка» – ІОТ-2018 [124] та прийнято до публікації у вигляді тез 20-ї міжнародної конференції SAIT 2018 [125].
Опис
Ключові слова
паралельні пристрої, директивний строк, складання розкладів, календарне планування, мінімізація сумарного відхилення, parallel machines, due date, scheduling, minimizing total deviation
Бібліографічний опис
Годна, А. В. Задача мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Годна Анастасія Вікторівна. – Київ, 2018. – 115 с.