Page 140 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 7: Assignment Problem – Balanced

as to which worker is to be assigned which job as to minimize the total job cost. The simple Notes
matrix would go like this:

Cost Matrix Job
1 2 J n
Individual 1 C11 C12 C1j C1n

2 C21 C22 C2j C2n
i Ci1 Ci2 Cij Cin
n Cn1 Cn2 Cnj Cnn

Although these types of problems could be solved by using transportation algorithm but a
more efficient method called the assignment algorithm is used to solve such typical problems.
th
th
C  indicates the cost of assigning i job to j individual
ij
th
th
X  (reference index) which indicates whether i job is assigned to j person or not.
ij
th
th
X = 1 if i job are assigned to j person.
ij
th
th
0 if i job are assigned to j person.
Consider the example:
There are 6 persons and 6 jobs to be allotted.
Let the assignment of jobs be as shown below:
1 2 3 4 5 6

1

2

3

4

5

6

The assignments are 1  2, 2  3, 3  1, 4  6, 5  4, 6  5.
Here, x = 0 since the first job is not allotted to first person.
11
X = 1 since the first job is allotted to second person.
12
Similarly, x = x = x = x = 0, and
21 22 32 34
x = x = x = x = 1
31 46 54 65
Sum of all jobs assigned to first person =  


LOVELY PROFESSIONAL UNIVERSITY 135