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.
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.