Assignment Problem

Jobs for all GCETT

S
 Jobs
Introduction 1 2 .. j .. n
• A special case of Transportation Problem.
1 C11 C12 C1j C1n

Assignee
.. ..
• There will be a set of n jobs to be executed.
2 C21 C22
• There will be n assignees available to execute the jobs. .. C2j .. C2n
.. ..
• Assignees can be persons, machines, plants, time slots. .. .. .. .. ..
• Every assignee is capable of doing all the jobs. C Ci2 Cij Cin
i i1 .. ..
• Each assignee is to be assigned exactly 1 job.
.. .. .. .. .. .. ..
• Each job is to be assigned to exactly 1 assignee.
job C
• A cost Cij is associated with assignee i for executing n j.n1 Cn2 .. Cnj .. Cnn
• Objective is to determine all the n assignment such that total cost is minimized.

Preetam K Sur, Assistant Professor, Computer Science & Engineering Dep

artment
GCETTS 2
 Vs Transportation Problem
Comparison

Jobs Destination
Suppl Suppl
1 2 .. j .. n y 1 2 .. j .. n y

1 C11 C12 C1j C1n 1 C11 C12 C1j C1n

Assignee

.. .. 1 .. .. S1

Source
2 C21 C22 .. C2j .. C2n 1 2 C21 C22 .. C2j .. C2n S2
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
i Ci1 Ci2 .. Cij .. Cin 1 i Ci1 Ci2 .. Cij .. Cin Si
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
n Cn1 Cn2 .. Cnj .. Cnn 1 m Cm1 Cm2 .. Cmj .. Cmn Sm
Deman Deman
d 1 1 .. 1 .. 1 d
D1 D2 .. Dj .. Dn

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 3
Vs Transportation Problem
Assignment Problem Transportation Problem

• Number of assignees and jobs have to • Number of sources and destinations

be equal. need not be equal.
• Hence the cost matrix has necessarily to • Hence, the cost matrix need not be a
be square matrix. square matrix.
• The decision variable, Xij, denoting the i- • The decision variable, Xij, denoting the
th person is assigned j-th job can be quantity transported from i-th source to
either 0 or 1. j-th destination can be any possible
positive value.
• The supply and demand value is exactly • The supply and demand value is
1 for each of the assignee and job. generally different for each source and
destination.
• The problem is unbalanced if the
number of jobs and number of assignee • Problem is unbalanced if the total
differs supply and total demand differs.

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 4
Mathematically
Assignment Problem Transportation Problem

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 5
Balancing
• An assignment problem is balanced iff the number of assignee matches exactly with
number of jobs.
• Otherwise, it is unbalanced.
• Similar to transportation problem, we cannot solve an unbalanced assignment
problem.
• Similar to transportation problem, we have to add a dummy row / column to make an
unbalanced assignment problem Jobsas balanced to solve it.
1 all
• Similar to transportation problem, 2 the3cost 4of dummy
5 row / column will be 0.
1 4 3 6 2 7
Assignee

2 10 12 11 14 16
3 4 3 2 1 5
D1 0 0 0 0 0
D2 0 0 0 0 0
Preetam K Sur, Assistant Professor, Computer Science & Engineering
Department GCETTS 6
Hungarian Method
Solving Assignment Problem

1. Row reduction : Subtract the minimum element of each row from all the elements of respective
rows.
• Equivalent cost table with each row having a zero element
2. Column reduction : Subtract the minimum element of each column from all the elements of
respective column.
• This two steps will provide an equivalent cost table with each row and column having a zero element.
3. Now draw minimum number of horizontal and vertical lines to cover all the zeros in the
resulting matrix.
4. If the number of lines < n, modify the table in the following way –
a. Determine the smallest uncovered element in the table.
b. Subtract this element from all the uncovered elements.
c. Add the smallest uncovered element to the intersections of the covering lines.
5. Repeat from step 3 until number of lines become n.
6. If number of lines becomes n, it means the optimal solution is reached.
7. To find the optimal solution, make an assignment one at a time having zero element
a. Start with rows or columns having only single zero. Assign it. (If not available, break tie arbitrarily.)
Preetam K Sur, Assistant Professor, Computer Science & Engineering
b. Cross out the row and column once you assign a cell.
Department GCETTS 7
Example
Jobs
Machin
1 2 3 4 5
Job e Cost
Machine

A 10
8
7 3
1
0 3
1
0 0
2 8
6
4
1 D 3
B 9
7
6
4 7
5
4
2 8
6
5
3 2
0 7
5
3
1
2 A 3
C 7
5
4 5
3
2 6
4
3 0
2 4
2
0
3 E 9
D 3
1
0 5
3
2 8
6
5 0
2 4
2
0
4 B 2
E 9
3
2
0 10
4
3
1 9
3
2
0 6
0 10
4
2
0
5 C 4
Total Cost 21

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 8
Maximization in Assignment Problem
• The cost matrix will be replaced by profit matrix.
• Hence, the objective function tries to maximize the total profit.
• To solve it, we need to convert the profit matrix into loss matrix.
• To do it, we need to subtract all the elements from the highest element of the profit
matrix.
• Then we can1apply
2 the3Hungarian
4 5 method on the1 loss2matrix
3 to4find5out the
assignments.
A 32 38 40 28 40 A 9 3 1 13 1

B 40 24 28 21 36 B 1 17 13 20 5

C 41 27 33 30 37 C 0 14 8 11 4

D 22 38 41 36 36 D 19 3 0 5 5

E 29 33 40 35 39 E 12 8 1 6 2
Preetam K Sur, Assistant Professor, Computer Science & Engineering
Department GCETTS 9
Travelling
Salesman
Problem
As an Assignment Problem

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 10
Travelling Salesman Problem
• A salesman has to visit n cities.
• He wants to start from a particular city.
• Visit each city exactly once and then return to his starting point.
• Moving from a city to another one incurs some cost / time / distance.
• The objective of the salesman is to minimize his cost / time / distance while covering
all the cities. A B C D E
A ∞ 4 10 14 2

B 12 ∞ 6 10 4

C 16 14 ∞ 8 14

D 24 8 12 ∞ 10

E 2 6 4 16 ∞
Preetam K Sur, Assistant Professor, Computer Science & Engineering
Department GCETTS 11
Mathematically
• If Cij represents the cost of travelling from city i to city j,
• And, Xij represents whether the salesman visits from city i to city j
• Then the objective function is –

• The assignment tables gives from which city to which city

the salesman need to visit to minimize the cost.
• We need to sequence those visits to find if it covers all the
cities.
• i.e. whether the assignment provides a Hamiltonian
cycle.
• Additional Constraint
• Xij is chosen such that no city is visited twice before all
the cities are visited.

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 12
 Cell Sequence
Sequence Cost
Cost

Solving Travelling Salesman

(A, B) AA →
→BB→
→CC→
→DD→
→EE→
→AA 30
30
Sequencing Infeasibl
(D, C) A → B → E →
• Apply Hungarian method on the cost matrix of Travelling Salesman problem.A
Assignments e
• Check if the solution satisfies the additional
(D, constraint.
E) A → B → C → D → EA→→AE → A 30
B→C→D→B
• If yes, then sequencing the assignments gives the optimal solution.
• Otherwise, apply the method of enumeration. A B C D E
• Find out next minimum non-zero element & all the cells
having that value.
A ∞ 4
2 10
6 12
14 2
0
• Consider those cells one by one and do the following B 12
8 ∞ 6
0 10
6 4
0
• Assign the respective cell.
• Update all other assignments such that only one C 16
8 14
6 ∞ 8
0 14
6
assignment per row and column is maintained.
• Find out if it satisfies additional constraint. If yes calculate
total cost.
D 16
24 8
0 12
2 ∞ 10
2
• Once all such cells are considered, find out which E 2
0 6
4 4
0 16
14 ∞
assignment gives optimal solution.

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 13
Summary
• Assignment Problem is a special case of Transportation problem.
• We use Hungarian method to solve assignment problem.
• Obtain modified cost matrix after row reduction and column reduction.
• Find out the minimum number of line required to cover all the zeros in the modified
matrix.
• If number of lines = n, then the optimal solution is obtained.
• Otherwise, find the minimum uncovered element; subtract it from all the uncovered
elements and add it to the intersection points
• Repeat from the step of drawing the lines.
• Maximization assignment problem can be solved using Hungarian method by
converting the profit matrix as loss matrix.
• Travelling Salesman problem can be represented as an assignment problem with an
additional constraint.
• We can employ Hungarian method to find out the solution of Travelling Salesman
problem.
Preetam K Sur, Assistant Professor, Computer Science & Engineering
Department GCETTS
• If the solution doesn’t satisfy the additional constraint, we can use enumeration 14
Thank You!

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Department GCETTS 15