USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Max-Type Assignment Problems

When the objective of the assignment is to maximize. the problem is called 'Max-type assignment problem'. This is solved by converting the profit matrix to an opportunity loss matrix by subtracting each element from the highest element of the profit matrix. Then the minimization of the loss matrix is the same as the maximization of the profit matrix.


Example 5. A company is faced with the problem of assigning 4 jobs to 5 persons. The expected profit in rupees for each person on each job are as follows :

Find the assignment of persons to jobs that will result in a maximum profit.

Solution. The above problem is unbalanced max.-type assignment problem. The maximum element is 86. By subtracting all the elements from it obtain the following opportunity loss matrix.

Now a dummy job 15 is added with zero losses. Then bring zeros in each column by subtracting the respective minimum element from each column we obtain the following matrix.

Let us cover all the zeros by minimum number of lines and is given below

Since the no. of lines = order of the matrix, we have to select 5 zeros such that they cover all the rows and columns. This is done in the following :

The optimal assignment is

I->J4, II->J2, III->J5, IV->J l, V->J3 and maximum profit = $ (81 + 79 + 86 + 71) =$ 31 7. Here person III is idle.


Note. The max.-type assignment problem can also be converted to a minimization problem by multiplying all the elements of the profit matrix by - l. Then the Hungarian method can be applied directly.




  1. Solve the following assignment problems :




2. A machine tool decides to make six sub-assemblies through six contractors A, B, C, D, E and F. Each contractor is to receive only one sub-assembly from A 1, A2, A3, A4, A5 and A6. But the contractors C and E are not competent for the A4 and A2 assembly respectively. The cost of each subassembly by the bids submitted by each contractor is shown below (in hundred rupees) :

Find the optimal assignments o f the assemblies to contractors so as to minimize the total cost.


3. Five programmers, in a computer centre, write five programmes which run successfully but with different times. Assign the programmers to the programmes in a such a way that the total time taken by them is minimum taking the following time matrix :

4. Consider the problem of assigning seven jobs to seven persons. The assignment costs are given as follows :

Determine the optimal assignment schedule.


5. Solve the following unbalanced assignment problems



6. There are five operators and six machines in a machine shop. The assig11ment costs are given in the table below

Operator A cannot operate machine M2 and operator E cannot operate machine MS. Find the optimal assignment schedule.


7. A batch of 4 jobs can be assigned to 5 different machines. The setup time for each job on various machines is given below :

Find an optimal assignment of jobs to machines which will minimize the total setup time.


8. A construction company has to move six large cranes from old construction sites to new construction sites. The distances (in miles) between the old and the new sites are given below :




Determine a plan for moving the cranes such that the total distance involved in the move will be minimum.


9. A company wants to assign five sales person to five different regions to promote a product. The expected sales (in thousand) are given below :

Solve the above assignment problem to find the maximum total expected sale.


10. A company makes profit ($) while processing different jobs on different machines (one machine to one job only). Now the company is facing problem of assigning 4 machines to 5 jobs. The profits are estimated as given below :

Determine the optimal assignment for maximum total profits