[논문]대기행렬모형에 의한 워크플로우 시간분석

박진수

doi:10.9709/jkss.2014.23.3.001

대기행렬모형에 의한 워크플로우 시간분석
A Workflow Time Analysis Applying the Queueing Model 원문보기

한국시뮬레이션학회논문지 = Journal of the Korea Society for Simulation, v.23 no.3, 2014년, pp.1 - 9

박진수 (용인대학교 경영정보학과)

초록
AI-Helper

전통적인 워크플로우 시간분석은 단위작업을 독립적인 M/M/1 대기행렬모형에 적용하여 수행해왔다. M/M/1 시스템 성능척도의 일반해들을 활용하면 여러 가지 분석이 가능해진다. 특히 워크플로우 시스템의 AND 구조를 분석함에 있어 M/M/1 시스템 성능척도를 활용하면 그 체재시간에 대한 분석이 가능하다. 그러나 실질적인 AND 구조를 정확히 묘사하기 위해서는 각각의 M/M/1 시스템이 독립이라는 가정이 없어야 한다. 본 연구는 이러한 한계를 극복하기 위해 한 업무에 대한 모든 단위작업이 동시에 시작하는 상황으로 가정한다. 이 가정 하에서는 M/G/1 시스템의 성능척도를 이용하여 이론적 분석이 가능해진다. 또한 시뮬레이션을 이용하여 실질적인 AND 구조를 정확히 묘사할 수 있는 방법론을 소개한다. 마지막으로 가상의 시스템을 구성하여 이론적인 해와 시뮬레이션 결과들을 수록함으로써 제안된 방법론들을 검증한다. 본 연구에서 사용된 주요 시스템 성능척도는 평균대기시간과 평균체재시간이다.

Abstract ▼ AI-Helper

Traditional workflow time analyses have been performed treating an activity as an independent M/M/1queueing system. Using the general forms of performance measures in the M/M/1 system, various aspects of analyses can be performed. Especially, on the time analysis of an AND structure in a workflow system, the mean system sojourn time can be formalized by applying the performance measures of M/M/1 system. In the real workflow system, the AND structure cannot be described correctly under the assumption of independent M/M/1 systems. To overcome this limitation, this research makes the assumption that the all activities for a task starts simultaneously. In this situation, the theoretical solution can be derived using the performance measures of the M/G/1 system. In addition, the simulation modeling method will be proposed to analyze the AND structure of a real workflow system. Finally, some numerical results from the theoretical solutions and simulation models will be provided for verification. The main performance measures used in this research are mean queueing time and mean sojourn time.

주제어

AI 본문요약
AI-Helper

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

문제 정의

[11]이 제안한 AND 구조의 워크플로우 분석에 대한 일반화 및 확장 분석 방법을 소개한다(본 논문에서는 편의상 Truong et al.의 분석 방법을 기존연구라 칭하겠다). 먼저 기존연구에서의 시스템 가정과 그 분석결과를 간략히 살펴보자.
이러한 가정을 갖는 시스템은 기존연구에서 제안된 AND 시스템과는 절차상에 있어 상이한 형태이지만 시스템 체재시간은 물론 대기시간과 최종 서비스시간에 대한 분석이 가능하게 해준다. 더불어 본 논문에서는 이를 AND 구조의 입력과 서비스가 지수분포가 아닌 일반 분포인 경우에 대해서도 확장하여 분석하고, 시뮬레이션 모델을 통해 단위작업의 동시시작 가정이 없는 경우에 대한 분석결과도 제시하고자 한다.
마지막으로 가상의 시스템을 구성하여 이를 제안된 분석방법대로 계산하고 시뮬레이션 수행결과와 비교하여 검증하였다. 또한 시뮬레이션 결과를 통해 기존연구의 활용 가능성을 검토하였다.
이러한 상황 하에서는 AND 구조 자체가 M/G/1 시스템으로 설명되며 그 일반해를 이용하면 평균대기시간과 평균체재시간을 이론적으로 유도할 수 있다. 아울러 본 논문에서는 단위작업의 동시시작 가정이 없는 시스템의 분석을 위한 대안으로 상세한 시뮬레이션 알고리즘을 제안한다.

가설 설정

Fig. 1의 AND 구조 시스템을 확장하여 Xi들의 작업 시간이 각각 E(Xi) = 1/μi 인 일반분포 Fi(•)을 따른다고 가정해보자.
1의 점선으로 구성된 부분, 즉 단위작업 A가 끝난 시점부터 단위작업 B가 시작하기 직전까지이다. 기존 연구에서는 X₁부터 X_n까지의 작업을 모두 독립적인 M/M/1 모형으로 가정하여 분석하였다.
1과 같은 시스템을 가정한다. 기존연구와의 다른 점은 선행 업무의 모든 작업이 완료된 이후 다음 업무가 시작된다고 가정하며 각 단위작업 X_i들은 서로 독립이라는 것이다. 이 가정에 의해 모든 단위작업이 동시에 시작하는 상황이 이루어진다.
는 M/M/1 시스템으로 설명되지만 이를 AND 구조로 아우르면 독립적인 M/M/1 시스템만으로는 설명할 수 없게 된다. 따라서 본 연구에서는 모든 단위작업을 동시에 시작하도록 가정을 두고 분석을 시도하였다. 이러한 가정을 갖는 시스템은 기존연구에서 제안된 AND 시스템과는 절차상에 있어 상이한 형태이지만 시스템 체재시간은 물론 대기시간과 최종 서비스시간에 대한 분석이 가능하게 해준다.
체재시간의 의미는 2절에서의 의미와 동일하며 결국 대기시간과 서비스시간의 합으로 계산된다. 마지막으로 대기행렬시스템의 안정상태에 대한 해가 존재하기 위해서는 평균서비스시간이 평균도착간격보다 작아야 한다는 가정을 기본으로 한다.
본 논문에서는 기존의 AND 구조 시스템에 가정을 하나 추가한다. 업무가 도착하면 각 단위작업의 대기열에서 대기하는 것이 아니라 하나의 대기열에서 대기하다가 선행 업무가 종료되면 모든 단위작업을 일제히 시작하는 상황으로 가정한다.
본 논문은 기본적으로 Fig. 1과 같은 시스템을 가정한다. 기존연구와의 다른 점은 선행 업무의 모든 작업이 완료된 이후 다음 업무가 시작된다고 가정하며 각 단위작업 X_i들은 서로 독립이라는 것이다.
본 논문에서는 기존의 AND 구조 시스템에 가정을 하나 추가한다. 업무가 도착하면 각 단위작업의 대기열에서 대기하는 것이 아니라 하나의 대기열에서 대기하다가 선행 업무가 종료되면 모든 단위작업을 일제히 시작하는 상황으로 가정한다. 이는 실제로 컴퓨터 또는 인터넷이 활용되는 IT(information technology) 분야에서 충분히 존재할 수 있는 상황이며 다른 비즈니스프로세스에 대해서도 활용가능한 상황이 존재한다.

제안 방법

의 기존연구[11]에서 제시한 방법으로 계산한 결과를 나타낸다. 기존연구결과로는 단위작업이 M/M/1인 경우에 대해서만, 그리고 평균체재시간만을 구할 수 있으므로 네 시스템 중 시스템 1과 2에 대한 평균체재시간을 계산하여 수록하였다. 수록된 결과에 의하면 시뮬레이션 결과에 대한 기존연구결과의 오차율이 각각 약 5.
물론 단위작업에 대해 M/M/1 시스템을 가정하는 경우 이론적인 해를 구할 수 있으나 본 논문에서는 추후 연구과제로 남겨두도록 하겠다. 대신에 본 논문에서는 시뮬레이션 모델을 이용하여 해당 시스템을 분석하는 방법을 제안한다.
다음 절에서는 이 시스템들을 대상으로 대기행렬모형 분석에 의해 대기시간과 체제시간을 계산하고 시뮬레이션 결과를 통해 이를 검증한다. 또한 단위작업의 동시시작 가정을 제거한 경우의 결과를 보이고 그 중 시스템 1, 2의 결과와 기존연구의 결과를 비교해 보도록 한다. 시뮬레이션은 정확성을 기하기 위해 transient period를 100,000 단위 시간, 수행시간을 1,000,000 단위시간으로 설정하여 100 회 독립반복 수행하였다.
본 논문에서는 대기행렬모형을 이용하여 워크플로우의 AND 구조에 대해 시간분석을 수행하였다. 먼저 기존연구에서 제시된 결과를 고찰하고 그 한계점과 확장 가능성을 제시하였다. 각 업무에 대한 모든 단위작업이 동시에 시작된다고 가정한다면 AND 구조 시스템은 M/G/1 또는 GI/G/1 시스템으로 해석이 가능해진다.
각 분포에 사용되는 모수들은 지수분포의 경우 도착률(λ) 또는 서비스율(μ_i)을 나타내며, Erlang 분포에 사용된 두 번째 모수도 동일한 의미이다. 모수로 사용된 수치들은 각 시스템이 안정상태에 도달할수 있는 조건, 즉 1미만의 서버이용률을 만족하는 수치들로서 경험적 방법에 의해 도출하였다.
본 논문에서는 대기행렬모형을 이용하여 워크플로우의 AND 구조에 대해 시간분석을 수행하였다. 먼저 기존연구에서 제시된 결과를 고찰하고 그 한계점과 확장 가능성을 제시하였다.
본 절에서는 앞서 제시한 이론적 해의 검증과 시스템 확장을 위해 가상의 시스템을 구성하여 이론적 해를 찾아보고 확장된 버전에 대한 시뮬레이션을 수행한다. 본 논문에서는 먼저 Table 1에서 제시된 바와 같이 네 개의 가상 시스템을 구성하였다. Table 1에 제시된 시스템 1과 2는 각 단위작업이 전형적인 M/M/1 시스템들로 구성되어 있다.
본 연구는 워크플로우의 AND 구조를 특정 가정 하에서 분석하여 해를 도출하였으나 가정이 없는 경우에 대해 서는 시뮬레이션 방법론만을 제안하였다. 물론 가정이 없는 경우에 대해서 기존연구의 결과를 활용할 수 있겠지만 정확한 분석을 위해서는 가정이 없는 경우에 대한 이론적 분석을 시도하는 것도 의미 있는 연구라 할 수 있겠다.
본 절에서는 앞서 제시한 이론적 해의 검증과 시스템 확장을 위해 가상의 시스템을 구성하여 이론적 해를 찾아보고 확장된 버전에 대한 시뮬레이션을 수행한다. 본 논문에서는 먼저 Table 1에서 제시된 바와 같이 네 개의 가상 시스템을 구성하였다.
또한 단위작업의 동시시작 가정을 제거한 경우의 결과를 보이고 그 중 시스템 1, 2의 결과와 기존연구의 결과를 비교해 보도록 한다. 시뮬레이션은 정확성을 기하기 위해 transient period를 100,000 단위 시간, 수행시간을 1,000,000 단위시간으로 설정하여 100 회 독립반복 수행하였다.
각 업무에 대한 모든 단위작업이 동시에 시작된다고 가정한다면 AND 구조 시스템은 M/G/1 또는 GI/G/1 시스템으로 해석이 가능해진다. 이를 토대로 평균대시기간과 평균체재시간을 분석하였으며 단위작업의 동시시작 가정이 없는 경우에 대한 시뮬레이션 모델링 방법론을 제시하였다. 마지막으로 가상의 시스템을 구성하여 이를 제안된 분석방법대로 계산하고 시뮬레이션 수행결과와 비교하여 검증하였다.

대상 데이터

즉 단위작업 A를 마치고 나면 X₁부터 X_n까지의 모든 단위작업에 입력되어 이들이 전부 완료되어야지만 단위작업 B에 입력된다. 분석의 대상은 Fig. 1의 점선으로 구성된 부분, 즉 단위작업 A가 끝난 시점부터 단위작업 B가 시작하기 직전까지이다. 기존 연구에서는 X₁부터 X_n까지의 작업을 모두 독립적인 M/M/1 모형으로 가정하여 분석하였다.
워크플로우는 SEQUENCE, AND, XOR, LOOP의 네 가지 구조(structures)로 구성되며 본 연구에서 분석하고자 하는 대상은 AND 구조이다. AND 구조는 여러 개의 단위작업(activity; 본래 사전적 용어가 따로 존재하지만 본 논문에서는 그 의미상 ‘단위작업’으로 기술)을 모두 수행해야 해당 업무 또는 정보처리가 종료되는 형태의 비즈니스프로세스를 지칭한다.

데이터처리

이를 토대로 평균대시기간과 평균체재시간을 분석하였으며 단위작업의 동시시작 가정이 없는 경우에 대한 시뮬레이션 모델링 방법론을 제시하였다. 마지막으로 가상의 시스템을 구성하여 이를 제안된 분석방법대로 계산하고 시뮬레이션 수행결과와 비교하여 검증하였다. 또한 시뮬레이션 결과를 통해 기존연구의 활용 가능성을 검토하였다.

성능/효과

또한 GI/G/1 형태인 시스템 4의 경우 오차가 현저히 높게 나타나는데 이는 이론치가 근사해법에 의한 결과이기 때문이다. 본 논문에 수록하지 않은 별도의 실험결과들을 종합해 본 결과 서버이용률이 1에 근접할수록 이론적 근사해는 참값에 근접하며 그 값이 작을수록 오차가 커진다는 것을 확인하였다. 이는 식 (10)을 유도하는 과정[5]에서 확인할 수 있는 당연한 결과이다.
7%인 것으로 계산된다. 본 논문에 수록하지 않은 여러 실험 결과들을 종합해 볼 때, 서버이용률이 작아질수록 기존연구 결과의 오차는 커지며 커질수록 오차가 작아지는 것을 확인할 수 있었다. 따라서 2장에서 언급했던 바와 같이 기존연구 결과는 서버이용률이 충분히 클 때 해당 시스템에 대한 근사해로 사용가능할 것이다.
기존연구결과로는 단위작업이 M/M/1인 경우에 대해서만, 그리고 평균체재시간만을 구할 수 있으므로 네 시스템 중 시스템 1과 2에 대한 평균체재시간을 계산하여 수록하였다. 수록된 결과에 의하면 시뮬레이션 결과에 대한 기존연구결과의 오차율이 각각 약 5.9%와 5.7%인 것으로 계산된다. 본 논문에 수록하지 않은 여러 실험 결과들을 종합해 볼 때, 서버이용률이 작아질수록 기존연구 결과의 오차는 커지며 커질수록 오차가 작아지는 것을 확인할 수 있었다.
오차율의 결과로 볼 때 본 논문에서 제시한 분석방법 및 그 결과가 타당하다는 것을 확인할 수 있다. 시스템 3의 경우 서버이용률이 0.

후속연구

물론 가정이 없는 경우에 대해서 기존연구의 결과를 활용할 수 있겠지만 정확한 분석을 위해서는 가정이 없는 경우에 대한 이론적 분석을 시도하는 것도 의미 있는 연구라 할 수 있겠다. 또한 본 연구는 단편적인 AND 구조만을 분석하였으나 이를 토대로 전체 워크플로우 시스템을 대기행렬 네트워크로 보고 분석하는 연구도 필요할 것이라 판단된다.
이 가정이 성립하지 않으면 정확한 이론적 해를 구하는 것이 매우 어려워진다. 물론 단위작업에 대해 M/M/1 시스템을 가정하는 경우 이론적인 해를 구할 수 있으나 본 논문에서는 추후 연구과제로 남겨두도록 하겠다. 대신에 본 논문에서는 시뮬레이션 모델을 이용하여 해당 시스템을 분석하는 방법을 제안한다.
3에서 보는 바와 같이 모든 단위작업은 동시에 시작되며 이들이 모두 종료되어야 서비스가 종료된 것으로 판단하고 체재시간과 서비스시간을 계산한다. 본 시뮬레이션 알고리즘은 앞서 분석한 결과를 검증하기 위한 수단으로 사용 가능하며 단위작업의 수가 많아져 이론적 해를 계산하기 힘든 경우에도 활용할 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	AND 구조를 정확히 묘사하기 위해 필요한 것은 무엇인가?	특히 워크플로우 시스템의 AND 구조를 분석함에 있어 M/M/1 시스템 성능척도를 활용하면 그 체재시간에 대한 분석이 가능하다. 그러나 실질적인 AND 구조를 정확히 묘사하기 위해서는 각각의 M/M/1 시스템이 독립이라는 가정이 없어야 한다. 본 연구는 이러한 한계를 극복하기 위해 한 업무에 대한 모든 단위작업이 동시에 시작하는 상황으로 가정한다.
	전통적인 워크플로우 시간분석은 어떻게 수행되었는가?	전통적인 워크플로우 시간분석은 단위작업을 독립적인 M/M/1 대기행렬모형에 적용하여 수행해왔다. M/M/1 시스템 성능척도의 일반해들을 활용하면 여러 가지 분석이 가능해진다.
	본 연구에서 M/M/1 대기행렬모형의 한계를 극복하기 위해 제안한 것은 무엇인가?	그러나 실질적인 AND 구조를 정확히 묘사하기 위해서는 각각의 M/M/1 시스템이 독립이라는 가정이 없어야 한다. 본 연구는 이러한 한계를 극복하기 위해 한 업무에 대한 모든 단위작업이 동시에 시작하는 상황으로 가정한다. 이 가정 하에서는 M/G/1 시스템의 성능척도를 이용하여 이론적 분석이 가능해진다. 또한 시뮬레이션을 이용하여 실질적인 AND 구조를 정확히 묘사할 수 있는 방법론을 소개한다.

참고문헌 (12)

Lee, H.W., Queueing Theory: Stochastic Process Approach, 3rd Edition, Sigma Press, Seoul, pp. 495-876, 2006.
Burke, P.J., "The output of a queueing system", Operations Research, Vol. 4, No. 6, pp. 699-704, 1956.

상세보기
Chang, D.-H., Son, J.H., Kim, M.H., "Critical path identification in the context of a workflow", Information and Software Technology, Vol. 44, pp. 405-417, 2005.
Jeong, K.-Y., Cho, H., Phillips, D.T., "Integration of queueing network and IDEF3 for business process analysis", Business Process Management Journal, Vol. 14, No. 4, pp. 471-482, 2008.

상세보기
Kingman, J.F.C., "The single server queue in heavy traffic", Proceedings of the Cambridge Philosophical Society, Vol. 57, pp. 902-904, 1961.

상세보기
Li, H., Yang, Y., "Dynamic checking of temporal constraints for concurrent workflows", Electronic Commerce Research and Applications, Vol. 4, pp. 124-142, 2005.

상세보기
Marshall, K.T., "Some inequalities in queueing", Operations Research, Vol.16, pp. 651-665, 1968.

상세보기
Reijers, H.A., van der Aalst, W.M.P, "The effectiveness of workflow management systems: Predictions and lessons learned", International Journal of Information Management, Vol. 25, pp. 458-472, 2005.

상세보기
Son, J.H., Kim, M.H., "Improving the performance of time-constrained workflow processing", The Journal of Systems and Software, Vol. 58, pp. 211-219, 2001.

상세보기
Son, J.H., Kim, J.S., Kim, M.H., "Extracting the workflow critical path from the extended well-formed workflow schema", Journal of Computer and Systems Sciences, Vol. 70, pp. 86-106, 2005.

상세보기
Truong, N.K.V, Choi, Y., Kim, I., Shin, S., Hwang, W.J., "A Probabilistic Approach to Workflow Time Analysis for Business Process Mangement", International Journal of Human and Social Sciences, Vol. 5, No. 12, pp. 811-815, 2010.
Zhuge, H., Cheung, T., Pung, H., "A timed workflow process model", The Journal of Systems and Software, Vol. 55, pp. 231-243, 2001.

상세보기

표제어: 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

연합인증