<br>

UNIT-3
HCHAPTER

4.1
Assignment Problems

Introduction
4
are confronting the conflicting need for
In the world of trade, business organizations
antimal utilization of their limited resources
among competing activities. When the
information available on resources and relationship between variables is
known we can use
LP very reliably. The course of action chosen will invariably lead
to optimal or nearly optimal
LP are:
results. The problems which gained much importance under

Transportation problerns
Assignment problems
in which the
The assignment problem is a special case of transportation problem
objective is to assign a number of origins to equal number of destinations
at minimum cost
(or maximum profit). It involves assignment of people to projects, jobs
to machines, workers
to jobs and teachers to classes etc., while minimizing the total assignment costs.

One of the important characteristics of assignment problem is that only

one job (or
worker) is assigned to one machine (or project). Hence the number of
sources are equal the
number of destinations and each requirement and capacity value is exactly
one unit.
Although assignment problem can be solved using the techniques of Linear
rogramming or the transportation method, the assignment method is much faster and
eficient. This method was developed by Harold Kuhn, a Hungarian mathematician and is
herefore known as the Hungarian method of assignment problem. In order
to use this
method, one needs to know only the cost of making all the possible assignments.

Each assignment problem has a matrix (table) associated with it. Normally, the objects
(or people) one wishes to assign are expressed in rows, whereas the columns represent the
lasks (or things) assigned to
then. The numbers in the table would then be the costsa
associated with each particular assignment. It may be noted that the assignment problem is
variation of
transportation problem withtwo characteristics:
1. The cost matrix is a square matrix, and
2.
Ihe optimum solution for the problem is such that there will be only
one
assignment in a row or column of the cost matrix.
<br>

184 Operations Research

4.1.1 Definition
An assignment problem is a special type of lincar programming problem where the
objective is to rninimize the cost or time of completing a number of jobs by a number of
persons.

4.1.2 Solution Methods

The most popular methods of solving assignment problems are:
Simplex method
Transportation method
Hungarian method
Simplex method and Transportation method have already been discussed in the
previous chapters.
To illustrate the nature of assignment problem, let us consider that, there are
n' jobs to be performed and "n" persons are available for doing the jobs. Assume that cach
person can do each job at a time, though with varying degree of efficiency. Suppose, C be
the cost (payment) if the h person is assigned the th job, then the problem is to ind an
assignment (which job should be assigned to which person) so that the total cost lor
performing all jobs is minimun. The assignment can be stated in the form of n xn cost
matrix of real numbers as shown in the table 4.1.
Jobs
1
3 n
1

Persons i

Table 4. I Cost-matrix

4.2 Hungarian Method for Solving Assignment Problem

There are various ways of solving assignment problems. It can be formulated as a lincar
program, and the Simplex method can be used to solve it. In addition, since it can be
formulatcd as a network problem, the network simplex method may solve it quickly.
However, sometimes the Simplex method is inefficient for assignment problems
(particularly problems with a high degree of degeneracy). The Hungarian Algorithm
developed by Harold Kuhn has been used with a good deal of success on these problems and
s summarized as follows.
<br>

Assignment Problems 185

Step 1: Ifthe problem is of maximization type, convert it into minimization type and if it is
minimization type, retain as it is.
To convert maximization to minimization, choose the maximum element in
the entire matrix and subtract all the elements from it. Alternatively you can
place a negative sign before each element of the profit matrix, so that it
becomes a cost-matrix.
Unless otherwise stated, the problem is always assumed to be of minimization
type.
Step 2: Determine the cost table from the given problern.
Ifthe number of sourccs is equal to number of destinations (square matrix of
order n), go to step 4.
If the number of sources is not equal to the number of destinations, go to
step3.
Step 3: Add a dummy source or dummy destination, so that the cost table becomes a
square matrix. The cost entries of the dummy source/destinations are always zero.
Step 4: Locate the smallest element in cach row of the given cost matrix and then subtract
the same from each element of the row.
Step 5: In the reduced matrix obtained in the step 4, locate the smallest elernent of each
column and then subtract the same from each element of that column. Each
column and row now have at least one zero.
Step 6: In the modified matrix obtained in the step 5, search for the optimal assignment as
follows:
Draw the least number of horizontal and vertical lines (or shade rows and
columns) so as to cover all zeros. If the number of lines drawn (N) is equal to
n, the order of matrix, then an optirmum assignment has been obtained. Le.
N=n where N is the number of lines drawn.
IfN<n procced to Step 7.
Step 7: Determine the smallest cost cell among the uncrossed cells. Subtract this cost from
all uncrossed cells and add the same to all those cells lying at the intersection of
horizontal and vertical lines.
Step 8: Repeat the steps 6 and 7 until N=n.
Step 9: Choose the row/column which has only one zero. Allocate by enclosing the zero in
a square [0] and cancel out (-t) all other zeros in that row and column. Continue
till allallocations are made.
If a row and/or column has two or more zeros and one cannot be chosen by
inspection then assign arbitrarily any one of these zeros and cross out all other
zeros of that row / column.
<br>

186 Operations Research

Step 10: Finally there exactly one enclosed zero in each row and column of the e
will be
matrix. The assignment schedule corresponding to these zeros is the opimum
(maximal) assignment.

4.3 Simple Illustrations

Example 4.1
Solve the following assignment problem.

Jo bs
II II IV Row min

A 42 35 28 21 P,= 21

B 30 25 20 15 P,= 15
Machines
C 30 25 20 15 Pg= 15

D 24 20 16 12 12
P=

Solution
The given problem is minimization type and it is also a square matrix
Applying step (4) Applying step (5)
III IV

A 21 7 II IV
14

A 9 6 3 0
B 15 10 5

B 3 2
C 15 10 5 0

C 3 2
D 12 4

Colurmn q= 12 q,= 8 4;= 49,= 0 D 0

min