Создание математических моделей и методов иерархического планирования и принятия решений в производственных системах с ограниченными ресурсами
Общая фундаментальная проблема, на решение которой направлен проект – разработка математических моделей и методов иерархического планирования и принятия решений в сложных организационно-производственных системах с сетевым представлением технологических процессов и ограниченными ресурсами.
Создана методология построения иерархических моделей планирования и принятия решений в сложных организационно-производственных системах. На ее основе разработана иерархическая модель планирования, которой отвечает принципиально новый уровень математического обеспечения и в которой общая математическая модель задачи календарного планирования заменена последовательностью дискретных математических моделей, совместимых с иерархией решений, которые должны быть приняты на каждом уровне управления. Разработанная система взаимосвязанных моделей и методов их решения позволяет учитывать большое количество разнообразных производственных связей, имеющихся ресурсов, сложность продукции, большое количество стадий производства, неодновременность поступления заданий на выполнение. В отличие от существующих методов планирования, лучшие из которых содержат линейную или случайную комбинацию разных правил предпочтения, что не гарантирует качества полученных решений, в процессе решения задачи планирования определяется стратегия поиска глобального оптимума, что позволяет получить решения, близкие к оптимальным.
На основе разработанной авторами конструктивной теории решения труднорешаемых задач комбинаторной оптимизации, не имеющей аналогов в мире, создана система новых высокоэффективных взаимосвязанных алгоритмов решения задач планирования по разным критериям оптимальности, эффективные точные методы и новые модифицированные ПДС- алгоритмы (алгоритмы с полиномиальной и декомпозиционной составляющими) решения известных NP-трудных задач теории расписаний, лежащих в основе разработанных моделей, по критериям минимизации суммарного запаздывания выполнения заданий одним прибором (МСЗ) и минимизации суммарного штрафа за запаздывание выполнения заданий одним прибором (МСШ). Для задачи МСЗ верхняя оценка вычислительной сложности полиномиальной составляющей алгоритма определена как полином третьей степени от числа заданий, для экспоненциальной составляющей алгоритма определены условия, выполнение которых в процессе реализации алгоритма приводит к существенному увеличению объема вычислений. Статистические исследования показали, что вне этих условий для произвольной индивидуальной задачи реализованное количество направленных перестановок и отсечений экспоненциальной составляющей алгоритма позволяет получать точное решение для задач размерности до 1000 заданий, что невозможно сделать существующими методами. Для задачи МСШ получены решения для задач, не разрешимых известными методами, доказана их оптимальность. Получены условия выполнения полиномиальной составляющей и отсечения экспоненциальной составляющей алгоритма. Алгоритм также позволяет в результате введения правил декомпозиции и дополнительных условий отсечения бесперспективных вариантов строить быстродействующие эффективные эвристические алгоритмы со значением показателя качества, которое незначительно отличается от оптимального, с оценкой этого отклонения для каждой индивидуальной задачи.
На основе нового авторского подхода к решению задачи многокритериального выбора созданы конструктивные математические модели оптимизации линейного и выпуклого квадратичного программирования в методе анализа иерархии Саати для нахождения весов по хорошо или плохо согласованным неоднородным матрицам парных сравнений, по матрицам парных сравнений, не содержащим цифровой информации и по матрицам парных сравнений с односторонними ограничениями. Новые модели оптимизации решают проблему нахождения весов по плохо согласованной неоднородной матрице и обоснование эффективности полученного решения, что существенно расширяет возможности их практического использования.
Создана информационная технология и интегрированный пакет программ, реализующий решение задач планирования в сложных организационно-производственных системах по различным критериям оптимальности и задачи многокритериального выбора на основе новых моделей оптимизации по неоднородным матрицам парных сравнений для нахождения весов в методе анализа иерархии Саати. Таким образом, впервые в комплексе решена проблема как построения календарных планов по разным критериям оптимальности, так и выбора наилучшего из них.