Operations Management - Assignment Problems

 

Assignment Problems – Introduction

 

Like transportation problem, assignment problem is also another type of special linear programming problem.

 

There are many situations where the assignment of people or machines and so on, may be called for. Assignment of workers to different machines, clerks to various check-out counters, salesmen to different sales areas, service crews to different districts, are typical examples of these situations. The assignment is a problem because people possess varying abilities for performing different jobs and, therefore, the costs of performing the jobs by different people are different. Obviously, if all persons could do a job in the same time (i.e. at the same speed) or at the same cost then it would not matter who of them is assigned the job. Thus, in an assignment problem, the question is how should the assignments be made in order that the total cost involved is minimised (or the total value is maximised when pay-offs are given in terms of, say, sales or profits and so on).

 

 

There are four methods of solving an assignment problem:

(a)         Complete Enumeration Method;

(b)         Transportation Method;

(c)          Simplex Method; and

(d)         Hungarian Assignment Method (HAM).

Assignment Problems – Hungarian Assignment Method (HAM)

 

It is one of the four methods of solving an assignment problem. It is specially designed to handle the assignment problems in an efficient way. This method is based on the concept of opportunity cost. For a typical balanced assignment problem involving a certain number of persons and an equal number of jobs, and with an objective function of the minimisation type, the steps for applying the method are as follows:

 

Step 1: Row Operation

Locate the smallest cost element in each row of the cost table. Now subtract this smallest element from each element in that row. As a result, there shall be at least one zero in each row of this new table, called the First Reduced Cost Table.

 

Step 2: Column Operation

Locate the smallest cost element in each column of the reduced cost table. Now subtract this smallest element from each element in that column. As a consequence of this action, there would be at least one zero in each of the rows and columns of this Second Reduced Cost Table.

 

Step 3: Line Drawing Operation (Optimality Test)

Draw the minimum number of horizontal and vertical lines that are required to cover all the zero elements in the second reduced cost table. If the number of lines drawn is equal to ‘n’ (the number of rows/columns) the solution is optimal, and in this case Step 6 should be followed next. But if the number of lines drawn is smaller than ‘n’, the solution is not optimal, and in this case Step 4 should be followed next.

 

Step 4: Table Operation

Select the smallest uncovered (i.e. uncovered by the lines) cost element of the table. Subtract this element from all the uncovered elements including the smallest element itself and add this element to each of the elements located at the intersection of any two lines. The cost elements through which only one line passes remain unaltered.

 

Step 5: Repeating Operation

Repeat Steps 3 and 4 until an optimal solution is obtained.

 

Step 6: Job Assignment Operation

Once the optimal solution is obtained, job assignments are made as indicated by the ‘zero’ elements. This is done as follows:

(a)     Locate a row which contains only one ‘zero’ element. Assign the job corresponding to this element to its corresponding person. Cross out the other zero(s), if any, in the column corresponding to the element.

(b)     Repeat (a) for each of such rows which contain only one ‘zero’ element.

(c)      Repeat the same operations as in (a) and (b) in respect of each column containing only one ‘zero’ element, crossing out the other zero(s), if any, in the row corresponding to the element.

(d)     If there is no more row or column with only a single ‘zero’ element left, then select a row or column arbitrarily and choose one of the jobs (or persons) and make the assignment. Now cross the remaining zeros in the corresponding column and row in respect of which the assignment is made.

(e)     Repeat steps (a) through (d) until all assignments are made.

(f)       Determine the total cost with reference to the original cost table.

Assignment Problems – Some Special Cases

 

Unbalanced Assignment Problems

The Hungarian method of solving an assignment problem requires that the number of columns should be equal to the number of rows. When they are equal, the problem is a balanced problem, and when not, it is called an unbalanced problem. Thus, where there are 5 workers and 4 machines, or when there are 4 workers and 6 machines, for instance, we have unbalanced situations in which one-to-one match is not possible. In case the machines are in excess, the excess machine(s) would remain idle and so is the case when workers are in excess – the number of excess workers would not get an assignment.

 

In such situations, dummy column(s) [If number of column(s) is less than number of row(s)] or dummy row(s) [If number of row(s) is less than number of column(s)] are inserted with zeros as the cost elements. For example, when the given cost matrix is of the dimension 4 × 5, a dummy row would be included. In each column in respect of this row, a ‘zero’ would be placed. After this operation of introducing dummy columns/rows, the problem is solved in the usual manner.

 

Constrained Assignment Problems

It happens sometimes that a worker cannot perform a certain job or is not to be assigned a particular job. To cope with this situation, the cost of performing that job by such person is taken to be extremely large (which is written as M). Then the solution to the assignment problem proceeds in the usual manner as discussed earlier. The effect of assigning prohibitive cost to such person-job combinations is that they do not figure in the final solution.

 

Unique vs Multiple Optimal Solutions

In the process of making assignments, it was stated earlier that we select a row/column with only a single zero to make an assignment. However, a situation may arise wherein the various rows and columns, where assignments are yet to be done, have all multiple zeros. In such cases, we get multiple optimal solutions to the given problem.

 

When a problem has a unique optimal solution, it means that no other solution to the problem exist which yields the same objective function value (cost, time, profit, etc.) as the one obtained from the optimal solution derived. On the other hand, in a problem with multiple optimal solutions, there exists more than one solution which all is optimal and equally attractive.

 

Maximisation Problem

In some situations, the assignment problem may call for maximisation of profit, revenue, etc. as the objective. For example, we may be faced with the problem of assignment of salesmen in different regions in which they can display different qualities in making sales (reflected in amounts of sales executed by them). Obviously, in such a situation, assignment would be made in such a way that the total expected revenue is maximised.

 

For dealing with a maximisation problem, we first change it into an equivalent minimisation problem. This is achieved by subtracting each of the elements of the given pay-off matrix from a constant (value) K. Thus, we may simply put a negative sign before each of the elements/values of the given pay-off matrix (which is equivalent to subtracting each value from zero). Usually, the largest of all values in the given matrix is located and then each one of the values is subtracted from it (the largest value is taken so as to avoid the appearance of negative signs). Then the problem is solved the same way as a minimisation problem is.

Travelling Salesman Problem

 

Objective of a travelling salesman

The objective of a travelling salesman is to select the sequence in which the cities are visited in such a way that his total travelling cost or time is minimised.

 

Conditions

There are two conditions which have to be satisfied when solving a travelling salesman problem and these are:

         1)        No city is to be visited twice before the tour of all the cities is completed; and

         2)        Going from city ‘i’ to ‘i’ is not permitted.

 

Steps for solving a travelling salesman problem

 

STEP: 1

Treat the problem as a normal assignment problem and solve it using the same usual procedure. If the optimal solution of the assignment problem satisfies the above two conditions, then it is also an optimal solution of the given travelling salesman problem. But, if the solution to the assignment problem does not satisfy the above two conditions, follow the following steps after solving the problem as a normal assignment problem to find the optimal solution for the travelling salesman problem.

 

STEP: 2

Make assignment again, after treating the minimum non-zero element of the previous table as ‘zero’, in the same way as assignment is made for an optimal solution with the only exception that in this case one assignment has to be made compulsorily to the minimum non-zero element treated as zero.

 

STEP: 3

At this stage, if the number of assignments is less than the size of the matrix, the solution is not optimal. Therefore, we have to go back to the table where we got minimum number of lines covering all the zeros exactly same as the size of the matrix. Here, we have to find the smallest uncovered (i.e. uncovered by lines) cost element of the table and subtract this element from all the uncovered elements and add to each of the elements located at the intersections of any two lines. The cost elements through which only one line passes will remain unaltered.

 

STEP: 4

Draw minimum number of lines in the modified table covering all the zeros. If the number of lines is equal to the size of the matrix, we have got a new optimal solution of the assignment problem to make assignment again.

 

STEP: 5

After the assignments are made as above in Step: 4, if the solution still does not satisfy the above two conditions, follow Step: 2, but this time the minimum non-zero element to be treated as zero should not be the earlier one, but rather it should be a new one without considering the earlier one.

 

STEP: 6

At this stage, if the number of assignments is equal to the size of the matrix and satisfies the above two conditions, the solution is optimal for the travelling salesman problem, or otherwise follow Step: 2 again and this time also the minimum non-zero element to be treated as zero should not be the earlier ones, but rather it should be a new one without considering the earlier ones.

 

STEP: 7

At this stage, if the number of assignments is equal to the size of the matrix and satisfies the above two conditions, the solution is optimal for the travelling salesman problem. But, if the number of assignments is less than the size of the matrix, the solution is not optimal and in that case repeat Steps: 6 and 7 until the optimal solution for the travelling salesman problem is obtained.