5.1 INTRODUCTION AND FORMULATION
The assignment problem is a particular case of transportation problem in which the number of jobs (or origins or sources) are equal to the number of facilities (or destinations or machines or persons and so on). The objective is to maximise total profit of allocation or to minimise the total cost. An assignment problem is a completely degenerate form of a transportation problem. The units available at each origin and the units demanded at each destination are all equal to one.
Mathematical Formulation of an Assignment Problem
Given n jobs (or activities) and n persons (or facilities) and effectiveness (in terms of cost, profit, time and others) of each person for each job, the problem lies in assigning each person to one and only one job so that the given measure of effectiveness is optimised.
Let cij be the cost of assigning ith person to the jth job. The assignment problem can be stated in the form of n × n cost matrix or effectiveness matrix (cij) as shown in the Table.
Let xij denote the assignment of person i to job j such that
subject to the constraints
for i = 1,2,… n
for i = 1,2,… n
xij = 0 or 1, for all i and j.
Note than an assignment problem is an n × n transportation problem with each ai = bj = 1.
Assignment problem is completely a degenerate form of a transportation problem. The units available at each origin and units demanded at each destination are all equal to one. This means exactly one occupied cell in each row and each column of the transportation table, that is, only n occupied cells in place of the required n + n − 1 = 2n − 1 occupied cells.
Because of degeneracy, the problem cannot be solved by either simplex method or transportation method. For example, in a simplex method, for a problem involving five persons/jobs, there will be 5 × 5 = 25 decision variables and 2 × 5 = 10 inequalities. It is difficult to solve this problem manually.
In a transportation method, in order to remove degeneracy, (n − 1) number of dummy allocations will be required to proceed with the transportation model. The problem of degeneracy at each solution makes the computation by the transportation method inefficient.
So, we go for a method called the Hungarian method developed by the Hungarian mathematician D. Konig to find the optimal solution without having to make a direct comparison of every solution.
5.2 HUNGARIAN ASSIGNMENT ALGORITHM
First, we prove the following theorems which form the basis of the assignment algorithm.
The optimum assignment schedule remains unaltered if we add or subtract a constant to/from all the elements of the row or column of the assignment cost matrix.
Proof: Let we add or subtract a constant say ui, vj to/from all the elements of the ith row and jth column of the cost matrix. The new cost matrix is . The objective function is
Note that U and V are constants, hence an assignment (xij) which minimises z will also minimise z*.
If for an assignment problem all cij ≥ 0 then an assignment schedule (xij) which satisfies xijcij = 0, must be optimal.
These theorems can be used in two different ways to solve the assignment problem. If in an assignment problem some cost elements are negative we convert the problem into an equivalent assignment problem with all cost elements as non-negative by adding a suitable large constant to the elements of the relevant row or column. Next, we look for a feasible solution which has zero assignment cost after adding suitable constants to the elements of various rows and columns. Since it has been assumed that all the cost elements are non-negative, this assignment must be optimum.
5.2.3 Hungarian Assignment Algorithm
Various steps of the computational procedure for obtaining an optimal solution may be summarized as follows:
Step 1: If the number of rows are not equal to the number of columns and vice versa, then a dummy row or dummy column must be added with zero cost elements.
Step 2: Find the smallest cost in each row of the cost matrix. Subtract this smallest cost element from each element in that row. Therefore, there will be at least one zero in each row of this new matrix which is called the first reduced cost matrix.
Step 3: In the reduced cost matrix, find the smallest elements in each column. Subtract the smallest cost elements from each element in that column. As a result, there would be at least one zero in each row and column of the second reduced cost matrix.
Step 4: Determine an optimum assignment as follows:
- Examine the rows successively until a row with exactly one zeros is found. Box around the zero element as an assigned cell and cross out all other zero in its column. Proceed in this manner until all the rows have been examined. If there are more than one zero in any row, then do not consider that row and pass on to the next row.
- Repeat the procedure for the columns of the reduced cost matrix. If there is no single zero in any row or column of the reduced matrix, then arbitrarily choose a row or column having the minimum number of zeros. Arbitrarily, choose zero in the row or column and cross the remaining zeros in that row or column.
Repeat steps (i) and (ii) until all zeros are either assigned or crossed out.
Step 5: An optimal assignment is found, if the number of assigned cells equals the number of rows (and columns). If a zero cell is arbitrarily chosen, there may be an alternate optimum. If no optimum solution is found (some rows or columns without an assignment), then go to next step.
- Mark (✓) to those rows where no assignment has been made.
- Mark (✓) to those columns which have zeros in the marked rows.
- Mark (✓) rows (not already marked) which have assignments in marked columns.
- The process may be repeated until no more rows or columns can be checked.
- Draw straight lines through all unmarked rows and marked columns.
Step 7: If the minimum number of lines passing through all the zeros is equal to the number of rows or columns, the optimum solution is attained by an arbitrary allocation in the positions of the zeros not crossed in step 3. Otherwise go to the next step.
Step 8: Revise the cost matrix as follows:
- Find the elements that are covered by a line. Choose the smallest of these elements and subtract this element from all the uncrossed elements and add the same at the point of intersection of the two lines.
- Other elements crossed by the lines remain unchanged.
Step 9: Go to step 4 and repeat the procedure till an optimum solution is attained.
The assignment cost of assigning any one operator to any one machine is given below.
Find the optimal assignment.
Step 1: Subtracting the smallest element of each row from every element of the corresponding row, we get the reduced matrix as:
Step 3: Starting with row 1, we box a single zero (i.e. make assignment), and cross (×) all other zeros in its column. Thus, we get
Since each row and each column contain exactly one assignment, the current assignment is optimal. The optimum schedule is
A → II, B → IV, C → III, D → I
and the optimum assignment cost is
[5 + 3 + 3+ 5] = 16.
A department has five employees with five jobs to be performed. The time (in hours) each man will take to perform each job is given in the cost matrix.
How should the jobs be allocated, one per employee, so as to minimise the total man-hours?
Solution: Applying step1 and 2 of the algorithm, the reduced time matrix is shown below:
The solution is not optimal since only four assignments are made.
Step 4: Since row D does not have any assignment we tick this row (✓)
- Now, there is a zero in the Ist and IVth column of the ticked row, So, we tick I and IVth column.
- Mark ✓ in the rows B and E since columns I and IV have an assignment in rows B and E, respectively.
- Draw straight lines through all unmarked rows A and C and marked columns, I and IV as shown below:
Step 5: In step 4, the minimum number of lines drawn is 4, which is less than the order of the cost matrix (order is 5), indicating that the current assignment is not optimum.
To increase the minimum number of lines, we generate new zeros in the modified matrix.
Step 6: Develop the new Table by selecting the smallest element among all uncovered elements by the lines. Here, the element is 2. Subtract this element from all the uncovered elements and add the same to all the elements lying at the intersection of the lines. We obtain the following new reduced cost matrix.
Step 7: Repeat steps 3 to 6 to find a new solution. This new assignment is:
Since the number of assignments (5) equals the number of rows (5), the solution is optimal. The optimum assignment is:
A → II, B → I, C → V, D → III, E → IV
The minimum total time for this assignment schedule is 5 + 3 + 2 + 9 + 4 = 23 hours.
Solve the assignment problem represented by the matrix:
- Subtract the smallest element in each row from all the elements in that row.
- Subtract the smallest element in each column from all the elements in that column.
Step 2: Make the zero-assignment as shown below. Since row 2 and column 5 have no assignment, go to the next step. See the following Table.
Step 3: Mark ✓ in row 2 as it is not having an assignment and in columns (1 and 6) as they are columns of ticked row 2 having zero’s.
Next, mark ✓ to the rows (3 and 6) as these two rows contain assignment in marked columns (1 and 6).
Next, in marked row 3, there is zero in column 2. Assignment is made in this column which corresponds to row 5. So, mark ✓ to row 5 and column 2.
Since the number of lines is five which is less than the number of rows or columns, we move to the next step to get the optimal solution.
Step 5: The smallest element among all uncovered elements is 4. Subtract 4 from all elements not covered by lines and add 4 to all the elements that lie at the intersection of this lines. A reduced matrix is formed. Then, make zero assignments as shown below.
The other solution is:
Hence, the optimal assignments are:
- A → 4, B → 1, C → 6, D → 3, E → 2, F → 5
- A → 4, B → 6, C → 2, D → 3, E → 5, F → 1.
with minimum cost z = 142.
- Non square matrix (unbalanced assignment problem)
The Hungarian method of assignment requires that the number of columns and rows in the assignment matrix must be equal. When the given cost matrix is not a square matrix, then the problem is called an unbalanced problem. In this case dummy row(s) or column(s) with zero cost is added to make it a square matrix. These cells are treated the same way as the real cells during the process. Then, adopt the Hungarian method to find the solution.
- Maximization problem
There may be problems of maximising the profit, revenue, and so on. Such problems may be solved by converting the given maximisation problem into a minimisation problem before the Hungarian method is applied. The transformation may be done in the following two ways:
- by subtracting all the elements from the highest element of the matrix.
- by multiplying the matrix elements by − 1.
- Multiple optimal solutions
While making an assignment in the reduced assignment matrix, it is possible to have two or more ways to strike off certain number of zeros. Such situation leads to multiple solutions with the same optimal value of objective function. In such cases the most suitable solution may be considered by the decision-maker.
- Restrictions on assignments (or) impossible assignment
Cells in which assignments are not allowed are assigned a very heavy cost (written as M or ∞). Such cells are prohibited to enter into the final solution.
Example 1 Unbalanced Problem
In the modification of a plant layout of a factory four new machines M1, M2, M3, M4 are to be installed in a machine shop. There are five vacant places, A, B, C, D and E that are available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost of placing of machine i at place j (in rupees) shown below:
Find the optimal assignment schedule.
Apply the Hungarian method to get the optimal solution. The optimal solution is shown below:
The optimal solution is obtained. The schedule are:
M1 → A, M2 → B, M3 → E, M4 → D, M5 → C
and the total minimum cost is : 9 + 9 + 7 + 7 + 0 = 32.
A department head has four task to be performed and three subordinates to perform the task. The subordinates differ in efficiency. The estimates of time, each subordinate would take to perform, is given below in the matrix. How should he allocate the tasks one to each person, so as to minimise the total man hours?
The optimum assignment is I → 1, II → 3, III → 2, IV → 4. The total minimum time is [9 + 6 + 20 + 0] = 35 hours.
Example 3 Maximisation Problem
A company has four territories open, and four salesman available for the assignment. The territories are not equally rich in their sales potential; it is estimated that a typical salesman operating in each territory would bring in the following annual sales:
Four salesman are also considered to differ in their ability. It is estimated that working under the same conditions, their yearly sales would be proportional as follows:
If the criterion is maximise expected total sales, then the intuitive answer is to assign the best salesman to the richest territory, the next best salesman to the second richest and so on. Verify this answer by the assignment technique.
Step 1: Construct the effectiveness matrix.
To avoid the fractional values of annual sales of each salesman in each territory, for convenience consider the yearly sales as 21 (the sum of sale proportion = 7 + 5 + 5 + 4 = 21), taking 10,000 as one unit. Now, divide the individual sales in each territory by 21 to obtain the required annual sales by each salesman.
Thus, the maximum sales matrix is obtained as follows:
Subtract from the highest element (i.e. 42) among all the elements of the given cost matrix.
The resulting matrix is
Step 3: Apply Hungarian method to get the optimal solution.
- Subtract the smallest element in each row from every element in that row.
- Subtract the smallest element in each column. The reduced matrix is obtained as follows:
Step 4: Assignment is made in row A. All zeros in the assigned column I are crossed out. Column II has only one zero in cell (D, II). Assignment is made in this column and other zeros are crossed in row D. The reduced matrix is shown below:
Step 5: Since rows B and C does not have any assignments, we tick this row. Since there is a zero in the I column of the ticked row, we tick I column. Further, there is an assignment in the first row of the ticked column, so we tick first row. Draw lines through all unmarked rows and marked columns.
Step 6: Revised matrix is developed by selecting the minimum element (= 1) among all uncovered elements by the lines. Subtract 1 from each uncovered element and add it to the element at the intersection of two lines. The revised Table is:
Again, the solution is not optimal. Repeat Step 1 to 5. Two alternative optimal assignments we get are:
The two possible solutions are:
- A → I, B → III, C → II, D → IV
- A → I, B → II, C → III, D → IV
with maximum sales of (42 + 20 + 25 + 12) = 99
[or (42 + 25 + 20 + 12) = 99.]
Both solution show the best salesman A is assigned to the richest territory I, the worst salesman D to the poorest territory IV. Salesman B and C are equally good and they may be assigned II or III.
Example 4 Maximisation Problem
A company has a team of four salesman and there are four districts where the company wants to start its business. After taking into account the capabilities of salesman and the nature of districts, the company estimates that the profit per day in rupees for each salesman in each district is as below:
Find the assignment of salesman to various districts which will yield maximum profit.
Step 1: Convert the maximisation problem into a minimisation problem by subtracting all the elements from the highest element 16. The reduced matrix is:
Step 2: Apply Hungarian algorithm to get the optimal solution. The optimum assignment is as follows:
Since the number of assignment = order of cost matrix, the current solution is optimal. The schedule is:
A → 1, B → 3, C → 2, D → 4
profit per day = [16 + 15 + 15 + 15] = 61.
Example 5 Multiple Solutions
Solve the minimal assignment problem whose cost matrix is given below:
- Subtract the smallest element in the row from each element in that row.
- Subtract the smallest element in the column from each element in that column.
Since single zeros do not exist either in the columns or in the rows, we get the following alternative solutions:
The possible optimal solutions with each of cost 20 are:
I → 2, II → 3, III → 4, IV → 1
I → 1, II → 2, III → 3, IV → 4
I → 3, II → 2, III → 1, IV → 4
I → 3, II → 2, III → 4, IV → 1
I → 2, II → 3, III → 1, IV → 4
Example 6 Restrictions on Assignments
Four new machines M1, M2, M3, M4 are to be installed in a machine shop. There are five vacant places A, B, C, D, E that are available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost matrix is shown below:
Solution: As machine M2 cannot be placed at C, M3 cannot be placed at A, assign a large cost M in cells (M2, C) and (M3, A). The assignment problem is unbalanced. So, balance it by adding a dummy row with cost 0 as shown below:
Applying Hungarian method, the following matrix is obtained.
The optimal assignment is:
M1 → A, M2 → B, M3 → E, M4 → D, M5 → C (C will remain vacant).
Total assignment cost = (4 + 4 + 2 + 2) = 12.
5.4 TRAVELLING SALESMAN PROBLEM
Suppose a salesman wants to visit a certain number of cities starting from his headquarters. The distances (or cost or time) of journey between every pair of cities, denoted by cij, that is, distance from city i to city j is assumed to be known. The problem is:
Salesman starting from his home city visiting each city only once and returns to his home city in the shortest possible distance (or at the least cost or in the least time).
Given n cities and distance cij, the salesman starts form city 1, then any permutation of 2, 3, …, n represents the number of possible ways for his tour. So, there are (n − 1)! possible ways for his tour. The problem is to select an optimal route that could achieve his objective.
The problem may be classified as:
- Symmetrical: If the distance between every pair of cities is independent of the direction of his journey.
- Asymmetrical: For one or more pair of cities the distance changes with the direction.
The distance (or cost or time) from city i to city j is cij and xij = 1, if the salesman goes directly from city i to city j, and xij = 0 otherwise. Then the objective function is
with the additional restriction that xij must be so chosen that no city is visited twice before the tour is completed. In particular, he cannot go directly from city i to i. So, assign cij = ∞.
However, all cij > 0 and cij + cjk > cik for all i, j, k.
Omit the variable xij from the problem specification. It is also important to note that only single xij = 1 for each value of i and j. The cost matrix is shown below:
A machine operator processes five types of items on his machine each week, and must choose a sequence for them. The set-up cost per change depends on the item presently on the machine and the set-up to be made according to the following table:
If he processes each type of item only once each week, how should he sequence the items on his machine in order to minimise the total set-up cost?
Step 1: Reduce the cost matrix using Steps 1 and 2 of the Hungarian algorithm and then make assignments in rows and columns having single zeros as usual.
Step 2: Note that row 2 is not assigned. So, mark ✓ to row 2. Since there is a zero in the 4th column of the marked row, we tick 4th column. Further, there is an assignment in the first row of 4th column. So, tick first row. Draw lines through all unmarked rows and marked columns. We can find number of lines is 4 which is less than the order of the matrix. So, go to next step (See table).
Step 3: Subtract the lowest element from all the elements not covered by these lines and add the same with the elements at the intersection of two lines. Then we get the table as:
The optimum assignment is 1 → 4, 2 → 1, 3 → 5, 4 → 2, 5 → 3 with minimum cost as 20.
This assignment schedule does not provide us the solution of the travelling salesman problem as it gives 1 → 4, 4 → 2, 2 → 1, without passing through 3 and 5.
Next, we try to find the next best solution which satisfies this restriction. The next minimum (non-zero) element in the cost matrix is 1. So, we bring 1 into the solution. But the element ‘1’ occurs at two places. We consider all cases separately until we get an optimal solution.
1 → 4, 4 → 2, 2 → 3, 3 → 5, 5 → 1
When an assignment is made at (3, 2) instead of zero assignment at (3, 5), the resulting assignment schedule is
1 → 5, 5 → 3, 3 → 2, 2 → 4, 4 → 1
The total set-up cost in both the cases is 21.
Solve the following travelling-salesman problem.
Solution: After subtracting the smallest element of each row from all the row elements of the corresponding row we obtain the first reduced matrix. Next, subtract the smallest element of each column from all the column elements of the corresponding column. We obtain the second reduced matrix. Then, make the assignment in rows and columns having single zero. We get
Since only three assignments are made, which is less than the order of the cost matrix, the current assignment is not optimal.
Proceeding as usual, we get the second iteration as:
which gives optimal solution. The optimum assignment is
A → C, B → D, C → B, D → A
A → C, C → B, B → D, D → A
with minimum cost = 128.
Solve the travelling salesman problem given by the following data:
c12 = 20, c13 = 4, c14 = 10, c23 = 5, c34 = 6
c25 = 10, c35 = 6, c45 = 20 where cij = cji
and there is no route between cities i and j if the value for cij is not shown.
Solution: The cost matrix is:
Repeating the steps as before using the Hungarian algorithm, the optimum table obtained is:
The solution is
1 → 3, 3 → 4, 4 → 1, 5 → 2, 2 → 5
which is not the solution of the travelling salesman problem as the sequence obtained is not the cyclic order.
The next lowest number (other than 0) is 1. Therefore, make an assignment in the cell (3, 2) having the element 1. Consequently, make an assignment in the cell (5, 4) having element 8, instead of zero element in the cell (5, 2). The assignment Table is
The shortest route for the travelling salesman is
1 → 3 → 2 → 5 → 4 → 1.
1. What is an assignment problem? Give two areas of its applications.
2. Explain the conceptual justification that an assignment problem can be viewed, as a linear programming problem.
3. Explain the difference between a transportation problem and an assignment problem.
4. What is the dual of an assignment problem? What are the techniques used in solving an assignment problem.
5. Show that the assignment problem is a special case of the transportation problem. Why is the transportation method to find the optimal solution not preferred in the assignment problem.
6. Describe the mathematical formulation of an assignment problem.
7. Explain the steps in the Hungarian method for solving assignment problems.
8. Find the optimal solution for the assignment problem with the following cost matrix.
[Answer: A → I, B → IV, C → V, D → III, E → II, minimum cost = 60.]
9. Show that the lines drawn in the assignment algorithm pass through all the zeros and have the property that every line passes through one and only one assignment.
10. Five men are available to do five different jobs. From the past records, the time (in 2 hour) that each man takes to do each job is known and given in the following Table.
Find the assignment of men to jobs that will minimise the total time taken.
[Answer: A → III, B → V, C → I, D → IV, E → II, optimal value = 13 hours.]
11. A company has four machines on which three jobs have to be done. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following Table.
What are the job assignments which will minimise the cost?
[Answer: A → P, B → Q, C → R, D → S, cost = 50.]
12. Solve the following assignment problems.
[Answer: A → 5, B → 1, C → 4, D → 3, E → 2 minimum cost = 9.]
13. The owner of a small machine shop has four machinists available to assign jobs for the day. Five jobs are offered with the expected profit (in ) for each machinist on each job as follows:
Find the assignment of machinists to jobs that will result in a maximum profit. Which job should be declined?
[Answer: 1 → D, 2 → B, 3 → C, 4 → E, 5 → A, cost = 37.60. Job A should be declined.]
14. How do you deal with the assignment problem where the objective function is to be maximised?
15. Explain how to modify an effectiveness matrix in an assignment problem if a particular assignment is prohibited.
16. What is an unbalanced assignment problem? How is the Hungarian method applied for obtaining a solution if the matrix is rectangular?
17. In an assignment problem, how do you take care of an impossible assignment.
18. A department has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. The estimates of the profit in rupees each man would earn is given in the effectiveness matrix. How should the tasks be allocated, one to each man, so as to maximise the total earnings?
[Answer: 1 → B, 2 → D, 3 → A, 4 → C with maximum earnings = 110.]
19. Consider the problem of assigning five operators to five machines. The assignment costs are given below:
Operator A cannot be assigned to machine M3 and operator C cannot be assigned to machine M4. Find the optimum assignment schedule.
[Answer: A → M4, B → M3, C → M2, D → M1, E → M5, minimum cost = 25.]
20. A student has five days to revise the subject before examination. The course is divided into 4 sections. He decides to devote a whole day to the study of some section so that he may study a section for one day, two days, three days and so on, or not at all. The expected grade points he will get for alternative arrangements are as follows:
How should he distribute the days to various sections to maximise his grade point average?
21. Assign the five jobs to the five men so as to maximise the sales.
22. Solve the following unbalanced problem of assigning four jobs to three different men. The time to perform the job by different men is given in the following Table.
[Answer: M1 → J4, M2 → J1, M3 → J2, M4 → J3, minimum time = 16 hrs.]
23. Explain the nature of a travelling salesman problem and give its mathematical formulation.
24. What is the difference between assignment problem and travelling salesman problem?
25. What is the objective of the travelling salesman problem?
26. Write short note on travelling salesman problem.
27. Solve the travelling salesman problem as to minimise the cost per cycle.
[Answer: 1 → 5 → 2 → 3 → 4 → 1, cost = 62.]
28. Solve the travelling salesman problem, given
c12 = 16, c13 = 4, c14 = 12, c23 = 6, c34 = 5, c25 = 8
c35 = 6, c45 = 20, cij = cji, cii = ∞,
for all values of i and j not given in the data.
[Answer: 1 → 2 → 5 → 3 → 4 → 1, with minimum cost = 47.]
It is proposed to lay submarine cable of smallest length to connect all the islands by telephone connections. Find the minimum spanning tree for the six islands mentioned.
[Answer: A → B, B → A, C → D, D → C, E → F, F → E, minimum distance = 440.]
30. Solve the travelling salesman problem.
[Answer: A → B → C → D → E → A, minimum cost = 30.]