Задача мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроями

Скорочена інформація про документ
dc.contributor.advisorЖданова, Олена Григорівна
dc.contributor.authorМаленко, Анастасія Олексіївна
dc.date.accessioned2018-07-06T09:19:49Z
dc.date.available2018-07-06T09:19:49Z
dc.date.issued2018
dc.description.abstractenMaster’s thesis: 101 pages, 26 figures, 22 tables, 1 appendix, 55 references. Relevance. Scheduling problems have been widely studying in the literature for 50 years, considerable attention from many scholars and practitioners around the world is given to their consideration. The complex real problems faced by different types of companies have become a challenge to find ways to solve them. The results obtained by researches of various scholars indicate the urgency of the problem and the need for its further research. Thus, one can confidently say that the question of the scheduling problems is one of the most common issues in the field of operations research and management sciences. The question of scheduling problems covers the studying the complexity of problems, the development of accurate, approximate and heuristic algorithms for their solution. At the same time, most works are devoted to the development of combinatorial approaches. However, as practice shows, the possibilities of combinatorial algorithms are essentially limited by the dimensionality of solvable problems. In this regard, it is relevant to develop a software product to scheduling tasks by parallel machines, which will help minimize the total deviation from a common due date. Relationship of work with scientific programs, plans, themes. The work was carried out at National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute» the department of Computer-Aided Management and Data Processing Systems within the theme “Effective methods for solving the problems of the theory of schedules” (state registration number 0117U000919). Purpose and objectives of the study. Improving the quality of solving problem scheduling tasks at the expense of construction an optimal or close to optimal schedule, which minimizes the average deviation time from due dates. The following tasks:  performing the known scheduling results analytical review;  developing an algorithm for minimizing the total deviation for common due date by parallel machine scheduling; 6  developing a software implementation of the algorithm in a form that can be used for schedule optimizing;  performing an analysis of the results. The object of study is operational planning of small-scale production. Subject of research: models and methods for solving scheduling problems in order to minimize the total deviation of completion times from a common due date by parallel machines. Scientific novelty of the research. A heuristic algorithm for solving the problem of minimizing the total deviation from the common policy term when performing tasks with parallel devices is developed. Publications. Materials of the work are published in the International Scientific Journal "Scientific Review" - № 9 (14). - p. 14-32 in 2017 [1], materials are also published in the theses of the 20th International Scientific and Technical Conference SAIT 2018 [2] and in the scientific conference of students, graduate students and postgraduates "Informatics and Computing" 2018 [3].uk
dc.description.abstractukМагістерська дисертація: 101 с., 26 рис., 22 табл., 1 додаток, 55 джерел. Актуальність. Задачі теорії розкладів широко вивчаються в літературі останні 50 років, їх розгляду приділяється значна увага з боку багатьох вчених і фахівців-практиків по всьому світу. Складні реальні задачі, з якими стикаються різні типи компаній, стали викликом для пошуку шляхів їх розв’язання. Результати отримані дослідженнями різних науковців свідчать про актуальність проблеми та потребу в її подальшому дослідженні. Таким чином, можна з упевненістю сказати, що питання теорії розкладів є одним з найбільш поширених питань в галузі дослідження операцій і наук управління. Проблематика теорії розкладів охоплює дослідження обчислювальної складності задач, розробку точних, наближених та евристичних алгоритмів їх розв’язання. При цьому більшість праць присвячено розвитку комбінаторних підходів. Однак, як показує практика, можливості комбінаторних алгоритмів суттєво обмежені розмірністю розв’язуваних задач. У зв’язку з цим актуальною є розробка програмного продукту для складання розкладу виконання завдань паралельними пристроями, який допоможе мінімізувати сумарне відхилення від директивних строків. Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках теми «Ефективні методи розв’язання задач теорії розкладів» (№ 0117U000919). Мета і завдання дослідження – підвищення якості розв’язку задач календарного планування за рахунок побудови оптимального чи близького до оптимального розкладу, що дозволяє мінімізувати середній час відхилення від директивних строків. 4 Для досягнення мети необхідно виконати наступні завдання:  виконати аналітичний огляд відомих результатів, з розв’язання поставленої в рамках роботи задачі;  розробити алгоритм створення календарного плану виконання завдань паралельними пристроями, що мінімізує сумарне відхилення моментів завершення завдань від директивних строків;  розробити програмну реалізацію розробленого алгоритму;  виконати аналіз отриманих результатів. Об’єкт дослідження – оперативно-календарне планування дрібносерійного виробництва. Предмет дослідження – моделі та методи розв’язання задач календарного планування з метою мінімізації сумарного відхилення виконання завдань від директивних строків паралельними пристроями. Методи дослідження, застосовані в роботі, базуються на методах та алгоритмах теорії розкладів та дослідження операцій. Наукова новизна отриманих результатів. Розроблено евристичний алгоритм розв‘язання задачі мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроями. Публікації. Матеріали роботи опубліковано у Міжнародному науковому журналі «Науковий огляд» – №9(14). – с. 14–32 у 2017 році [1], також матеріали опубліковано в тезах 20-ї Міжнародної науково-технічної конференції SAIT 2018 [2], наукової конференції студентів, магістрантів та аспірантів «Інформатика та обчислювальна техніка» – ІОТ-2018 [3].uk
dc.format.page101 с.uk
dc.identifier.citationМаленко, А. О. Задача мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроями : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Маленко Анастасія Олексіївна. – Київ, 2018. – 101 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/23799
dc.language.isoukuk
dc.publisher.placeКиївuk
dc.subjectрозкладuk
dc.subjectдирективний строкuk
dc.subjectмомент запускуuk
dc.subjectпаралельні пристроїuk
dc.subjectідентичні пристроїuk
dc.subjectпропорційні пристроїuk
dc.subjectзапізненняuk
dc.subjectвипередженняuk
dc.subjectмінімізація сумарного відхиленняuk
dc.subjectscheduleuk
dc.subjectdue dateuk
dc.subjectrelease dateuk
dc.subjectparallel machinesuk
dc.subjectidentical machinesuk
dc.subjectproportional machinesuk
dc.subjecttardinessuk
dc.subjectearlinessuk
dc.subjectminimizing total deviationuk
dc.subject.udc519.854.2uk
dc.titleЗадача мінімізації сумарного відхилення від спільного директивного строку при виконанні завдань паралельними пристроямиuk
dc.typeMaster Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Malenko_magistr.pdf
Розмір:
6.94 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.74 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (АСОІУ)
Магістерські роботи