Assignment Technique

Dr. T. T. Kachwala

Slide 2

Assignment Technique
Introduction
An assignment problem is a special class of linear programming

problem.
The objective of an assignment problem is to determine the

optimal assignment of given tasks to a set of workers that they can perform with varying efficiency, in terms of time taken, cost, amount of sales and so on.
Thus, if there are n tasks to perform and an equal number of persons

who can do them, in varying times which are known, the algorithm

seeks to assign the jobs to persons in such a manner that each person
gets one job and the total time in which all jobs can be done is the minimum. The algorithm works in varied situations wherein pairings are sought to be made.

Slide 3

Assignment Technique
Introduction (continued)
Assignment problems can be solved by :
1.

Completely enumerating all possibilities

and choosing the best one.

2.

Drafting and solving the problem as a linear

(integer) programming problem.

3.

Drafting and solving the problem as a transportation problem.

4.

Hungarian assignment method (HAM).

Slide 4

Assignment Technique
Objective Function: Optimum Assignment (or Allocation) of Jobs to Facilities
Example :

Six contractors submitted quotation for six projects. It was decided that one contractor should be given one project as otherwise it was feared that the time for completion & quality of workmanship will be affected. The estimates given by each of them on all the contracts in thousands of rupees are given below:
----------------------------------------------------------------------------------------Contractor Quotation for project (Rs. in thousands) I II III IV V VI ----------------------------------------------------------------------------------------A 41 72 39 52 25 51 B 22 29 49 65 81 50 C 27 39 60 51 32 32 D 45 50 48 52 37 43 E 29 40 39 26 30 33 F 82 40 40 60 51 30 -----------------------------------------------------------------------------------------

Determine the optimum allocation of projects to the contractors and the corresponding total cost.

Slide 5

Assignment Technique
Hungarian solution (Mathematician Konig from Country Hungarian)

In the given example, 6 projects have to be assigned

to 6 contractors. There are 6! (6*5*4*3*2*1 = 720) possible ways to perform this allocation
In the complete enumeration study, one has to

calculate the total cost for each of the 720 solutions & then select the allocation with the minimum total cost
Alternately, we can apply Hungarian solution which

will directly give the optimum allocation & the corresponding minimum total cost

Slide 6

Assignment Technique
Unbalanced Problems:

If an assignment problem has equal number of jobs and workers, it

is called balanced problem, while if the two do not match, the problem is unbalanced.
An unbalanced problem is balanced, as a first step, by introducing

the necessary number of dummy jobs or workers (rows / columns), as required. To illustrate, if there are seven workers and five jobs, then two dummy jobs would be introduced.
The cost elements for the dummy workers / jobs would be taken to

be M (high positive value). The workers getting dummy jobs would, in fact, not be given any job.

Slide 7

Assignment Technique
Maximisation Assignment Problems:
Sometimes, an assignment problem calls for assigning people to

different areas where they can give the maximum benefit. For example, sales expected from different salesmen in various sales zones may be given. The problem may be to assign each one of them in such a manner that the total sales may be maximised.
A maximisation type of problem is first converted to an equivalent

minimisation problem by subtracting each value of the given matrix from a constant value, which is usually taken to be the largest of the given values. The resulting matrix is termed as Opportunity Loss Matrix and is then solved as any minimisation problem.
If a maximisation problem is unbalanced, it is first balanced by adding

dummy worker(s) / job(s) with zero elements.

Slide 8

Assignment Technique
Prohibited Assignments:
If a worker cannot perform a particular job or he is not

been

assigned

particular

job,

then

such

an

assignment is called prohibited assignment.

M which is a very large value, replaces the cost

element for each prohibited assignment. The problem is then solved as usual. The prohibited assignments will continue to be shown by M, with no changes in them in row as well as column reductions.

Slide 9

Assignment Technique

Working Rules and Guidelines (Hungarian Solution)

Step 1: Check if Assignment matrix (AM) is balanced. {A balanced AM

is that matrix where number of rows = number of columns }. If AM is

balanced, no adjustment is required. However, if AM is unbalanced, then add appropriately a dummy row / column to balance the matrix.

Step 2: Check if AM is a cost matrix. If it is a cost matrix, the value of the cells of a dummy row / columns are taken as M {'M' is a very high positive value}. However, if it is a Profit matrix, the values of a dummy

row / column are taken as '0 (zero). Further, if it is a cost matrix, no

further adjustment is required. However if it is a profit matrix, then convert it into an equivalent cost matrix, by using the following mathematical relation:

Slide 10

Assignment Technique

Working Rules and Guidelines (Hungarian Solution Continued)

Cij = P - Pij
Where 'Cij' is the cost value of a cell corresponding to
the ith row / jth column, Pij is the corresponding profit value P = (Pijs) max

Steps 3: Simplify the matrix {cost balanced matrix}

by performing Row Minima and Column Minima

operations {The sequence of Performing Row Minima & Column Minima operations is arbitrary}

Slide 11

Assignment Technique

Working Rules and Guidelines (Hungarian Solution Continued)

Step 4:

Test the simplified solution for optimality (Draw minimum number of lines to cover the zeros). If the simplified solution passes the optimality test, we conclude that it is an optimum solution.

However, if it fails the optimality test then we conclude that it is not an optimum solution. In such a case, we modify the solution through a procedure of adjustment.

Test the modified solution for optimality. Continue this procedure of adjustment and testing for

optimality, till we reach the optimum solution.

Slide 12

Assignment Technique

Working Rules and Guidelines (Hungarian Solution Continued)

Step 5: Perform allocation of jobs to facilities Step 6: Calculate total cost / total profit with reference to the optimum allocation using data given in the original (source) matrix.

Additional Notes:

Row Minima operation: Proceed row wise, Identify for each row the minimum value. Subtract this minimum value from all the cells of that row. Continue this procedure for all the rows of the matrix.

Slide 13

Assignment Technique

Additional Notes: (Hungarian Solution Continued)

Column Minima operation: Proceed column wise, Identify for

each column the minimum value. Subtract this minimum

value from all the cells of that column. Continue this procedure for all the column of the matrix.

The sequence of performing Row Minima & Column Minima

operation is arbitrary. However for an unbalanced AM, from the point of view of convenience of calculations, the sequence will depend on the nature of the adjustment e.g. If adjustment is in the form of a dummy row, we perform row minima first & like wise if adjustment is in the form of a

dummy column, we perform column minima first.

Slide 14

Assignment Technique

Testing the solution for optimality:

Proceed row wise. Identify a row with a single zero. Enclose this zero in

a square bracket, cancel the remaining zeros with a cross(x)

corresponding to this column. Continue this procedure, till all the row with a single zero is identified. If in a row there is more than one zero, leave the zeroes unmarked.

Identify the row without a square bracket and without unmarked zeros. Put 1 for that row. Starting from this row, identify crossed zeros. Corresponding to this column Put 2 . Starting from this column identify square bracket. Corresponding to this row put 3. Continue this procedure till all the appropriate rows & columns have been indicated by a

Slide 15

Assignment Technique
Testing the solution for optimality: (Continued)

Draw lines across the row without the mark and

line across the column with the mark. Count the

number of lines drawn.
If the number of lines drawn

= number of Rows /

Column, it means we have reached the optimum solution. However if number of lines drawn

Number of Rows / Column it means we have not

reached an optimum solution. In such cases, modify the solution through a procedure of - adjustment.

Slide 16

Assignment Technique

Working Rules and Guidelines (Hungarian Solution continued)

Modification of solution ( - adjustment ):

Select the value of corresponding to the minimum value of an uncovered cell.

Subtract the value of from all the uncovered cells of the matrix Add the value of to all the cells at the intersection of the lines drawn

The remaining cells, which are covered but which are not at the intersection of the lines drawn, remain unchanged.

Allocation of Jobs to Facilities:

Zeros in the square bracket are guides for allocation. It signifies the least cost allocation for that row.