Chapter 4 - Assignment Problem part 1

• Introduction
• Hungarian Method - Algorithm
• Hungarian Method - Examples
• Crew Assignment Problem
• Travelling Salesman Problem
• Optimal solutions is Assignment problem
a) unbalanced assignment problem
b) maximization in assignment.
c) Multiple optimal solutions

Home work Questions:

Compare between assignment and transportation proplem.

Uses and applications of assignment problem

Formulation of Assignment problem

Assumptions of Assignment problem

1
 Assignment Problem: Linear Programming
Introduction: The assignment problem is a special type of transportation problem,
Definition : Assignment problem is a transportation problem which involves the
allocation of n different tasks to n different agents such that total cost or time is
minimized .
objective is to minimize the cost or time of completing a number of jobs by a number
of persons.

Relationship:

The Assignment Problem is a special case of the Transportation Problem where:

• Supply and demand at each point = 1

• All variables are binary (0 or 1)

Uses of assignment problem

a. The model's primary usefulness is for planning.
b. The assignment problem also encompasses an important sub-class of so-called
shortest- (or longest-) route models.
c. The assignment model is useful in solving problems such as, assignment of machines
to jobs, assignment of salesmen to sales territories, travelling salesman problem, etc.

It may be noted that with n facilities and n jobs, there are n! possible assignments.
One way of finding an optimal assignment is to write all the n! possible arrangements,
evaluate their total cost, and select the assignment with minimum cost.
But, due to heavy computational burden this method is not suitable. This chapter
concentrates on an efficient method for solving assignment problems that was developed
by a Hungarian mathematician [Link].

2
Formulation of an assignment problem
1. Suppose a company has n persons of different capacities available for performing
each different job in the concern, and there are the same number of jobs of different
types.
2. One person can be given one and only one job.
3. The objective of this assignment problem is to assign n persons to n jobs, so as to
minimize the total assignment cost.
4. The cost matrix for this problem is given below:

Generalized Form of an Assignment Problem

The optimization model is

Minimize c11x11 + c12x12 + ------- + cnnxnn

subject to
xi1 + xi2 +..........+ xin = 1 i = 1, 2,......., n
x1j + x2j +..........+ xnj = 1 j = 1, 2,......., n

xij = 0 or 1

Assumptions in Assignment Problem

• Number of jobs is equal to the number of machines or persons.

• Each man or machine is assigned only one job.
• Each man or machine is independently capable of handling any job to be done.
• Assigning criteria is clearly specified (minimizing cost or maximizing profit).

3
 Steps in Hungarian Method (Hungarian Algorithm)

1. Identify the minimum element in each row and subtract it from every element of
that row.

2. Identify the minimum element in each column and subtract it from every element
of that column.

3. Make assignment in the opporunity cost table (every zero cell is either
assigned or crossed (X). )

i. For each row or column with a single zero value cell that has not be assigned or
eliminated, box that zero value as an assigned cell.
ii. For every zero that becomes assigned, cross out (X) all other zeros in the same row
and the same column.
iii. If for a row and a column, there are two or more zeros and one cannot be chosen
by inspection, then you are at liberty to choose the cell arbitrarily for assignment.
iv. The above process may be continued until every zero cell is either assigned or
crossed (X).

4. An optimal assignment is found, if the number of assigned cells equals the number
of rows (and columns).
In case you have chosen a zero cell arbitrarily, there may be alternate optimal
solutions. If no optimal solution is found, go to step 5.

5. Draw the minimum number of vertical and horizontal lines necessary to cover all
the zeros in the reduced matrix obtained from step 3 by adopting the following
procedure:

i. Mark all the rows that do not have assignments.

ii. Mark all the columns (not already marked) which have zeros in the marked rows.
iii. Mark all the rows (not already marked) that have assignments in marked
columns.
iv. Repeat steps 5 (i) to (iii) until no more rows or columns can be marked.
v. Draw straight lines through all unmarked rows and marked columns.

6. Select the smallest element from all the uncovered elements. Subtract this smallest
element from all the uncovered elements and add it to the elements, which lie at the
intersection of two lines. Thus, we obtain another reduced matrix for fresh
assignment.

7. Go to step 3 and repeat the procedure until you arrive at an optimal assignment.

4
Example 1: Hungarian Method
The Funny Toys Company has four men available for work on four separate jobs. Only
one man can work on any one job. The cost of assigning each man to each job is given in
the following table. The objective is to assign men to jobs in such a way that the total cost
of assignment is minimum

Step 1 Identify the minimum element in each row and subtract it from every element
of that row. The result is shown in the following table.

Step 2 Identify the minimum element in each column and subtract it from every
element of that column.

5
Step-3: Make assignment in the opporunity cost table

i. For each row or column with a single zero value cell that has not be assigned or
eliminated, box that zero value as an assigned cell.
ii. For every zero that becomes assigned, cross out (X) all other zeros in the same
row and the same column.
(1) Rowwise cell (A,1) is assigned, so columnwise cell (B,1) crossed off.

(2) Rowwise cell (C,2) is assigned, so columnwise cell (D,2) crossed off.

(3) Columnwise cell (D,3) is assigned, so rowwise cell (D,4) crossed off.

Step 4 : Number of assignments = 3, number of rows = 4

Which is not equal, so solution is not optimal..
Step 5: Cover the 0 with minimum number of lines

i. Mark all the rows that do not have assignments.

ii. Mark all the columns (not already marked) which have zeros in the marked rows.
iii. Mark all the rows (not already marked) that have assignments in marked
columns.
iv. Draw straight lines through all unmarked rows and marked columns
(1) Mark(✓) row B since it has no assignment

(2) Mark(✓) column 1 since row B has 0 in this column

(3) Mark(✓) row A since column 1 has an assignment in this row A.

(4) Since no other rows or columns can be marked, therefore draw straight lines
through the unmarked rows C,D and marked columns 1

6
Step 6:
Develop the new revised table by selecting the smallest element, among the cells not
covered by any line (say k = 1)
Subtract k = 1 from every element in the cell not covered by a line.
Add k = 1 to every element in the intersection cell of two lines

Now again make the assignments for the reduced matrix.

Repeat Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell (C,2) is assigned, so columnwise cell (D,2) crossed off.

(2) Rowwise cell (A,1) is assigned, so columnwise cell (B,1) crossed off., so rowwise
cell (A,3) crossed off.

(3) Rowwise cell (B,4) is assigned, so columnwise cell (D,4) crossed off.

(4) Rowwise cell (D,3) is assigned

7
Final Table: Hungarian Method

Since the number of assignments is equal to the number of rows (& columns), this is
the optimal solution.
The total cost of assignment = A1 + B4 + C2 + D3
Substituting values from original table:
20 + 17 + 17 + 24 = Rs. 78.

8
Example 2: Hungarian Method
The Winner Publishing Company employs typists on hourly basis. There are five
typists for service and their charges and speeds are different.
According to an earlier understanding only one job is given to one typist and the typist
is paid for full hour even if he works for a fraction of an hour. Find the least cost
allocation for the following data:

Solution. The following matrix gives the cost incurred if the ith typist (i = A, B, C, D
& E) executes the jth job (j = P, Q, R, S & T)

9
Identify the minimum element in each row and subtract it from every element of
that row.

Identify the minimum element in each column and subtract it from every element of
that column.

Make the assignments for the reduced matrix

1. The number of assigned cells is not equal to the number of rows (and columns).
10
 2. Therefore, we draw the minimum number of vertical and horizontal lines
necessary to cover all the zeros in the reduced matrix

Repeating the usual process as explained in the previous example, we get the following
matrix:.

The number of assigned cells is not equal to the number of rows (and columns).
Therefore, we draw the minimum number of vertical and horizontal lines necessary
to cover all the zeros in the reduced matrix

11
12
13
Comparison Table: Transportation vs Assignment Problem

Feature Transportation Problem Assignment Problem

Generalized Linear Programming Special case of Transportation

Type of Problem
Problem Problem

Minimize total assignment cost (or

Objective Minimize total transportation cost
maximize profit)

Minimize cost of assigning tasks

Purpose Minimize cost of transporting goods
to agents

Multiple sources to multiple One-to-one assignment between

Structure
destinations tasks and agents

Cost Matrix Rectangular (e.g., 3×4, 4×5) Square (e.g., 4×4, 5×5)

Each agent/task is assigned

Constraints Supply and demand must be met
exactly once

Logistics, supply chain, resource Job assignments, scheduling,

Application Areas
distribution project management

Amount of goods transported (can be Binary decision (1 if assigned, 0

Variables
fractional) otherwise)

Common Vogel’s Approximation Method, MODI, Hungarian Method, Branch and

Algorithms Northwest Corner Bound

Number of May involve multiple units from one Exactly one assignment per row
Assignments source to one destination and column

14
The Travelling Salesman Problem (TSP)
USING HUNGARINA METHOD
TSP finds the shortest possible route that visits each city exactly once and returns to
the starting city for a given a list of cities and the distances between each pair of
cities.

15
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell (Depo,C) is assigned, so columnwise cell (A,C) crossed off.

(2) Rowwise cell (B,D) is assigned

(3) Columnwise cell (D,B) is assigned, so rowwise cell (D,Depo),(D,A) crossed off.

(4) Columnwise cell (C,Depo) is assigned, so rowwise cell (C,A) crossed off.

Step-4: Number of assignments = 4, number of rows = 5

Which is not equal, so solution is not optimal.

Step-5: Cover the 0 with minimum number of lines

(1) Mark(✓) row A since it has no assignment

(2) Mark(✓) column C since row A has 0 in this column

(3) Mark(✓) row Depo since column C has an assignment in this row Depo.

(4) Since no other rows or columns can be marked, therefore draw straight lines
through the unmarked rows B,C,D and marked columns C

16
Step-6: Develop the new revised table by selecting the smallest element, among the
cells not covered by any line (say k = 1)
Subtract k = 1 from every element in the cell not covered by a line.
Add k = 1 to every elment in the intersection cell of two lines.

Repeat steps 3 to 6 until an optimal solution is arrived.

17
Step-3: Make assignment in the opporunity cost table

Step-4: Number of assignments = 5, number of rows = 5

The solution gives the sequence : Depo→A,A→C,C→Depo
The above solution is not a solution to the travelling salesman problem as he
visits each city only once.
The next best solution can be obtained by bringing the minimum non-zero element,
i.e., 1 into the solution.
The cost 1 occurs at 2 places. We will consider all the cases separately until the
acceptable solution is obtained

18
Step-4: Number of assignments = 5, number of rows = 5
The solution gives the sequence : Depo→C,C→A,A→B,B→D,D→Depo

So solution is optimal

Travelling salesman problem using Hungarian method calculator

The Travelling Salesman Problem (TSP) – example

19
 Unbalanced Assignment Problem
1. In the previous section, the number of persons and the number of jobs were assumed to be
the same.
2. In this section, we remove this assumption and consider a situation where the number of
persons is not equal to the number of jobs.
3. In all such cases, fictitious rows and/or columns are added in the matrix to make it a square
matrix.
4. Then, we apply the usual Hungarian algorithm to this resulting balanced assignment
problem
Example: Unbalanced Assignment Problem

Solution: Since the number of persons is less than the number of jobs, we introduce a
dummy person (D) with zero values. The revised assignment problem is given below :.

20
Assignment Problem: Maximization
1. There are problems where certain facilities have to be assigned to a number of jobs,
so as to maximize the overall performance of the assignment.
2. The Hungarian Method can also solve such assignment problems, as it is easy to
obtain an equivalent minimization problem by converting every number in the
matrix to an opportunity loss.
3. The conversion is accomplished by subtracting all the elements of the given matrix
from the highest element.
4. It turns out that minimizing opportunity loss produces the same assignment
solution as the original maximization problem.
Example: Maximization Assignment Problem

Solution. Here, the highest value is 62. So we subtract each value from 62. The conversion
is shown in the following table.

Now the above problem can be easily solved by Hungarian method. After applying
steps 1 to 3 of the Hungarian method, we get the following matrix.

21
Multiple Optimal Solutions: Assignment Problem
Sometimes, it is possible to cross out all the zeros in the reduced matrix in two or more
ways.

If you can choose a zero cell arbitrarily, then there will be multiple optimal
solutions with the same total pay-off for assignments made.

In such a case, the management may select that set of optimal assignments, which is
more suited to their requirement.

22