Assignment Problem
Assignment Problem
• An assignment problem seeks to minimize the total cost
of assignment of m worker to m jobs, given that the cost
of worker i performing job j is cij .
• It assumes all workers are assigned and each job is
performed.
• An assignment problem is a special case of a
transportation problem in which all supplies and all
demands are equal to 1; hence assignment problems
may be solved as linear programs.
Assignment Problem
Network Representation
c11
1 1
c12
c13
c21
2
c22 2
c23
c32
c31
3 c33 3
Workers Jobs
Assignment Problem
Linear Programming Formulation
Min cijxij
ij
s.t. xij = 1 for each worker i
j
xij = 1 for each job j
i
xij = 0 or 1 for all i and j
Assignment Problem Example
The Hungarian Method
1. Subtract row minimum from each element in the row
2. Subtract column minimum from each element in the
column
3. Cover the zeroes with as few lines as possible
4. If the number of lines = m = n, then optimal solution is
hidden in zeroes
5. Otherwise, find the minimum cost that is not covered by
any lines
1. Subtract it from all uncovered elements
2. Add it to all elements at intersections (covered by two lines)
6. Back to step 3
The Hungarian Method – Optimal Solution
How to identify the optimal solution:
• Make the assignments one at a time in positions that
have zero elements.
• Begin with rows or columns that have only one zero.
Cross out both the row and the column involved after
each assignment is made.
• Move on to the rows and columns that are not yet
crossed out to select the next assignment, with
preference given to any such row or column that has
only one zero that is not crossed out.
• Continue until every row and every column has exactly
one assignment and so has been crossed out.
Solved example:
Minimum uncovered
number
Minimum uncovered
number
Optimal Solution
JOB TIME
1-C 6
2-D 9
3-E 15
4-A 14
5-B 11
55
Example-1
There are 3 jobs A, B, and C and three machines X, Y, and
Z. All the jobs can be processed on all machines. The time
required for processing job on a machine is given below in
the form of matrix. Make allocation to minimize the total
processing time.
Machines (time in hours)
X Y Z
A 11 16 21
Jobs
B 20 13 17
C 13 15 12
Example-2
A company has four jobs to be completed. Each
machine must be assigned to complete one job.
The time required to setup each machine for
completing each job is shown in the table below.
Company wants to minimize the total setup time
needed to complete the four jobs.
Setup times
(Also called the cost matrix)
Time (Hours)
Job1 Job2 Job3 Job4
Machine 1 14 5 8 7
Machine 2 2 12 6 5
Machine 3 7 8 3 9
Machine 4 2 4 6 10
Example-3
Multiple optimal solution
Job (Hours)
A B C D
Machine 1 5 3 2 8
Machine 2 7 9 2 6
Machine 3 6 4 5 7
Machine 4 5 7 7 8
Example-4
Unbalanced Problem
Worker
I II III
Job A 9 12 11
Job B 8 13 17
Job C 20 12 13
Job D 21 15 17
Example-5
Unbalanced Problem
Job (Hours)
A B C D
M1 9 14 19 15
M2 7 17 20 19
M3 9 18 21 18
M4 10 12 18 19
M5 10 15 21 16
Example-6
• The ABC company has a taxi waiting at each of
the four cab stands. Four customers have called
and requested service. The distance in miles
from the waiting taxis to the customer are given
in the matrix below. Find the optimal assignment
of taxis to customers so as to minimize the total
driving distances to the customer.
Cost Matrix
Cab Sites Customer (Dist in miles)
A B C D
Stand 1 40 50 60 65
Stand 2 30 38 46 48
Stand 3 25 33 41 43
Stand 4 39 45 51 59
