Assignment

62

ASSIGNMENT PROBLEMS

62.1 INTRODUCTION

Imagine, if in a printing press there is one machine and one operator is there to operate. How would you employ the worker? Your immediate answer will be, the available operator will operate the machine. Again suppose there are two machines in the press and two operators are engaged at different rates to operate them. Which operator should operate which machine for maximising profit? Similarly, if there are n machines available and n persons are engaged at different rates to operate them. Which operator should be assigned to which machine to ensure maximum efficiency? While answering the above questions we have to think about the interest of the press, so we have to find such an assignment by which the press gets maximum profit on minimum investment. Such problems are known as "assignment problems". In this lesson we will study such problems.

62.2 OBJECTIVES

After completion of this lesson you will be able to: formulate the assignment problem know Hungarian method to find proper assignment employ Hungarian method to find proper assignment

98::Mathematics

62.3 FORMULATION OF THE PROBLEM

Let there are n jobs and n persons are available with different skills. If the cost of doing jth work by ith person is c ij. Then the cost matrix is given in the table 1 below:

Jobs Persons 1 2 . . . . i . . . . n 1 c 11 c 21 . . . . c i1 . . . . c n1 2 c 12 c 22 . . . . c i2 . . . . c n2 3 c 13 c 23 . . . . c i3 . . . . ........ j ........ c 1j ........ c 2j ............ ............ ............ ............ ........ c ij ............. ............. ............. ........ c nj ........ n ........ c 1n ........ c 2n ............. ............. ............. ............. ........ c in ............ ............ ............. ........ c nn

Table 1

c n3

Now the problem is which work is to be assigned to whom so that the cost of completion of work will be minimum. Mathematically, we can express the problem as follows:...