Assignment Problems for Optimization in Logistics

When a problem involves the allocation of some resources to different tasks, it comes under the purview of assignment problems. This is a special class of linear programming problem. The objec­tive of the assignment problem is to determine the optimum assignment of given tasks that a set of workers can perform with varying efficiency, in terms of time taken and cost. If there are n tasks to perform and an equal number of persons who can do them, in varying time periods that are known, the algorithm seeks to assign the jobs to the persons in such a manner that each person gets one job and all jobs can be done in the minimum possible time. These problems can be solved by:

• Completely enumerating all possibilities and choosing the best one
• Drafting and solving the problems as linear (integer) programming problems
• Approaching them as transportation problems
• Using the Hungarian assignment method

The problem is put in a matrix form. For example, the crew members of an airline have to be assigned various flight schedules, taking into consideration their duty hours, minimum cost of over­time and availability of flights and so on. This problem can be solved by the assignment method.

1. Hungarian Method

1. This method of solving the assignment problem requires the number of columns to be equal to the number of rows.
2. When the numbers of the columns and the rows are equal, the problem is a balanced problem.
3. When the above numbers are not equal, it is called an unbalanced problem.
4. For example, when there are five workers and four machines or three workers and four machines, we have an unbalanced situation.
5. I n the case of excess machines, the machines will be idle; and workers will be idle in the case where there is an excess of them.
6. I n the case of an unbalanced situation, a dummy column or row is inserted; whichever is smaller in number.
7. I n the dummy column or row, the value placed at all places is zero.
8. After putting in the dummy entry and zero values, the problem is solved in the usual manner.

2. Algorithm

Step 1: For the original cost matrix, identify each row’s minimum, and subtract it from all the entries of rows (i.e., row reduction).

Step 2: Using the new matrix, subtract the smallest number in each column from all other columns and again form a new matrix (i.e., column reduction).

Step 3: Check the numbers to see if there is a zero for each row and column, and draw the minimum number of lines necessary to cover all the zeros in the matrix.

Step 4: If the number of lines is equal to the number of rows, the matrix is optimal and the problem is solved.

Step 5: Optimum assignment is obtained by zero entries in the matrix.

• Example 1. Time taken by workers for various jobs is given in the following matrix. Assign the job to the worker for the optimum time.

Source: Sople V.V (2013), Logistics Management, Pearson Education India; Third edition.