Applied Mathematical Sciences, Vol. 8, 2014, no. 160, 7979 - 7986 HIKARI Ltd, www.m-hikari.com http://dx.doi.org/10.12988/ams.2014.410796 A New Diagonal Optimal Approach for Assignment Problem M. Khalid Department of Mathematical Sciences Federal Urdu University of Arts, Sciences & Technology Karachi-75300, Pakistan Corresponding Author Mariam Sultana Department of Mathematical Sciences Federal Urdu University, Karachi-75300, Pakistan Faheem Zaidi Department of Mathematical Sciences Federal Urdu University, Karachi-75300, Pakistan Copyright © 2014 M. Khalid, Mariam Sultana and Faheem Zaidi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract Different situations give rise to the assignment problem, where we must discover an optimal way to assign ‘n’ objects to ‘m’ in an bijective function. We have, in this research, propose the possibility of solving exactly the Linear Assignment Problem with a method that would be more efficient than the Hungarian method of exact solution. This method is based on applying a series of pairwise interchanges of assignments to a starting heuristically generated feasible solution, wherein each pairwise interchange is guaranteed to improve the objective function value of the feasible solution.It seems that our algorithm finds the optimal solution which is the same as one found by the Hungarian method, but in much simpler. 7980 M. Khalid et al. Keywords: Assignment Problem; Cost Minimization; Diagonal Sum; Linear Integral Programming Introduction The Assignment method picks a ‘task’ and matches it with the most appropriate ‘agent’, from which the most efficient outcome may be obtained. Since its introduction in 1952, many different approaches have been developed for finding best solutions to the assignment problem. A few important ones should be mentioned: Hungarian Method by Kuhn and Munkres [1, 2] was one of the earliest ones; linear programming was proposed by Dantzig [3]; the Auction Algorithm was developed by Bertsekas [4]. Other methods may include one by Kosowsky and Yuille [5] that uses statistical physics, another by Basirzadh [6] called Ones Assignment method, which is somewhat similar to the Hungarian and minimizes or maximizes the objective function,the revised Ones Assignment Method by Muley and Ghade [7]. Lastly, new improved ones assignment mehod by authors of this study [8]. This study puts forward and investigates a fresh approach to the solution of the assignment problem. Looking at it from a research point of view, presenting old problems in a new framework should be credited because it gives a clear grounding for comparing different methods. It also helps in the enrichment of the understanding of dynamics that govern this phenomenon. The assignment problem is not only an old problem but a very practical one that has given rise to much theoretical and practical analysis, and that definitely warrants a thorough investigation. The Assignment Problem (Mathematical Formulation) An assignment problem is a bijective mapping of a finite set N  1,2,3,....., n into itself i.e. permutation  assigning some j  i  to each i  N . The set of all permutations (assignments) of n items will be denoted by S n and has n ! elements. Every permutation  of the set N  1,2,3,....., n corresponds uniquely to a permutation matrix X   x tj  with x ij  1 for j  i  and x ij  0 for j  i  . Thus, a permutation matrix X  x tj  can be defined as a matrix which fulfills the following conditions n  x ij  1 for  j  1,2,3,...., n  x ij  1 for  i  1,2,3,...., n i 1 n j1 x ij  0,1 for  i, j  1,2,3,..., n A new diagonal optimal approach for assignment problem 7981 New Purpose Algorithm The new algorithm is as follow: 1) Locate the two cells that have minimum cost and next to minimum cost. in each row, then write their difference (penalty) along the side of the table against the corresponding row. 2) Locate the two cells that have minimum cost and next to minimum cost in each column, then write their difference (penalty) below the table against the corresponding column. 3) Locate the maximum penalty. If it is along the side of the table, make maximum assignment to the cell having minimum cost in that row. If it is below the table, make maximum assignment to the cell having minimum cost in that column. Continue in the same manner until all assignments are made. 4) If the penalties corresponding to two or more rows/columns are equal, find the difference between first and third minimum value. Identify the maximum among them and assign the minimum cost among them. This step gives the initial solution. Remarks: For finding the optimal solution, we will follow step 5 and 6 5) Write these assigned costs on the top of the column of original assignment problem. Let a j be the assigned cost for column j . Subtract a j from each entry of c ij of the corresponding column of assignment matrix 6) Construct a rectangle in such a way that one corner contains negative penalty and remaining two corners are allocated to the assigned cost values in corresponding row and column. Calculate the sum of extreme cells of unassigned diagonal, say d ij . Locate  d ij  0 . Identify the most negative d ij and exchange the assigned cell of diagonals. Continue the process until all negative penalties are resolved. Remarks: If any d ij  0 , then exchange the cells of diagonals at the end. Numerical Examples This method is illustrated with some numerical examples. Example 1: Consider an assignment problem with five jobs assign to five workers so that the cost is minimized. W1 W2 W3 W4 W5 J1 J2 J3 J4 J5 11 9 13 21 14 17 7 16 24 10 8 12 15 17 12 16 6 12 28 11 20 15 16 26 13 7982 M. Khalid et al. By using step 1 and 2, write the difference (penalty) against corresponding row and column. Identify the maximum penalty. Assign the cell with minimum cost, as per step 3. Repeat till all values have been assigned. 11 9 13 21 14 17 7 16 24 10 8 12 15 17 12 16 6 12 28 11 20 15 16 26 13 2, 2, 2, 8 3, 6 4, 4, 7 5 2, 3, 4, 10 3,3,3 1 1,2,2,3 4,4,4,5 1,2 All assigned costs are written on the top of the columns of original assignment matrix. Subtract assigned cost from each entry of the corresponding column of the assignment matrix. Identify all the negative penalties. 21 10 8 6 16 11 9 13 21 14 17 7 16 24 10 8 12 15 17 12 16 6 12 28 11 20 15 16 26 13 -10 7 -12 -3 -8 6 0 14 -7 0  0 4 7 9 4 10 0 6 22 5 4 -1 0 10 -3 we check the values of d ij by using step 6 d11 -10 0 d 31 -8 0 0 10 0 9 -1 d 22 2 d 51 d 55 0 5 2 d 21 -12 0 0 22 10 0 14 -7 0 7 d 25 0 6 5 -3 0 6 0 0 -3 3 -1 0 A new diagonal optimal approach for assignment problem 7983 After exchange of assigned cells, repeat step 5 and 6 until all negative penalties are resolved. 11 10 17 6 16 11 9 13 21 14 16 6 12 28 11 20 15 16 26 13 17 7 16 24 10 8 12 15 17 12 0 7 -9 10 4 -2 -3 -5 0 -1 2 6 -2 6 0 10 14 0 22 10 3 0 -5 5 -3  d 13  1 ; d 21  8 ; d 22  2 ; d 23  17 d 25  5 ; d 33  8 ; d 53  9 ; d 55  3 Since, the sum of all unassigned diagonal cells is greater than zero, optimal solution has been successfully achieved. Hence, the minimum cost will be Min Cost  11  6  16  17  10  60 Example 2: An assignment problem with six jobs assign to five workers so that the cost is minimized W1 W2 W3 W4 W5 J1 J2 J3 J4 J5 J6 12 10 11 6 8 10 18 10 14 12 15 25 3 10 11 22 15 8 13 7 18 8 16 12 15 9 13 12 13 10 By introducing dummy variable and follow steps 1 to 3, gives us 12 10 11 6 8 0 10 18 10 14 12 0 15 25 3 10 11 0 6, 2, 2, 4 10, 0, 2, 4, 8 3, 7 22 15 8 13 7 0 18 8 16 12 15 9 13 12 13 10 0 0 7, 13 1, 6(8) 8, 1, 2, 4, 4 2,2,2,2,2 2,2,2,2,6 5,5 4,4,6(7),6 1,1,1 0 7984 M. Khalid et al. Steps 1 - 4 get an initial feasible solution.Steps 5&6 iterate from a feasible solution to an optimal solution, stopping when all d (i, j) are non-negative. Following step 5, we have 6 10 3 7 12 10 11 6 8 0 10 18 10 14 12 0 15 22 18 8 25 15 16 12 3 8 15 9 10 13 13 12 11 7 13 10 0 0 0 0 d 56 8 0 0 -2 d 61 0 13 -6 0 0 12 6 7 d 64 6 0 12 15 18 -4 4 8 22 8 16 0 5 0 0 1 15 -3 0 4 7 6 13 0 2 2 8 0 13 -2 -6 -10 -3 -7 0 -12  d 36 22 0 0 -3 19 d16 0 8 d 63 0 15 -3 0 12 d 62 0 18 -10 0 0 13 -7 0 d 66 6 16 0 0 -12 Here,  d ij  0 , therefore an optimal solution has been achieved. Min Cost  10  12  3  6  7  0  38 Example 3: Consider an assignment problem with 6  6 matrix. W1 W2 W3 W4 W5 W6 J1 J2 J3 J4 J5 J6 41 22 27 45 29 82 72 29 39 50 40 40 39 49 60 48 39 40 52 65 51 52 26 60 25 81 32 37 30 51 51 50 32 43 33 30 Applying, new proposed algorithm on it, we have 4 -4 0 4 8 A new diagonal optimal approach for assignment problem 41 22 27 45 29 82 72 29 39 50 40 40 5, 10, 5, 10, 5, 10(11) 18 7985 39 49 60 48 39 40 52 65 51 52 26 60 25 81 32 37 30 51 51 14,14 50 7,7,7 32 5,5,5,5 43 6,6,2,2 33 3 30 10,10,10(10),10 0, 1, 8, 8, 8 25 5, 7 2, 2, 2, 2, 13 Step 5 yields 27 29 48 26 25 30 41 22 27 45 29 82 72 29 39 50 40 40 39 49 60 48 39 40 52 65 51 52 26 60 25 81 32 37 30 51 51 50 32 43 33 30 14 -5 0 18 2 55  43 0 10 21 11 11 -9 1 12 0 -9 -8 26 0 21 39 56 20 25 7 2 26 12 13 0 5 3 34 26 0 Calculating the value of d ij d13 d 53 -9 0 0 12 0 26 -9 0 3 17 d 21 -5 0 0 10 d 63 0 13 -8 0 5 5 Since,  d ij  0 , we get an optimal solution. the minimum cost of this assignment matrix is Min Cost  27  29  48  26  25  30  185 Conclusion The Assignment problem revolves around the prospect of discovery of one-to-one matching between a pair of sets, which is optimal. A new algorithm has been 7986 M. Khalid et al. proposed in this paper to achieve an exact optimal solution of an assignment problem. There is a vast difference between previously reported algorithm and this new one. Even with an addition of a few new features, the new method is efficient and fast, and can replace old algorithms wherever they have been used. Acknowledgements. The authors would like to thank the reviewers for the comments which led to an improvement in the paper. Special thanks to Ms. Wishaal Khalid for proof reading. References [1] H. Kuhn, The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly, 2 (1955), 83 - 97. http://dx.doi.org/10.1002/nav.3800020109 [2] J. Munkres, Algorithms for the Assignment and Transportation Problems, Journal of the Society of Industrial and Applied Mathematics, 5 (1957), 32 - 38. http://dx.doi.org/10.1137/0105003 [3] G. B. Dantzig and M. N. Thapa, Linear Programming: Theory and extensions, Springer, 1997. [4] D. P. Bertsekas, Auction Algorithms for Network Flow Problems: A Tutorial Introduction, Computational Optimization and Applications, 1 (1992), 7 - 66. http://dx.doi.org/10.1007/bf00247653 [5] J. Kosowsky and A. Yuille, Solving the Assignment Problem with Statistical Physics, IEEE, 1991. http://dx.doi.org/10.1109/ijcnn.1991.155168 [6] H. Basirzadeh, Ones Assignment Method for solving assignment problems, Applied Mathematical Sciences, l (2012), 2345 - 2355. [7] K. P. Ghadle and Y. M. Muley, Revised Ones Assignment Method for solving assignment problem. Journal of Statistics and Mathematics, 4 (2013), 147-150. [8] M. Khalid, Mariam Sultana and Faheem Zaidi, “New Improved Ones Assignment Method Applied Mathematical Sciences, Vol. 8, 2014, no. 84, 4171 – 4177. http://dx.doi.org/10.12988/ams.2014.45327 Received: October 10, 2014; Published: November 18, 2014