Задача складання розкладу виконання робіт з відношенням передування паралельними пристроями за критерієм мінімізації загального часу виконання робіт
Вантажиться...
Дата
2018
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Магістерська дисертація: 96 с., 26 рис., 5 табл., 4 додатки, 117 джерел.
Актуальність. Успіх виробництва та його прибутковість на пряму залежить від процесу планування роботи на ньому. Ключовою складовою процесу планування є розробка ефективного плану виконання робіт виробничої діяльності. Для створення таких планів застосовують різні методи, зокрема методи теорії розкладів.
Більшість задач теорії розкладів відносяться до класу NP-повних задач. Виникає проблема в тому, що відомі методи не завжди дозволяють отримувати близькі до оптимальних розклади робіт на виробництві за прийнятний час.
На ряду з іншими NP-повними задачами теорії розкладу стоїть задача складання розкладу виконання робіт з відношенням передування паралельними пристроями з метою мінімізації загального часу виконання робіт. У зв’язку з цим, актуальною є розробка алгоритмів для даної задачі, що забезпечать високу якість отримуваних результатів і не будуть потребувати значних обчислювальних ресурсів.
Мета дослідження – підвищення ефективності календарного планування за рахунок побудови оптимального чи близького до оптимального розкладу виконання робіт з відношенням передування паралельними пристроями шляхом мінімізації загального часу виконання робіт.
Для досягнення мети необхідно виконати наступні задачі:
− виконати огляд відомих результатів з розв’язання поставленої в рамках роботи задачі;
− розробити алгоритми побудови початкового розкладу та провести експериментальні дослідження їх ефективності;
− сформулювати достатні умови оптимальності для розв’язуваної задачі;
− розробити алгоритм створення календарного плану мінімізації загального часу виконання робіт з відношенням передування паралельними пристроями;
− розробити програмну реалізацію розробленого алгоритму;
− виконати аналіз отриманих результатів.
Об’єкт дослідження – процес календарного планування виконання робіт.
4
Предмет дослідження – методи календарного планування виконання робіт паралельними пристроями.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського» в рамках теми «Ефективні методи розв’язання задач теорії розкладів» (№ ДР 0117U000919).
Наукова новизна отриманих результатів
Розроблено підходи та методи розв’язання поставленої задачі. Використання створених моделей на основі розроблених достатніх умов оптимальності (ДОУ), дозволяє істотно підвищити швидкодію складання розкладів на підприємстві. Публікації. Матеріали роботи опубліковані в збірнику праць Міжнародної наукової конференції на тему «Глобальне конкурентне середовище: розвиток сучасних соціально-економічних систем», м. Кишенів, Республіка Молдова, 21 квітня 2017 року [1]; у збірці науково-практичній конференції «Інформатика та обчислювальна техніка-ІОТ- 2018», м. Київ, НТУУ «КПІ ім. Ігоря Сікорського», 23-24 квітня 2018 року [2].
Опис
Ключові слова
паралельні пристрої, складання розкладів, календарне планування, відношення передування, мінімізація загального часу виконання робіт, parallel machines, scheduling, calendar planning, relation of precedence, minimize makespan in tasks scheduling
Бібліографічний опис
Дубок, К. В. Задача складання розкладу виконання робіт з відношенням передування паралельними пристроями за критерієм мінімізації загального часу виконання робіт : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Дубок Катерина Валентинівна. – Київ, 2018. – 117 с.