Assignment Problems:MATHEMATICAL FORMULATION OF THE PROBLEM

<< Transportation Problems:REVIEW QUESTIONS

Assignment Problems:SOLUTION OF AN ASSIGNMENT PROBLEM >>

Operations Research (MTH601)

201

Segment VI: Assignment Problems

Lectures 36- 37

201

Operations Research (MTH601)

202

INTRODUCTION

A special type of problem called the assignment problem is also an allocation problem. Here we have n

jobs to perform with n persons and the problem is how to distribute the jobs to the different persons involved.

Depending on the intrinsic capacity or merit or potential of the individual, he will be able to accomplish the task

in different times. Then the objective function in assigning the different jobs to different persons is to find the

optimal assignment that will minimize the total time taken to finish all the jobs by the individuals. For example,

we have four different building activities say, construction of a hotel, a theatre, a hospital and a multistoried

building and there are four contractors competing for these jobs. Each contractor has to be assigned only one

job. The allocation should aim to minimize the total time taken to complete the construction of all four activities

after assigning only one job to one individual. In fact there are (4!) permutations possible for allocating 4 jobs to

4 contractors. We have 24 possible ways and it is tiresome to list all the possible ways and find the best one. If

we have more jobs to be allocated, it is even difficult to list out the different permutations of allocations, then

what to speak of choosing the best combinations!

The problem may be stated formally as follows. Given an nxn array of real numbers representing the

individual return associated with assigning one item to one person. We have to find the best assignment so that

the total return is optimal.

Consider the following example, given below in the table 1

Table 1

Jobs

Men

In the above example, the elements of the matrix represent the times taken by A, B, C and D in accomplishing

the jobs 1, 2, 3 and we have to find which job is to be assigned to whom so that the total time taken will be

minimum. This is the objective function. Thus, this is also an allocation problem. A solution can be found to the

above problem by the algorithem used to solve the transportation problem of degenerate transportation problem.

In this way only 4 cells will be allocated. This leads to problem of degenerate transportation problem. There

should be (4 + 4 + 1) = 7 allocations in the initial basic feasible solution, but we have only 4 allocations. Hence

it is the degeneracy.

MATHEMATICAL FORMULATION OF THE PROBLEM

Considering the above example, we have four jobs and four persons. We want to allot one job to one

person so that the total time taken will be minimum. We shall formulate a mathematical model for the problem.

Let the decision variable xij be the assignment of ith job to jth person, and cij be the time taken for ith job

by the jth person.

z=∑

∑

cij

xij

The objective function is to minimize

i =1

j =1

202

Table of Contents: