Ревотюк Михаил Павлович, к.т.н., доцент, доцент кафедры информационных технологий автоматизированных систем
220013, г. Минск, ул. П. Бровки, 6
тел. +375-17-293-86-58
Revotjuk Mikhail Pavlovich, PhD, Associate Professor, Associate Professor of Information Technologies in Automated Systems Department
220013, Minsk, P. Brovka str., 6
tel. +375-17-293-86-58
cтарший преподаватель кафедры информационных технологий автоматизированных систем
г. Минск
Senior Lecturer of Information Technologies in Automated Systems Department
Minsk
д.т.н., профессор, профессор кафедры систем управления
г. Минск
D.Sci., Professor, Professor of Control Systems Department
Minsk
д.т.н., профессор, декан факультета информационных технологий и управления
г. Минск
D.Sci., Professor, Dean of Faculty of Information Technologies and Control
Minsk
Цель работы – разработка моделей и алгоритмов оптимизации паросочетаний в динамически формируемых графах асимметричных отношений в координируемых открытых системах взаимодействующих агентов с централизованным и коллективным управлением. Динамическая асимметричная задача оптимизации паросочетаний здесь возникает как результат компромиссной аппроксимации отображения метода динамического программирования на поток известных открытых задач о назначении или нескольких странствующих коммивояжёров. Однако представленные таким образом альтернативы ветвления на независимых задачах не учитывают взаимозависимость реальных отношений между агентами и их заданиями, включая их привязку ко времени. Игнорирование зависимости альтернатив ветвления приводит к задержке момента или потере качества назначения заданий координируемым агентам. Основная идея предлагаемой реализации известного для эффективного управления принципа – откладывание момента принятия окончательного решения на наиболее поздний момент, учет восприимчивости системы к локальным изменениям переменных состояния. Взаимозависимость состояний выявляется на основе анализа соответствия графа текущего паросочетания оптимальному решению на подграфе совершенного паросочетания. Переход между состояниями реализуется инкрементальной версией алгоритма реоптимизации решения линейных задач о назначении методом кратчайшего пополняющего пути. Пространство состояний поиска – динамически формируемый двудольный разреженный граф альтернатив сочетания агентов и задач, представленный списком дуг. Для выделения множеств изменившихся дуг предложено дополнить веса дуг границами интервалов устойчивости решения, факультативно формируемых в фоновом режиме. По умолчанию вес измененной дуги совпадает с границей интервала устойчивости. На каждом цикле коррекции списков агентов, задач и их ассоциаций выделяются подмножества элементов, для которых требуется пересмотр паросочетания. Усиленное условие отбора таких элементов – выход за границы интервала устойчивости. При этом асимметрия задачи назначения учитывается выбором структуры смежности для доли графа с минимумом вершин. В результате время реакции процедур решения задачи назначения сокращается на порядок.
The purpose of the work is to develop models and algorithms for optimizing matching in dynamically generated graphs of asymmetric relations in coordinated open systems of interacting agents with centralized and collective control. The dynamic asymmetric matching optimization problem arises here as a result of a compromise approximation of the mapping of the dynamic programming method onto a stream of known open assignment problems or several traveling salesmen. However, the branching alternatives presented in this way for independent tasks do not take into account the interdependence of real relationships between agents and their tasks, including their relationship to time. Ignoring the dependence of branching alternatives leads to a delay in the moment or to a loss in the quality of assignment of tasks to coordinated agents. The main idea of the proposed implementation of the principle known for effective control is to postpone the moment the final decision is made to the latest moment, taking into account the susceptibility of the system to local changes in state variables. The interdependence of states is revealed on the basis of the analysis of the correspondence of the graph of the current matching with the optimal solution on the subgraph of perfect matching. The transition between states is implemented by the incremental version of the reoptimization algorithm for solving linear problems of assigning the shortest replenishing path using the method. The space of search states is a dynamically generated bipartite sparse graph of alternatives for a combination of agents and tasks, represented by a list of arcs. To highlight the sets of changed arcs, it is proposed to supplement the weight of the arcs with the boundaries of the stability intervals of the solution, optionally formed in the background. By default, the weight of the modified arc matches the boundary of the stability interval. On each correction cycle of the lists of agents, tasks, and their associations, subsets of elements are selected for which reconsideration of matching is required. An enhanced condition for the selection of such elements is to go beyond the boundaries of the stability interval. In this case, the asymmetry of the assignment problem is taken into account by choosing the adjacency structure for the fraction of the graph with a minimum of vertices. As a result, the reaction time of procedures for solving the assignment problem is reduced by an order of magnitude.
The authors declare that there are no conflicts of interest present.