User:Pkkapoor/Assignment Problem-an introduction

Introduction to assignment problem

In real life, we are faced with the problem of allocating different personnel/ workers to different jobs. Not everyone has the same ability to perform a given job. Different persons have different abilities to execute the same task and these different capabilities are expressed in terms of cost/profit/time involved in executing a given job. Therefore, we have to decide:How to assign different workers to different jobs” so that, cost of performing such job is minimized. And such assignment problems and methods of their solutions is the subject matter of this chapter.

Objectives Main objective of this chapter is to equip the learner to deal with following situation: a) Assignments of different jobs to different workers/different machines on one to one basis where time or cost of performing such job is given. b) Assignment of different personal to different location or service station with the objective to maximize sales/profit/consumer reaches. c) To deal with a situation where number of jobs to be assigned do not match with number of machines/workers. d) To deal with a situation where some jobs can not be assigned to specific machines/workers.

INTRODUCTION: The assignment problem is a special type of linear programming problem. We know that linear programming is an allocation technique to optimize a given objective. In linear programming we decide how to allocate limited resources over different activities so that, we maximize the profits or minimized the cost.

Similarly in assignment problem, assignees are being assigned to perform different task. For example, the assignees can be employees who need to be given work assignments, is a common application of assignment problem. However assignees need not be people. They could be machines, vehicle, plants, time slots etc. to be assigned different task.

ASSUMPTIONS OF AN ASSIGNMENT PROBLEM:

An assignment problem must satisfy the following assumptions: 1. The number of assignees and number of task are the same (this number is denoted by n). 2. Each assignee is to be assigned to perform exactly one task. 3. Each task is to be performed by exactly one assignee. 4. There is a cost or profit associated with assignees performing different task. 5. The objective is to determine how all n assignment should be made to optimize the given pay offs which are expressed in terms of cost, time spent, distance, revenue earned, production obtained etc.

AREAS OF USE:

There exist numbers of areas where assignment problem can be used. In fact, whenever we have to make an assignment on one to one basis assignment technique is used. For example, assignments of different jobs to different workers, assignments of different machines to different workers, assignments of different salesmen to different sales centre/location, assignments of different products to different machines, assigning different rooms to different managers.

TERMINOLOGY USED:

1. Assignment problem: it refers to the problems relating allocation or assignment of resources to different activities on one to one basis.

2. Assignment table: it is a table which shows the data relating to the problems in certain rows and columns with their respective pay offs.

3. Balanced/ standard assignment problem: it refers to an assignment problem where numbers of rows are equal to number of columns. Consider a machine shop with ‘n’ jobs and ‘m’ machines, where number of jobs are equal to the number of machines i.e. n=m. it is known as balanced assignment problem. 4. Unbalanced/ non-standard assignment problem: it refers to an assignment problem where numbers of rows are not equal to number of columns. Consider a machine shop with ‘n’ jobs and ‘m’ machines, where number of jobs is not equal to the number of machines i.e. ‘n’ is not equal to ‘m’. It is known as unbalanced assignment problem. 5. Feasible solution: it refers to n! Assignments on one to one basis for ‘n’ jobs and ‘n’ worker problem. In Hungarian assignment Method it refers to reduced cost table which consist of at least one zero in each column/row. 6. Optimum feasible solution: optimum feasible solution is that where maximize or minimize the cost of an assignment the profit/sales.