Solving the Unbalanced Assignment Problem: Simpler Is Better

Show more

Received 7 June 2016; accepted 27 June 2016; published 30 June 2016

1. Introduction

The assignment problem is a standard topic discussed in operations research textbooks (See for example, Hillier and Lieberman [1] or Winston [2] ). A typical presentation requires that n jobs must be assigned to n machines such that each machine gets exactly one job assigned to it. If the number of jobs is not equal to the number of machines, then the assignment problem is first balanced. This requires that either dummy (fictitious) jobs or machines are added to the problem so that the number of jobs will equal the number of machines. The typical textbook solution to the balanced assignment problem is then found using Kuhn’s [3] Hungarian method.

Problems in which there are more jobs than machines and more than one job can be assigned to a machine can easily be handled as a balanced assignment problem with a little modeling effort. The idea is to “make copies” or “clone” the machines. This approach is discussed in Hillier and Lieberman [1] on page 336 with an example given in Table 8.29 on page 340. Also, problem 28 on page 411 of Winston [2] illustrates this modeling approach. For example, the numerical problem given in Yadaiah and Haragopal [4] requires the assignment of eight jobs to five machines such that each machine gets at least one job assigned to it and no machine gets more than two jobs assigned to it. The standard textbook approach would “clone” each of the five machines and add two dummy jobs to create a 10 by 10 balanced assignment problem. In a textbook, this problem would usually be solved with the Hungarian method, but other solution approaches are possible―the formulation is separate from the solution approach.

In Yadaiah and Haragopal [4] , they use a different approach to solve the unbalanced assignment problem (see their paper for details). If there are n jobs to be assigned to m machines with n strictly greater than m, then they solve a series of k balanced assignment sub-problems each of size m by m where k is the floor (round down) of n/m. The last problem that they solve is a balanced assignment problem of size [n-km] by [n-km]. Instead of using the Hungarian method to solve each sub-problem, they use a Lexi-search approach (See Pandit [5] and Ramesh [6] ). Their approach would be an alternative solution methodology to the textbook approach; however, we will show in the next section, using the numerical example from Yadaiah and Haragopal [4] , that their approach does not guarantee the optimal solution.

2. Yadaiah and Haragopal’s Numerical Example Revisited

Their numerical example is given in Table 1 and their method requires the solution of two sub-problems: a 5 by 5 and a 3 by 3. Please see Yadaiah and Haragopal [4] for details of their solution approach.

The first sub-problem solved byYadaiah and Haragopal [4] , is given in Table 2.

Their Lexi-search solution to this sub-problem is the following assignment:

J3 assigned to M1, J4 assigned to M2, J5 assigned to M3, J6 assigned to M5, and J7 assigned to M4 with a cost of 870. The second sub-problem is given in Table 3.

Their Lexi-search solution to this sub-problem is the following assignment:

J1 assigned to M4, J2 assigned to M5, and J8 assigned to M2 with a cost of 680. The final assignment cost is

Table 1. Cost matrix.

Table 2. First sub-problem.

870 + 680 = 1550. It can easily be checked using the Hungarian method, that these sub-problems were solved optimally. In their paper,

Yadaiah and Haragopal have a minor typo on page 88, they have 870 + 670 = 1550. It should read 870 + 680 = 1550.

We will now solve the original problem of assigning these eight jobs to five machines such that each machine is used at least once, but not more than twice.

Using the approach suggested in both Hillier and Lieberman [1] and Winston [2] , we formulate the balanced 10 by 10 assignment problem given in Table 4.

Solving the balanced assignment problem given in Table 4 using the Hungarian method yields the “reduced” cost matrix given in Table 5.

Table 3. Second sub-problem.

Table 4. Textbook formulation.

Table 5. Final Hungarian method cost matrix.

From Table 5, we can read the optimal assignment to be

J1 assigned to M5 at a cost of 210,

J2 assigned to M1 at a cost of 250,

J3 assigned to M1 at a cost of 180,

J4 assigned to M2 at a cost of 210,

J5 assigned to M3 at a cost of 190,

J6 assigned to M5 at a cost of 140,

J7 assigned to M4 at a cost of 180,

J8 assigned to M2 at a cost of 190,

For a total minimum cost of 1520 (not 1550).

Both of these assignments use each machine at least once and no more than twice, but the standard textbook formulation solved with the Hungarian method gets the guaranteed optimal solution of 1520―maybe simpler is better. The flaw with their approach is that their assignment is not optimal because their decomposition into sub- problems does not guarantee an optimal solution to the original problem as illustrated by this example.

References

[1] Hillier, F.S. and Lieberman, G.J. (2010) Introduction to Operations Research. 9th Edition, McGraw-Hill, New York.

[2] Winston, W.L. (2004) Operations Research: Applications and Algorithms. Thomson, Belmont.

[3] Kuhn, H.W. (1955) The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 5, 83- 97.

http://dx.doi.org/10.1002/nav.3800020109

[4] Yadaiah, V. and Haragopal, V.V. (2016) A New Approach of Solving Single Objective Unbalanced Assignment Problem. American Journal of Operations Research, 6, 81-89.

http://dx.doi.org/10.4236/ajor.2016.61011

[5] Pandit, S.N.N. (1963) Some Quantitative Combinatorial Search Problems. PhD Thesis, IIT, Khargpur.

[6] Ramesh, M. (1997) Lexi-Search Approach to Some Combinatorial Programming Problem. PhD Thesis, University of Hyderabad, Hyderabad.