[논문]PERT 요소공정의 주경로 확률 산정 모델 개발

윤득노; 김태곤; 한이철; 이정재

doi:10.5389/ksae.2010.52.2.027

PERT 요소공정의 주경로 확률 산정 모델 개발
Development Model for Estimating Critical Path Probability of Element Path in PERT 원문보기

한국농공학회논문집 = Journal of the Korean Society of Agricultural Engineers, v.52 no.2, 2010년, pp.27 - 34

윤득노 (서울대학교 생태조경.지역시스템공학부 대학원) , 김태곤 (서울대학교 생태조경.지역시스템공학부 대학원) , 한이철 (서울대학교 생태조경.지역시스템공학부 대학원) , 이정재 (서울대학교 조경.지역시스템공학부, 서울대학교 농업생명과학연구원)

Abstract ▼ AI-Helper

The PERT is one form of probabilistic network and can have many critical paths in the concept of each work has dispersed complete time. Here we propose two operators to estimate the probabilistic complete time about serial and parallel connections, and in each junction node, probability of critical path is estimated by new operator. Then we compare the estimated results with robability of critical path with deterministic CPM and Monte Carlo simulation (MCS). Our results show that all paths in PERT can be critical path, and proposed operators are efficient and accurate probabilistic calculators compare MCS result.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

먼저 복합 SP-네트워크의 내부 SP-네트워크를 Parallel Reduction Operator (PRO)과 컨볼루션을 이용하여 단순 병렬연결 된 SP-네트워크로 축약 변환하고, 단계적으로 단순 병렬연결 된 SP-네트워크를 Probabilistic Critical Path Calculator (PCPC)로 경로별 확률을 계산하면 모든 경로의 주경로가 될 확률을 계산할 수 있다. 본 연구에서는 복합공정으로 계획된 네트워크에서 경로의 확률적 주경로를 계산할 수 있도록 하기 위하여 복합 SP-네트워크의 PCPC 확률계산방법을 제안하고, 타당성을 검증하였다.
기존의 연구들이 보였던 결과 값의 근사적 결점을 보완하기 위해서는 확률연산을 통하여 계산을 줄이면서 정해를 얻는 방법을 생각 할 수 있다. 본 연구에서는 효율적인 확률연산 방법과 직렬 또는 병렬로 연결되는 공정 간의 확률계산을 종합할 수 있는 방법을 SP-네트워크를 대상으로 고안하고자 하였다.
그러나 이것은 네트워크 전체 노드의 「완료시간-확률」 분포 성격을 반영하지 못한다. 이를 개선하기 위해 본 연구에서는 컨볼루션, PRO, PCPC를 이용하여 모든 경로에 대하여 주경로가 될 확률을 구하였다.

가설 설정

이 PERT 네트워크는 한번 완료된 경로는 반복되지 않으며 (acyclic), ①에서 시작되어 ⑪로 진행된다 (direction). 제안된 네트워크는 폐쇄되어 있고, 순수직렬과 병렬연결로 구성된 SP-네트워크 (Series Parallel - Network)로서, 각 노드들이 가지는 확률적인 평균 소요시간과 표준편차, 분포형태를 Table 1과 같이 가정하였다.

제안 방법

Van Slyke (1963), Burt (1970), Dodin (1984) 등은 일반 적으로 의사난수가 난수에 가까운 경우 MCS의 결과를 신뢰할 수 있다고 하였다. 따라서 본 연구의 결과를 의사난수를 이용한 MCS 결과를 비교하여 검증하였다. 또, Malcom et al.
마찬가지로 ② → (④,⑤) → ⑨를 등가의 노드인 ⑭로, ③ → (⑥,⑦,⑧) → ⑩을 등가의 노드인 ⑮로 축소한 뒤에 , ① → ⑭ → ⑪, ① → ⑮ → ⑪을 대상으로 PCPC을 이용하여 확률적 주경로를 계산하였다.
따라서 노드 i, 노드 j의 「완료시간-확률」 분포를 단일 확률분포로 나타내어 분기점과 합일점 사이의 연결을 단순 병렬연결로 만들어야한다. 본 연구에서는 Ringer (1969, 1971)가 제안한 컨볼루션을 이용하여 직렬로 연결된 노드를 하나의 동일한 노드로 축약하였다. Ringer가 제안한 직렬 축약에 의한 「완료시간-확률」 분포는 식 (1) (4)와 같다.
이로 인해 CPM은 단일 주경로 외의 다른 노드의 확률적인 요소를 반영하지 못하게 된다. 이를 극복하고자 본 연구에서는 컨볼루션, PRO, PCPC을 이용하여 SP 네트워크를 순수 병렬연결로 만든 뒤 확률적주경로를 구하였고, 결과 값을 MCS을 이용하여 검증하였다. 이를 통해 다음과 같은 결과를 얻었다.
컨볼루션과 PRO을 이용하여 네트워크의 각 노드별 확률분포를 하나의 동일한 「완료시간-확률」 분포로 나타내었다. 이를 이용하여 내부 SP-네트워크를 PCPC 계산을 위한 단순 병렬연결로 축소하였다.
임의의 네트워크를 구성하여 2절에서 구한 컨볼루션 PRO, PCPC의 적응성을 검토하였다 (Fig. 5). 이 PERT 네트워크는 한번 완료된 경로는 반복되지 않으며 (acyclic), ①에서 시작되어 ⑪로 진행된다 (direction).
확률적 주경로를 산정하기 위하여 본 연구에서는 PCPC를 이용하였다. PCPC를 이용한 확률적 주경로를 산정하기 위해서는 대상이 되는 네트워크의 형태가 Fig.
확률적 주경로를, 분기점이 되는 노드 1, 2, 3을 대상으로 PCPC를 이용하여 계산하였다 (Table 2). 그리고 Fig.

이론/모형

따라서 본 연구의 결과를 의사난수를 이용한 MCS 결과를 비교하여 검증하였다. 또, Malcom et al. (1959)이 제안한 방법에 따라 CPM 방법과도 비교하였다. MCS에서 사용되는 난수는 1,000,000회 계산을 기준으로 하여 결과를 도출하였다.

성능/효과

1. 컨볼루션과 PRO을 이용하여 네트워크의 각 노드별 확률분포를 하나의 동일한 「완료시간-확률」 분포로 나타내었다. 이를 이용하여 내부 SP-네트워크를 PCPC 계산을 위한 단순 병렬연결로 축소하였다.
2. CPM은 결정론적 방법으로 단일 주경로를 구하고 있다. 그러나 이것은 네트워크 전체 노드의 「완료시간-확률」 분포 성격을 반영하지 못한다.
3. 본 연구에서 구한 확률적 주경로는 MCS에 의한 결과에1 % 미만의 오차로 근접하였다. 이를 통해 본 연구에서 제시한 컨볼루션, PRO, PCPC을 이용한 확률적 주경로 산정이 유의한 수준에서 정확하다고 판단된다.
5. 본 연구에서 제안한 연산자는 MCS보다 능률적으로 주경로 결과 값을 도출하였다.
Table 3의 결과는 기존 CPM에 의할 경우 단일 Path 2를 주경로가 되는데 반하여 본 연구의 결과는 모든 경로가 주경로로 될 수 있음을 보이고 있다는 것을 확인 할 수 있다. 이결과는 MCS에서도 공히 확인할 수 있어서 결정론적 CPM의 한계를 잘 보여주고 있으며, 결정론이 path 2를 주경로로 채택하고 있으나 본 연구 및 MCS는 오히려 path 3이 주경로가 될 확률이 가장 높은 것으로 나타나 CPM으로 구한 주경로가 가장 중요한 경로가 아닐 수도 있음을 보이고 있다.
본 연구에서 PCPC를 이용한 결과 값의 도출 시간과 동일한 시간 안에 MCS를 마치기 위한 난수의 값은 약 50,000번으로 측정 되었다. 반면, 본 연구의 결과 값을 검증하기 위해 설정한 1,000,000번의 난수는 PCPC보다 더 많은 계산 소요시간을 나타냈다. 따라서 PCPC는 MCS보다 계산시간의 면에서 유리함을 알 수 있다.
, 2005; Yao and Chu, 2007). 본 연구에서 PCPC를 이용한 결과 값의 도출 시간과 동일한 시간 안에 MCS를 마치기 위한 난수의 값은 약 50,000번으로 측정 되었다. 반면, 본 연구의 결과 값을 검증하기 위해 설정한 1,000,000번의 난수는 PCPC보다 더 많은 계산 소요시간을 나타냈다.
Table 3의 결과는 기존 CPM에 의할 경우 단일 Path 2를 주경로가 되는데 반하여 본 연구의 결과는 모든 경로가 주경로로 될 수 있음을 보이고 있다는 것을 확인 할 수 있다. 이결과는 MCS에서도 공히 확인할 수 있어서 결정론적 CPM의 한계를 잘 보여주고 있으며, 결정론이 path 2를 주경로로 채택하고 있으나 본 연구 및 MCS는 오히려 path 3이 주경로가 될 확률이 가장 높은 것으로 나타나 CPM으로 구한 주경로가 가장 중요한 경로가 아닐 수도 있음을 보이고 있다. 이는 각 노드의 평균적인 완료시간 뿐만 아니라 분산이 전체 공정에 미치는 효과에 의해 발생한다고 판단된다.
9는 MCS가 난수가 커짐에 따라 PCPC에 근사하고 있음을 나타낸다. 이로부터 모든 경로의 확률적 주경로를 검토함에 있어 PCPC가 MCS에 비하여 적은 계산시간 동안에 신뢰도가 높은 수준의 결과 값을 도출 할 수 있음을 알 수 있었다.
본 연구에서 구한 확률적 주경로는 MCS에 의한 결과에1 % 미만의 오차로 근접하였다. 이를 통해 본 연구에서 제시한 컨볼루션, PRO, PCPC을 이용한 확률적 주경로 산정이 유의한 수준에서 정확하다고 판단된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	PERT의 기능은?	프로젝트 관리에 필요한 예상 완료시간, 여유시간과 각 공정의 우선순위를 판단하는 데에는 Process Estimation and Review Technique (PERT)가 가장 널리 이용되고 있다(Robillard and Trahan, 1977; Soroush, 1994; Chen and Chang, 2001). PERT는 가장 긴 완료시간을 나타내는 경로인 주경로 (critical path)를 파악하고 주경로를 기준으로 다른 경로에 속한 노드별 여유시간을 산정한다. 따라서 PERT의 연구에 있어 주경로의 산정은 완료시간 및 여유시간의 계산에 영향을 줄 뿐만 아니라 (Chen et al.
	Critical Path Method의 단점은?	CPM은 각 공정별 완료시간을 상수로 가정하고, 이를 순차적으로 더하여 가장 긴 완료시간을 갖는 경로를 주경로로 정의하므로 단일한 값이 산출 된다 (Dodin, 1984; Liang and Han, 2004). 그러나 공정별 완료시간은 확률적 성격을 갖기 때문에 주경로는 확률의 문제가 될 수밖에 없고, 모든 경로가 주경로가 될 확률이 있는 데도 불구하고 CPM은 이를 반영하지 못하고 있다.(Dodin, 1984; Dodin and Sirvanci, 1990; Williams, 1992; Soroush, 1994; Yang and Chen, 2000).
	PERT의 연구에서 주경로 산정은 무엇에 영향을 주는가?	PERT는 가장 긴 완료시간을 나타내는 경로인 주경로 (critical path)를 파악하고 주경로를 기준으로 다른 경로에 속한 노드별 여유시간을 산정한다. 따라서 PERT의 연구에 있어 주경로의 산정은 완료시간 및 여유시간의 계산에 영향을 줄 뿐만 아니라 (Chen et al., 1997), 프로젝트의 병목현상과 과부하 등을 사전에 예측하여 방지하도록 도움을 준다(Van Slyke, 1963). 또 주경로 상에 있는 공정의 지연은 전체 프로젝트 완료시간을 지연시키므로 (Chen et al.

참고문헌 (23)

Burt, J. M. Jr., 1970. Monte Carlo techniques for stochastic network analysis, In Winter Simulation Conference, No. 9, 146-153. New York, United States.: IEEE.
Burt, J. M. and M. B. Garman, JR., 1971. Conditional Monte Carlo: A simulation technique for stochastic network analysis, In Management Science 8(3): 207-217.

상세보기
Chen, S. and T. Chang, 2001. Finding multiple possible critical path using fuzzy PERT, In Institute of Electrical and Electronics Engineers 31(6): 930-937.

상세보기
Chen, Y., Dan R. and Kwei T., 1997. Critical path in an activity network with time constraints, In European Journal of Operational Research 100(1): 122-133.

상세보기
Dodin, B., 1984. Determining the K most critical paths in PERT networks, In Operator Research Society of America 32(4): 859-877.

상세보기
Dodin, B. and S. E. Elmaghraby 1985. Approximating the distribution functions in stochastic networks, In Computer and Operation Research 12(3): 251-264.

상세보기
Dodin, B. and M. Sirvanci., 1990. Stochastic networks and the extreme value distribution, In Computer and Operation Research 17(4): 397-409.

상세보기
Elmaghraby S. E., 2000. On criticality and sensitivity in activity networks, In European Journal of Operational Research 127(2): 220-238.

상세보기
Fatemi Ghomi, S. M. T. and E. Teimouri, 2001. Path critical index and activity critical index in PERT networks, In European Journal of Operational Research

상세보기
Fulkerson, D. R., 1962. Expected critical path length in PERT networks, In Operations research 10(6): 808-817.

상세보기
Gong, D. and J. E. Rowings Jr, 1995. Calculation of safe float use in risk-analysis-oriented network scheduling, In International Journal of Project Management 13(3): 187-194.

상세보기
Lee, J., H. Yi, M. Park and J. Lee, 2005. An investigation of project completion time estimation method in PERT network for planning and management in large-scale systems, In Proc. of the Korean Society of Agricultural Engineerings Conference 695-699.
Liang G. and T. Han, 2004. Fuzzy critical path for project network, In Information and Management Science 15(4): 29-40.
Malcom, D. G., J. H. Roseboom, C. E. Clack and W. Fazar, 1959. Application of a technique for research and development program Evaluation, In Operations

상세보기
Ringer, L. J., 1969. Numerical operators for statistical PERT critical path analysis, In Management Science 16(2): 136-143

상세보기
Ringer, L. J., 1971. A statistical theory for PERT in which completion times of activities are inter-dependent, Management Science 17(11): 717-723.

상세보기
Robillard, P. and M. Trahan, 1977. The completion time of PERT networks, In Operations Research 25(1): 15-29.

상세보기
Sigal, C. E., A. A. B. Pritsker and J. J. Solberg, 1979. The use of cutsets in Monte Calros analysis of stochastic network, In Mathematic and Computers in Simulation 21(4): 376-384.

상세보기
Soroush H. M., 1994. The most critical path in a PERT network, In Operational Research Society 45(3): 287-300.

상세보기
Van Slyke, R. M., 1963. Monte Carlo method and the PERT problem, In Operations Research and the Management Sciences 11(5): 839-860.

상세보기
Williams T. M., 1992. Criticality in stochastic networks, In Operational Research Society 43(4): 353-357.

상세보기
Yang, H. and Y. Chen, 2000. Finding the critical path in an activity network with time-switch constraints, In European Journal of Operational Research 120: 603-613.

상세보기
Yao, M. and W. Chu, 2007. A new approximation algorithm for obtaining the probability distribution function for project complement time, In Computers and Mathematics with Applications 54(2): 282-295.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증