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

ABSTRACT

Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest; however, their approach does not guarantee the optimal solution. In this short paper, we will show that solving this same example from the Yadaiah and Haragopal paper by using a simple textbook formulation to balance the problem and then solve it with the classic Hungarian method of Kuhn yields the true optimal solution with a cost of 1520.

Keywords:

Assignment Problem, Hungarian Method, Textbook Formulation

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

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.

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.

Cite this paper

Nathan Betts,Francis J. Vasko, (2016) Solving the Unbalanced Assignment Problem: Simpler Is Better. American Journal of Operations Research,06,296-299. doi: 10.4236/ajor.2016.64028

References