ASSIGNMENT PROBLEM

Introduction

The Assignment Problem (AP) which has many applications in allocation and scheduling,
for example in assigning salesmen to different regions, vehicles and drivers to different route,
products to factories, jobs to machines, contracts to bidders and research problems to teams,
etc.

Assignment is generally made on one-to-one basis and if there are more jobs to do than can
be done, one can decide which job to leave undone or what resource to add.

Definition of the Assignment Model

An assignment problem concerns as to what happens to the effectiveness function when we

associate each number of ‘origins’ with each of the same number of ‘destinations’.

Each resource or facility (origin) is to be associated with one and only one job (destination)
and associations are to be made in such a way so as to maximize (or minimize) the total
effectiveness.

Resources are not divisible among jobs, nor are jobs divisible among resources.

The Assignment Problem can define as follows: -

Given n facilities, n jobs and the effectiveness of each facility to each job, here the problem
is to assign each facility to one and only one job so that the measure of effectiveness is
optimized. Here the optimization means Maximized or Minimized.

There are many management problems that have an assignment problem structure.

Thus, an assignment problem can be represented by n x n matrix which constitutes n!

possible ways of making assignment.

Note that with n facilities and n jobs there are n! possible assignments. The simplest way of
finding an optimum assignment is to write all the n! possible arrangements, evaluate their
total cost and select the assignment with minimum cost.

But this method leads to a calculation problem of formidable size even when the value of n is
moderate.

For n=10 a realistic situation, the possible number of arrangements is

n! = 10! = 3,268,800

For n=20 the possible number of arrangements is

n! = 20! = 2,432,902,008,176,640,000.

1
The Mathematical Model

The assignment problem can be stated as follows:

Given n x n matrix of real numbers, Cij – referred to as the rating or effective matrix

Where; Cij > 0, for i , j= 1,2,……,n where cij is the cost of assigning ith person to the jth job,

Find n x n matrix X= xij- referred to as the assignment matrix, such that

xij = x2ij, ij = 1,2,……,n ………………………….Eqn. 1

Σni=1 xij = Σnj=1 xij = 1 …………………………….Eqn. 2

and minimize
T = Σi Σj cij xij………………………………Eqn. 3

Equations 1 and 2 are conditions which jointly specify that;

a) xij = is 1, if facility i is assigned to job j; and

is 0, if otherwise

b) Each row and column of matrix X will have one element unity and all other elements
zero;
c) Condition eqn. 3, together with eqn. 1 and 2, specify that a set of n elements is to be
chosen from matrix C, with no two elements in the same row or same column such
that the sum of the elements in the set is minimal; and
d) When these three conditions are satisfied simultaneously, we obtain the permutation
matrix for the optimal solution.

Example 1

A project manager has four project officers and four projects on hand. The officer’s
efficiency differ significantly and the project also differ in complexity. The manager
estimates the time each officer would take to complete each project and as shown in the
matrix below:

Man
Task I II III IV
A 18 36 27 21
B 23 38 14 36
C 48 29 28 25
D 29 36 34 20

The matrix is considered as the effectiveness matrix. How should the manager allocate the
officers to projects so as to minimize the total time.

There are 4! = 24 feasible solutions and therefore 24 possible permutations matrices. The
possible solutions, the optimal assignment is

A = I, B = III, C = II and D = IV

2
and total man-hour for completion of tasks are 81

Assignment Problem Structure and Solution

The structure of the Assignment problem is similar to a transportation problem, as follows:

Jobs
1 2 3 …….. …….. n 1
1 C11 C12 C1n 1
2 C21 C22 C2n
. . . . . . .
Workers . . . . . . .
. . . . . . .
. . . . . . .
n Cn1 Cn2 ……. …….. Cnn 1
1 1 …….. ……... 1

th th
The element cij represents the measure of effectiveness when i person is assigned j job.
Assume that the overall measure of effectiveness is to be minimized. The element xij
represents the number of ith individuals assigned to the jth job. Since ith person can be
assigned only one job and jth job can be assigned to only one person we have the
following

xi1 +xi2+................+xin = 1, where i=1,2,.......,n

x1j+x2j +................+xnj =1, wherej=1,2,.......,n

and the objective function is formulated as

Minimize c11x11 + c12x12 + ........... + cnnxnn

xij ≥ 0

The assignment problem is actually a special case of the transportation problem where

m = n and ai = bj = 1.

However, it may be easily noted that any basic feasible solution of an assignment problem
contains (2n – 1) variables of which (n – 1) variables are zero. Because of this high degree
of degeneracy the usual computation techniques of a transportation problem become very
inefficient.

The Solution of the Assignment Problem

Theorem I

It states: -

In an “assignment problem, if we add or subtract a constant to every element of a row (or

column) in the cost matrix, then an assignment which minimizes the total cost on one matrix
also minimizes the cost on the other matrix”.

3
This result may be used in two different methods to solve the assignment problem.

Theorem II

It states: -

“If all cij ≥ 0 and we can find a set xij = x*ij such that Σi Σj cij xij = 0, then this solution is
optimal.”

The above two theorems indicate that if one can create a new c`ij matrix with zero entries,
and if these zero elements or a subset thereof, constitute feasible solution, then this feasible
solution is the optimal solution.

Thus, the method of solution consists of adding (in case matrix elements are negative) or
subtracting constants from rows and columns until sufficient number of c`ijs become zero to
yield a solution with a value of zero.

The Solution of the Assignment Problem Model

The Opportunity Cost Method

The cost of any action consists of opportunities that are sacrificed (foregone) in taking that
action. Consider the following table which contains the cost in KSHs. of processing each job
A, B, and C on machines X, Y, and Z.

Table 1
Machines
X Y Z
A 25 15 22
Jobs B 31 20 19
C 35 24 17

Suppose it is decided to process job A on machine X.

The sacrifice is referred to as an opportunity cost.

The decision to process job A on machine X precludes the assignment of this job to machine
Y, given the constraints that one and only one job can be assigned to a machine.

More precisely these costs can be called the Machine Opportunity Costs with regard to job
A.

Similarly, if the lowest cost of row B is subtracted from all the costs in this row, we would
have the machine-opportunity costs with regard to job B. The same step in row C would give
the machine-opportunity costs for job C.

4
This is represented in the following table:

Table 2
Machines
X Y Z
A 10 0 7
Jobs B 12 1 0
C 18 7 0

In addition to these machine-opportunity costs, there are job-opportunity costs also. Job A,
B or C, for instance, could be assigned to machine X.

A zero-opportunity cost is involved in the assignment of job A to machine X, since this is

the best assignment for machine X (column X).

Hence job-opportunity costs for each column (each machine) are obtained by subtracting the
lowest cost entry in each column from all the cost entries in that column.

If the lowest entry in each column of table 2 is subtracted from all the cost entries of that
column, the resulting table is called total opportunity cost table.

Table 3
Machines
X Y Z
A 10-10=0 0-0=0 7-0=7
Jobs B 12-10=2 1-0=1 0-0=0
C 18-10=8 7-0=7 0-0=0

It may be recalled that the objective is to assign the jobs to the machine so as to minimize the
total costs.

The total opportunity cost table contains four cells with zeros, each indicating a zero-
opportunity cost for that cell (assignment).

Hence,

1) Job A could be assigned to machine X or Y; and

2) Job B to machine Z.

All assignments having zero opportunity costs.

Thus, to make an optimal assignment of the three jobs to the three machines, there must be
three zero cells in the table such that a complete assignment to these cells can be made with
a total opportunity cost of zero.

This method consists of drawing minimum number of lines covering all zero cells in the total
opportunity cost table.

If the minimum number of lines equals the number of rows (or columns) in the table, an
optimal assignment can be made and the problem is solved.

5
If, however, the minimum number of lines is less than the number of rows (or columns), an
optimal solution assignment cannot be made.

In this case, there is need to develop a new total opportunity cost table.

Table 4
Machines
X Y Z
A 0 0 7 Line 1
Jobs B 2 1 0
C 8 7 0
Line 2

To accomplish this, we

a) Choose the smallest element in the table not covered by a straight line and subtract
this element from all other elements not having a line through them; and
b) Add this smallest element to all elements lying at the intersection of any two lines.

The revised cost table is as shown.

Table 5
Machines
X Y Z
A 0 0 7+1=8
Jobs B 2-1=1 1-1=0 0
C 8-1=7 7-1=6 0

As the minimum number of lines covering all zeros is three and there are three rows (or
column), an optimal assignment can be made.

The optimal assignments are: -

1) A to X;
2) B to Y; and
3) C to Z.

In larger problems, however, the assignment may not be readily apparent and there is need
for more systematic procedure.

Hungarian Method

It involves a rapid reduction of the original matrix and finding of set of n independent zeros,
one in each row and column, which results in optimal solution.

The method consists of the following steps: -

The Hungarian Method is discussed in the form of a series of computational steps as follows,
when the objective function is that of minimization type.

6
Step 1:

Prepare a square matrix. This step will not be required for n x n assignment problem. For
m x n (m ≠ n) problems, a dummy column or a dummy row, as the case may be, is added to
make the matrix square.

Step 2:

Reduce the matrix. Subtract the smallest element of each row from all the elements of the
row. So, there will be at least one zero in each row.

Examine if there is at least one zero in each column. If not, subtract the minimum element
of the column(s) not containing zero from all the elements of that column(s).

This step reduces the elements of the matrix until zeros, called zero opportunity costs, are
obtained in each column.

Step 3:

Check whether an optimal assignment can be made in the reduced matrix or not. For this the
procedure is: -

a) Examine rows successively until a row with exactly one unmarked zero is obtained.
Make an assignment to this single zero by making square ( ) around it. Cross (X)
all other zeros in the same column as they will not be considered for making any
more assignments in that column. Proceed in this way until all rows have been
examined;
b) Now examine columns successively until a column with exactly one unmarked zero
is found. Make an assignment there by making a square ( ) around it and cross
(X) any other zeros in the same row;
c) In case there is no row or column containing single unmarked zero (they contain
more than one unmarked zero), mark square ( ) around unmarked zero arbitrarily
and cross (X) all other zeros in its row and column. Proceed in the same manner till
there is no unmarked zero left in the cost matrix;
d) Repeat sub-sets (a) and (b) till one of the following two things occur: -

i. There is one assignment in each row and in each column. In this case the
optimal assignment can be made in the current solution, i.e., the current
feasible solution is an optimal solution. The minimum number of lines
crossing all zeros is n, the order of the matrix; and
ii. There is some row and/or column without assignment. In this case optimal
assignment cannot be made in the current solution. The minimum number of
lines crossing all zeros have to be obtained in this case by following step 4.

7
Step 4:

Find the minimum number of lines crossing all zeros. This consists of the following sub-
sets: -

a) Mark (√) the rows that do not have assignments;

b) Mark (√) the columns (not already marked) that have zeros in marked rows;
c) Mark (√) the rows (not already marked) that have assignments in marked columns;
d) Repeat sub-sets (b) and (c) till no more rows or columns can be marked;
e) Draw straight lines through all unmarked rows and marked columns. This gives
the minimum number of lines crossing all zeros. If this number is equal to the
order of the matrix, then it is an optimal solution, otherwise go to step 5.

Step 5:

Iterate towards the Optimal Solution. Examine the uncovered elements.

Select the smallest element and subtract it from all the uncovered elements. Add this
smallest element to every element that lies at the intersection of two lines.

Leave the remaining elements of the matrix as such.

This yields second basic feasible solution.

Step 6

Repeat steps 3 through 5 successively until the number of lines crossing all zeros becomes
equal to the order of the matrix.

In such a case, every row and column will have one assignment. This indicates that an
optimal solution has been obtained.

The total cost associated with this solution is obtained by adding the original costs in the
assigned cells.

8
Example 1:

A machine tool company decides to make four subassemblies through four contractors. Each
contractor is to receive only one subassembly. The cost of each subassembly is determined by
the bids submitted by each contractor and is shown in the table below in (KSHs.”000”).

Table 1
Contractor
1 2 3 4
1 15 13 14 17
Subassembly 2 11 12 15 13
3 13 12 10 11
4 15 17 14 16

a) Formulate the mathematical model for the problem.

b) Show that the assignment model is a special case of the transportation model.
c) Assign the different subassemblies to contractors so as to minimize the total cost.

Solution

a) Formulate the mathematical model for the problem.

Step I:

Key decision is what to whom i.e., which subassembly be assigned to which contractor or
what are the “n” optimum assignments on 1-1 basis.

Step II:

Feasible alternative are n! possible arrangements for n x n assignments situation. In the

given situation there are 4! Different arrangements.

Step III:

Objective is to minimize the total cost involved.

i.e., minimize Z = Σni=1 Σnj=1 cij xij = Σ4i=1 Σ4j=1 cij xij = 15x11 + 13x12 + 14x13 + 17x14 + 11x21 +
12x22 + 15x23 + 13x24 +13x31 + 12x32 + 10x33 + 11x34 + 15x41 + 17x42 + 14x43 + 16x44.

9
Step IV

Constraints:

(a) Constraints on subassemblies are: -

x11 + x12 + x13 + x14 = 1

x21 + x22 + x23 + x24 = 1

x31 + x32 + x33 + x34 = 1

x41 + x42 + x43 + x44 = 1

(b) Constraints on contractors are: -

x11 + x21 + x31 + x41 = 1

x12 + x22 + x32 + x42 = 1

x13 + x23 + x33 + x43 = 1

x14 + x24 + x34 + x44 = 1

xij ≥ 0

Comparing this model with the transportation model, we find that ai = 1: i = 1,2,3,4 and bj =
1, j = 1,2,3,4.

Thus, the assignment model can be represented as in the table 2.

a) All right-hand side constants in the constraints are unity i.e., ai = 1, bj = 1.

Table 2
Contractor (facilities, supply
agents or means)
1 2 3 4 ai
Subassembly 1 15 13 14 17 1
(jobs, tasks or 2 11 12 15 13 1
requirements) 3 13 12 10 11 1
4 15 17 14 16 1
Demand bj 1 1 1 1

b) All coefficients of xij in the constraints are unity.

c) m = n.

10
(iii) Solution of the model

Step I

Prepare a square matrix.

Step II

Reduce the matrix: This involves the following sub-steps:

Subset 1: Subtract the minimum element of each row from all the elements of the row.

The resulting reduced matrix will have at least one zero element in each row.

Table 3
Contractor
1 2 3 4
1 2 0 1 4
Subassembly 2 0 1 4 2
3 3 2 0 1
4 1 3 0 2

Check if there is at least one zero element in each column also.

If so, stop here.

If not, proceed to substep 2.

Subset 2: Mark the column that do not have zero element.

Now subtract the minimum element of each such column from all the elements of that
column.

Subset 2: Mark the columns that do not have zero elements.

Table 4 represents the resulting reduced matrix that contains at least one zero element in
each row and in each column.

Table 4
Contractor
1 2 3 4
1 2 0 1 3
Subassembly 2 0 1 4 1
3 3 2 0 0
4 1 3 0 1
Initial basic feasible
solution

11
Step III

Check if Optimal Assignment can be made in the Current Solution or not.

Basis for making this check is that if the minimum number of lines crossing all zeros is
less than n (in our example n = 4), then an optimal assignment can be made in the current
solution.

Subset 1: Examine rows successively until a row with exactly one unmarked zero is found.
Make a square ( ) around this zero, indicating that an assignment will be made there.

Mark (X) all other zeros in the same column showing that they cannot be used for making
other assignments.

Now proceed in this manner until all rows have been examined.

This is shown in the matrix (Table 5) below.

Table 5
Contractor
1 2 3 4
1 2 0 1 3
Subassembly 2 0 1 4 1
3 3 2 0 0
4 1 3 0 2

Subset 2: Next examine columns for single unmarked zeros, making them ( ) and also
marking (x) any other zeros in their rows.

Repeat the process till no unmarked zero is left in the cost matrix.

Subset 3: Repeat sub-steps 1 and 2 successively till one of the two things occurs:

a) There may be no row and column without assignment i.e., there is one assignment in
each row and in each column. The minimum number of lines crossing all zeros will
be equal to “n”; and
b) There may be some row and/or column without assignment. The minimum
numbers of lines crossing all zeros have to be obtained in this case.

In our case, subsets 2 and 3 are not necessary since there is no column left unmarked.

Thus, minimum total cost is

= KSHs. {(13x1) + (11x1) + (11x1) + (14x1)}x 1000 = KSHs. 49,000

12
and the optimal assignments policy is

1) subassembly 1- Contractor 2;
2) subassembly 2- Contractor 1;
3) subassembly 3- Contractor 4;
4) subassembly 4- Contractor 3;

The minimum cost of KSHs. 49,000 can also be determined by summing up all the elements
that were subtracted during the solution procedure i.e., {[13+11+10+] + 1} x 1000 = 49,000

Example 2:

A work shop contains four persons available for work on the four jobs. Only one person can
work on any one job. The following table shows the cost of assigning each person to each
job. The objective is to assign person to jobs such that the total assignment cost is a
minimum.

Jobs
1 2 3 4
A 20 25 22 28
Person B 15 18 23 17
C 19 17 21 24
D 25 23 24 24

Solution

As per the Hungarian Method

Step 1: The cost Table

Jobs
1 2 3 4
A 20 25 22 28
Person B 15 18 23 17
C 19 17 21 24
D 25 23 24 24

Step 2: Find the First Reduced Cost Table

Jobs
1 2 3 4
A 0 5 2 8
Person B 0 3 8 2
C 2 0 4 7
D 2 0 1 1

13
Step 3: Find the Second Reduced Cost Table

Jobs
1 2 3 4
A 0 5 1 7
Person B 0 3 7 1
C 2 0 3 6
D 2 0 0 0

Step 4: Determine an Assignment

The resultant table is shown below:

Jobs
1 2 3 4
A 0 5 1 7
Person B 0 3 7 1
C 2 0 3 6
D 2 0 0 0

Step 5:

The solution obtained in Step 4 is not optimal.

Step 6:

Cover all the zeros of the table shown in the Step 4 with three lines (since already we made
three assignments).

This is shown in the table given below:

Jobs
1 2 3 4
A 0 5 1 7
Person B 0 3 7 1
C 2 0 3 6
D 2 0 0 0

14
Step 7:

Develop the new revised table.

Which is shown below:

Jobs
1 2 3 4
A 0 5 1 7
Person B 0 2 7 0
C 2 0 4 6
D 1 0 1 0

Step 8:

Now, go to Step 4 and repeat the procedure until we arrive at an optimal solution
(assignment).

Step 9:

Determine an assignment

This is shown in the following table

Jobs
1 2 3 4
A 0 4 0 6
Person B 0 2 6 0
C 3 0 3 6
D 3 0 0 0

The total cost of assignment is: 78 that is A1 + B4 + C2 + D3

20 + 17 + 17 + 24 = 78

Variations of the Assignment Problem

1) Non-Square Matrix (Unbalanced Assignment Problem). Since the Hungarian

method of solution requires a square matrix, fictitious or jobs may be added and zero
costs be assigned to the corresponding cells of the matrix. These cells are then treated
the same way as the real cost cells during the solution procedure.
2) Maximization Problem. This has to be changed to minimization before the
Hungarian method may be applied. This transformation may be done in either of the
following two ways: -

a) By subtracting all the elements from the largest elements of the matrix; and
b) By multiplying the matrix element by -1.

15
 The Hungarian method can then be applied to this equivalent minimization problem to
obtain the optimal solution.

3) Restriction on Assignments. Such problems can be solved by assigning a very heavy

cost (infinite cost) i.e., ∞ or m to the corresponding cell. Such a job will then be
automatically excluded from further consideration (making assignments).
4) Alternative Optimal Solution. In such case, there will be alternative optimal solution
with the same cost. Alternative optimal solutions offer a great flexibility to the
management since it can select the one which is most suitable to its requirement.

Unbalanced Assignment Problem

Such kind of assignment problem is called as balanced assignment problem.

Suppose if the number of person is different from the number of jobs then the assignment
problem is called as unbalanced.

If the number of jobs is less than the number of persons, some of them can’t be assigned any
job. So that we have to introduce one or more dummy jobs of zero duration to make the
unbalanced assignment problem into balanced assignment problem.

This balanced assignment problem can be solved by using the Hungarian Method. The
persons to whom the dummy jobs are assigned are left out of assignment.

Similarly, if the number of persons is less than number of jobs then we have to introduce
one or more dummy persons with zero duration to modify the unbalanced into balanced
and then the problem is solved using the Hungarian Method. Here the jobs assigned to
the dummy persons are left out.

Non- Square Matrix

Example 2:

Solve the following unbalanced assignment problem of minimizing the total time for
performing all the jobs.

Jobs
1 2 3 4 5
A 5 2 4 2 5
B 2 4 7 6 6
C 6 7 5 8 7
Workers
D 5 2 3 3 4
E 8 3 7 8 6
F 3 6 3 5 7

16
Solution:

The revised assignment problem is as follows:

Jobs
1 2 3 4 5 6
A 5 2 4 2 5 0
B 2 4 7 6 6 0
C 6 7 5 8 7 0
Workers
D 5 2 3 3 4 0
E 8 3 7 8 6 0
F 3 6 3 5 7 0

Now the problem becomes balanced one since the number of workers is equal to the
number jobs.

So that the problem can be solved using Hungarian Method.

Step 1: The cost Table

Jobs
1 2 3 4 5 6
A 5 2 4 2 5 0
B 2 4 7 6 6 0
C 6 7 5 8 7 0
Workers
D 5 2 3 3 4 0
E 8 3 7 8 6 0
F 3 6 3 5 7 0

Step 2: Find the First Reduced (by row) Cost Table

Jobs
1 2 3 4 5 6
A 5 2 4 2 5 0
B 2 4 7 6 6 0
C 6 7 5 8 7 0
Workers
D 5 2 3 3 4 0
E 8 3 7 8 6 0
F 3 6 3 5 7 0

Step 3: Find the Second Reduced (by column) Cost Table

Jobs
1 2 3 4 5 6
A 3 0 1 0 1 0
B 0 2 4 4 2 0
C 3 5 2 6 3 0
Workers
D 2 0 0 1 0 0
E 6 1 4 6 2 0
F 1 4 0 3 3 0

17
Step 4: Determine an Assignment

By using the Hungarian Method the assignment is made as follows:

Check row C has one zero. Assign C6 and mark X the zeros in the columns. Row B has
one zero. Assign B1 and mark X the zeros in the columns (non in this column). Row F has
one zero. Assign F3 and mark X the zeros in the columns D3. Column 4 has one zero box
4A and mark x A2. Column 5 has one zero box D5 and mark x D2.

Jobs
1 2 3 4 5 6
A 3 0 1 0 1 0
B 0 2 4 4 2 0
C 3 5 2 6 3 0
Workers
D 2 0 0 1 0 0
E 6 1 4 6 2 0
F 1 4 0 3 3 0

Step 5:

The solution obtained in Step 4 is not optimal. Because we were able to make five
assignments when six were required.

Step 6:

Cover all the zeros of the table shown in the Step 4 with five lines (since already we made
five assignments).

Check row E since it has no assignment. Note that row B has a zero in column 6, therefore
check column 6.

Then we check row C since it has a zero in column 6. Note that no other rows and columns
are checked.

Now we may draw five lines through unchecked rows (row A, B, D and F) and the checked
column (column 6). This is shown in the table given below:

Jobs
1 2 3 4 5 6
A 3 0 1 0 1 0
B 0 2 4 4 2 0
C 3 4 1 5 2 0
Workers
D 2 0 0 1 0 0
E 6 1 4 6 2 0
F 1 4 0 3 3 0

18
Step 7:

Examine those elements that are not covered by a line in the table given in Step 6.

Take the smallest element in this case the smallest element is 1.

Subtract this smallest element from the uncovered cells and add 1 to elements (A6, B6, D6
and F6) that lie at the intersection of two lines.

Finally, we get the new revised cost table, which is shown below:

Jobs
1 2 3 4 5 6
A 3 0 1 0 1 0
B 0 2 4 4 2 0
C 2 3 0 4 1 1
Workers
D 2 0 0 1 0 0
E 5 0 3 5 1 0
F 1 4 0 3 3 0

Step 8:

Now, go to Step 4 and repeat the procedure until we arrive at an optimal solution
(assignment).

Step 9:

Determine an assignment

Jobs
1 2 3 4 5 6
A 3 0 1 0 1 1
B 0 2 4 4 2 1
C 2 3 0 4 1 0
Workers
D 3 0 0 1 0 1
E 5 0 3 5 1 0
F 1 4 0 3 3 1

Since the number of assignments equal to the number of rows (columns), the assignment
shown in the above table is optimal.

Thus, the: -

1) worker A is assigned to Job 4;

2) worker B is assigned to job 1;
3) worker C is assigned to job 6;
4) worker D is assigned to job 5;
5) worker E is assigned to job 2; and
6) worker F is assigned to job 3.

Since the Job 6 is dummy so that worker C can’t be assigned.

19
The total minimum time is: 14

That is A4 + B1 + D5 + E2 + F3

2 + 2 + 4 + 3 + 3 = 14

Example 3:

A marketing company wants to assign three employees viz. A, B, and C to four offices
located at W, X, Y and Z respectively. The assignment cost for this purpose is given in
following table.

W X Y Z
A 160 220 240 200
Employees B 100 320 260 160
C 100 200 460 250

Since the problem has fewer employees than offices so that we have introduce a dummy
employee with zero cost of assignment.

The revised problem is as follows:

W X Y Z
A 160 220 240 200
Employees B 100 320 260 160
C 100 200 460 250
D 0 0 0 0

Now the problem becomes balanced.

This can be solved by using Hungarian Method as in the case of Example 2.

Infeasible Assignment Problem

Sometimes it is possible a particular person is incapable of performing certain job or a

specific job can’t be performed on a particular machine. In this case the solution of the
problem takes into account of these restrictions so that the infeasible assignment can be
avoided.

The infeasible assignment can be avoided by assigning a very high cost to the cells where
assignments are restricted or prohibited.

20
Example 4:

A computer centre has five jobs to be done and has five computer machines to perform them.
The cost of processing of each job on any machine is shown in the table below.

Jobs
1 2 3 4 5
Computer 1 70 30 X 60 30
Machine 2 X 70 50 30 30
3 60 X 50 70 60
4 60 70 20 40 X
5 30 30 40 X 70

These have been shown by X in the cost table.

The objective here is to assign the jobs to the available machines so as to minimize the total
cost without violating the restrictions as mentioned above.

Solution

Step 1: The cost Table

Because certain jobs cannot be done on certain machines we assign a high cost say for
example 500 to these cells i.e. cells with X and modify the cost table.

The revised assignment problem is as follows:

Jobs
1 2 3 4 5
Computer 1 70 30 500 60 30
Machine 2 500 70 50 30 30
3 60 500 50 70 60
4 60 70 20 40 500
5 30 30 40 500 70

Now we can solve this problem using Hungarian Method.

Step 2: Find the First Reduced (by row) Cost Table

Jobs
1 2 3 4 5
Computer 1 40 0 470 30 0
Machine 2 470 40 20 0 0
3 10 450 0 20 10
4 40 50 0 20 480
5 0 0 10 470 40

21
Step 3: Find the Second Reduced (by column) Cost Table

Jobs
1 2 3 4 5
Computer 1 40 0 470 30 0
Machine 2 470 40 20 0 0
3 10 450 0 20 10
4 40 50 0 20 480
5 0 0 10 470 40

Step 4: Determine an Assignment

Jobs
1 2 3 4 5
Computer 1 40 0 470 30 0
Machine 2 470 40 20 0 0
3 10 450 0 20 10
4 40 50 0 20 480
5 0 0 10 470 40

Step 5:

The solution obtained in Step 4 is not optimal. Because we were able to make four
assignments when five were required.

Step 6:

Cover all the zeros of the table shown in the Step 4 with four lines (since already we made
four assignments).

Jobs
1 2 3 4 5
Computer 1 40 0 470 30 0
Machine 2 470 40 20 0 0
3 10 450 0 20 10
4 40 50 0 20 480
5 0 0 10 470 40

Step 7:

Develop the new revised table.

Examine those elements that are not covered by a line in the table given in Step 6.

Take the smallest element in this case the smallest element is 20.

22
Finally, we get the new revised cost table, which is shown below:

Jobs
1 2 3 4 5
Computer 1 40 0 470 50 0
Machine 2 450 20 0 0 0
3 10 450 0 20 10
4 20 30 0 20 460
5 0 0 10 470 40

Step 8:

Now, go to Step 4 and repeat the procedure until we arrive at an optimal solution
(assignment).

Step 9:

Determine an assignment

Jobs

1 2 3 4 5
Computer 1 40 0 470 50 0
Machine 2 450 20 0 0 0
3 0 450 0 20 10
4 20 30 0 20 460
5 0 0 10 470 40

Since the number of assignments equal to the number of rows (columns), the assignment
shown in the above table is optimal.

Thus, the: -

1) Machine 1 is assigned to Job 5;

2) Machine 2 is assigned to job 4;
3) Machine 3 is assigned to job 1;
4) Machine 4 is assigned to job 3; and
5) Machine 5 is assigned to job 2.

The minimum assignment cost is: 30 + 30 + 60 + 20 + 30 = 170

23
Maximization in an Assignment Problem

There are situations where certain facilities have to be assigned to a number of jobs so as to
maximize the overall performance of the assignment. In such cases the problem can be
converted into a minimization problem and can be solved by using Hungarian Method.

Here the conversion of maximization problem into a minimization can be done by

subtracting all the elements of the cost table from the highest value of that table.

Example 5:

Consider the problem of five different machines can do any of the required five jobs with
different profits resulting from each assignment as illustrated below:

Machine
1 2 3 4 5
1 40 47 50 38 50
Jobs 2 50 34 37 31 46
3 50 42 43 40 45
4 35 48 50 46 46
5 38 72 51 51 49

Find out the maximum profit through optimal assignment.

Solution

This is a maximization problem, so that first we have to find out the highest value in the
table and subtract all the values from the highest value. In this case the highest value is 72.

The new revised table is given below:

Machine
1 2 3 4 5
1 32 35 22 34 22
Jobs 2 22 38 35 41 26
3 22 30 29 32 27
4 37 24 22 26 26
5 34 0 21 21 23

This can be solved by using the Hungarian Method.

24