Earticle

초록

영어

This paper proposes an algorithm that easily finds an optimal solution for linear bottleneck assignment problems. It is either threshold or augmenting path algorithm that is generally used to solve the bottleneck assignment problem. This paper proposes a reverse-delete algorithm that follows 2 steps. Firstly, the algorithm deletes the maximum cost in a given matrix until it renders a single row or column. Next, the algorithm improves any solution that contains a cost exceeding the threshold value Cij. Upon its application to 28 balanced assignment problems and 7 unbalanced problems, the algorithm is found to be both successful and simple.

한국어

본 논문은 선형 병목할당 문제의 최적해를 간단히 찾는 알고리즘을 제안하였다. 일반적으로 병목할당 문제 의 최적해는 한계 또는 증대경로 알고리즘으로 구한다. 제안된 알고리즘은 2단계를 수행하는 역-삭제 알고리즘이다. 첫 번째로, 행 또는 열의 개수가 1개가 될 때까지 최대 비용을 삭제하여 초기해를 구한다. 두 번째로 한계치 보다 큰 값이 초기해로 선택되었으면 해를 개선하는 과정을 수행하였다. 제안된 알고리즘을 28개의 병목 균형 할당 문제와 7개의 병목 불균형 할당 문제에 적용한 결과 최적해를 쉽게 찾는데 성공하였다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. LSAP와 LBAP
 Ⅲ. 역-삭제 알고리즘
 Ⅳ. 알고리즘 적용성 평가
 Ⅴ. 결론
 References

키워드

저자

• 이상운 [ Sang-Un, Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380