Assignment Problem

A job production unit has four jobs P, Q, R, S which can be manufactured on each of the four machines I, II, III and IV. The processing cost of each job for each machine is given in the following table :

Complete the following activity to find the optimal assignment to minimize the total processing cost.

Solution:

Step 1: Subtract the smallest element in each row from every element of it. New assignment matrix is obtained as follows :

Step 2: Subtract the smallest element in each column from every element of it. New assignment matrix is obtained as above, because each column in it contains one zero.

Step 3: Draw minimum number of vertical and horizontal lines to cover all zeros:

Step 4: From step 3, as the minimum number of straight lines required to cover all zeros in the assignment matrix equals the number of rows/columns. Optimal solution has reached.

Examine the rows one by one starting with the first row with exactly one zero is found. Mark the zero by enclosing it in (`square`), indicating assignment of the job. Cross all the zeros in the same column. This step is shown in the following table :

Step 5: It is observed that all the zeros are assigned and each row and each column contains exactly one assignment. Hence, the optimal (minimum) assignment schedule is :

Hence, total (minimum) processing cost = 25 + 21 + 19 + 34 = ₹`square`

Fill in the blank :

An _______ is a special type of linear programming problem.

A plant manager has four subordinates and four tasks to perform. The subordinates differ in efficiency and task differ in their intrinsic difficulty. Estimates of the time subordinate would take to perform tasks are given in the following table:

Complete the following activity to allocate tasks to subordinates to minimize total time.

Solution:

Step I: Subtract the smallest element of each row from every element of that row:

Step II: Since all column minimums are zero, no need to subtract anything from columns.

Step III: Draw the minimum number of lines to cover all zeros.

Since minimum number of lines = order of matrix, optimal solution has been reached

Optimal assignment is A →`square`  B →`square`

C →IV  D →`square`

Total minimum time = `square` hours.

Solve the following problem :

A dairy plant has five milk tankers, I, II, III, IV and V. These milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.

How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?

Fill in the blank :

When an assignment problem has more than one solution, then it is _______ optimal solution.

In a factory there are six jobs to be performed each of which should go through two machines A and B in the order A - B. The processing timing (in hours) for the jobs arc given here. You are required to determine the sequence for performing the jobs that would minimize the total elapsed time T. What is the value of T? Also find the idle time for machines · A and B.

A job production unit has four jobs P, Q, R, and S which can be manufactured on each of the four machines I, II, III, and IV. The processing cost of each job for each machine is given in the following table:

Find the optimal assignment to minimize the total processing cost.

Find the optimal solution for the assignment problem with the following cost matrix.