CN-122019090-A - Multi-machine cooperation task allocation optimization method and system based on contract network

CN122019090ACN 122019090 ACN122019090 ACN 122019090ACN-122019090-A

Abstract

The invention relates to the field of industrial control automation, and provides a multi-machine cooperation task allocation optimization method based on a contract network. The method comprises the steps that a manager node generates a corresponding task notice for one or more tasks to be processed and broadcasts the task notice to a plurality of worker nodes, the worker nodes calculate corresponding grading values by using a preset grading function according to evaluation standards of the tasks and form a grading matrix, grading results are sent to the manager node, the manager node builds the grading matrix according to the received grading results, a hungarian algorithm is used for solving the grading matrix, an optimal task allocation scheme meeting task assignment constraint conditions is obtained, and task execution instructions are issued to selected worker nodes. And the scoring result is structured and organized by utilizing the scoring matrix, and the optimal matching between the task and the worker is realized based on the Hungary algorithm, so that the efficiency and stability of task distribution are obviously improved, and the method is particularly suitable for the automatic task scheduling requirement in a multi-task multi-main-body cooperative scene.

Inventors

YU ZHIQUN
WANG TIANLIN
JIANG ZHENGHAO
XIE CANHUA
WU MENGWEI
SHI WEI
FU PANPAN

Assignees

浙江中控研究院有限公司
浙江至控科技有限公司

Dates

Publication Date: 20260512
Application Date: 20260127

Claims (10)

1. A multi-machine cooperation task allocation optimization method based on a contract network is characterized by comprising the following steps: step S1, a manager node generates a corresponding task notification book aiming at one or more tasks to be processed, and broadcasts the task notification book to a plurality of worker nodes, wherein the task notification book comprises task identifiers corresponding to the tasks, task content and evaluation criteria for evaluating task matching degree; Step S2, based on the task notification, the worker node calculates corresponding grading values by using a preset grading function according to the evaluation standard of the task and forms a grading matrix, and sends grading results to the manager node, wherein the grading function is that Wherein S is a scoring value, n is an evaluation dimension, The weight value representing the i-th dimension, Step S3, constructing a scoring matrix of the task to be distributed and the worker node according to the received scoring result by the manager node, and solving the scoring matrix by using a Hungary algorithm to obtain an optimal task distribution scheme meeting task assignment constraint conditions; step S4, according to the optimal task allocation scheme, the manager node issues task execution instructions to the selected worker nodes; And S5, selecting the worker nodes to execute the task according to the task execution instruction, and feeding back an execution result to the manager node.
2. The method for optimizing allocation of multiple collaborative tasks according to claim 1, wherein the manager node generates a corresponding task notification for one or more tasks to be processed, and broadcasts the task notification to a plurality of worker nodes, wherein the task notification includes task identifiers corresponding to the tasks, task content, and evaluation criteria for evaluating task matching degree, and the method comprises: The manager node obtains task description information of one or more tasks, including the task identifier, the task content, the task type and the execution requirement; Setting the evaluation standard for evaluating the task matching degree for each task based on the task type and the execution requirement, wherein the evaluation standard comprises task complexity, required resource capacity, priority and time requirement; And packaging the task identification and the evaluation standard into a task notice, and sending the task notice to one or more worker nodes according to a broadcasting strategy.
3. The method of claim 1, wherein the task notification further comprises execution constraints, the execution constraints comprising node resource limitations, acceptable time windows, task dependencies, or node role permission requirements.
4. The multi-machine collaborative task allocation optimization method according to claim 3, wherein based on the task notification, the worker node calculates corresponding scoring values using a preset scoring function and forms a scoring matrix according to the evaluation criteria of the task, and sends scoring results to the manager node, comprising: The worker node receives the task notification and analyzes the task identifier, the task content, the evaluation criteria and the execution constraint condition; based on the evaluation criteria and the execution constraint conditions contained in the task notification, invoking the scoring function to evaluate the matching degree to obtain a corresponding scoring value, And forming scoring vectors according to the scoring values corresponding to the tasks and the sequence of the task identifications, and sending the scoring vectors to the manager node.
5. The method of claim 4, wherein the manager node constructs a scoring matrix for the task to be distributed and the worker node according to the received scoring result, and the method comprises: Receiving scoring vectors fed back from a plurality of worker nodes, wherein each scoring vector corresponds to a scoring value of one worker node for all the tasks to be processed; Splicing the scoring values in a row or column mode according to a preset task index sequence based on the scoring vector of each worker node to construct the scoring matrix of the task to be distributed and the worker node, wherein each element of the scoring matrix represents the scoring value of the corresponding worker node to the appointed task; and carrying out integrity check and standardization treatment on the scoring matrix to ensure that all tasks obtain effective scores and are compared under the unified scoring scale.
6. The method for optimizing allocation of multiple cooperative tasks according to claim 5, wherein the scoring matrix is And each element in the scoring matrix represents a scoring value of the corresponding worker node to the corresponding task, and the scoring value is calculated by a scoring function according to the scoring standard and the execution constraint condition in the task notification.
7. The multi-machine collaborative task allocation optimization method according to claim 6, wherein solving the scoring matrix using a hungarian algorithm to obtain an optimal task allocation scheme that satisfies task assignment constraints, comprises: performing dimension filling processing by taking the scoring matrix as input, and filling m-n columns of all-zero columns on the right side of the scoring matrix when the number of worker nodes is larger than the number of tasks to be processed so as to construct the scoring matrix in square form mxm ; Obtaining the maximum element value k in the scoring matrix, and constructing a new assignment problem matrix by taking the maximum element value k as a reference M is the number of worker nodes, and n is the number of tasks to be processed; to the assignment problem matrix Performing a normalization operation to construct a matrix S ", the normalization operation comprising subtracting the minimum element of each row of the matrix S' from the element of that row, and subtracting the minimum element of each column of the resulting new coefficient matrix from the element of that column; Based on the normalized matrix S '', executing the Hungary algorithm, and outputting the corresponding assignment correspondence between the worker nodes and the tasks.
8. The multi-machine collaborative task allocation optimization method according to claim 7, wherein executing the hungarian algorithm based on the normalized matrix s″ outputs an assigned correspondence between the corresponding worker node and the task, comprising: step S31, searching a matrix S '' for a zero element with unique row and column as an initial assignment candidate element; Step S32, when the number of the selected worker nodes is the same as the number of the tasks to be processed, the assignment relation between the tasks and the worker nodes is directly output; step S32, if not, selecting a row containing only one zero element from the matrix rows corresponding to the tasks which are not assigned, as a current assignment candidate, marking the other zero elements of the column where the zero element is located as exclusion elements, and preventing repeated assignment: Step S33, repeatedly executing the step S32 until the unique zero element meeting the condition cannot be selected, and acquiring a current feasible initial allocation scheme; Step S34, when the task or the worker node which is not allocated is still matched, constructing a minimum covered line set for the zero elements which are not allocated, searching a minimum non-zero value in the uncovered scoring matrix positions of the minimum covered line set, subtracting the minimum non-zero value from all elements in the uncovered positions, adding the elements in the double-covered positions, and thus adjusting the matrix to generate a new scoring matrix S ' ' '; and step S35, repeating the steps S31 to S34 based on the updated scoring matrix S ' ' ', until the optimal task allocation scheme with all the tasks forming the unique assignment relation with the worker node is obtained.
9. The method according to claim 8, wherein in step S34, constructing a minimum coverage line set for the zero elements that have not been allocated, includes: step S341, marking all lines which do not contain any assigned marking elements; Step S342, marking columns containing the zero elements in all marked rows; step S343, marking the row containing the assigned marking element in all marked columns; Step 344, repeatedly executing the step 342 and the step 343 until the marking behavior is not added; step S345, using all the rows that are not marked and all the columns that are marked as line coverage paths, all the zero elements in the matrix are covered.
10. A multi-machine cooperation task allocation optimization system based on a contract network, which adopts the multi-machine cooperation task allocation optimization method according to any one of claims 1 to 9, and is characterized by comprising the following steps of, The system comprises a broadcasting module, a plurality of worker nodes and a manager node, wherein the broadcasting module is used for generating a corresponding task notification for one or more tasks to be processed by the manager node, and broadcasting the task notification to the plurality of worker nodes, wherein the task notification comprises a task identifier corresponding to the task, task content and an evaluation standard for evaluating the matching degree of the task; the scoring calculation module is used for calculating corresponding scoring values by using a preset scoring function according to the evaluation standard of the task based on the task notification, forming a scoring matrix and sending the scoring result to the manager node; the allocation calculation module is used for constructing a scoring matrix of the task to be allocated and the worker node according to the received scoring result, and solving the scoring matrix by using a Hungary algorithm to obtain an optimal task allocation scheme meeting task assignment constraint conditions; the instruction issuing module is used for issuing a task execution instruction to the selected worker node by the manager node according to the optimal task allocation scheme; And the execution feedback module is used for selecting the worker nodes to execute the task according to the task execution instruction and feeding back the execution result to the manager node.

Description

Multi-machine cooperation task allocation optimization method and system based on contract network Technical Field The invention relates to the field of industrial control automation, in particular to a multi-machine cooperation task allocation optimization method and system based on a contract network. Background In the multi-equipment cooperative scene of industrial automation, intelligent manufacturing and the like, how to reasonably distribute a plurality of tasks to be executed to different execution equipment is a key problem for guaranteeing the system efficiency and the resource utilization rate. The distributed task allocation method is widely applied to multi-machine cooperation task scheduling due to the characteristics of high elasticity, expandability and the like. The contract network cooperation method is a distributed task cooperation method which is widely applied at present. The method refers to bidding mechanisms in commercial contracts, the participation subject is divided into two roles of a manager and a worker, the manager issues a task notice, the worker decides whether to bid and execute a task according to self conditions, and the whole process comprises four stages of bidding, winning bid and confirming. However, with the increase of the cooperation scale and the increase of the task number, the traditional contract net method gradually exposes the defects that firstly, a manager needs to evaluate and select optimal bidding from a large number of bidding schemes one by one, the calculation burden is too heavy, secondly, each worker needs to submit complete bidding content, so that the system communication pressure is high, thirdly, in the scene of parallel execution of a plurality of tasks, the method usually processes one by one according to the task sequence, the optimal allocation of the whole task cannot be realized, the problems of uneven resource utilization, suboptimal scheduling result and the like are easy to occur, and the application effect of the method in a large-scale multi-machine cooperation environment is limited. Therefore, an improved task allocation method is needed, which simplifies the communication process, reduces the burden of a manager, and supports the simultaneous optimal allocation of multiple tasks, so as to improve the overall scheduling efficiency and the resource utilization effect of the system. Disclosure of Invention Aiming at the problems, the invention aims to provide a multi-machine collaborative task allocation optimization and system based on a contract network, which aims to solve the problems that in the prior art, a manager needs to evaluate a large number of bids to cause heavy calculation load, a worker submits complete bidding contents to cause high communication pressure, and a plurality of tasks are allocated in sequence to realize global optimization. The above object of the present invention is achieved by the following technical solutions: The invention provides a multi-machine cooperation task allocation optimization method based on a contract network, which comprises the following steps: step S1, a manager node generates a corresponding task notice for one or more tasks to be processed, and broadcasts the task notice to a plurality of worker nodes, wherein the task notice comprises task identifications corresponding to the tasks, task content and evaluation criteria for evaluating task matching degree; Step S2, based on the task notification, the worker node calculates corresponding grading values by using a preset grading function according to the evaluation standard of the task, forms a grading matrix, and sends the grading result to the manager node, wherein the grading function is that Wherein S is a scoring value, n is an evaluation dimension,The weight value representing the i-th dimension,A score representing the ith dimension; step S3, the manager node constructs a scoring matrix of the task to be distributed and the worker node according to the received scoring result, and solves the scoring matrix by using a Hungary algorithm to obtain an optimal task distribution scheme meeting task assignment constraint conditions; step S4, according to the optimal task allocation scheme, the manager node issues task execution instructions to the selected worker nodes; and S5, each selected worker node executes the task according to the task execution instruction and feeds back an execution result to the manager node. Further, the manager node generates a corresponding task notification for one or more tasks to be processed, and broadcasts the task notification to a plurality of worker nodes, wherein the task notification comprises task identifiers corresponding to the tasks, task content and evaluation criteria for evaluating task matching degree, and the task notification comprises: the manager node acquires task description information of one or more tasks, including task identification, task content, task types and execution req