Задача мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями
| dc.contributor.advisor | Жданова, Олена Григорівна | |
| dc.contributor.author | Годна, Анастасія Вікторівна | |
| dc.date.accessioned | 2018-07-04T10:02:06Z | |
| dc.date.available | 2018-07-04T10:02:06Z | |
| dc.date.issued | 2018 | |
| dc.description.abstracten | Master’s thesis: 117 pages, 32 figures, 23 tables, 1 appendix, 125 references. Relevance. The theory of schedules and operational scheduling are important and interesting directions in the field of optimization and are currently experiencing a period of rapid development. This is connected, first of all, to the emergence of fundamentally new types of products, technologies, intensification of production, its continuous updating and improvement. The rapid development of communication systems, the Internet, logistics structures puts for mathematicians new tasks, including in the field of scheduling theory. In practice, there are many diverse tasks of calendar planning of production and sales of products, the efficient use of equipment and other resources, the coordination of the work of various services, and so on. A variety of mathematical models and scheduling methods usually puts for mathematicians and programmers the inevitable problem of constructing fast algorithms and their effective program implementation, taking into account the features of a solvable problem. Most tasks in the theory of scheduling and operational scheduling are NP-hard, and there are serious difficulties in solving them, since building an optimal schedule requires a great deal of time even with relatively small dimensions of the input data. In such a situation, it is necessary to conduct more in-depth research of problems within the framework of complexity theory. In this regard, it is important to develop a software product for drawing up schedules for the execution of tasks with parallel devices, which will help minimize the total deviation from the policy terms. 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 efficiency of scheduling by building optimal or near to optimal schedules and minimizing the total deviation time from the due dates. The following tasks: performing the known scheduling results review; developing an algorithm for minimizing total deviation time from the due dates for parallel machine scheduling; 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 the process of operational scheduling. Subject of research: models and methods for solving scheduling problems in order to minimize the total deviation of task`s execution from due dates by parallel machines. Research methods: theory of schedules, operations research and complexity theory. Scientific novelty of the research. The approach is developed to solve the problem of minimizing the total deviation of completion times from due dates by parallel machines. The method for solving the problem of minimizing the total deviation of completion times from due dates by parallel machines and has statistically stable high performance indicators. Publications. The materials are presented in the scientific article of the international scientific journal "Scientific Review" [123] (certificate of state registration КВ № 20878-10678Р), published in the abstracts a scientific conference of students, undergraduates and graduate students "Informatics and Computer Science" - ICT-2018 [124] and accepted for publication at 20th International scientific-technical conference SAIT 2018 "System analysis and information technologies" [125]. | uk |
| dc.description.abstractuk | Магістерська дисертація: 117 с., 32 рис., 23 табл., 1 додаток, 125 джерел. Актуальність. Теорія розкладів і календарне планування утворюють одне з важливих і цікавих напрямків в області оптимізації та в даний час переживають період бурхливого розвитку. Це пов'язано, перш за все, з появою принципово нових видів продукції, технологій, інтенсифікацією виробництва, його безперервним оновленням і вдосконаленням. Стрімкий розвиток систем зв'язку, інтернету, логістичних структур ставить перед математиками нові завдання, в тому числі в області теорії розкладів. На практиці виникає безліч різноманітних завдань календарного планування виробництва і збуту продукції, ефективного використання обладнання та інших ресурсів, узгодження роботи різних служб і так далі. Різноманітність математичних моделей і методів складання розкладів зазвичай ставить перед прикладними математиками й програмістами неминучу проблему побудови швидких алгоритмів і їх ефективної програмної реалізації з урахуванням особливостей вирішуваної задачі. Більшість задач теорії розкладів і календарного планування є NP-складними, і виникають серйозні труднощі при їх вирішенні, так як побудова оптимального розкладу вимагає великих затрат часу навіть при порівняно невеликих розмірностях вхідних даних. У такій ситуації необхідно проводити більш глибокі дослідження задач в рамках теорії складності. У зв’язку з цим актуальною є розробка програмного продукту для складання календарних планів виконання завдань паралельними пристроями, який допоможе мінімізувати сумарне відхилення від директивних строків. Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках теми «Ефективні методи розв’язання задач теорії розкладів» (номер держреєстрації 0117U000919). Мета дослідження – підвищення якості розв’язку задач календарного планування за рахунок побудови оптимального чи близького до оптимального розкладу, що дозволяє мінімізувати сумарний час відхилення від директивних строків. Для досягнення мети необхідно виконати наступні завдання: провести аналіз відомих результатів з розв’язання поставленої в рамках роботи задачі; розробити алгоритм створення календарного плану виконання завдань паралельними пристроями, що мінімізує сумарне відхилення моментів завершення завдань від директивних строків; виконати програмну реалізацію розробленого алгоритму; дослідити ефективність алгоритму при різних вхідних даних шляхом проведення обчислювальних експериментів; Об’єкт дослідження – процес календарного планування виконання завдань. Предмет дослідження – моделі та методи розв’язання задач календарного планування з метою мінімізації сумарного відхилення виконання завдань від директивних строків паралельними пристроями. Методи дослідження. Для виконання поставлених завдань у роботі було використано методи: теорії розкладів, дослідження операцій та теорії складності (при розробленні методів розв’язання задач складання розкладів). Наукова новизна отриманих результатів. Розроблено трьохетапний евристичний алгоритм розв‘язання задачі мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями. Набув подальшого розвитку метод розв’язання задачі задачі мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями та має статистично сталі високі показники роботи. Публікації. Матеріали роботи представлено у науковій статті міжнародного наукового журналу «Науковий огляд» [123] (свідоцтво про державну реєстрацію КВ № 20878-10678Р), опубліковані в тезах наукової конференції студентів, магістрантів та аспірантів «Інформатика та обчислювальна техніка» – ІОТ-2018 [124] та прийнято до публікації у вигляді тез 20-ї міжнародної конференції SAIT 2018 [125]. | uk |
| dc.format.page | 115 с. | uk |
| dc.identifier.citation | Годна, А. В. Задача мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Годна Анастасія Вікторівна. – Київ, 2018. – 115 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/23757 | |
| dc.language.iso | uk | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | паралельні пристрої | uk |
| dc.subject | директивний строк | uk |
| dc.subject | складання розкладів | uk |
| dc.subject | календарне планування | uk |
| dc.subject | мінімізація сумарного відхилення | uk |
| dc.subject | parallel machines | uk |
| dc.subject | due date | uk |
| dc.subject | scheduling | uk |
| dc.subject | minimizing total deviation | uk |
| dc.subject.udc | 519.854.2 | uk |
| dc.title | Задача мінімізації сумарного відхилення моментів завершення від директивних строків при виконанні завдань паралельними пристроями | uk |
| dc.type | Master Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Hodna_magistr.pdf
- Розмір:
- 1.93 MB
- Формат:
- Adobe Portable Document Format
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 7.74 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: