Page 174 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 8: Assignment Problem – Unbalanced

Self Assessment Notes

State true or false:
7. For a salesman to visit n cities, there are (n+1)! ways to plan his tour.
8. An essential condition in a travelling salesman problem is that a salesman, who wishes to
travel through his territory visiting various cities, wishes to visit one city only once.
9. Mere Reduction is not the solution to travelling salesman problem; hence the solution is
to find an optimal route that could achieve the objective of the salesman.

8.6 Summary

 Assignment problem is one of the special cases of transportation problems. The goal of
the assignment problem is to minimize the cost or time of completing a number of jobs by
a number of persons. An important characteristic of the assignment problem is the number
of sources is equal to the number of destinations. It is explained in the following way.
1. Only one job is assigned to person.

2. Each person is assigned with exactly one job.
 Assignment problem can have various variants such as maximization assignment problem,
unbalanced assignment problem, multiple optimal solutions assignment problems and
travelling salesman problem.
 The assignment problem where the number of persons is not equal to the number of jobs
is called an unbalanced assignment problem. A dummy variable, either for a person or job
(as it required) is introduced with zero cost or time to make it a balanced one.
 While making an assignment in the reduced assignment matrix, it is possible to have two
or more ways to strike off a certain number or zeroes. Such a situation indicates multiple
optimal solutions with the same optimal value of objective function.
 In maximization assignment problems, the objective is to maximize profit, revenue, etc.
Such problems can be solved by converting the given maximization problem into a
minimization problem.
 In a travelling salesman problem is a special type of Assignment problem. In this given a
number of cities and the costs of travelling from one to the other, it is required to determine
the cheapest route that visits each city once and then returns to the initial city.

8.7 Keywords

An Infeasible Assignment: Infeasible assignment occurs when a person is incapable of doing
certain job or a specific job cannot be performed on a particular machine. These restrictions
should be taken in to account when finding the solutions for the assignment problem to avoid
infeasible assignment.
Balanced Assignment Problem: This is an assignment where the number of persons is equal to
the number of jobs.
Dummy Job/ Person: Dummy job or person is an imaginary job or person with zero cost or time
introduced in the unbalanced assignment problem to make it balanced one.

Unbalanced Assignment Problem: This is the case of assignment problem where the number of
persons is not equal to the number of jobs. A dummy variable, either for a person or job (as it
required) is introduced with zero cost or time to make it a balanced one.

LOVELY PROFESSIONAL UNIVERSITY 169