Інформаційна технологія календарного та оперативного планування в системах з мережевим представленням технологічних процесів
| dc.contributor.author | Лисецький, Тарас Миколайович | |
| dc.date.accessioned | 2021-04-06T12:01:49Z | |
| dc.date.available | 2021-04-06T12:01:49Z | |
| dc.date.issued | 2021 | |
| dc.description.abstracten | The dissertation is dedicated to research of information technology (IT) of job-shop scheduling in systems with precedence constraints based on highly efficient job-shop scheduling methods. Thanks to formalization of precedence constraints, modification of aggregation and disaggregation procedures and the procedures of coordinated planning from earlier created three-level scheduling model (3LM), substantiation of reducing the planning problem by any of the five basic criteria to a single scheduling problem, operational (the third level of 4LM) and operative (the fourth level of 4LM) planning levels formalization and development of the algorithms for operational scheduling and adjustments, an integral set of models and methods was created for the first time — the four-level model (4LM) of job-shop scheduling. The 4LM implements an efficient approximation method for Multi-Stage Job-Shop Scheduling Problems (MSJSP) in social and economic systems with precedence constraints and limited resources and methods of operational and operative planning. 4LM includes the decision-making unit (DMU) as a separate component that takes decisions during production planning. The process of obtaining operational plan (third level of 4LM) based on results of coordinated planning (second level of 4LM) has been formalized: if optimality criterion is one of the five base criteria then the operational planning task is defined and solved as multi-stage job-shop scheduling problem (task or task group completion times become due times for multi-stage job-shop scheduling problem), an affective solving method use PDC-algorithms for single stage scheduling; if optimality criterion is synthetic (linear combination of base criteria) alternative methods for building operational plan were suggested. One of them is original modified method of coordinated planning. Two algorithms for coordinated plan correction were developed, which are used on the fourth level. The first algorithm is a modification of algorithmic planning procedure on 1-3 levels. The problem is solved by one of four base criteria or their linear combination. The second algorithm of operational planning incorporates formal algorithm (includes PDC-algorithms for hard combinatorial problems) and planning by experts. In case of possibility of results implementation, the second algorithm effectively solves the problem of operational adjustment of operational plan obtained on the third level of planning. Therefore, for the first time 4LM implements scheduling procedure as both formal procedures and as well as expert decisions. For the first time, the efficiency of the MSJSP solving method has been proved by studying the efficiency of the solving algorithm for a problem of the 4LM’s first level with the use of statistical methods. It is shown that regardless of type of industry, operations processing order and an implementation of JSP, solving of scheduling problem by one of these five optimality criteria is reduced to obtaining a feasible solution of the JSP by criterion of earliest job start time maximization. It is shown that solving efficiency of the JSP depends on efficiency of the first level of 4LM. Therefore, efficiency of MWCT problem solving is studied and statistically substantiated. The efficiency of the PDC-algorithm and the approximation algorithm has been proven for the case when weights of all nodes of the precedence graph, except the final ones, are zero (MWCTZ problem). The mathematical models for solving a scheduling problem “Uniform parallel-machine scheduling with independent jobs whose start times are less than a common due date to minimize total tardiness” (MTTPM) (used at the fourth level of 4LM) have been created. Unlike others, the new method allows to get exact solution for problems with tens of thousands of variables in case of optimality criteria fulfillment otherwise approximate solution with evaluation of deviation from optimum. The MTTPM problem was also generalized to the case when some or all jobs must not violate the common due date. An approximation algorithm based on the sequential solution of two different MTTPM problems has been developed. Three statements characterizing the theoretical properties of the approximation algorithm are proved. These statements allow: finding conditions when the problem has no solution; finding sufficient conditions of conditionally-optimal solution (optimal under condition that schedule is found for given job set which all are non-delayed); finding statistically sufficient factors of solution optimality; finding the lowest limit of functional value of optimal solution. The problem properties have been investigated and theoretically substantiated. On the basis of 4LM, an IT for job-shop scheduling in systems with precedence constraints has been created. It was implemented as general-purpose job-shop scheduling information system. The system is used to automate the production planning process at the "LETA" enterprise (Mukachevo town). It can work with data of real production sizes — hundreds of thousands of jobs on thousands of machines. | uk |
| dc.description.abstractru | Работа посвящена созданию информационной технологии календарного и оперативного планирования (КОП) в системах с сетевым представлением технологических процессов на основе высокоэффективных методов решения задач КОП, формализации пооперационного сетевого представления дискретных технологических процессов, модификации известных процедур агрегации и дезагрегации сетевой модели и согласованного планирования, обоснования сведения задачи планирования по любому из пяти базовых критериев к одной задаче составления расписаний. Впервые создан целостный комплекс моделей и методов — четырехуровневая модель КОП. Разработан новый метод решения NP-трудной задачи теории расписаний «Составление расписания выполнения независимых заданий идентичными параллельными приборами, моменты запуска которых меньше общего директивного срока», позволяющий получать точное решение для задач с десятками тысяч переменных при выполнении признаков его оптимальности или приближенное решение с оценкой отклонения от оптимума при их невыполнении. Разработана информационная технология календарного и оперативного планирования в системах с сетевым представлением технологических процессов. Система используется на предприятии ФГ «ЛЕТА» (г. Мукачево). | uk |
| dc.description.abstractuk | Робота присвячена створенню інформаційної технології (ІТ) календарного та оперативного планування (КОП) в системах з мережевим представленням технологічних процесів на основі високоефективних методів розв’язання задач КОП, формалізації поопераційного мережевого представлення дискретних технологічних процесів, модифікації відомих процедур агрегації та дезагрегації мережевої моделі та узгодженого планування, обґрунтування зведення задачі планування за будь-яким з п’яти базових критеріїв до однієї задачі складання розкладів. Вперше створено цілісний комплекс моделей та методів — чотирьохрівнева модель КОП. Розроблено новий метод розв’язання NP-складної задачі теорії розкладів «Складання розкладу виконання незалежних завдань ідентичними паралельними пристроями, моменти запуску яких менше спільного директивного строку», який дозволяє отримувати точний розв’язок для задач із десятками тисяч змінних при виконанні ознак його оптимальності або наближений розв’язок з оцінкою відхилення від оптимуму при їх невиконанні. Створена інформаційна технологія календарного та оперативного планування в системах з мережевим представленням технологічних процесів. Система використовується на підприємстві ФГ «ЛЕТА» (м. Мукачево). | uk |
| dc.format.page | 27 с. | uk |
| dc.identifier.citation | Лисецький, Т. М. Інформаційна технологія календарного та оперативного планування в системах з мережевим представленням технологічних процесів : автореф. дис. … канд. наук. : 05.13.06 – інформаційні технології / Лисецький Тарас Миколайович. – Київ, 2021. – 27 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/40451 | |
| dc.language.iso | uk | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | багатоетапна задача календарного планування | uk |
| dc.subject | оперативне планування | uk |
| dc.subject | теорія розкладів | uk |
| dc.subject | multi-stage scheduling problem | uk |
| dc.subject | operational planning | uk |
| dc.subject | scheduling theory | uk |
| dc.subject | многоэтапная задача календарного планирования | uk |
| dc.subject | оперативное планирование | uk |
| dc.subject | теория расписаний | uk |
| dc.subject.udc | 004.9:658.5:519.854 | uk |
| dc.title | Інформаційна технологія календарного та оперативного планування в системах з мережевим представленням технологічних процесів | uk |
| dc.type | Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Lysetskyi_aref.pdf
- Розмір:
- 785.17 KB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.01 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: