CHAPTE FOUR

ASSIGNMENT PROBLEMS
Definition and Objective

 The Assignment Problem(AP) refers to the class of

LPPs that involves determining the most efficient
assignment of;
 people to projects,
 salespeople to territories,
 contracts to bidders ,
 jobs to machines, and so on.
 The objective is to assign a number of resources to
an equal number of activities so as to;
 minimize total costs or total time or
 maximize total profit of allocation.
Cont…

 The problem of assignment arises because available

resources such as men, machines, etc have varying
degrees of efficiency for performing different
activities such as job.
 Therefore, cost, profit or time of performing the
different activities is different.
 The AP works under the condition that the number of
origins is equal to the number of destinations.
 m=n
 Hence assignment is made on the basis of 1:1.
Assumptions

1. Number of jobs is equal to the number of machines or

persons.
2. Each man or machine is loaded with one and only one
job.
3. Each man or machine is independently capable of
handling any of the job being presented.
4. Loading criteria must be clearly specified such as;
 “minimizing operating time” or
 “maximizing profit” ,or
 “minimizing production cost” or
 “minimizing throughout (production cycle) time ” etc.
Remark

 TheAP is considered as a special TP in which

the supply at each source and the demand at
each destination are always one unit.
 Since the supply and demand are always equal
to one unit in each row and column, there is no
need to write them in the assignment table.
Hungarian Assignment Method(HAM)

 Developed by Hungarian mathematician D.Konig

 It works on the principle of reducing the given cost
matrix (the principle of matrix reduction) to a matrix of
opportunity costs.
 If we can reduce the cost matrix to the extent of
having at least one zero in each row and column, then
it will be possible to make optimal assignments.
Cont…

 Opportunity costs show the relative penalties

associated with assigning resource to an activity as
opposed to making the best or least-cost
assignment.
Steps in Solving Assignment Problems

Step.1. Develop the cost table from the given problem

 If the number of rows does not equal the number of
columns and vice versa, then a dummy row or dummy
column must be added. The assignment costs for
dummy cells are always zero.
Step 2.Find the opportunity cost table
 The transformation of the cost matrix to what is
termed as a total-opportunity cost matrix.
 It involves two operations
Cont…

a. Perform row operation

i.e. Locate the smallest element in each row of the given
cost table and then subtract that from each element
of that row
b. Perform column operation
 In the reduced matrix obtained from 2(a) ,locate the
smallest element in each column and then subtract
that from each element of that column. Notice that
each row and column now have at least one zero
value.
Cont…

Step 3.Test for an optimal assignment

The procedure is:
a. Draw the minimum number of Horizontal and /or
Vertical lines necessary to cover all zeros costs.
 Draw the lines by trial and error but always try to
cover two or more zeros with one line.
b. Count the number of the lines
 If the number of lines equals either the number of
rows or columns in the table, an optimal assignment
can be made.
 If the number of lines is less than the number of rows

or columns, an improvement is possible (we proceed

to step 4).
Cont…

Step 4. Improve the present opportunity cost table

(matrix)
This is done by the following operations:
a. Find the smallest entry in the uncovered cells (cells with
no lines through them) and subtract it from all entries
in the uncovered cells.
b. Add the same smallest entry to those cells in which the
lines intersect (cells with two lines them)
c. Cells with one line through them are transferred (i.e.
unchanged to the improved table).
Cont…

 In those problems where the first improvement does

not yield an optimal solution, we keep on improving
the solution by repeating step 4 until an optimal
solution is achieved.
Step 5: Make an optimal assignment
 An optimal assignment should be made to cells with a
zero entry, maintaining the one-to-one requirement
 Note that multiple optimal solutions are possible.
Cont…

Example:
 1. A computer center has three programmers. The
center wants three application programs to be
developed. The head of the computer center, after
studying carefully the programs to be developed,
estimate the computer time in minutes required by the
experts for the application programs as follows:
 Assign the programmers to the programs in such a

way that the total computer time is minimum.

Cont…

P rogram m ers Programs (estimated time in

minutes)
A B C
1 120 100 80

2 80 90 110

3 110 140 120

Cont…
The Atlantic Coast Conference has four basketball games on a
particular night. The conference office wants to assign four
team officials to the four games in a way that will minimize
the total distance traveled by the officials. The distances in
miles for each team of officials to each game location are
shown in the following table.
Game Sites
Officials
Chicago Atlanta Durham Clemson
A 210 90 180 160
B 100 70 130 200
C 175 105 140 170
D 80 65 105 120
Special Cases in the Assignment
Problems
A. Multiple Optimal Solutions
 While making an assignment in the reduced
assignment matrix, it is possible to have two or
more ways to strike off a number of zeros.
 Such situation indicates multiple optimal solutions
with the same optimal value of objective function. In
such cases the more suitable solution may be
considered by the decision-maker.
Cont…

B. Maximization case in assignment problems

 There may arise situations when the assignment problem calls
for maximization of profit, revenue, etc as the objective
function.
 Such problem may be solved by converting the given
maximization problem into a minimization problem by the
following procedure:
i. Find the largest profit coefficient in the entire.
ii. Subtract each entry in the original table from the largest profit
coefficient.
 The transformed assignment problem so obtained can be solved by using
the Hungarian method.
Cont…

C. Unbalanced Assignment problem

 The Hungarian method of assignment requires that the

number of columns and rows in the assignment matrix

be equal. However, when the given cost matrix is not a
square matrix, the assignment problem is called an
unbalanced problem. In such cases a dummy row(s) or
column(s) are added in the matrix (with zeros as the
cost elements) to make it a square matrix. After
making the given cost matrix a square matrix, the
Hungarian method may be used to solve the problem.
Cont…

D. Restrictions on Assignments
 In certain instances, it may happen that a particular
match or pairing may be either undesirable or
otherwise unacceptable. For example, an employee
may not have the skills necessary to perform a
particular job or a machine may not be equipped to
handle a particular operation. In such cases, the cost
of performing that particular activity by a particular
resource is considered to be very large (written as M
or ∞ ) so as to prohibit the entry of this pair of
employee-job into the final solution.
Cont…

 When such a restriction is present, a letter

(M) is often placed in the table in the position
that would represent a paring. Analysis is
performed as usual except the M is ignored
throughout the analysis. That is, M is not used
in any reductions, nor is any value added to
it or subtracted from it during the course of
the analysis.