Operation Research
The Assignment Problem
Marine Technology Faculty – ITS Surabaya
Introduction
Special type of transportation problem.
Also called an allocation problem.
There is n jobs to perform with n persons.
Objective function (in assigning the different job
to different persons) is to find the optimal
assignment that will minimize the total time
taken to finish all the jobs by the individuals.
Mathematical Formulation
Men
Jobs
A B C D
1 5 6 8 7
2 4 7 6 6
3 5 4 6 5
4 6 7 4 6
Let the decision variable xij be the assignment of ith
job to jth person, and cij be the time taken for ith job
by the jth person.
Mathematical Formulation
The objective function is to minimize :
Subject to :
Row Restriction :
▪ x11 + x12 + x13 + x14 = 1 for job 1
▪ x21 + x22 + x23 + x24 = 1 for job 2
▪ x31 + x32 + x33 + x34 = 1 for job 3
▪ x41 + x42 + x43 + x14 = 1 for job 4
Mathematical Formulation
Column Restriction :
▪ x11 + x21 + x31 + x41 = 1 for person 1
▪ x12 + x22 + x32 + x42 = 1 for person 1
▪ x13 + x23 + x33 + x43 = 1 for person 1
▪ x14 + x24 + x34 + x44 = 1 for person 1
and xij = 0 or 1
In general,
▪ x11 + x12 + … + x1n = 1 for i = 1, 2, …, n
▪ x11 + x21 + … + xn1 = 1 for j = 1, 2, …, n
Important !
We shall not attempt simplex algorithm or
the transportation algorithm to get a
solution to an assignment problem.
Certain systematic procedure has been devised
so as to obtain the solution to the problem with
ease.
Theorem
If in assignment problem we add a constant to
every element of a row or column in the
effectiveness matrix then an assignment that
minimizes the total effectiveness in one matrix
also minimizes the total effectiveness in the
other matrix.
Example 1
Worker
Step 1 : select the Jobs
A B C D
minimum element in 1 10 20 18 14
each row. Subtrack 2 15 25 9 25
3 30 19 17 12
from all the element 4 19 24 20 10
in that row.
Worker
Jobs
A B C D
1 0 10 8 4
2 6 16 0 16
3 18 7 5 0
4 9 14 10 0
Example 1
Worker
Step 2 : select the Jobs
A B C D
minimum element in 1 0 10 8 4
each column. 2 6 16 0 16
Subtrack from all the 3 18 7 5 0
4 9 14 10 0
element in that
collumn.
Worker
Jobs
A B C D
1 0 3 8 4
2 6 9 0 16
3 18 0 5 0
4 9 7 10 0
Example 1
Step 3 : at
least there is one
zero in each row
and each collumn. Worker
Used to Jobs
A B C D
indicate the
assignment, and 1 0 3 8 4
another zero with 2 6 9 0 16
X. 3 18 0 5 0
4 9 7 10 0
Example 1
Worker
Step 4 : assigned Jobs
A B C D
certain jobs to certain 1 0 3 8 4
worker. 2 6 9 0 16
3 18 0 5 0
4 9 7 10 0
jobs worker
1 A
2 C
3 B
4 D
Example 2
1
1
1 2
2
2 3
3
3 4
4
4 5
5
5
1
1
1 5
5
5 0
00 3
3
3 2
2
2 6
6
6
2
2
2 00 0
0
0 5
5
5 4
4
4 7
7
7
3
3
3 0
0
0 3
3
3 0000 4
4
4 0000
4
4
4 0
0
0 1
1
1 0000 3
3
3 0000
5
5
5 6
6
6 5
5
5 0
0
0 00 0
0
0
Hungarian Algorithm
Steping:
1. Use to all rows for which assignment have
not been made.
2. Use to column not already marked
3. Use to rows not already marked
4. Repeat (2) and (3)
5. Draw lines through all unmark rows and
column
6. Examine the elements
7. Proceed to make an assignment
Example 1
Building
Contractor Contractor
Building
1 2 3 4 1 2 3 4
A 48 48 50 44 A 4 4 6 0
B 56 60 60 68 B 0 4 4 12
C 96 94 90 85 C 11 9 5 0
D 42 44 54 46 D 0 2 12 4
Contractor
?
Building
1 2 3 4
A 4 2 2 0
B 0 2 0 12
C 11 7 1 0
D 0 0 8 4
Example 1
Building
Contractor Contractor
Building
1 2 3 4 1 2 3 4
A 4 2 2 0 A 3 1 2 0
B 0 2 0 12 B 0 2 0 12
C 11 7 1 0 C 10 6 0 0
D 0 0 8 4 D 0 0 8 4
Contractor
Building
1 2 3 4
A 3 1 2 0 Building A is alloted to contractor 4
B 0 2 0 12 Building B is alloted to contractor 1
C 10 6 0 0 Building C is alloted to contractor 3
D 0 0 8 4 Building D is alloted to contractor 2
