Unit – III

Lecture– III
Mr.R.R.Kshatriya
Assistant Professor,
Department of Civil Engineering,
Matoshri College of Engineering and Research Centre, Nashik.
Savitribai Phule Pune University, Pune.
Department of Civil Engineering

Contents of Unit-III
 Transportation model
 Balanced
 Unbalanced Minimization

 Assignment model
Minimization /
 Balanced Maximization
 Unbalanced
Operation Research
Department of Civil Engineering

Contents of Lecture
 Balanced Assignment model (minimization)

Operation Research
Department of Civil Engineering

The Assignment model

 The transportation model is a special case of linear programming model and
assignment problem is a special case of transportation model, therefore it is also
a special case of linear programming model.
 Hence it must have all the properties of linear programming model. That is it
must have: (i) an objective function, (ii) it must have structural constraints, (iii)
It must have non-negativity constraint and (iv) The relationship between
variables and constraints must have linear relationship.
 The objective is to assign a number of resources to an equal number of activities,
so as to minimize total cost or to maximize total profit of allocation.
 Example: assigning jobs to machine, contracts to bidders, salesmen to different
region, etc.

Operation Research
Department of Civil Engineering
Flow chart

Operation Research
Department of Civil Engineering

Balanced Assignment
Problem (minimization)

Operation Research
Department of Civil Engineering

Example 1
A department has 5 employees to which 5 jobs are to be assigned, so as to minimize
the total time to perform all jobs. The time (in hours) required to perform each job
by each employees are given in the following table:

Employees
Job
1 2 3 4 5
A 10 5 13 15 16
B 3 9 18 13 6
C 10 7 2 2 2
Find an optimal policy,
D 7 11 9 7 12 which will minimize the
E 7 9 10 4 12 total time.

Operation Research
Department of Civil Engineering
Solution
Step 1: Find the smallest element from each row and column
Employees Min.
Job
1 2 3 4 5 from row
A 10 5 13 15 16 5
B 3 9 18 13 6 3
C 10 7 2 2 2 2
D 7 11 9 7 12 7
E 7 9 10 4 12 4
Min. from
3 5 2 2 2 14 21
column
As, ∑Min. from row > ∑Min. from column, Let’s perform row operation.

Operation Research
Department of Civil Engineering

Step 2: Subtract the smallest element from Step 3: Smallest element from uncovered
that particular row. cell is ‘2’. Subtract ‘2’ from all uncovered
cells, add ‘2’ at the intersection of lines and
5 0 8 10 11 keep covered cells as it is.
0 6 15 10 3 7 0 8 12 11
8 5 0 0 0 0 4 13 10 1
0 4 2 0 5 10 5 0 2 0
3 5 6 0 8 0 2 0 0 3
No. of order (N) = 5 3 3 4 0 6
No. of lines drawn (N1) = 4 No. of order (N) = 5
No. of lines drawn (N1) = 5
This is an optimal solution.
Operation Research
Department of Civil Engineering

Step 4: Find five zero, such that one zero

in each row and column.
Step 5: Optimal assignment policy
1 2 3 4 5
A 7 0 8 12 11 Time
Job Employee
B 0 4 13 10 1 (hours)
A 2 5
C 10 5 0 2 0
D 0 2 0 0 3 B 1 3
E 3 3 4 0 6 C 5 2
D 3 9
E 4 4
∑ 23 hours

Operation Research
Department of Civil Engineering

Example 2
Five skilled workers are available for five skilled jobs on the site. One worker is to
be assigned for each job. The time (in hours) required to execute each job by each
worker are given in the following table:
Job
Workers
A B C D E
1 3 9 2 3 7
2 6 1 5 6 6
3 9 4 7 10 3
Find an optimal assignment,
4 2 5 4 2 1 which will minimize the total
5 9 6 2 4 6 time.

Operation Research
Department of Civil Engineering
Solution
Step 1: Find the smallest element from each row and column
Jobs Min.
Workers
A B C D E from row
1 3 9 2 3 7 2
2 6 1 5 6 6 1
3 9 4 7 10 3 3
4 2 5 4 2 1 1
5 9 6 2 4 6 2
Min. from
2 1 2 2 1 8 9
column
As, ∑Min. from row > ∑Min. from column, Let’s perform row operation.

Operation Research
Department of Civil Engineering

Step 2: Subtract the smallest element from Step 3: Smallest element from uncovered
that particular row. cell is ‘1’. Subtract ‘1’ from all uncovered
cells, add ‘1’ at the intersection of lines and
1 7 0 1 5 keep covered cells as it is.
5 0 4 5 5 0 7 0 0 5
6 1 4 7 0 4 0 4 4 5
1 4 3 1 0 5 1 4 6 0
7 4 0 2 4 0 4 3 0 0
No. of order (N) = 5 6 4 0 1 4
No. of lines drawn (N1) = 3 No. of order (N) = 5
No. of lines drawn (N1) = 5
This is an optimal solution.
Operation Research
Department of Civil Engineering

Step 4: Find five zero, such that one zero

in each row and column.
Step 5: Optimal assignment policy
A B C D E
1 0 7 0 0 5 Time
Worker Job
2 4 0 4 4 5 (hours)
3 5 1 4 6 0 1 A 3
4 0 4 3 0 0 2 B 1
5 6 4 0 1 4 3 E 3
4 D 2
5 C 2
∑ 11 hours

Operation Research
Department of Civil Engineering

Example 3
An engineering firm wish to assign 5 project tasks to 5 engineers, so as to minimize
the total time to complete all tasks. The time (in days) required to complete each
task by each engineer are given in the following table:

Engin Project tasks

eers 1 2 3 4 5
A 3 5 10 15 8
B 4 7 15 18 8
C 8 12 20 20 12
Find an optimal policy,
D 5 5 8 10 6 which will minimize the
E 10 10 15 25 10 total time.

Operation Research
Department of Civil Engineering
Solution
Step 1: Find the smallest element from each row and column
Project tasks Min.
Engineers
1 2 3 4 5 from row
A 3 5 10 15 8 3
B 4 7 15 18 8 4
C 8 12 20 20 12 8
D 5 5 8 10 6 5
E 10 10 15 25 10 10
Min. from
3 5 8 10 6 32 30
column
As, ∑Min. from row < ∑Min. from column, Let’s perform column operation.

Operation Research
Department of Civil Engineering

Step 2: Subtract the smallest element from Step 3: Smallest element from uncovered
that particular column. cell is ‘1’. Subtract ‘1’ from all uncovered
cells, add ‘1’ at the intersection of lines and
0 0 2 5 2 keep covered cells as it is.
1 2 7 8 2 0 0 2 5 2
5 7 12 10 6 0 1 6 7 1
2 0 0 0 0 4 6 11 9 5
7 5 7 15 4 2 0 0 0 0
No. of order (N) = 5 6 4 6 14 3
No. of lines drawn (N1) = 2 No. of order (N) = 5
No. of lines drawn (N1) = 3
Operation Research
Department of Civil Engineering

Step 4: Smallest element from uncovered

cell is ‘3’. Subtract ‘3’ from all uncovered Step 5: Smallest element from uncovered
cells, add ‘3’ at the intersection of lines and cell is ‘1’. Subtract ‘1’ from all uncovered
keep covered cells as it is. cells, add ‘1’ at the intersection of lines and
0 0 2 5 2 keep covered cells as it is.
0 1 6 7 1 0 0 2 5 2
1 3 8 6 2 0 1 6 7 1
2 0 0 0 0 0 2 7 5 1
3 1 3 11 0 2 0 0 0 0
No. of order (N) = 5 3 1 3 11 0
No. of lines drawn (N1) = 4 No. of order (N) = 5
No. of lines drawn (N1) = 4
Operation Research
Department of Civil Engineering

Step 6: Smallest element from uncovered

cell is ‘1’. Subtract ‘1’ from all uncovered Step 7: Smallest element from uncovered
cells, add ‘1’ at the intersection of lines and cell is ‘2’. Subtract ‘2’ from all uncovered
keep covered cells as it is. cells, add ‘2’ at the intersection of lines and
1 0 2 5 2 keep covered cells as it is.

0 0 5 6 0 1 0 0 3 2
0 1 6 4 0 0 0 3 4 0
3 0 0 0 0 0 1 4 2 0
4 1 3 11 0 5 2 0 0 2

No. of order (N) = 5 4 1 1 9 0

No. of lines drawn (N1) = 4 No. of order (N) = 5
No. of lines drawn (N1) = 5
This is an optimal solution.
Operation Research
Department of Civil Engineering

Step 8: Find five zero, such that one zero

in each row and column.
1 2 3 4 5 Step 9: Optimal assignment policy
A 1 0 0 3 2 Engi Project Time
B 0 0 3 4 0 neer task (days)
C 0 1 4 2 0 A 3 10
D 5 2 0 0 2 B 2 7
E 4 1 1 9 0 C 1 8
D 4 10
E 5 10
∑ 45 days

Operation Research
Department of Civil Engineering

Summary
• Balanced Assignment model (minimization)

Operation Research
Department of Civil Engineering

Exercise 1
An automobile dealer wish to assign 4 repairman to 4 different jobs. The repairman have
somewhat different kind of skills and they exhibit different levels of efficiency from one job
to another. The dealer has estimated the number of man-hours that would be required for
each job-man combination. Find the optimal assignment that will results in the minimum
man-hours needed.
Job
Man
A B C D
1 5 3 2 8
2 7 9 2 6
3 6 4 5 7
4 5 7 7 8
Operation Research
Department of Civil Engineering

Thank you
Operation Research