Формалізація і розв’язання задач оптимального планування робіт за наявності різної продуктивності пристроїв
Вантажиться...
Дата
2018
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Магістерська дисертація: 107 с., 12 рис., 10 табл., 7 додатків, 82 джерела.
Актуальність. Планування виконання командою наявних завдань є важливим
процесом в багатьох галузях, наприклад, у розробці програмного забезпечення. На
сьогодні спостерігається зростання популярності покрокового (ітеративного)
підходу до виконання робіт у різних сферах нашого життя. Скрам є одним із
найбільш поширених гнучких підходів на сьогоднішній день. Ідея методології
Скрам полягає у роботі за ітераціями, тобто за деякими фіксованими проміжками
часу. У Скрамі ітерації називаються Спринтами. Для ітерації необхідно підібрати
набір завдань, які може виконати за цей проміжок часу команда, причому саме
такий набір, який принесе найбільшу цінність продуктові, що розробляється. Але
обговорення завдань та вирішення, які саме завдання можна взяти на виконання з
урахуванням різної продуктивності та досвідченості виконавців, є складним
процесом, який займає досить багато часу.
Саме тому актуальним є дослідження проблеми оптимального планування
виконання завдань, формальна постановка якої призводить до складних
оптимізаційних задач. В свою чергу це потребує розробки наближених алгоритмів
розв’язування задачі виконання завдань виконавцями з різною для досягнення
найбільшої сумарної цінності виконаної роботи. Враховуючи наявну в теорії
складання розкладів термінологію та специфіку задачі, вживатимемо терміни
“пристрої” та “виконавці” як взаємозамінні.
Мета дослідження – підвищення ефективності виконання завдань декількома
виконавцями (пристроями) з різною продуктивністю за рахунок зменшення витрат
часу на планування їх виконання.
Для досягнення мети необхідно виконати наступні завдання:
- виконати огляд відомих результатів з поставленої задачі;
- виконати формалізацію задачі планування роботи із врахуванням різної
продуктивності пристроїв;
- розробити наближені алгоритми для розв’язування поставленої задачі;
4
- розробити програмну реалізацію алгоритмів та моделей;
- виконати аналіз отриманих результатів.
Об’єкт дослідження – процес планування виконання завдань пристроями з
різною продуктивністю.
Предмет дослідження – методи планування виконання завдань пристроями з
різною продуктивністю.
Наукова новизна отриманих результатів полягає у формалізації задачі
планування роботи на ітерацію у методології Скрам як задачі оптимального
планування робіт за наявності різної продуктивності пристроїв; розробці алгоритму
для її розв’язування шляхом розбиття на підзадачі; розробці жадібного алгоритму
знаходження початкового розв’язку другої підзадачі, процедури генерації точок
околу в просторі розв’язків та розробці алгоритмів на основі схеми алгоритмів
локального пошуку.
Публікації. Матеріали роботи опубліковані у міжнародному журналі
«Науковий огляд», №3, 2018 [1, 2].
Зв'язок роботи з науковими програмами, планами, темами. Робота
виконувалась у філії кафедри автоматизованих систем обробки інформації та
управління Національного технічного університету України «Київський
політехнічний інститут ім. Ігоря Сікорського» в рамках науково-дослідної теми
Інституту кібернетики ім. В. М. Глушкова НАН України: «Розробити математичний
апарат, орієнтований на створення інтелектуальних інформаційних технологій
розв’язування проблем комбінаторної оптимізації та інформаційної безпеки» (шифр
теми: ВФ.180.11).
Опис
Ключові слова
оптимальне планування, гнучкі методології, скрам, пристрої з різною продуктивністю, детермінований локальний пошук, алгоритм імітаційного відпалу, G-алгоритм optimal scheduling, agile methodologies, scrum, unrelated machines, local search, simulated annealing, G-algorithm
Бібліографічний опис
Галкіна, Г. А. Формалізація і розв’язання задач оптимального планування робіт за наявності різної продуктивності пристроїв : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Галкіна Галина Андріївна. – Київ, 2018. – 106 с.