Створення математичних моделей та методів ієрархічного планування та прийняття рішень в виробничих системах з обмеженими ресурсами

Скорочена інформація про документ
dc.contributor.advisorПавлов, О. А.uk
dc.contributor.advisorPavlov, Alexander A.en
dc.contributor.advisorПавлов, А. А.ru
dc.contributor.departmentНауково-дослідний інститут інформаційних процесівuk
dc.contributor.researchgrantorНаціональний технічний університет України «Київський політехнічний інститут»uk
dc.date.accessioned2018-04-13T13:13:30Z
dc.date.available2018-04-13T13:13:30Z
dc.date.issued2010
dc.description.abstractenThe overall fundamental problem to be solved by the project is the development of mathematical models and methods of hierarchical planning and decision making in a complex organizational and production systems with network representation of technological processes and limited resources. The methodology for hierarchical models of planning and decision-making constructing in the complex organizational and production systems was created. On its basis the hierarchical planning model corresponding to a new level of mathematical software was developed, in which a general mathematical model of the scheduling problem is replaced by a sequence of discrete mathematical models which are compatible with the hierarchy of decisions that must be taken at each level of management. The system of interrelated models and methods created for solving them takes into account a wide variety of industrial ties, available resources, the production complexity, a large number of production stages, nonsimultaneous inflow of tasks. In contrast to existing methods of planning, the best of which contain a linear or a random combination of different preference rules that does not guarantee the quality of obtained solutions, the strategy for finding a global optimum is defined in the process of solving the planning problem, which allows to obtain solutions close to optimal. On the basis of the constructive theory for the intractable combinatorial optimization problems solution, which was developed by the authors and has no analogues in the world, a system of new highly interrelated algorithms was created for solving planning problems for different optimization criteria, effective accurate methods and the new modified PDC-algorithms (algorithms with polynomial and decompositional components) for solution of well-known NP-hard scheduling problems underlying the developed models, according to the criteria of total tardiness minimization on single machine (TT) and minimizing the total penalty for tardiness on single machine (TPT). For the TT problem the upper bound of computational complexity of the polynomial component of the algorithm was defined as a third-degree polynomial on the number of jobs; for the exponential component of the algorithm the conditions were defined that in the process of implementation of the algorithm lead to a significant increase of calculations. Statistical investigations have shown that outside these conditions for any individual problem the realized number of directed permutations and pruning for exponential component of the algorithm allows to obtain an exact solution for problems of dimension up to 1000 jobs that can not be done by existing methods. For the TPT problem were obtained solutions for problems not solvable by known techniques, their optimality was proven. The conditions obtained for the polynomial component execution and pruning for the exponential component of the algorithm. The algorithm also allows by implementation of decomposition rules and additional pruning conditions for unpromising options to build fast effective heuristic algorithms with the value of the quality index, which differs slightly from the optimum, with an estimation of this difference for each individual problem. Based on the new author’s approach of solving the multi-criteria choice problem the mathematical model of optimization were created for linear and convex quadratic programming in Saaty Analytic Hierarchy Process for finding the weights on well or poorly consistent heterogeneous matrices of paired comparisons, the matrices of paired comparisons that do not contain digital information and the matrices of paired comparisons with one-sided constraints. New optimization models solve the problem of finding the weights on poorly consistent heterogeneous matrix and of the solution effectiveness justification, which significantly expands the possibilities of their practical use. The information technology and integrated software suite were created that implement the planning problems solution in complex organizational and production systems for various optimization criteria and the problem of multi-criteria choice on the basis of new optimization models on heterogeneous matrices of paired comparisons for finding the weights in Saaty Analytic Hierarchy Process. Thus, for the first time the problem of constructing schedules on different optimization criteria and selecting the best of them was solved as the complex.uk
dc.description.abstractruОбщая фундаментальная проблема, на решение которой направлен проект – разработка математических моделей и методов иерархического планирования и принятия решений в сложных организационно-производственных системах с сетевым представлением технологических процессов и ограниченными ресурсами. Создана методология построения иерархических моделей планирования и принятия решений в сложных организационно-производственных системах. На ее основе разработана иерархическая модель планирования, которой отвечает принципиально новый уровень математического обеспечения и в которой общая математическая модель задачи календарного планирования заменена последовательностью дискретных математических моделей, совместимых с иерархией решений, которые должны быть приняты на каждом уровне управления. Разработанная система взаимосвязанных моделей и методов их решения позволяет учитывать большое количество разнообразных производственных связей, имеющихся ресурсов, сложность продукции, большое количество стадий производства, неодновременность поступления заданий на выполнение. В отличие от существующих методов планирования, лучшие из которых содержат линейную или случайную комбинацию разных правил предпочтения, что не гарантирует качества полученных решений, в процессе решения задачи планирования определяется стратегия поиска глобального оптимума, что позволяет получить решения, близкие к оптимальным. На основе разработанной авторами конструктивной теории решения труднорешаемых задач комбинаторной оптимизации, не имеющей аналогов в мире, создана система новых высокоэффективных взаимосвязанных алгоритмов решения задач планирования по разным критериям оптимальности, эффективные точные методы и новые модифицированные ПДС- алгоритмы (алгоритмы с полиномиальной и декомпозиционной составляющими) решения известных NP-трудных задач теории расписаний, лежащих в основе разработанных моделей, по критериям минимизации суммарного запаздывания выполнения заданий одним прибором (МСЗ) и минимизации суммарного штрафа за запаздывание выполнения заданий одним прибором (МСШ). Для задачи МСЗ верхняя оценка вычислительной сложности полиномиальной составляющей алгоритма определена как полином третьей степени от числа заданий, для экспоненциальной составляющей алгоритма определены условия, выполнение которых в процессе реализации алгоритма приводит к существенному увеличению объема вычислений. Статистические исследования показали, что вне этих условий для произвольной индивидуальной задачи реализованное количество направленных перестановок и отсечений экспоненциальной составляющей алгоритма позволяет получать точное решение для задач размерности до 1000 заданий, что невозможно сделать существующими методами. Для задачи МСШ получены решения для задач, не разрешимых известными методами, доказана их оптимальность. Получены условия выполнения полиномиальной составляющей и отсечения экспоненциальной составляющей алгоритма. Алгоритм также позволяет в результате введения правил декомпозиции и дополнительных условий отсечения бесперспективных вариантов строить быстродействующие эффективные эвристические алгоритмы со значением показателя качества, которое незначительно отличается от оптимального, с оценкой этого отклонения для каждой индивидуальной задачи. На основе нового авторского подхода к решению задачи многокритериального выбора созданы конструктивные математические модели оптимизации линейного и выпуклого квадратичного программирования в методе анализа иерархии Саати для нахождения весов по хорошо или плохо согласованным неоднородным матрицам парных сравнений, по матрицам парных сравнений, не содержащим цифровой информации и по матрицам парных сравнений с односторонними ограничениями. Новые модели оптимизации решают проблему нахождения весов по плохо согласованной неоднородной матрице и обоснование эффективности полученного решения, что существенно расширяет возможности их практического использования. Создана информационная технология и интегрированный пакет программ, реализующий решение задач планирования в сложных организационно-производственных системах по различным критериям оптимальности и задачи многокритериального выбора на основе новых моделей оптимизации по неоднородным матрицам парных сравнений для нахождения весов в методе анализа иерархии Саати. Таким образом, впервые в комплексе решена проблема как построения календарных планов по разным критериям оптимальности, так и выбора наилучшего из них.uk
dc.description.abstractukЗагальна фундаментальна проблема, на вирішення якої спрямовано проект – розробка математичних моделей та методів ієрархічного планування та прийняття рішень в складних організаційно-виробничих системах з мережним представленням технологічних процесів та обмеженими ресурсами. Створена методологія побудови ієрархічних моделей планування та прийняття рішень в складних організаційно-виробничих системах. На її основі розроблена ієрархічна модель планування, якій відповідає принципово новий рівень математичного забезпечення та в якій загальна математична модель задачі календарного планування замінена послідовністю дискретних математичних моделей, сумісних з ієрархією рішень, що повинні бути прийняті на кожному рівні управління. Розроблена система взаємозв’язаних моделей та методів їх розв’язання дозволяє враховувати велику кількість різноманітних виробничих зв’язків, наявних ресурсів, складність продукції, велику кількість стадій виробництва, неодночасність надходження завдань на виконання. На відміну від існуючих методів планування, кращі з яких містять лінійну чи випадкову комбінацію різних правил переваги, що не гарантує якості отриманих розв’язків, в процесі розв’язання задачі планування визначається стратегія пошуку глобального оптимуму, що дозволяє отримати розв’язки, близькі до оптимальних. На основі розробленої авторами конструктивної теорії розв’язання важкорозв’язуваних задач комбінаторної оптимізації, що не має аналогів у світі, створено систему нових високоефективних взаємозв’язаних алгоритмів розв’язання задач планування за різними критеріями оптимальності, ефективні точні методи та нові модифіковані ПДС-алгоритми (алгоритми з поліноміальною та декомпозиційною складовими) розв’язання відомих NP- складних задач теорії розкладів, що лежать в основі розроблених моделей, за критеріями мінімізації сумарного запізнення виконання завдань одним приладом (МСЗ) та мінімізації сумарного штрафу за запізнення виконання завдань одним приладом (МСШ). Для задачі МСЗ верхня оцінка обчислювальної складності поліноміальної складової алгоритму визначена як поліном третього ступеня від числа завдань, для експоненційної складової алгоритму визначені умови, виконання яких у процесі реалізації алгоритму приводить до істотного збільшення обсягу обчислень. Статистичні дослідження показали, що поза цими умовами для довільної індивідуальної задачі реалізована кількість спрямованих перестановок і відсікань експоненційної складової алгоритму дозволяє одержувати точний розв’язок для задач розмірності до 1000 завдань, що неможливо зробити існуючими методами. Для задачі МСШ отримані розв’язки для задач, що не розв’язані відомими методами, доведена їхня оптимальність. Отримані умови виконання поліноміальної складової та відсікання експоненційної складової алгоритму. Алгоритм також дозволяє в результаті введення правил декомпозиції та додаткових умов відсікання безперспективних варіантів будувати швидкодіючі ефективні евристичні алгоритми зі значенням показника якості, що незначно відрізняється від оптимального, з оцінкою цього відхилення для кожної індивідуальної задачі. На основі нового авторського підходу до розв’язання задачі багатокритеріального вибору створено конструктивні математичні моделі оптимізації лінійного та випуклого квадратичного програмування в методі аналізу ієрархії Сааті для знаходження ваг за добре чи погано погодженими неоднорідними матрицями парних порівнянь, за матрицями парних порівнянь, що не містять цифрової інформації та за матрицями парних порівнянь з однобічними обмеженнями. Нові моделі оптимізації вирішують проблему знаходження ваг за погано погодженою неоднорідною матрицею та обґрунтування ефективності отриманого розв’язку, що суттєво розширює можливості їх практичного використання. Створено інформаційну технологію та інтегрований пакет програм, що реалізує розв’язання задач планування в складних організаційно-виробничих системах за різними критеріями оптимальності та задачі багатокритеріального вибору на основі нових моделей оптимізації за неоднорідними матрицями парних порівнянь для знаходження ваг в методі аналізу ієрархії Сааті. Таким чином, вперше в комплексі розв’язано проблему як побудови календарних планів за різними критеріями оптимальності, так і вибору найкращого з них.uk
dc.format.page7 c.uk
dc.identifier.govdoc0108U001346
dc.identifier.other2100_0
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/22766
dc.language.isoukuk
dc.publisherНТУУ «КПІ»uk
dc.publisher.placeКиївuk
dc.subjectматематичні моделіuk
dc.titleСтворення математичних моделей та методів ієрархічного планування та прийняття рішень в виробничих системах з обмеженими ресурсамиuk
dc.title.alternativeMathematical models and methods creation for hierarchical planning and decision making in production systems with limited resourcesuk
dc.title.alternativeСоздание математических моделей и методов иерархического планирования и принятия решений в производственных системах с ограниченными ресурсамиuk
dc.typeTechnical Reportuk

Файли

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

Зібрання

Анотовані описи завершених науково-дослідних робіт КПІ ім. Ігоря Сікорського