최대후회 최소화 임계 경로 탐색 알고리듬
A Heuristic Algorithm to Find the Critical Path Minimizing the Maximal Regret
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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. Then the computational experiments shows the proposed algorithm contributes to the improvement of solution compared with the existing heuristic algorithms.
Abstract
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. Then the computational experiments shows the proposed algorithm contributes to the improvement of solution compared with the existing heuristic algorithms.
참고문헌 (15)
- Averbakh,I, "Interval data minmax regret network optimization problems", Discrete Applied Mathematics, 138, pp.289~301 (2004)
- Chanas,S, "The computational complexity of the criticality problems in a network with interval activity times", European Journal of Operational Research, 136(3), pp.541~550 (2002)
- Conde,E, "A minmax regret approach to the critical path method with task interval times", European Journal of Operational Research, 197(1), pp.235~242 (2009)
- Eppstein,D, "Finding the k shortest paths", SIAM Journal on Computing, 28(2), pp.652~673 (1998)
- Inuiguchi,M, "Minimax Regret Solution To Linear-Programming Problems With An Interval Objective Function", European Journal of Operational Research, 86(3), pp.526~536 (1995)
- 강준규, "불확실성 하의 최장경로문제에서 최대후회 최소화 경로 탐색 알고리듬", 한국경영공학회지, 14(3), pp.169~182 (2009), 한국경영공학회
- 강준규, "불확실성 하에서 최대후회 최소화 분해 계획", 산업경영시스템학회지, 32(4), pp.192~202 (2009), 한국산업경영시스템학회
- Kang,J.-G, "A Product Lifecycle Costing System with Imprecise End-of-Life Data", The 14th CIRP Conference on Life Cycle Engineering (2007), Waseda University
- Kang,J.-G, "Disassembly Sequencing with Imprecise Data:a Case Study", International Journal of Industrial Engineering-Theory,Applications and Practice, 10(4), pp.407~412 (2003)
- [URL]
- Kasperski,A, "An approximation algorithm for interval data minmax regret combinatorial optimization problems", Information Processing Letters, 97(5), pp.177~180 (2006)
- Kouvelis,P, "Robust Discrete Optimization and Its Application" (1997), Kluwer Academic Publishers
- Montemanni,R, "An Exact Algorithm for the Robust Shortest Path Problem with Interval Data", Computers and Operations Research, 31(10), pp.1667~1680 (2004)
- Montemanni,R, "A branch and bound algorithm for the robust spanning tree problem with interval data", European Journal of Operational Research, 161(3), pp.771~779 (2005)
- Zieliski,P, "The computational complexity of the relative robust shortest path problem with interval data", European Journal of Operational Research, 158(3), pp.570~576 (2004)