[논문]시스템 내 고객 수에 따라 서비스율과 도착율을 조절하는 M/G/1/K 대기행렬의 분석

최두일; 임대은

doi:10.9709/jkss.2015.24.3.027

시스템 내 고객 수에 따라 서비스율과 도착율을 조절하는 M/G/1/K 대기행렬의 분석
Analysis of an M/G/1/K Queueing System with Queue-Length Dependent Service and Arrival Rates 원문보기

한국시뮬레이션학회논문지 = Journal of the Korea Society for Simulation, v.24 no.3, 2015년, pp.27 - 35

초록
AI-Helper

대기행렬 시스템에는 고객들의 대기시간이 지나치게 길어지는 것을 막기 위해 다양한 정책들이 적용되는데, 본 연구에서는 고객숫자에 따른 제어 정책을 갖는 유한용량 M/G/1/K 대기행렬을 분석한다. 고객의 숫자에 따라 서버의 서비스율과 고객의 도착율을 조절하는 정책이다. 두 개의 한계점(thresholds) $L_1$과 $L_2$($${\geq_-}$$L1)를 설정하고 시스템 내 고객의 숫자가 $L_1$보다 작을 때는 시스템은 보통(또는 상대적으로 느린)의 서비스율(service rate)과 보통의 도착율(arrival rate)을 갖는다. 고객의 숫자가 증가하여 $L_1$이상이고 $L_2$보다 작으면 도착율은 그대로 이지만 서비스율을 증가시켜 빠르게 서비스한다. 이후 고객의 숫자가 더욱 증가하여 $L_2$ 이상이면 고객의 도착율도 작은 값으로 바꾸어 고객을 덜 입장시킨다. 위 정책을 갖는 M/G/1/K 대기행렬을 내재점 마코프 체인과 준-마코프 과정을 이용하여 분석하고 수치예제를 제시한다.

Abstract ▼ AI-Helper

We analyze an M/G/1/K queueing system with queue-length dependent service and arrival rates. There are a single server and a buffer with finite capacity K including a customer in service. The customers are served by a first-come-first-service basis. We put two thresholds $L_1$ and $L_2$($${\geq_-}L_1$$ ) on the buffer. If the queue length at the service initiation epoch is less than the threshold $L_1$, the service time of customers follows $S_1$ with a mean of ${\mu}_1$ and the arrival of customers follows a Poisson process with a rate of ${\lambda}_1$. When the queue length at the service initiation epoch is equal to or greater than $L_1$ and less than $L_2$, the service time is changed to $S_2$ with a mean of $${\mu}_2{\geq_-}{\mu}_1$$. The arrival rate is still ${\lambda}_1$. Finally, if the queue length at the service initiation epoch is greater than $L_2$, the arrival rate of customers are also changed to a value of $${\lambda}_2({\leq_-}{\lambda}_1)$$ and the mean of the service times is ${\mu}_2$. By using the embedded Markov chain method, we derive queue length distribution at departure epochs. We also obtain the queue length distribution at an arbitrary time by the supplementary variable method. Finally, performance measures such as loss probability and mean waiting time are presented.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 연구는 서버의 서비스율과 고객의 도착율을 모두 조절하는 대기행렬을 분석한다. 대기하는 고객수가 증가할 때 먼저 서비스율을 조절하고, 그래도 고객수가 증가하는 경우에는 도착율을 조절하는 정책으로 이를 해석적 (analytic)으로 분석한다.
본 연구는 앞서 소개된 모형들과 달리 서비스율과 도착율 두 가지 모두를 조절하는 새로운 정책에 관한 것이다. 두 가지 모두를 조절하는 정책 자체가 새로운 것은 아니지만, 기존 연구들과는 접근방법과 관심사가 다르다.
본 연구에서는 시스템에 있는 고객의 숫자에 따라 서비스율과 도착률을 조절하는 M/G/1/K 대기행렬을 해석적으로 분석하고 수치예제를 통해 시스템의 특성을 살펴보았다. 이러한 정책은 실제 통신 시스템이나 제조 시스템에서 높은 수준의 쓰루풋을 달성하기 위해 적용되고 있다.
본 연구의 모형에는 재시도 공간이 없으며 대기공간을 가정하여 분석한다. 정리하면, 본 연구는 기존 연구들과 달리 도착율과 서비스율을 모두 조절하는 M/G/1/K 모형에 관한 새로운 분석이다. 이 정책은 보다 현실적인 것으로, 서론의 반도체 제조라인의 예시와 같이 현실 문제에서는 혼잡도 해소를 위해 한 가지의 정책만을 적용하는 것이 아니라 여러 정책도 함께 또는 차례대로 적용하는 것을 반영한 것이다.

가설 설정

고객 숫자가 증가했으니 신속히 처리하려는 것을 가정하여 μ2 ≦ μ1으로 설정한다.
고객의 도착도 두 종류의 포아송 과정 (Poisson process)를 가정하는데 이 둘은 동일한 과정이지만 발생률만 다르며 각각 λ1과 λ2로 발생률을 표시한다.
그래도 고객수가 증가하여 L2이상이 되면 이제는 고객의 도착률을 λ2로 전환하는데 상대적으로 적은 숫자의 고객이 도착하게 하여 대기고객수를 줄여야 하므로λ2 ≦ λ1을 가정한다.
따라서 평균 고객수가 순서대로 차례를 기다리는 사람들의 숫자가 아닌 재시도 공간에서 재시도하고 있는 고객의 숫자이다. 본 연구의 모형에는 재시도 공간이 없으며 대기공간을 가정하여 분석한다. 정리하면, 본 연구는 기존 연구들과 달리 도착율과 서비스율을 모두 조절하는 M/G/1/K 모형에 관한 새로운 분석이다.
시스템에 고객이 총 K명일 때 도착하는 고객은 대기 공간에 입장할 수 없다. 서비스 시간의 분포는 두 종류의 임의의 일반 분포(general distribution)를 가정한다. 두 종류의 서비스 시간에 대한 확률변수는 각각 S₁과 S₂로 표시하며, 이들의 라플라스 변환(Laplace transform)은 G*₁(s)와 G*₂(s)으로 정의한다.
그리고 K = 15도 공통적으로 적용되었다. 제어정책이 없는 모형은 도착률과 서비스율이 변하지 않으므로 각각 5와 8을 가정하였다. 제어정책이 있는 모형에 대해서는 도착률은 λ₁ = 5과 λ₂ = 3로, 서비스율은 1/μ₁ = 6과 1/μ₂ = 8로 설정했다.

제안 방법

본 장에서는 먼저 분석 대상 모형을 소개하고 기호들을 정의한다. 그리고 서비스 종료시점(이탈시점)을 내재점으로 갖는 내재점 마코프 체인(embedded Markov chain)을 이용하여 이탈 시점의 고객수 분포를 도출한다. 이에 부가변수법(supplementary variable technique)을 적용하여 임의시점의 고객수 분포를 유도한다.
이에 부가변수법(supplementary variable technique)을 적용하여 임의시점의 고객수 분포를 유도한다. 그리고 평균 대기시간, 시스템 내 평균 고객수와 시스템이 꽉 차서 도착하는 고객의 입장이 거부될 확률 등의 성능지표들을 제시한다.
본 연구에서는 시스템 내 고객 숫자에 따라 고객의 도착율(arrival rate)과 서버의 서비스율(service rate)이 조절되는 유한용량 M/G/1/K 대기행렬을 다룬다. 먼저 시스템에는 서비스 받는 고객을 포함하여 최대 K명까지 입장이 가능하며 도착 순서에 따라 서비스를 제공(First-Come, First-Served)한다.
이번에는 시스템 내 고객 숫자에 따른 제어 정책이 없는 M/G/1/K 모형과 본 연구에서 소개한 제어정책을 적용한 M/G/1/K 모형의 성능을 비교한다. 서비스 시간의 분포는 모수가 5인 얼랑 분포와 지수분포를 가정하여 제어정책이 있는 모형과 없는 모형 모두에 적용하였다. 그리고 K = 15도 공통적으로 적용되었다.
이번에는 시스템 내 고객 숫자에 따른 제어 정책이 없는 M/G/1/K 모형과 본 연구에서 소개한 제어정책을 적용한 M/G/1/K 모형의 성능을 비교한다. 서비스 시간의 분포는 모수가 5인 얼랑 분포와 지수분포를 가정하여 제어정책이 있는 모형과 없는 모형 모두에 적용하였다.
임의시점 고객수 분포를 이용하여 시스템에 있는 고객들 숫자의 평균값과 평균 대기시간을 구할 수 있다. 이후 수치예제를 통해 확률분포의 변동 계수 및 한계점에 대한 정책을 변화시키면서 시스템의 특성을 연구하였다. 본 연구는 기존 연구들에서 분석되지 않은 새로운 모형을 분석하고 수치예제를 통해 정책의 특성을 연구했다는 점에서 기여도를 찾을 수 있을 것이며, 추후 연구로 적절한 비용 구조(cost structure)를 설계한 뒤 보다 경제적인 운용방법을 고안해보는 것도 기대할 수 있을 것이다.
본 연구의 중요성은 다음과 같이 설명할 수 있다. 제시되는 모형은 기존 연구들에서 소개되지 않았던 것으로 서비스율과 도착율을 모두 조절하는 혼잡도 조절정책을 갖는다. 분석되지 않았던 모형을 해석적으로 분석하여 고객수 분포 및 대기시간 등의 성능 지표를 제시하며, 여러 혼잡도 제어정책이 혼합 적용되는 현실을 볼 때 기존 모형 대비 보다 높은 응용력을 기대할 수 있다.

이론/모형

그리고 서비스 종료시점(이탈시점)을 내재점으로 갖는 내재점 마코프 체인(embedded Markov chain)을 이용하여 이탈 시점의 고객수 분포를 도출한다. 이에 부가변수법(supplementary variable technique)을 적용하여 임의시점의 고객수 분포를 유도한다. 그리고 평균 대기시간, 시스템 내 평균 고객수와 시스템이 꽉 차서 도착하는 고객의 입장이 거부될 확률 등의 성능지표들을 제시한다.

성능/효과

04명 정도 증가로 큰 차이가 없다. 즉, 본 실험조건 하에서는 서비스율을 변화시킨 것이 시스템 내 고객수를 줄이는데 상당히 효과적인 것으로 생각해볼 수 있다.

후속연구

이후 수치예제를 통해 확률분포의 변동 계수 및 한계점에 대한 정책을 변화시키면서 시스템의 특성을 연구하였다. 본 연구는 기존 연구들에서 분석되지 않은 새로운 모형을 분석하고 수치예제를 통해 정책의 특성을 연구했다는 점에서 기여도를 찾을 수 있을 것이며, 추후 연구로 적절한 비용 구조(cost structure)를 설계한 뒤 보다 경제적인 운용방법을 고안해보는 것도 기대할 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	대기시간을 관리하기 위해 적용되는 것은?	대기행렬 시스템에 입장한 고객들의 대기시간이 적절한 수준을 넘지 않도록 관리하는 것은 서비스의 품질보장 측면에서 높은 수준의 관심이 요구된다. 대기시간을 관리하기 위해 다양한 종류의 제어 정책들이 대기행렬에 적용되고 있는데 고객숫자(또는 대기열의 길이, queue length) 에 따라 서비스의 속도(또는 서비스율, service rate)를 조절하는 것도 대표적인 정책 중 하나이다. 고객수에 따라 서비스 속도(서비스율)를 조절하는 정책을 Banik[1]이 소개한 반도체 제조라인의 예를 통해 살펴보자.
	고객수에 따라 서비스 속도(서비스율)를 조절하는 정책의 예는 무엇이 있는가?	고객수에 따라 서비스 속도(서비스율)를 조절하는 정책을 Banik[1]이 소개한 반도체 제조라인의 예를 통해 살펴보자. 성능이 좋지만 운용 비용이 비싼, 그리고 성능은 떨어지지만 비용은 저렴한 제조 설비가 각 한 대 씩 있다. 여기서 좋은 성능은 높은 서비스율을 의미한다. 처리를 기다리는 lot의 숫자가 일정 수준 이하일 때는 낮은 성능의 설비를 저렴하게 가동한다. 대기하는 lot의 숫자가 일정 수준을 넘어서면 저성능의 설비는 가동을 멈추고 고성능의 설비를 가동하는 정책이다. 고성능 설비는 대기시간을 줄이는데 기여할 수 있으나 운영비용 측면에서는 부담이 될 수 있어 저성능 설비도 적절히 이용하는 것이다.
	대기행렬 시스템에서 중요한 것은?	대기행렬 시스템에 입장한 고객들의 대기시간이 적절한 수준을 넘지 않도록 관리하는 것은 서비스의 품질보장 측면에서 높은 수준의 관심이 요구된다. 대기시간을 관리하기 위해 다양한 종류의 제어 정책들이 대기행렬에 적용되고 있는데 고객숫자(또는 대기열의 길이, queue length) 에 따라 서비스의 속도(또는 서비스율, service rate)를 조절하는 것도 대표적인 정책 중 하나이다.

참고문헌 (15)

A.D. Banik (2014), "Some Aspects of Stationary Characteristics and Optimal Control of the BMAP/G？G/1/N ( ${\infty}$ ) Oscillating Queueing System", Applied Stochastic Models in Business and Industry, Vol. 31, No. 2, pp. 204-230.
H. Li, Y. Zhu and P. Yang (1995), "Computational Analysis of M(n)/G/1/N Queues with Setup Time", Computers & Operations Research, Vol. 22, pp. 829-840.

상세보기
H. Li and Y. Zhu (1997), "M(n)/G/1/N Queues with Generalized Vacations", Computers & Operations Research, Vol. 24, pp. 301-316.

상세보기
C. Lim and A. Tang (2011), "Dynamic Speed Scaling and Load Balancing of Interconnected Queues", in Information Theory and Applications Workshop (ITA), IEEE, pp. 1-10.
N. Lee and V.G Kulkarni (2014), "Optimal Arrival Rate and Service Rate Control of Multi-Server Queues", Queueing Systems, Vol. 76, pp. 37-50.

상세보기
M.Y. Kitaev and R.F. Serfozo (1999), "M/M/1 Queues with Switching Costs and Hysteretic Optimal Control", Operations Research, Vol. 47, pp. 310-312.
S. Yoon and M.E. Lewis (2004), "Optimal Pricing and Admission Control in a Queueing System with Periodically Varying Parameters", Queueing Systems, Vol. 47, pp. 177-199.

상세보기
S. Nishimura and Y.Jiangm (1995), "An $M^{X}/G/1$ Vacation Model with Two Service Modes", Probability in the Engineering and Informational Sciences, Vol. 9, pp. 355-374.

상세보기
A.N. Dudin, "Optimal Control for an MX/G/1 Queue with Two Operation Modes", Probability in the Engineering and Informational Sciences, Vol. 11, pp. 255-265.

상세보기
D.I. Choi (1999), "MAP/G/1/K Queue with Multiple Thresholds on Buffer", Communications-Korean Mathematical Society, Vol. 14, pp. 611-625.
U.C. Gupta, S.K. Samanta and V. Goswami (2014), "Analysis of a Discrete-time Queue with Load Dependent Service under Discrete-time Markovian Arrival Process", Journal of the Korean Statistical Society, Vol. 43, No. 4, pp. 547-557.
D.I. Choi, T.-S. Kim and S. Lee (2008), "Analysis of an MMPP/G/1/K Queue with Queue Length Dependent Arrival Rates, and its Application to Preventive Congestion Control in Telecommunication Networks", European Journal of Operational Research, Vol. 187, pp. 652-659.

상세보기
K.M. Adusumilli and J.J. Hasenbein (2010), "Dynamic Admission and Service Rate Control of a Queue", Queueing Systems, Vol. 66, pp. 131-154.

상세보기
B.D. Choi, Y.H. Chung and A.N. Dudin (2001), "The BMAP/SM/1 Retrial Queue with Controllable Operation Modes", European Journal of Operational Research, Vol. 131, pp. 16-30.

상세보기
D.I. Choi, T.S. Kim and S. Lee (2007), "Analysis of a Queueing System with a General Service Scheduling Function, with Applications to Telecommunication Network Traffic Control", European Journal of Operational Research, Vol. 178, pp. 463-471.

상세보기

저자의 다른 논문 :

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

연합인증