개선된 한계 알고리즘을 적용한 선형병목할당문제 (A Linear Bottleneck Assignment Problem Using Improved Threshold Algorithm)

서지정보

· 발행기관 : 한국정보기술학회
· 수록지 정보 : 한국정보기술학회논문지 / 14권 / 2호 / 125 ~ 133페이지
· 저자명 : 이상운

초록

본 논문은 선형 병목할당 문제(LBAP)의 최적 해를 간단히 찾는 알고리즘을 제안하였다. LBAP는 전형적인 할당 문제(AP)의 변형으로 동일한 수의 작업자에게 할당 된 작업들에 관한 완료시간 합 대신 가장 긴 완료시간을 최소화 시키는 것이 목적이다. 일반적으로 병목할당 문제의 최적 해는 한계나 수송문제 알고리즘으로 구한다. 그러나 AP에 대한 변환된 할당 행렬 원소들이 컴퓨터 프로그램으로 다루기에는 너무 큰 관계로 이들 방법의 적용성에 한계가 있다. 제안된 알고리즘은 행과 열의 최소치들 중에서 최대치인 한계치를 이용하여 최적 해를 구하는 방법을 적용하였다. 첫 번째로, 행과 열의 최소치를 구하고, 이들 중 최대치인 한계치보다 큰 비용은 삭제한다. 남아 있는 비용들 중에서 행이나 열에 1개 이상 존재하는 비용에 대해 최대치부터 삭제하는 방법을 적용하였다. 마지막으로 총비용을 감소시키는 최적화 과정이 수행되었다. 제안된 알고리즘을 29개의 병목 균형 할당 문제와 7개의 병목 불균형 할당 문제에 적용한 결과 최적 해를 쉽게 찾을 수 있었다.

영어초록

This paper suggests the simple linear bottleneck assignment problems (LBAP) to find the optimal solution. The LBAP, which is a variation of the classical assignment problem (AP), seeks to minimize the longest completion time rather than the sum of the completion times when a number of jobs are to be assigned to the same number of workers. Generally, the bottleneck assignment problem can be solved by threshold or transportation algorithm. However, their applicability is limited because some of the elements in the transformed assignment matrix for the AP can be too large to be handled by most computer programs. The proposed algorithm selects threshold value that is maximum cost among the minimum cost for each row and column. The costs in matrix are deleted more than threshold value. Then deletes the maximum cost in matrix until the number of cost in a row or a column is one. Finally, the optimization process has performed to reduce the total cost. For the 29 balanced bottleneck assignment problem and 7 unbalanced problem, this algorithm can be simply finds the optimal solution.

참고자료

· 없음