할당 문제의 최적 알고리즘

다국어 초록 (Multilingual Abstract)

This paper suggests simple search algorithm for optimal solution in assignment problem. Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm. The proposed algorithm reduces the 4 steps of Hungarian algorithm to 1 step, and only selects the minimum cost of row and column then gets the optimal solution simply. For the 27 balanced and 7 unbalanced assignment problems, this algorithm finds the optimal solution but the genetic algorithm fails to find this values. This algorithm improves the time complexity O(n³) of Hungarian algorithm to O(n). Therefore, the proposed algorithm can be general algorithm for assignment problem replace Hungarian algorithm.

참고문헌 (Reference)

1 Optimalon Software, "Transportation Problem(Minimal Cost)"

2 W. Snyder, "The Linear Assignment Problem"

3 J. E. Beasley, "Operations Research and Management Science: OR-Notes"

4 M. A. Trick, "Network Optimizations for Consultants"

5 D. Doty, "Munkres' Assignment Algorithm: Modified for Rectangular Matrices"

6 G. B. Dantzig, "Linear Programming and Extensions"

7 S. Noble, "Lectures 15: The Assignment Problem"

8 S. C. Niu, "Introduction to Operations Research"

9 L. Ntaimo, "Introduction to Mathematical Programming: Operations Research: Transportation and Assignment Problems"

10 J. Havlicek, "Introduction to Management Science and Operation Research"

11 Rai Foundation Colleges, "Information Research, In Bachelor of Business Administration, Business Administration"

12 Wikipedia, "Hungarian Algorithm"

13 R. Sedgewick, "Computer Science226: Data Structures and Algorithms"

14 R. Burkard, "Assignment Problems"

15 Wikipedia, "Assignment Problem"

16 A. Dimitrios, "Applications of a New Network-enabled Solver for the Assignment Problem in Computeraided Education" 1 (1): 19-23, 2005

17 K. Wayne, "Algorithm Design"

18 M. S. Radhakrishnan, "AAOC C222: Optimization"

19 R. M. Berka, "A Tutorial on Network Optimization"