Page 157 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research Dilfraz Singh, Lovely Professional University

Notes Unit 8: Assignment Problem – Unbalanced

CONTENTS
Objectives
Introduction

8.1 Variations of the Assignment Problem
8.2 Multiple Optimal Solutions
8.3 Maximization Assignment Problems

8.4 Unbalanced Assignment Problem
8.5 Routing Problems/Travelling Salesman Problems
8.5.1 Steps to Resolve Looping in Travelling Salesman Problem
8.6 Summary
8.7 Keywords

8.8 Review Questions
8.9 Further Readings

Objectives

After studying this unit, you will be able to:

 Know about variations of the assignment problem
 Learn how to solve an unbalanced assignment problem, profit maximization problem etc.
 Understand how to solve a travelling salesman problem

Introduction

The basic objective of an assignment problem is to assign n number of resources to n number of
activities so as to minimize the total cost or to maximize the total profit of allocation in such a
way that the measure of effectiveness is optimized.

The problem of assignment arises because available resources such as men, machines, etc., have
varying degree of efficiency for performing different activities such as job. Therefore cost, profit
or time for performing the different activities is different. Hence the problem is, how should the
assignments be made so as to optimize (maximize or minimize) the given objective.
The assignment model can be applied in many decision-making processes like determining
optimum processing time in machine operators and jobs, effectiveness of teachers and subjects,
designing of good plant layout, etc. This technique is found suitable for routing traveling
salesmen to minimize the total traveling cost, or to maximize the sales.
In this unit you will learn how to solve special types of assignment problems such as unbalanced
problems, travelling salesman problem etc.

152 LOVELY PROFESSIONAL UNIVERSITY