Assignment model
1
Assignment model
To solve the assignment problems
1. Enumeration methods(trial and error)
2. Simplex methods
3. Transportation methods
4. Hungarian methods(foods techniques)
2
Assignment model
The assignment model is a special form of a linear programming
model that is similar to the transportation model.
An assignment problem is a special form of transportation problem
where all supply and demand values equal one.
– One-to-one pairing.
Helps in assigning work/jobs to machines or employees with to
minimize or maximize objectives i.e. distance, time, cost, profit….
The right job for the right person, the right individual to the right
machine and it is not about specialization but responsibility
3
The steps of the assignment solution method
1. Formulate the problem as assignment methods
2. Perform Row reductions(row operation)select the smallest element at each
row and subtract each from the other element in the row including it self
3. Perform Column reductions(operation)select the smallest element from each
column and subtract it from the other element in that column including it self
4. Cover the zeros by using vertical and horizontal lines not diagonal lines and
be economical in using the lines i.e. , a single line should cover as much as
possible more zeros
5. If the number of lines used are exactly equals to the number of rows or
columns ,then the solution is optimal and make the assignment by encircling
the zeros at each row
The steps of the assignment solution method
[Link] the solution is not optimal , i.e., if the number of lines used are less than the
number of columns or rows, then
A. Select the smallest un covered element and
1, subtract that element from the other uncovered element including it self
[Link] that element on the covered elements which are at the intersection point
of two lines
[Link] reset elements which are covered but not at the intersection point of two
lines remain unchanged
B. make an adjustment and cover the zeros by using vertical and horizontal
lines
7. if the number of lines used are exactly equal to the number of rows or
columns,the solution is optimal and make the assignment
example
A computer center has four programs to be developed by four
programmers' .the head of the computer center after studding the
duration in developing the programs by four programmers in terms of
minutes, has estimated in the following problem. Solve the given
assignment problem by Hungarian method
example
example
Jobs
Example
A B C D
1 15 ETB 20 18 24
Employees
2 12 17 16 15
3 14 15 19 17
4 11 14 12 13
Required: make the assignment which minimizes cost
9
Row Reduction
Opportunity cost
Employees
A B C D
Employees
1 15 20 18 24
Job A B C D
2 12 17 16 15
1 0 5 3 9
3 14 15 19 17
Job 2 0 5 4 3
4 11 14 12 13
3 0 1 5 3
4 0 3 1 2
10
Column Reduction
Employees Opportunity cost
A B C D
1 0 5 3 9
Employees
Job 2 0 5 4 3
A B C D
3 0 1 5 3
1 0 4 2 7
4 0 3 1 2 Job 2 0 4 3 1
3 0 0 4 1
4 0 2 0 0
11
Covered zero values
Employees
A B C D
1 0 4 2 7
Job 2 0 4 3 1
3 0 0 4 1
4 0 2 0 0
Optimum?
12
Further Reduction
Employees The minimum number of
lines used to cover zeros
A B C D are equal to number of
rows/columns
1 0 4 2 7
Job 2 0 4 3 1 Employees
3 0 0 4 1 A B C D
4 0 2 0 0 1 0 3 1 6
Job 2 0 3 2 0
3 1 00 3 1
4 1 2 00 0
Optimum!
13
Make assignment
Job-employee assignment
Employees
1 A birr
A B C D
15
1 0 3 1 6
2 D
15
Job 2 0 3 2 0
3 B
3 1 0 3 1
15
4 1 2 0 0 4 C
12
ETB57
14
THE END!
15