Assignment Problem Algorithm Based on the First Selection Method of the Minimum Cost
Sang-Un Lee · 한국인터넷방송통신학회 논문지 · 2013
Abstract This paper proposes an algorithm that seeks the optimal solution for an assignment problem through a simplified process. Generally it is Hungarian algorithm that is prevalently used to solve a given assignment problem. The proposed algorithm reduces 4 steps Hungarian algorithm into 2 steps. Firstly, the algorithm selects the minimum cost from a matrix and deletes the rest of the rows and columns. Secondly, it improves on the solution through reassignment process. For 27 balanced assignment problems and 7 unbalanced problems, the proposed algorithm has successfully yielded the optimal solution, which Genetic algorithm has failed. This algorithm is thus found to be an appropriate replacement of Hungarian algorithm. Key Words : Hungarian algorithm, Balanced assignment, Unbalanced assignment, Minimum cost, Optimal solution * 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과접수일자 : 2013년 03월 11일, 수정완료 : 2013년 9월 20일게재확정일자 : 2013년 10월 11일Received: 11 March, 2013 / Revised: 20 September, 2013 /Accepted: 11 October, 2013