| Advertisement |
The Assignement Problem is another special case of Linear Programming (LLP). It occurs when n jobs are to be assigned to n facilities on a one-to-one basis with a view to optimising the resource required.
THE ASSIGNMENT ALGORITHM
The assingment problem can be solved by applying the following steps :
Step 1: Subtract the minimum element of each row from all the elements in that row. From each column of the matrix so obtained, subtract its minimum element. The resulting matrix is the starting matrix for the following procedure.
Step 2: Draw the minimum number of horizontal and vertical lines that cover all the zeros. If this number of lines is n, order of the matrix, optimal assignment can be made by skipping steps 3 and 4 and proceeding with step 5. If, however, this number is less than n, go to the next step.
Step 3: Here, we try to increase the number of zeros in the matrix. We select the smallest element out of these which do not lie on any line. Subtract this element from all such (uncovered) elements and add it to the elements which are placed at the intersections of the horizontal and vertical lines. Do not alter the elements through which only one line passes.
Step 4: Repeat steps 1, 2 and 3 until we get the minimum number of lines equal to n.
Step 5 (A) Starting with first row, examine all rows of matrix in step 2 or 4 in turn until a row containing exactly one zero is found. Surround this zero by () , indication of an assignment there. Draw a vertical line through the column containing this zero. This eliminates any confusion of making any further assignments in that column. Process all the rows in this way.
(B) Apply the same treatment to columns also. Starting with the first column, examine all columns until a column containing exactly one zero is found. Mark () around this zero and draw a horizontal line through the row containing this marked zero. Repeat steps 5A and B, until one of the following situations arises:
(i) No unmarked () or uncovered (by a line) zero is left,
(ii) There may be more than one unmarked zero in one column or row. In this case, put around one of the unmarked zero arbitrarily and pass 2 lines in the cells of the remaining zeros in its row and column. Repeat the process until no unmarked zero is left in the matrix.
