ASSIGNMENT
Assignment Problem is a special type of linear programming problem where the objective is to minimize the cost or time of completing a number of jobs by a number of persons.
The assignment problem in the general form can be stated as follows:
“Given n facilities, n jobs and the effectiveness of each facility for each job, the problem is to assign each facility to one and only one job in such a way that the measure of effectiveness is optimized (Maximized or Minimized).”Several problems of management have a structure identical with the assignment problem.
Example
A manager has four persons (i.e. facilities) available for four separate jobs (i.e. jobs) and the cost of assigning (i.e. effectiveness) each job to each person is given. His objective is to assign each person to one and only one job in such a way that the total cost of assignment is minimized.
APPLICATIONS OF ASSIGNMENT PROBLEM
Few applications of assignment problem are as follows:
- Assignment of employees to machines.
- Assignment of operators to jobs.
- Effectiveness of teachers and subjects.
- Allocation of machines for optimum utilization of space.
- Allocation of salesmen to different sales areas.
- Allocation of clerks to various counters.
In all the cases, the objective is to minimize the total time and cost or otherwise maximize the sales and returns.
HUNGARIAN METHOD
Hungarian method is named after Hungarian mathematician D Konig who developed the assignment problem.
The Hungarian method is also known as Flood’s Technique or the Reduced Matrix method. This method of assignment provides an efficient means of finding the optimal solutions without having to make a direct comparison of every option. It operates on a principle of matrix reduction.
STEPS IN HUNGARIAN METHOD
Hungarian method of assignment problem (minimization case) can be summarized in the following steps:
STEP 1: NOTE THE MATRIX
From the given problem, find out the cost table. Note that if the number of origins is not equal to the number of destinations then a dummy origin or destination must be added.
STEP 2: ROW REDUCTION
In each row of the table find out the smallest cost element, subtract this smallest cost element from each element in that row. So, that there will be at least one zero in each row of the new table. This new table is known as First Reduced Cost Table.
Step 3: COLUMN REDUCTION
In each column of the table find out the smallest cost element, subtract this smallest cost element from each element in that column. As a result of this, each row and column has at least one zero element. This new table is known as Second Reduced Cost Table.
STEP 4: MARK ASSIGNMENTS
Now determine an assignment as follows:
- For each row or column with a single zero element cell that has not be assigned or eliminated, box that zero element as an assigned cell.
- For every zero that becomes assigned, cross out all other zeros in the same row and for column.
- If for a row and for a column there are two or more zero and one can’t be chosen by inspection, choose the assigned zero cell arbitrarily.
- The above procedures may be repeated until every zero element cell is either assigned (boxed) or crossed out.
An optimum assignment is found, if the number of assigned cells is equal to the number of rows (and columns). In case a zero cell had chosen arbitrarily, there may be an alternate optimum. If no optimum solution is found i.e. some rows or columns without an assignment then go to Step 6.
STEP 5: MARKING ROWS AND COLUMNS
Draw a set of lines equal to the number of assignments which has been made in Step 4, covering all the zeros in the following manner:
- Mark check (√) to those rows where no assignment has been made.
- Examine the checked (√) rows. If any zero element cell occurs in those rows, check (√) the respective columns that contains those zeros.
- Examine the checked (√) columns. If any assigned zero element occurs in those columns, check (√) the respective rows that contain those assigned zeros.
- The process may be repeated until now more rows or column can be checked.
- Draw lines through all unchecked rows and through all checked columns.
STEP 7: REASSIGNMENT
Examine those elements that are not covered by a line. Choose the smallest of these elements and subtract this smallest from all the elements that do not have a line through them.
Add this smallest element to every element that lies at the intersection of two lines. Then the resulting matrix is a new revised cost table.
EXAMPLE OF HUNGARIAN METHOD
In a computer centre after studying carefully the three expert programmes, the head of computer centre, estimates the computer time in minutes required by the experts for the application programmes as follows:
Assign the
programmers to the programmes in such a way that the total computer time is
minimum.
The Hungarian method is used to obtain an optimal solution.
Step (1) & (2):
The minimum time element in row 1, 2 and 3 is 80, 80 and 110. respectively. Subtract these elements from all elements in this respective row.
The reduced time matrix is shown in following table (1) Table 1:
In reduced Table (1) the minimum time element in columns A, B, and C is 0,10 and 0 respectively; subtract these elements from all elements in this resp. column to get the reduced time matrix as shown in Table 2.
Step 3 (a):
Examine all the rows starting from first one and make the assignments at zero.
Assign this cell as shown in table 4.
(c) Since the number of Assignments (= 3) equal the no of rows (= 3), the optimal solution is obtained.
The pattern of assignment among programmers and programmes with their respective line (in minutes) is given below:
