Задача мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроями
Вантажиться...
Дата
2018
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Магістерська дисертація: 101 с., 26 рис., 22 табл., 1 додаток, 55 джерел.
Актуальність. Задачі теорії розкладів широко вивчаються в літературі останні 50 років, їх розгляду приділяється значна увага з боку багатьох вчених і фахівців-практиків по всьому світу. Складні реальні задачі, з якими стикаються різні типи компаній, стали викликом для пошуку шляхів їх розв’язання. Результати отримані дослідженнями різних науковців свідчать про актуальність проблеми та потребу в її подальшому дослідженні. Таким чином, можна з упевненістю сказати, що питання теорії розкладів є одним з найбільш поширених питань в галузі дослідження операцій і наук управління.
Проблематика теорії розкладів охоплює дослідження обчислювальної складності задач, розробку точних, наближених та евристичних алгоритмів їх розв’язання. При цьому більшість праць присвячено розвитку комбінаторних підходів. Однак, як показує практика, можливості комбінаторних алгоритмів суттєво обмежені розмірністю розв’язуваних задач.
У зв’язку з цим актуальною є розробка програмного продукту для складання розкладу виконання завдань паралельними пристроями, який допоможе мінімізувати сумарне відхилення від директивних строків.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках теми «Ефективні методи розв’язання задач теорії розкладів» (№ 0117U000919).
Мета і завдання дослідження – підвищення якості розв’язку задач календарного планування за рахунок побудови оптимального чи близького до оптимального розкладу, що дозволяє мінімізувати середній час відхилення від директивних строків.
4
Для досягнення мети необхідно виконати наступні завдання:
виконати аналітичний огляд відомих результатів, з розв’язання поставленої в рамках роботи задачі;
розробити алгоритм створення календарного плану виконання завдань паралельними пристроями, що мінімізує сумарне відхилення моментів завершення завдань від директивних строків;
розробити програмну реалізацію розробленого алгоритму;
виконати аналіз отриманих результатів.
Об’єкт дослідження – оперативно-календарне планування дрібносерійного виробництва.
Предмет дослідження – моделі та методи розв’язання задач календарного планування з метою мінімізації сумарного відхилення виконання завдань від директивних строків паралельними пристроями.
Методи дослідження, застосовані в роботі, базуються на методах та алгоритмах теорії розкладів та дослідження операцій.
Наукова новизна отриманих результатів. Розроблено евристичний алгоритм розв‘язання задачі мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроями.
Публікації. Матеріали роботи опубліковано у Міжнародному науковому журналі «Науковий огляд» – №9(14). – с. 14–32 у 2017 році [1], також матеріали опубліковано в тезах 20-ї Міжнародної науково-технічної конференції SAIT 2018 [2], наукової конференції студентів, магістрантів та аспірантів «Інформатика та обчислювальна техніка» – ІОТ-2018 [3].
Опис
Ключові слова
розклад, директивний строк, момент запуску, паралельні пристрої, ідентичні пристрої, пропорційні пристрої, запізнення, випередження, мінімізація сумарного відхилення, schedule, due date, release date, parallel machines, identical machines, proportional machines, tardiness, earliness, minimizing total deviation
Бібліографічний опис
Маленко, А. О. Задача мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроями : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Маленко Анастасія Олексіївна. – Київ, 2018. – 101 с.