할당문제에 관한 역-삭제 알고리즘

A Reverse-Delete Algorithm for Assignment Problems

The assignment problem offering an optimal assignment of n jobs to m machines within minimum total processing time has remained a difficult problem. This paper suggests the simplest optimal solution for assignment problem. Generally, the assignment problem is solved with Hungarian algorithm with time complexity . This algorithm reduces 4 steps of Hungarian algorithm to 2 steps with time complexity . Firstly, the maximum cost in matrix is eliminated until the cardinality of either row or column is reduced to 1. Secondly, improvement process is performed for unselected minimum cost. We were able to obtain the optimal solution for the 27 balanced assignment problems and 7 unbalanced problems by applying the suggested algorithm. It is expected that the suggested algorithm could be applied to general assignment algorithm in lieu of Hungarian algorithm.

주어진 개의 작업을 대의 기계가 최소의 시간으로 수행하도록 작업을 배정하는 할당문제는 난제로 알려져 있다. 본 논문은 할당 문제의 최적해를 간단히 찾는 알고리즘을 제안하였다. 일반적으로 할당 문제의 최적해는 수행 복잡도 의 Hungarian 알고리즘으로 구한다. 제안된 알고리즘은 Hungarian 알고리즘의 4단계를 2단계로 단축시켜 수행 복잡도를 으로 감소시켰다. 첫 번째로, 행 또는 열의 개수가 1개가 될 때까지 최대 비용을 삭제한다. 두 번째로 해로 선택되지 않은 최소비용에 대해 해를 개선하는 과정을 수행하였다. 제안된 알고리즘을 27개의 균형 할당 문제와 7개의 불균형 할당 문제에 적용한 결과 최적해를 쉽게 찾는데 성공하였다. 따라서 제안된 알고리즘은 Hungarian 알고리즘을 대체할 수 있는 일반화된 알고리즘으로 적용할 수 있을 것이다.