지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2012.8
- 수록면
- 117 - 126 (10page)
이용수
초록· 키워드
오류제보하기
주어진 n개의 작업을 m대의 기계가 최소의 시간으로 수행하도록 작업을 배정하는 할당문제는 난제로 알려져 있다. 본 논문은 할당 문제의 최적해를 간단히 찾는 알고리즘을 제안하였다. 일반적으로 할당 문제의 최적해는 수행 복잡도 O(n<SUP>2</SUP>)의 Hungarian 알고리즘으로 구한다. 제안된 알고리즘은 Hungarian 알고리즘의 4단계를 2단계로 단축시켜 수행 복잡도를 O(mn)으로 감소시켰다. 첫 번째로, 행 또는 열의 개수가 1개가 될 때까지 최대 비용을 삭제한다. 두번째로 해로 선택되지 않은 최소비용에 대해 해를 개선하는 과정을 수행하였다. 제안된 알고리즘을 27개의 균형 할당 문제와 7개의 불균형 할당 문제에 적용한 결과 최적해를 쉽게 찾는데 성공하였다. 따라서 제안된 알고리즘은 Hungarian 알고리즘을 대체할 수 있는 일반화된 알고리즘으로 적용할 수 있을 것이다.
목차
요약
Abstract
I. 서론
II. 관련 연구와 연구 배경
III. 역-삭제 알고리즘
IV. 알고리즘 적용성 평가
V. 결론
참고문헌
참고문헌 (22)
참고문헌 신청
1. [단행본] - B. Rainer / 2009 / Assignment Problems / SIAM
2. [학술지(정기간행물)] - H. W. Kuhn / 1955 / The Hungarian Method for the Assignment Problem / Naval Research Logistics Quarterly 2 (1) : 83 ~ 97
3. [단행본] - L. Ntaimo / 2005 / Introduction to Mathematical Programming: Operations Research: Chapter 7. Transportation and Assignment Problems / Pacific Grove, CA : 924 ~
4. [인터넷자원] - K. Kinahan / / Algorithm Animations for Practical Optimization: A Gentle Introduction
5. [인터넷자원] - D.N.Kumar / / Optimization Methods
2. [학술지(정기간행물)] - H. W. Kuhn / 1955 / The Hungarian Method for the Assignment Problem / Naval Research Logistics Quarterly 2 (1) : 83 ~ 97
3. [단행본] - L. Ntaimo / 2005 / Introduction to Mathematical Programming: Operations Research: Chapter 7. Transportation and Assignment Problems / Pacific Grove, CA : 924 ~
4. [인터넷자원] - K. Kinahan / / Algorithm Animations for Practical Optimization: A Gentle Introduction
5. [인터넷자원] - D.N.Kumar / / Optimization Methods
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2013-566-003392281