The Assignment Problem: An Example

1 The Assignment Problem: An ExampleA company has 4 machines available for Assignment to 4 tasks. Any machine can be assignedto any task, and each task requires processing by one machine. The time required to set upeach machine for the processing of each task is given in the table (Hours)Task 1 Task 2 Task 3 Task 4 Machine 113476 Machine 211154 Machine 36728 Machine 41359 The company wants to minimize the total setup time needed for the processing of all we think of the setup times as transportation costs and definexij= 1 if machineiis assigned to process taskj,0 if machineiis not assigned to process taskj,wherei= 1, 2, 3, 4 andj= 1, 2, 3, 4, then it is easily seen that what we have is a balancedtransportation problem with 4 sources (representing the machines), 4 sinks (representing thetasks)

2 , a single unit of supply from each source (representing the availability of a machine),and a single unit of demand at each sink (representing the processing requirement of a task).This particular class of transportation problems is called theassignment problems. Theseproblems can, of course, be solved by the streamlined Simplex algorithm. This is transportation tableau for this problem is given the least-cost method, an initial basic feasible solution can be easily obtained; this isshown in the tableau 2 3 4 134761100/1 0111542 1/1 /0 Sources67283 1/1 /013594 10/1 /0/1 /0/1 /0/1 /0/1 /0 These assignments are made in the following order:x41= 1,x33= 1,x42= 0,x12= 1,x24= 1,x14= 0, andx13= 0.

3 Notice that a standard feature of any basic feasible solutionin an Assignment problem is that it is , we will use theu-vmethod to conduct the optimality test. The modifiers associatedwith the current solution, based on the initial assignmentu1= 0, are shown in the 011154211u2= 2 Sources6728311u3= 513594101u4= 11111 Modifierv1= 2v2= 4v3= 7v4= 6It follows that the reduced costs associated with the nonbasic cells are: c11= 11, c21= 1, c22= 9, c23= 0, c31= 9, c32= 8, c34= 7, c43= 1, and c44= 4. Since c43= 1, thecurrent solution is not optimal, and the entering cell is cell (4,3).2 The stepping-stone path associated with cell (4,3) is shown below.

4 (1,2) (1,3) / / / / (4,2) (4,3) Notice that bothx13andx42are degenerate basic variables; therefore, the maximum possibleincrease for the entering variablex43is 0. This implies that we are about to conduct a pivotthat corresponds to the simple declaration thatx43replaces eitherx13orx42(but not both)as a degenerate basic variable in the basis. Since all three variables are equal to 0, there isno numerical change in the current solution. Such a pivot is called adegenerate us choose (arbitrarily) to letx13exit the current basis. Then, after conducting a pivotaccording to the above path and updating the modifiers (with the initial assignmentu4= 0),we obtain the new tableau 111154211u2= 1 Sources6728311u3= 3135941001u4= 01111 Modifierv1= 1v2= 3v3= 5v4= 5It is easily seen that the reduced costs associated with the nonbasic cells are: c11= 11, c13= 1, c21= 1, c22= 9, c23= 1, c31= 8, c32= 7, c34= 6, and c44= 4.

5 Since all ofthese are positive, we conclude that the current solution is (uniquely) optimal. Thus, it isoptimal to assign Machine 1 to Task 2, Machine 2 to Task 4, Machine 3 to Task 3, andMachine 4 to Task 1. The total setup time associated with this solution is 11 hours. Thiscompletes the solution of the noted earlier, every basic feasible solution in an Assignment problem is degeneracy is known to impede progress toward an optimal solution, other algorithmshave been developed for the solution of Assignment problems. These other algorithms are3designed with the avoidance of large numbers of degenerate pivots in mind; therefore, theyare more efficient than the streamlined Simplex algorithm.

6 We will not pursue the