Posted On :

Assignment problems are special case of linear programming problems. The task is to assign ‘i’ resources (i= 1, 2, 3, 4 …m) to ‘j’ tasks (j= 1, 2, 3, 4…n) in such a way that the total cost of performing the tasks is lowest.

Classic examples, like assigning the machine operator to the most suitable job, assigning the set of project managers to most suitable projects and assigning the subject to suitable faculty typically fall under the category of assignment problems.

In the machine operator- job assignment, the objective of the firm may be reducing the overall time taken or reducing the wastages by appropriately assigning the operators to the suitable job; in assigning the project managers to suitable projects, the firm may have an objective of reducing the overall lead time, or cost of operation; in the example of subject-faculty allocation, the university education administrator may be interested in reducing the total number of ‘failures’ in a class.

Thus, a typical assignment problem falls under the category of minimization model; of course, maximization models can also be solved by the Assignment algorithms after suitable modifications. The mathematical expression / formulation of the assignment problem shall be written as:

Thus, the assignment problems are zero-one problems, where the decision variables Xij take the value of either zero or one only. The assignment problems can also be consider as special case of ‘Transportation Models’, where, ‘m= n’; that is the number of sources is equal to number of destinations and ai=1 and bj=1 for all ‘i’ and ‘j’ values.

Even though the assignment problems are considered as special case of ‘transportation models’ or ‘linear programming’ models, it is seldom solved by these methods. We use a different algorithm, more efficient algorithm, which is evolved by a group of ‘Hungary’ mathematicians and named after them as ‘Hungarian Algorithm’.

1. The number of assignees and the number of tasks are equal in number.

2. Each assignee is to be assigned to exactly one task.

3. Each task is to be performed by exactly one assignee.

4. There is a cost Cij associated with assignee-i (i= 1, 2, 3 … n) performing a task j (j= 1, 2, 3 … n). This cost can also be estimated with moderate degree of precision always.

Tags : Operations Management - Transportation / Assignment & Inventory Management

Last 30 days 1289 views