최대후회 최소화 임계 경로 탐색 알고리듬

• 영문명: A Heuristic Algorithm to Find the Critical Path Minimizing the Maximal Regret
• 발행기관: 한국산업경영시스템학회
• 저자명: 강준규
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2010년 추계학술대회 논문집, 1~7쪽, 전체 7쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2010.11.30

영문 초록

Finding the critical path (or the longest path) on acyclic directed graphs, which is well-known as PERT/CPM, the ambiguity of each acr's length can be modeled as a range or an interval, in which the actual length of arc may realize. In this case, the min-max regret criterion, which is widely used in the decision making under uncertainty, can be applied to find the critical path minimizing the maximum regret in the worst case. Since the min-max regret critical path problem with the interval arc's lengths is known as NP-hard, this paper proposes a heuristic algorithm to diminish the maximum regret and the computational experiments shows the proposed algorithm contributes to the improvement of solution compared with the existing heuristic algorithms.

목차

1. 서 론

2. A Heuristic Algorithm and Improvement

3. Computational Experiments

4. 결론 및 추후연구

키워드

Minmax Regret Interval Data Robust Shortest Path