Труднорешаемые задачи комбинаторной оптимизации и теория ПДС-алгоритмов

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

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