QT/U4 Topic 6 Restriction in Assignment

It is sometimes possible that a particular person is incapable of doing certain work or a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the restricted (infeasible) assignment can be avoided. This can be achieved by assigning a very high cost (say ∞ or M)to the cells where assignments are prohibited, thereby restricting the entry of this pair of job-machine or resource-activity into the final solution.

Example : Five jobs are to be assigned to five men. The cost (in Rs.) of performing the jobs by each man is given in the matrix. The assignment has restrictions that Job 4 cannot be performed by Man 1 and Job 3 cannot be performed by Man 4 Find the optimal assignment of job and its cost involved.

Assignment Problem

Solution: Assign large value to the restricted combinations or introduce ‘M’, see table.

Large Value Assignment to Restricted Combinations

Reducing the matrix row-wise

Reducing the matrix column-wise

Draw minimum number of lines to cover all zeros, see Table.

All Zeros Covered

Now, number of lines drawn = Order of matrix, hence optimality is reached.
Allocating Jobs to Men.

Job Allocation to Men

Assignment Schedule and Cost

As per the restriction conditions given in the problem, Man 1 and Man 4 are not assigned to Job 4 and Job 3 respectively.