Step 1: Create a Cost Matrix:
Formulate a cost matrix representing the costs or benefits associated with each task-agent pair.
Ensure that the matrix is square.
Step 2: Subtract Row and Column Minima:
For each row, find the minimum element and subtract it from every element in that row. Next, do
the same for each column. This step is aimed at creating as many zeros as possible in the matrix.
Step 3: Cover Zeros with Minimum Number of Lines:
Cover the zeros with the minimum number of horizontal and vertical lines. If the number of lines
is equal to the matrix size, an optimal solution has been reached. If not, proceed to the next step.
Step 4: Identify the Smallest Uncovered Element:
Identify the smallest element that is not covered by any line. This element is referred to as the
minimum uncovered element (MUE).
Step 5: Adjust Matrix Elements:
Subtract the MUE from the uncovered elements and add it to the elements that are at the
intersection of two lines. This step modifies the matrix to continue the process of finding zeros
and covering lines.
Step 6: Repeat Until Optimality is Achieved:
Repeat steps 3 to 5 until an optimal assignment is achieved, which is when the number of lines
covering zeros equals the matrix size.
