Assignment Problem

What is Assignment Problem ?

The assignment problem is a special type of linear programming problem where assignees are being assigned to perform tasks or Jobs. For example, the assignees might be employees who need to be given work assignments. Assigning people to jobs is a common application of the assignment problem. However, the assignees need not be people. They could be machines, or vehicles, or plants, or even time slots to be assigned tasks.

To fit the definition of an assignment problem, these kinds of applications need to be formulated in a way that satisfies the following assumptions:

(i) The number of assignees and the number of tasks are the same (Balanced).

(ii) Each assignee is to be assigned to exactly one task.

(iii) Each task is to be performed by exactly one assignee.

(iv) There is a cost associated with assignee i performing task j

(v) The objective is to determine how all assignments should be made to minimize the total cost.

The general assignment model with n assignees and n tasks is presented as follows:

	Tasks
		1	2	……	n	1
Assignee	1					1
	2
	: : :	: : :	: : :	: : :	: : :	: : :
	n					1
	1	1	1		1

The assignment model is actually a special case of the transportation model in which the assignees represent the sources, and the tasks represent the destinations. In effect, the assignment model can be solved directly as a regular transportation model. Nevertheless, the fact that all supply and demand amounts equal 1 has led to the development of a simple solution algorithm called the Hungarain method. Although the new method appears totally unrelated to the transportation model, the algorithm is actually rooted in the simplex method, just as the transportation model is.

Mathematical Formulation of the problem

Let = 0, if the task not assigned to assignee

= 1, if the task assigned to assignee

The objective of the model is to determine the unknowns that minimize the overall cost:

Minimize

Subject to the constraints

for all i and j

The Assignment Algorithm – Hungarian method

The steps of the assignment algorithm are as follows:

Step 1: For the original cost matrix, identify each row’s minimum, and subtract it from all the entries of the row.

Step 2: For the matrix resulting from step 1, identify each column’s minimum, and subtract it from all the entries of the column.

Step 3: Assign the zeroes:

(a) Examine the rows of the current matrix successively until a row with exactly one unmarked zero is found. Circle this zero, indicating that an assignment will be made there. Cross out all other zeroes lying in the column of above encircled zero. The crossed cells will not be considered for any future assignment. Continue this manner until all the rows have been taken care of.

(b) Similarly for column.

Step 4: Check for Optimality: Repeat step 3 successively till one of the following occurs.

(a) There is no row and no column without assignment. In such a case, the current assignment is optimal.

(b) There may be some row or column without assignment. In this case, the current solution is not optimal. Proceed to next step.

Step5: Draw minimum number of lines crossing all zeroes as follows: If the number of lines equal to the order of the matrix, then the current solution is optimal, otherwise it is not optimal. Proceed to the next step.

Step6: Examine the elements that do not have a line through them. Select the smallest of these elements and subtract the same from all the elements that do not have a line through them, and add this element to every element that lies in the intersection of the two lines. Repeat this until an optimal assignment is reached.

Example 3.4:

Joe’s three children – John, Karen and Terri – want to earn some money to take care of personal expenses during a school trip to the local zoo. Joe has chosen three tasks for his children: mowing the lawn, painting the garage, and washing the family cars. To avoid anticipated sibling competition, he asked them to summit (secret) bids for what they feel was a fair pay for each of the three tasks. The understanding then was that all three children would abide their father’s decision as to who gets which tasks. The following table summarizes the bids received.

	Mow	Paint	Wash
John	15	10	9
Karen	9	15	10
Terri	10	12	8

Based on this information, how should Joe assign the tasks?

Solution:

Let and be row i and column j minimum costs as defined in step 1 and 2 respectively.

	Mow	Paint	Wash	Row minimum
John	15	10	9
Karen	9	15	10
Terri	10	12	8

	Mow	Paint	Wash
John	6	1	0
Karen	0	6	1
Terri	2	4	0
Column minimum

	Mow	Paint	Wash
John	6	0	0
Karen	0	5	1
Terri	2	3	0

The cells with underscored zero entries provide the optimum solution. The total cost is 9 + 10 + 8 = 27. This amount also will always equal .

Unbalanced Assignment Problem

When the cost matrix of an assignment problem is not a square matrix (# of assignees is not equal to the # of tasks), the assignment is called an unbalanced assignment problem. In such problems, dummy rows or columns are added in the matrix so as to complete it to form a square matrix.