Assignment Problems – Introduction
Like
transportation problem, assignment problem is also another type of special
linear programming problem.
There are many
situations where the assignment of people or machines and so on, may be called
for. Assignment of workers to different machines, clerks to various check-out
counters, salesmen to different sales areas, service crews to different
districts, are typical examples of these situations. The assignment is a
problem because people possess varying abilities for performing different jobs
and, therefore, the costs of performing the jobs by different people are
different. Obviously, if all persons could do a job in the same time (i.e. at
the same speed) or at the same cost then it would not matter who of them is
assigned the job. Thus, in an assignment problem, the question is how should
the assignments be made in order that the total cost involved is minimised (or
the total value is maximised when pay-offs are given in terms of, say, sales or
profits and so on).
There are four
methods of solving an assignment problem:
(a)
Complete
Enumeration Method;
(b)
Transportation
Method;
(c)
Simplex
Method; and
(d)
Hungarian
Assignment Method (HAM).
Assignment Problems – Hungarian Assignment
Method (HAM)
It is one of
the four methods of solving an assignment problem. It is specially designed to
handle the assignment problems in an efficient way. This method is based on the
concept of opportunity cost. For a typical balanced assignment problem
involving a certain number of persons and an equal number of jobs, and with an objective function
of the minimisation type, the steps for applying the method are as
follows:
Step 1: Row
Operation
Locate the smallest cost element in each row of the
cost table. Now subtract this smallest element from each element in that row.
As a result, there shall be at least one zero in each row of this new table,
called the First Reduced Cost Table.
Step 2: Column
Operation
Locate the smallest cost element in each column of the
reduced cost table. Now subtract this smallest element from each element in
that column. As a consequence of this action, there would be at least one zero
in each of the rows and columns of this Second Reduced
Cost Table.
Step 3: Line
Drawing Operation (Optimality Test)
Draw the minimum number of horizontal and vertical
lines that are required to cover all the zero elements in the second reduced
cost table. If the number of lines drawn is equal to ‘n’ (the number of
rows/columns) the solution is optimal, and in this case Step 6 should be
followed next. But if the number of lines drawn is smaller than ‘n’, the
solution is not optimal, and in this case Step 4 should be followed next.
Step 4: Table
Operation
Select the smallest uncovered (i.e. uncovered by the
lines) cost element of the table. Subtract this element from all the uncovered
elements including the smallest element itself and add this element to each of
the elements located at the intersection of any two lines. The cost elements
through which only one line passes remain unaltered.
Step 5: Repeating
Operation
Repeat Steps 3 and 4 until an optimal solution is
obtained.
Step 6: Job
Assignment Operation
Once the optimal solution is obtained, job assignments
are made as indicated by the ‘zero’ elements. This is done as follows:
(a)
Locate
a row which contains only one ‘zero’ element. Assign the job corresponding to
this element to its corresponding person. Cross out the other zero(s), if any,
in the column corresponding to the element.
(b)
Repeat
(a) for each of such rows which contain only one ‘zero’ element.
(c)
Repeat
the same operations as in (a) and (b) in respect of each column containing only
one ‘zero’ element, crossing out the other zero(s), if any, in the row
corresponding to the element.
(d)
If
there is no more row or column with only a single ‘zero’ element left, then
select a row or column arbitrarily and choose one of the jobs (or persons) and
make the assignment. Now cross the remaining zeros in the corresponding column
and row in respect of which the assignment is made.
(e)
Repeat
steps (a) through (d) until all assignments are made.
(f)
Determine
the total cost with reference to the original cost table.
Assignment Problems – Some Special Cases
Unbalanced Assignment Problems
The Hungarian
method of solving an assignment problem requires that the number of columns
should be equal to the number of rows. When they are equal, the problem is a
balanced problem, and when not, it is called an unbalanced problem. Thus, where
there are 5 workers and 4 machines, or when there are 4 workers and 6 machines,
for instance, we have unbalanced situations in which one-to-one match is not
possible. In case the machines are in excess, the excess machine(s) would
remain idle and so is the case when workers are in excess – the number of
excess workers would not get an assignment.
In such
situations, dummy column(s) [If number of column(s) is less than number of
row(s)] or dummy row(s) [If number of row(s) is less than number of column(s)]
are inserted with zeros as the cost elements. For example, when the given cost
matrix is of the dimension 4 × 5, a dummy row would be included. In each column
in respect of this row, a ‘zero’ would be placed. After this operation of
introducing dummy columns/rows, the problem is solved in the usual manner.
Constrained Assignment Problems
It happens sometimes
that a worker cannot perform a certain job or is not to be assigned a particular
job. To cope with this situation, the cost of performing that job by such
person is taken to be extremely large (which is written as M). Then the
solution to the assignment problem proceeds in the usual manner as discussed
earlier. The effect of assigning prohibitive cost to such person-job
combinations is that they do not figure in the final solution.
Unique vs Multiple Optimal Solutions
In the process
of making assignments, it was stated earlier that we select a row/column with
only a single zero to make an assignment. However, a situation may arise
wherein the various rows and columns, where assignments are yet to be done,
have all multiple zeros. In such cases, we get multiple optimal solutions to
the given problem.
When a problem
has a unique optimal solution, it means that no other solution to the problem
exist which yields the same objective function value (cost, time, profit, etc.)
as the one obtained from the optimal solution derived. On the other hand, in a
problem with multiple optimal solutions, there exists more than one solution
which all is optimal and equally attractive.
Maximisation Problem
In some
situations, the assignment problem may call for maximisation of profit,
revenue, etc. as the objective. For example, we may be faced with the problem
of assignment of salesmen in different regions in which they can display
different qualities in making sales (reflected in amounts of sales executed by
them). Obviously, in such a situation, assignment would be made in such a way
that the total expected revenue is maximised.
For dealing
with a maximisation problem, we first change it into an equivalent minimisation
problem. This is achieved by subtracting each of the elements of the given
pay-off matrix from a constant (value) K. Thus, we may simply put a negative
sign before each of the elements/values of the given pay-off matrix (which is
equivalent to subtracting each value from zero). Usually, the largest of all
values in the given matrix is located and then each one of the values is
subtracted from it (the largest value is taken so as to avoid the appearance of
negative signs). Then the problem is solved the same way as a minimisation
problem is.
Travelling Salesman Problem
Objective of a travelling salesman
The objective
of a travelling salesman is to select the sequence in which the cities are
visited in such a way that his total travelling cost or time is minimised.
Conditions
There are two
conditions which have to be satisfied when solving a travelling salesman
problem and these are:
1)
No
city is to be visited twice before the tour of all the cities is completed; and
2)
Going
from city ‘i’ to ‘i’ is not permitted.
Steps for solving a
travelling salesman problem
STEP: 1
Treat the problem as a normal assignment problem and
solve it using the same usual procedure. If the optimal solution of the
assignment problem satisfies the above two conditions, then it is also an
optimal solution of the given travelling salesman problem. But, if the solution
to the assignment problem does not satisfy the above two conditions, follow the
following steps after solving the problem as a normal assignment problem to
find the optimal solution for the travelling salesman problem.
STEP: 2
Make assignment again, after treating the minimum
non-zero element of the previous table as ‘zero’, in the same way as assignment
is made for an optimal solution with the only exception that in this case one
assignment has to be made compulsorily to the minimum non-zero element treated
as zero.
STEP: 3
At this stage, if the number of assignments is less
than the size of the matrix, the solution is not optimal. Therefore, we have to
go back to the table where we got minimum number of lines covering all the
zeros exactly same as the size of the matrix. Here, we have to find the
smallest uncovered (i.e. uncovered by lines) cost element of the table and
subtract this element from all the uncovered elements and add to each of the
elements located at the intersections of any two lines. The cost elements
through which only one line passes will remain unaltered.
STEP: 4
Draw minimum number of lines in the modified table
covering all the zeros. If the number of lines is equal to the size of the
matrix, we have got a new optimal solution of the assignment problem to make
assignment again.
STEP: 5
After the assignments are made as above in Step: 4, if
the solution still does not satisfy the above two conditions, follow Step: 2,
but this time the minimum non-zero element to be treated as zero should not be
the earlier one, but rather it should be a new one without considering the
earlier one.
STEP: 6
At this stage, if the number of assignments is equal
to the size of the matrix and satisfies the above two conditions, the solution
is optimal for the travelling salesman problem, or otherwise follow Step: 2
again and this time also the minimum non-zero element to be treated as zero
should not be the earlier ones, but rather it should be a new one without
considering the earlier ones.
STEP: 7
At this stage, if the number of assignments is equal
to the size of the matrix and satisfies the above two conditions, the solution
is optimal for the travelling salesman problem. But, if the number of
assignments is less than the size of the matrix, the solution is not optimal
and in that case repeat Steps: 6 and 7 until the optimal solution for the
travelling salesman problem is obtained.