Assignment Problem
1
• Examples of assignment problem
Row Column Cell entry
Jobs Machines Processing time/cost
Programmer Program Coding time
Operators Assignments Processing time/cost
Drivers Routes Travel time
Teachers Subjects Students pass percentage
2
Assignment Problem
Introduction
This is a special type of transportation problem
in which each source should have the capacity
to fulfill the demand of any one of the
destinations.
In other words, any operator would be able to
perform any job regardless of his skill, although
the cost (or the time taken) will be more if the
job does not match with operator’s skill.
3
General Format
n : number of jobs = number of machines
cij : processing cost (or time) of job i by machine j.
Objective: to assign the jobs to the machines such that the total
processing cost (or time) is minimized.
Constraints: Each job is assigned to exactly one machine and
Each machine performs exactly one job
Machine
1 2 … j … n
1 c11 c12 … c1j … c1n
2 c21 c22 … c2j … c2n
Job
. Square cost matrix n x n
i ci1 ci2 … cij cin
.
n cn1 cn2 cnj cnn 4
General LP formulation
Decision variables
1, If job i is assigned to machine j
xij
0, Otherwise
Formulation
n n
Minimize Z = c x
i 1 j 1
ij ij
Subject to
n
x
j 1
ij 1, i 1, 2, ,n Each job is assigned to exactly one machine
x
i 1
ij 1, j 1, 2, ,n Each machine performs exactly one job
xij 0, i 1, 2, , n; j 1, 2, ,n
5
Solving Assignment Problem: Hungarian Algorithm
Theorem: Optimal solution of the assignment problem remains unchanged if a
constant is added (subtracted) to (from) any row (column) of cost matrix
Proof:
Let ui be subtracted from each element of the ith row
and vj be subtracted from each element of the jth row
cij cij cij ui v j
n n n n
Z cij xij (cij ui v j ) xij
i 1 j 1 i 1 j 1
n n n n n n
cij xij ui xij v j xij
i 1 j 1 i 1 j 1 j 1 i 1
From constraints
n
n n
Z ui v j ij x 1, i
i 1 j 1 j 1
Z Z constant n
ij x 1, j
Min Z Min Z i 1
Can prepare a new matrix with zero cost element for some cells 6
Hungarian Algorithm
Step 1: Subtract the smallest element of each row from all the elements of that row.
(Row reduction)
Step 2: Subtract the smallest element of each column from all the elements of that
column. (Column reduction)
(As a result, there would be at least one zero in each row and column of the reduced matrix)
Step 3: Determine an optimal assignment as follows:
(i) Starting with the first row of the reduced matrix, examine each row one by
one until a row with exactly one zero is found. Make assignment in the cell
with zero element and cross out all other zeros in the corresponding column.
(ii) Repeat the procedure for columns.
Repeat (i) and (ii) until all zeros are either assigned or crossed out.
Step 4: If the number of assigned cells equals the number of rows (columns), then
optimal assignment is found and Stop. Otherwise, go to Step 5
7
Hungarian Algorithm Contd…
Step 5: Cover all the zeros using minimum number of horizontal and/or vertical
lines as follows:
(i) Tick all unassigned rows
(ii) If a ticked row has an unassigned zero, then tick the corresponding column
(not already ticked)
(iii) If a ticked column has an assignment, then tick the corresponding row (not
already ticked)
(iv) Repeat (ii) and (iii) till no more ticking is possible.
(v) Draw lines through unticked rows and ticked columns. The number of lines
represents the maximum number of assignments possible.
Step 6: Select the smallest uncovered element. This element is subtracted from every
uncovered element and added to every element at the intersection of two
lines.
Step 7: Go to Step 3 and repeat the procedure till an optimal solution is obtained.
8
Example 1: 4 Jobs and 4 persons
Person
P1 P2 P3 P4
J1 5 9 3 6
J2 8 7 8 2
Job
J3 6 10 12 7
J4 3 10 8 6
Row Reduction operation Column Reduction operation Assignment
Person Person Job Person
P1 P2 P3 P4 P1 P2 P3 P4 J1 P3
J1 2 6 0 3 J1 2 2 0 3 J2 P4
J2 6 5 6 0 J2 6 1 6 0
Job Job J3 P2
J3 0 4 6 1 J3 0 0 6 1
J4 P1
J4 0 7 5 3 J4 0 3 5 3
Total Cost = 3+2+10+3 = 18 9
Example 2: 5 jobs 5 Machines
Machine
M1 M2 M3 M4 M5
J1 11 7 10 17 10
J2 13 21 7 11 13
Job
J3 13 13 15 13 14
J4 18 10 13 16 14
J5 12 8 16 19 10
10
Example: Contd…
Row Reduction Operation
Step 1: Subtract the smallest element of each row from all the elements
of that row. (Row reduction)
Machine Machine
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 11 7 10 17 10 J1 4 0 3 10 3
J2 13 21 7 11 13 J2 6 14 0 4 6
Job Job
J3 13 13 15 13 14 J3 0 0 2 0 1
J4 18 10 13 16 14 J4 8 0 3 6 4
J5 12 8 16 19 10 J5 4 0 8 11 2
11
Example: Contd…
Column Reduction Operation
Step 2: Subtract the smallest element of each column from all the elements of that
column. (Column reduction)
Machine Machine
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 4 0 3 10 3 J1 4 0 3 10 2
J2 6 14 0 4 6 J2 6 14 0 4 5
Job Job
J3 0 0 2 0 1 J3 0 0 2 0 0
J4 8 0 3 6 4 J4 8 0 3 6 3
J5 4 0 8 11 2 J5 4 0 8 11 1
Example: Contd…
Step 3: Determine an optimal assignment as follows:
(i) Starting with first row of the reduced matrix, examine each row one by one until a row
with exactly one zero is found. Make assignment in the cell with zero element and
cross out all other zeros in the corresponding column.
(ii) Repeat the procedure for the columns.
Repeat (i) and (ii) until all zeros are either assigned or crossed out.
Machine
M1 M2 M3 M4 M5
J1 4 0 3 10 2
J2 6 14 0 4 5
Job
J3 0 0 2 0 0
J4 8 0 3 6 3
J5 4 0 8 11 1
Example: Contd…
Step 4: If the number of assigned cells equals the number of rows (and columns), then
optimal assignment is found and Stop. Otherwise, go to Step 5
Machine
M1 M2 M3 M4 M5
J1 4 0 3 10 2
J2 6 14 0 4 5
Job
J3 0 0 2 0 0
J4 8 0 3 6 3
J5 4 0 8 11 1
Number of assignments made is less than number of rows/columns
Example: Contd…
Step 5: Cover all the zeros with minimum number of horizontal and/or vertical lines as
follows:
(i) Tick all unassigned rows
(ii) If a ticked row has an unassigned zero, then tick the corresponding column (not
already ticked)
(iii) If a ticked column has an assignment, then tick the corresponding row (not already
ticked)
(iv) Repeat (ii) and (iii) till no more ticking is possible.
(v) Draw lines through unticked rows and ticked columns. The number of lines
represents the maximum number of assignments possible.
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 4 0 3 10 2 J1 4 0 3 10 2 √
J2 6 14 0 4 5 J2 6 14 0 4 5
J3 0 0 2 0 0 J3 0 0 2 0 0
J4 8 0 3 6 3 J4 8 0 3 6 3 √
J5 4 0 8 11 1 J5 4 0 8 11 1 √
√
Example: Contd…
Step 6: Select the smallest uncovered element. This element is subtracted from every
uncovered element and added to every element at the intersection of two lines.
Step 7: Go to Step 3 and repeat the procedure till an optimal solution is obtained.
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 4 0 3 10 2 √ J1 3 0 2 9 1
J2 6 14 0 4 5 J2 6 15 0 4 5
J3 0 0 2 0 0 J3 0 1 2 0 0
J4 8 0 3 6 3 √ J4 7 0 2 5 2
J5 4 0 8 11 1 √ J5 3 0 7 10 0
√
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 3 0 2 9 1 √ J1 2 0 1 8 0
J2 6 15 0 4 5 J2 6 16 0 4 5
J3 0 1 2 0 0 J3 0 2 2 0 0
J4 7 0 2 5 2 √ J4 6 0 1 4 1
J5 3 0 7 10 0 J5 3 1 7 10 0
√
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 2 0 1 8 0 J1 2 0 1 8 0 √
J2 6 16 0 4 5 J2 6 16 0 4 5
J3 0 2 2 0 0 J3 0 2 2 0 0
J4 6 0 1 4 1 J4 6 0 1 4 1 √
J5 3 1 7 10 0 J5 3 1 7 10 0 √
√ √
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 1 0 0 7 0 J1 1 0 0 7 0 √
J2 6 17 0 4 6 J2 6 17 0 4 6 √
J3 0 3 2 0 1 J3 0 3 2 0 1
J4 5 0 0 3 1 J4 5 0 0 3 1 √
J5 2 1 6 9 0 J5 2 1 6 9 0 √
√ √ √
17
M1 M2 M3 M4 M5 M1 M2 M3 M4 M5
J1 1 0 0 7 0 √ J1 0 0 0 6 0
J2 6 17 0 4 6 √ J2 5 17 0 3 6
J3 0 3 2 0 1 J3 0 4 3 0 2
J4 5 0 0 3 1 √ J4 4 0 0 2 1
J5 2 1 6 9 0 √ J5 1 1 6 8 0
√ √ √
M1 M2 M3 M4 M5
Optimal Assignment:
J1 0 0 0 6 0 J1-> M1
J2 5 17 0 3 6 J2-> M3
J3-> M4
J3 0 4 3 0 2
J4-> M2
J4 4 0 0 2 1 J5-> M5
J5 1 1 6 8 0
Total Cost = 11+7+13+10+10 = 51
18
Special Cases in Assignment Problem
• Assignment Problem with Maximization objective
• Number of Assignees ≠ Number of Assignment
(Unbalanced Assignment Problem)
• Reduced Matrix does not contain single zero in any
row or column
• A particular job i should not be performed by resource j
19
Maximization type assignment problem
Unless otherwise stated, the assignment problem is a
minimization type.
• If the problem is a maximization problem (Profit,
sales, effectiveness, etc.), convert the problem into a
minimization problem by multiplying each cij by -1.
• Then apply the usual procedure of an assignment
problem.
20
Example : Assign 4 sales persons to four different
sales regions such that total sales is maximized.
Sales
region
1 2 3 4
Sales
person
1 10 22 12 14
2 16 18 22 10
3 24 20 12 18
4 16 14 24 20
21
Modified data , after multiplying the cell entries
by -1.
Sales
region
1 2 3 4
Sales
person
1 -10 -22 -12 -14
2 -16 -18 -22 -10
3 -24 -20 -12 -18
4 -16 -14 -24 -20
22
Row Reduction
Sales
region
1 2 3 4
Sales
person
1 -10 -22 -12 -14
2 -16 -18 -22 -10
3 -24 -20 -12 -18
4 -16 -14 -24 -20
23
Row Reduction
Sales
region
1 2 3 4
Sales
person
1 12 0 10 8
2 6 4 0 12
3 0 4 12 6
4 8 10 0 4
24
Column reduction
Sales
region
1 2 3 4
Sales
person
1 12 0 10 4
2 6 4 0 8
3 0 4 12 2
4 8 10 0 0
25
Start making Assignments
Sales
region
1 2 3 4
Sales
person
1 12 0 10 4
2 6 4 0 8
3 0 4 12 2
4 8 10 0 0
26
Sales
region
1 2 3 4
Sales
person
1 12 0 10 4
2 6 4 0 8
3 0 4 12 2
4 8 10 X
0 0
27
Sales
region
1 2 3 4
Sales
person
1 12 0 10 4
2 6 4 0 8
3 0 4 12 2
4 8 10 X
0 0
28
Solution is feasible and optimal
Sales
region
1 2 3 4
Sales
person
1 12 0 10 4
2 6 4 0 8
3 0 4 12 2
4 8 10 X
0 0
29
• Result:
Sales person Sales region Sales
1 2 22
2 3 22
3 1 24
4 4 20
30
Unable to get single zero in any row or
column of the reduced matrix
If there is no single zero in any row or column of the reduced matrix,
then arbitrarily select a row or column having minimum number of
zeros.
Arbitrarily, choose a zero in the selected row or column for
assignment and cross the remaining zeros in that row or column.
Apply the usual procedure.
Multiple Optimal Solution
Example :
Employee A B C D
Assignment
I 2 3 4 5
II 4 5 6 7
III 7 8 9 8
IV 3 5 8 4 31
Row Reduction
Employee A B C D
Assignment
I 0 1 2 3
II 0 1 2 3
III 0 1 2 1
IV 0 2 5 1
32
Column Reduction
Employee A B C D
Assignment
I 0 0 0 2
II 0 0 0 2
III 0 0 0 0
IV 0 1 3 0
33
Employee A B C D
Assignment
I X0 0 0 2
II X0 0 0 2
III X0 0 0 0
IV 0 1 3 0X
34
Employee A B C D
Assignment
I X0 0 0 2
II X0 0 0 2
III X0 X0 0X 0
IV 0 1 3 0X
35
Employee A B C D
Assignment
I X0 0 X0 2
II X0 X
0 0 2
III X0 X0 0X 0
IV 0 1 3 0X
36
Employee A B C D
Assignment
I X0 0 X0 2
II X0 X
0 0 2
III X0 X0 0X 0
IV 0 1 3 0X
I → B, II → C, III → D, IV → A
Other optimal assignments are also possible each with cost 20.
I → A, II → B, III → C, IV → D
I → C, II → B, III → A, IV → D
I → C, II → B, III → D, IV → A
I → B, II → C, III → A, IV → D 37
Number of Assignees ≠ Number of Assignment
(Unbalanced Assignment Problem)
• The assignment problem usually has a square matrix with n jobs
to be assigned to n resources.
• Sometimes we may have fewer resources (rows) or fewer jobs
(columns).
• In these cases, we make the matrix square by creating additional
dummy rows or dummy columns depending whether we have
fewer rows or columns.
• For example,
If the problem has four rows and six columns, we convert it to a
6x6 problem by adding two dummy rows.
If it is a 7x5 problem, we create two additional dummy columns.
• The dummy rows and columns have zero cost.
38
Example
Job 1 2 3 4
Person
A 7 5 8 4
B 5 6 7 4
C 8 7 9 8
39
Introduce a dummy person
Job 1 2 3 4
Person
A 7 5 8 4
B 5 6 7 4
C 8 7 9 8
D
0 0 0 0
(Dummy)
40
Row reduction
Job 1 2 3 4
Person
A 3 1 4 0
B 1 2 3 0
C 1 0 2 1
D
0 0 0 0
(Dummy)
41
Job 1 2 3 4
Person
A 3 1 4 0
B 1 2 3 X
0
C 1 0 2 1
D
0 0 0 X
0
(Dummy)
42
Job 1 2 3 4
Person
A 3 1 4 0
B 1 2 3 X
0
C 1 0 2 1
D
0 X0 0 X
0
(Dummy)
43
Job 1 2 3 4
Person
A 3 1 4 0
B 1 2 3 X
0
C 1 0 2 1
D
0 X0 X
0 X
0
(Dummy)
44
Job 1 2 3 4
Person
A 3 1 4 0
B 1 2 3 X
0 √
C 1 0 2 1
D
0 X0 X
0 X
0
(Dummy)
45
Job 1 2 3 4
Person
A 3 1 4 0
B 1 2 3 X
0 √
C 1 0 2 1
D
0 X0 X
0 X
0
(Dummy)
46
Job 1 2 3 4
Person
A 3 1 4 0 √
B 1 2 3 X
0 √
C 1 0 2 1
D
0 X0 X
0 X
0
(Dummy)
47
Job 1 2 3 4
Person
A 3 1 4 0 √
B 1 2 3 X
0 √
C 1 0 2 1
D
0 X0 X
0 X
0
(Dummy)
48
Job 1 2 3 4
Person
A 2 0 3 0
B 0 1 2 0
C 1 0 2 2
D
0 0 0 1
(Dummy)
49
Job 1 2 3 4
Person
A 2 X
0 3 0
B 0 1 2 0
C 1 0 2 2
D
(Dummy)
0 X0 0 1
50
Job 1 2 3 4
Person
A 2 X
0 3 0
B 0 1 2 X
0
C 1 0 2 2
D
(Dummy)
0 X0 0 1
51
Job 1 2 3 4
Person
A 2 X
0 3 0
B 0 1 2 X
0
C 1 0 2 2
D
X
0 X0 0 1
(Dummy)
52
Job 1 2 3 4
Person
A 2 X
0 3 0
B 0 1 2 X
0
C 1 0 2 2
D
X
0 X0 0 1
(Dummy)
Thus the optimum allocation is:
A 4, B 1 C 2 D 3 (Job 3 is not done by any real person)
Optimal cost = 4+5+7 = 16
53
A particular Assignment i should not be
performed by resource j
• In this case, put cij = M (where M is a large positive
number tends to infinity) in the minimization problem
and proceed.
• Example:
Job A B C D
Machine
1 20 - 32 27
2 15 20 17 18
3 16 18 - 20
4 - 20 18 24
54
Job A B C D
Machine
1 20 M 32 27
2 15 20 17 18
3 16 18 M 20
4 M 20 18 24
55
Row Reduction
Job A B C D
Machine
1 0 M 12 7
2 0 5 2 3
3 0 2 M 4
4 M 2 0 6
56
Column Reduction
Job A B C D
Machine
1 0 M 12 4
2 0 3 2 0
3 0 0 M 1
4 M 0 0 3
57
Job A B C D
Machine
1 0 M 12 4
2 X0 3 2 0
3 X0 0 M 1
4 M 0 0 3
58
Job A B C D
Machine
1 0 M 12 4
2 X0 3 2 0
3 X0 0 M 1
4 M 0 0 3
59
Job A B C D
Machine
1 0 M 12 4
2 X0 3 2 0
3 X0 0 M 1
4 M X0 0 3
60
Job A B C D
Machine
1 0 M 12 4
2 X0 3 2 0
3 X0 0 M 1
4 M X0 0 3
1 → A, 2 → D, 3 → B, 4 → C
61
