대기행렬(Queuing theory) 18.1 왜 대기행렬을 공부해야 하는가? 18.2 대기행렬모형의 요소들 18.3 지수분포의 역할 18.4 순수 출생 및 사망모형들 18.5 일반 포아송 대기행렬모형 18.6 특별한 포아송 대기행렬들 18.7 (M/G/1):(GD/∞/∞)

대기행렬(Queuing theory) 18.1 왜 대기행렬을 공부해야 하는가? 18.2 대기행렬모형의 요소들 18.3 지수분포의 역할 18.4 순수 출생 및 사망모형들 18.5 일반 포아송 대기행렬모형 18.6 특별한 포아송 대기행렬들 18.7 (M/G/1):(GD/∞/∞) 18.8 다른 대기행렬모형들 18.9 대기행렬 의사결정모형들

Queuing System : Wikipedia
In Queuing theory is the mathematical study of waiting lines, or queues. In queuing theory a model is constructed so that queue lengths and waiting times can be predicted. Queuing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service. Queuing theory has its origins in research by Agner Krarup Erlang when he created models to describe the Copenhagen telephone exchange. The ideas have since seen applications including telecommunication, traffic engineering, computing and the design of factories, shops, offices and hospitals.

18.1 왜 대기행렬을 공부해야 하는가? Life is waiting.
서비스를 제공하는 비용 .vs. 고객들이 경험하는 대기 비용 대기행렬에 대한 연구 – 대표적인 성과 척도들 대기행렬의 평균 길이 대기행렬에서의 평균 대기시간 평균 설비 활용도

18.1 왜 대기행렬을 공부해야 하는가? 예제 18.1-1 (패스트푸드점) McBurger : 3개의 서비스 카운터
서비스를 좀 더 빨리 제공하기를 원한다. 계산원의 수 1 2 3 4 5 6 7 평균 대기시간(분) 16.2 10.3 6.9 4.8 2.9 1.9 1.3

18.1 왜 대기행렬을 공부해야 하는가? 예제 18.1-1 (패스트푸드점)
비용기반모형 – 서비스 제공 비용 + 고객들 대기 비용

18.1 왜 대기행렬을 공부해야 하는가? 연습문제 18.1A – 1번 (McBurger의 확장)
계산원의 수가 5명일 때, 이 운영 시스템의 (종업원들이 일하고 있는 시간 비율로 표현한) 생산성은 얼마인가? 이 식당의 경영자는 평균 대기시간을 3분 정도로 유지하고 싶어 하고, 동시에 시설의 효율을 대략 90% 정도 유지하기를 원한다. 이 두 가지 목표들을 달성할 수 있을까? 계산원의 수 1 2 3 4 5 6 7 유휴율(%) 8 12 18 29 36 42

18.2 대기행렬모형의 요소들 주요 요소들 – 고객(customer)과 서버(server)
고객의 도착 – 도착시간 간격(interarrival time)으로 측정 서비스 – 고객당 서비스시간(service time)으로 측정 도착시간 간격 & 서비스 시간 – 확률적 또는 확정적 대기행렬의 크기(Queue Size) – 대기행렬 규칙(Queue Discipline) – FCFS, LCFS, SIRO 대기행렬의 거동 – 줄 바꿈(jockeying), 거절(balk), 취소(renege) 서비스 시설의 설계 또는 고객 생성 모집단의 성격

18.2 대기행렬모형의 요소들 연습문제 18.2A – 1번 (고객과 서버들을 파악하라) 공항에 도착하는 항공기들
기다리는 승객을 위한 택시 승차장 공장도구함에서 인출한 도구들 우체국에서 처리하는 편지들 대학에서 교과목 수강 신청 법률 사건 슈퍼마켓에서 계산대 운영 주자창 문제

18.3 지수분포의 역할 도착은 무작위(random)로 발생 – 무작위 도착시간 간격과 서비스 시간 – 지수 분포
𝑓 𝑡 =𝜆 𝑒 −𝜆𝑡 , 𝑡>0 지수분포의 특성 𝐸 𝑡 = 1 𝜆 , 𝑃 𝑡≤𝑇 = 0 𝑇 𝜆 𝑒 −𝜆𝑡 𝑑𝑡=1− 𝑒 −𝜆𝑇

18.3 지수분포의 역할 지수분포의 완전 무작위 특성 – 기억 상실성 8시 2분에 고객 도착, 현재 시각 8시 20분 8시 29분에 다음 고객이 도착할 확률 – 𝑃 𝑡≤9 =1− 𝑒 −9𝜆 𝑃 𝑡>𝑇+𝑆|𝑡>𝑆 =𝑃{𝑡>𝑇} ⇒ 𝑃 𝑡>29|𝑡>20 =𝑃{𝑡>9} 𝑃 𝑡>𝑇+𝑆|𝑡>𝑆 = 𝑃{𝑡>𝑇+𝑆, 𝑡>𝑆} 𝑃{𝑡>𝑆} = 𝑃{𝑡>𝑇+𝑆} 𝑃{𝑡>𝑆} = 𝑒 −𝜆(𝑇+𝑆) 𝑒 −𝜆𝑆 = 𝑒 −𝜆𝑇 =𝑃{𝑡>𝑇}

18.4 순수 출생 및 사망모형들 순수 출생 (pure birth) 모형 순수 사망 (pure death) 모형
순수 출생모형 𝑝 0 𝑡 =𝑡 기간 동안 도착이 없을 확률, 𝑝 0 𝑡 = 𝑒 −𝜆𝑡 매우 작은 시간 간격 h > 0 𝑝 0 ℎ = 𝑒 −𝜆ℎ =1−𝜆ℎ+ 𝜆ℎ 2 2! −⋯= 1−𝜆ℎ+0( ℎ 2 ) 지수분포 - h > 0에 최대 1건의 사건(도착)이 발생한다 : 가정 lim ℎ→0 𝑝 1 ℎ = lim ℎ→0 1− 𝑝 0 (ℎ) ≈1−𝜆ℎ

18.4 순수 출생 및 사망모형들 18.4.1 순수 출생모형 𝑡 기간 동안 도착하는 도착횟수의 분포 유도
𝑝 𝑛 𝑡 = 𝑡 기간 동안 𝑛 번의 도착이 발생할 확률 매우 작은 시간 간격 h > 0 𝑝 𝑛 𝑡+ℎ ≈ 𝑝 𝑛 𝑡 1−𝜆ℎ + 𝑝 𝑛−1 𝑡 𝜆ℎ, 𝑛>0 𝑝 0 𝑡+ℎ ≈ 𝑝 0 𝑡 1−𝜆ℎ , 𝑛=0

18.4 순수 출생 및 사망모형들 18.4.1 순수 출생모형 𝑝 𝑛 𝑡 의 𝑡에 대한 1차 미분식 유도 – 위 식 정리
𝑝 𝑛 𝑡 의 𝑡에 대한 1차 미분식 유도 – 위 식 정리 𝑝 ′ 𝑛 𝑡 = lim ℎ→0 𝑝 𝑛 𝑡+ℎ − 𝑝 𝑛 (𝑡) ℎ =−𝜆 𝑝 𝑛 (𝑡)+𝜆 𝑝 𝑛−1 𝑡 , 𝑛>0 𝑝 ′ 0 𝑡 = lim ℎ→0 𝑝 0 𝑡+ℎ − 𝑝 0 (𝑡) ℎ =−𝜆 𝑝 0 (𝑡), 𝑛>0 ⇒ 𝑝 𝑛 𝑡 = 𝜆𝑡 𝑛 𝑒 −𝜆𝑡 𝑛! , 𝑛=0,1,2,⋯ ⇒ t 기간 동안 평균 도착 고객 수가 𝐸{𝑛 𝑡 =𝜆𝑡 인 포아송분포

18.4 순수 출생 및 사망모형들 18.4.1 순수 출생모형 𝑝 𝑛 𝑡 = 𝜆𝑡 𝑛 𝑒 −𝜆𝑡 𝑛! , 𝑛=0,1,2,⋯
지수분포 포아송분포 확률변수 연속도착 간의 시간 간격 t 지정한 기간 T동안 발생한 도착 회수 n 범위 𝑡≥0 𝑛=0,1,2,⋯ 확률밀도함수 𝑓 𝑡 =𝜆 𝑒 −𝜆𝑡 , 𝑡>0 𝑝 𝑛 𝑡 = 𝜆𝑡 𝑛 𝑒 −𝜆𝑡 𝑛! , 𝑛=0,1,2,⋯ 평균값 1 𝜆 시간 𝑇동안 𝜆𝑇 도착 누적확률 𝑃 𝑡≤𝐴 =1− 𝑒 −𝜆𝐴 𝑝 𝑛≤𝑁 𝑇 = 𝑝 0 𝑇 +⋯+ 𝑝 𝑁 𝑇 P{A동안 도착이 없을 확률} 𝑃 𝑡>𝐴 = 𝑒 −𝜆𝐴 𝑝 0 𝐴 = 𝑒 −𝜆𝐴

Gamma Distribution:

18.4 순수 출생 및 사망모형들 예제 18.4.1 (대도시 신생아 출생모형)
신생아들 출생 비율=12분 1명, 출생시간 간격은 지수분포 연간 태어나는 평균 신생아의 수 하루 동안 신생아가 1명도 태어나지 않을 확률 어떤 3시간 기간 중의 처음 2시간 동안 40건의 출생증명서를 발급한 상태에서 충 3시간 동안 50건의 출생 증명서를 발급할 확률

18.4 순수 출생 및 사망모형들 예제 18.4.1 (대도시 신생아 출생모형)
신생아들 출생 비율=12분 1명, 출생시간 간격은 지수분포 연간 태어나는 평균 신생아의 수 𝜆= 24× = 120명 일 연간 신생아 수 = 𝜆𝑡 = 120ⅹ365=43,800명/년

18.4 순수 출생 및 사망모형들 𝑝 0 1 = (120×1) 0 𝑒 −120×1 0! = 𝑒 −120 =0
예제 (대도시 신생아 출생모형) 신생아들 출생 비율=12분 1명, 출생시간 간격은 지수분포 하루 동안 신생아가 1명도 태어나지 않을 확률 𝑝 0 1 = (120×1) 0 𝑒 −120×1 0! = 𝑒 −120 =0 𝑃 𝑡>1 = 𝑒 −120 =0

18.4 순수 출생 및 사망모형들 예제 (대도시 신생아 출생모형) 신생아들 출생 비율=12분 1명, 출생시간 간격은 지수분포 어떤 3시간 기간 중의 처음 2시간 동안 40건의 출생증명서를 발급한 상태에서 충 3시간 동안 50건의 출생 증명서를 발급할 확률 𝑝 = ( ×1) 10 𝑒 −5×1 10! =0.0813

18.4 순수 출생 및 사망모형들 18.4.2 순수 사망모형 시간 0에 N 명의 고객들이 있는 상태, 새로운 도착(X)
출발은 시간당 μ 고객의 비율로 발생 𝑡 시간 후에 n 명의 고객이 남아 있을 확률 𝑝 𝑛 𝑡 𝑝 𝑁 𝑡+ℎ = 𝑝 𝑁 𝑡 1−𝜇ℎ 𝑝 𝑛 𝑡+ℎ = 𝑝 𝑛 𝑡 1−𝜇ℎ + 𝑝 𝑛+1 𝑡 𝜇ℎ, 0<𝑛<𝑁 𝑝 0 𝑡+ℎ = 𝑝 0 𝑡 1 + 𝑝 1 (𝑡)𝜇ℎ

18.4 순수 출생 및 사망모형들 ⇒ 𝑝 𝑛 𝑡 = 𝜇𝑡 𝑁−𝑛 𝑒 −𝜇𝑡 𝑁−𝑛 ! , 𝑛=1,2,⋯,𝑁
순수 사망모형 𝑝′ 𝑁 𝑡+ℎ = −𝜇𝑝 𝑁 𝑡 𝑝′ 𝑛 𝑡 =−𝜇 𝑝 𝑛 𝑡 +𝜇 𝑝 𝑛+1 𝑡 , 0<𝑛<𝑁 𝑝′ 0 𝑡 =𝜇 𝑝 1 (𝑡) ⇒ 𝑝 𝑛 𝑡 = 𝜇𝑡 𝑁−𝑛 𝑒 −𝜇𝑡 𝑁−𝑛 ! , 𝑛=1,2,⋯,𝑁 𝑝 0 𝑡 =1− 𝑛−1 𝑁 𝑝 𝑛 (𝑡)

18.4 순수 출생 및 사망모형들 예제 18.4.2 (슈퍼마켓 화원 장미 판매) 매주 초에 18더즌의 장미를 가지고 판매 시작
평균적 한 번에 1더즌씩 1일에 3더즌의 장미 판매 실제 수요는 포아송 분포를 따름 재고 수준이 5더즌에 도달하면 새로 18더즌의 장미 주문 주 중에 장미를 주문할 확률 매주 말 폐기 처분하는 장미의 평균 값

18.4 순수 출생 및 사망모형들 예제 (슈퍼마켓 화원 장미 판매) 주 중에 장미를 주문할 확률 t 일까지 장미를 주문할 확률 𝑝 𝑛≤5 𝑡 = 𝑝 0 𝑡 +⋯+ 𝑝 5 𝑡 = 𝑝 0 𝑡 + 𝑛=1 5 (3𝑡) 18−𝑛 𝑒 −3𝑡 18−𝑛 ! 𝑡=1,2,⋯,7 t (일) 1 2 3 4 5 6 7 𝜇𝑡 9 12 15 18 21 𝑝 𝑛≤5 𝑡 .0000 .0088 .1242 .4240 .7324 .9083 .9755

18.4 순수 출생 및 사망모형들 𝐸 𝑛 𝑡=7 = 𝑛=0 18 𝑛 𝑝 𝑛 7 =.664≈1 더즌
예제 (슈퍼마켓 화원 장미 판매) 매주 말 (t=7) 폐기하는 장미의 평균값, 𝐸 𝑛 𝑡=7 계산 𝑝 𝑛 7 , 𝑛=0,1,2, ⋯ 필요 𝐸 𝑛 𝑡=7 = 𝑛=0 18 𝑛 𝑝 𝑛 7 =.664≈1 더즌

18.5 일반 포아송 대기행렬모형 도착시간 간격과 서비스 시간은 지수분포 도착(출생)과 출발(사망)을 결합한 모형 개발
대기행렬모형 – 장기 혹은 안정상태(steady state) 거동에 기초 일반모형 – 도착률 및 출발률이 상태 종속 (state dependent) notation (기호) n = (대기행렬과 서비스 시설을 합친) 시스템에 있는 고객의 수 𝜆 𝑛 =시스템에 n 명의 고객이 있는 상태에서의 도착률 𝜇 𝑛 =시스템에 n 명의 고객이 있는 상태에서의 출발률 𝑝 𝑛 =시스템에 n 명의 고객이 있을 안정상태 확률

18.5 일반 포아송 대기행렬모형 𝑝 𝑛 확률 값들은 위 전이율 다이어그램을 사용하여 도출
𝑝 𝑛 확률 값들은 위 전이율 다이어그램을 사용하여 도출 작은 시간 간격 ℎ>0에 대해서 1건보다 더 많은 사건 발생 확률≒0 𝑛→𝑛−1 ( 𝜇 𝑛 으로 출발), 𝑛→𝑛+1 ( 𝜆 𝑛 으로 도착) 상태 0→1 ( 𝜆 0 으로 도착)

18.5 일반 포아송 대기행렬모형 상태 𝑛>0 유입 기대 비율= 𝑛 유출 기대 비율
(상태 𝑛 유입 기대 비율)= 𝜆 𝑛−1 𝑝 𝑛−1 + 𝜇 𝑛+1 𝑝 𝑛+1 (상태 𝑛 유출 기대 비율)= (𝜆 𝑛 + 𝜇 𝑛 ) 𝑝 𝑛 균형 방정식 (balance equation) 𝜆 𝑛−1 𝑝 𝑛−1 + 𝜇 𝑛+1 𝑝 𝑛+1 =( 𝜆 𝑛 + 𝜇 𝑛 ) 𝑝 𝑛 𝜇 1 𝑝 1 = 𝜆 0 𝑝 0

𝑝 𝑛 = 𝜆 𝑛−1 𝜆 𝑛−2 ⋯ 𝜆 0 𝜇 𝑛 𝜇 𝑛−1 ⋯ 𝜇 1 𝑝 0 , 𝑛=1,2, ⋯
18.5 일반 포아송 대기행렬모형 균형 방정식 (balance equation) 풀기 𝑛=0 : 𝜇 1 𝑝 1 = 𝜆 0 𝑝 0 ⇒ 𝑝 1 = (𝜆 0 / 𝜇 1 ) 𝑝 0 𝑛=1 : 𝜆 0 𝑝 0 + 𝜇 2 𝑝 2 =( 𝜆 1 + 𝜇 1 ) 𝑝 1 ⇒ 𝑝 2 = 𝜆 1 𝜆 0 𝜇 2 𝜇 1 𝑝 0 수학적 귀납법 𝑝 𝑛 = 𝜆 𝑛−1 𝜆 𝑛−2 ⋯ 𝜆 0 𝜇 𝑛 𝜇 𝑛−1 ⋯ 𝜇 1 𝑝 0 , 𝑛=1,2, ⋯ 𝑝 0 값은 어떻게 구할까 ?

18.5 일반 포아송 대기행렬모형 예제 18.5-1 (BBK 슈퍼마켓 – 3개의 계산대 운영)
고객 수에 따라 가동 계산대의 수를 달리 운영 고객들 – 평균 도착률이 시간당 10명인 포아송 분포 고객당 계산시간은 평균이 12분인 지수분포 슈퍼마켓에 있는 고객의 수 가동 계산대의 수 1~3 1 4~6 2 7명 이상 3

18.5 일반 포아송 대기행렬모형 예제 18.5-1 (BBK 슈퍼마켓 – 3개의 계산대 운영) 𝜆 𝑛 =𝜆=10 고객/시간
𝜇 𝑛 = 5 고객/시간 𝑛=0,1,2,3 10 고객/시간 𝑛=4,5, 고객/시간 𝑛=7,8,⋯

𝑝 1 = (𝜆 0 / 𝜇 1 ) 𝑝 0 =(10/5) 𝑝 0 =2 𝑝 0 𝑝 2 = ( 𝜆 1 𝜆 0 / 𝜇 2 𝜇 1 ) 𝑝 0 = ( 10 5 ) 2 𝑝 0 =4 𝑝 0 𝑝 3 = ( 10 5 ) 3 𝑝 0 =8 𝑝 0 𝑝 4 = ( 10 5 ) 𝑝 0 =8 𝑝 0 , 𝑝 5 = 𝑝 6 =8 𝑝 0 𝑝 𝑛≥7 = ( 10 5 ) ( ) 𝑛−6 𝑝 0 =8 ( 2 3 ) 𝑛−6 𝑝 0

𝑝 0 + 𝑝 ( 2 3 ) 2 +8 ( 2 3 ) 3 +⋯ =1 𝑝 ( ⋯) =1 𝑝 ( 1 1− 2 3 ) =1 1개의 계산대만 운영할 확률은 ?

18.6 특별한 포아송 대기행렬모형

18.6 특별한 포아송 대기행렬모형 그림 18-3 notation (기호) (a/b/c):(d/e/f) a = 도착분포

18.6 특별한 포아송 대기행렬모형 그림 18-3 notation (기호 a와 b)
M = 마코비안(또는 포아송) 도착∙출발분포 (시간간격의 분포 ?) D = 상수(확정적) 시간 𝐸 𝑘 = 얼랑 또는 감마분포 (또는 독립적인 지수분포의 합) GI = 도착시간 간격의 일반 분포 대기행렬 규칙의 표기법 MFCFS , LCFS , SIRO , GD (M/D/10):(GD/20/∞)

18.6 특별한 포아송 대기행렬모형 18.6.1 안정상태 성과척도들
대표적인 성과척도들 - 시스템 = {대기행렬, 서비스 시설} 𝐿 𝑠 = 시스템에 있는 평균 고객 수 𝐿 𝑞 = 대기행렬에 있는 평균 고객 수 𝑊 𝑠 = 시스템에서 평균 대기시간 𝑊 𝑞 = 대기행렬에서 있는 평균 대기시간 𝑐 = 서비스 중인 평균 서버의 수 𝐿 𝑠 = 𝑛=1 ∞ 𝑛 𝑝 𝑛 𝐿 𝑞 = 𝑛=𝑐+1 ∞ (𝑛−𝑐) 𝑝 𝑛 𝐿 𝑠 = 𝜆 𝑒𝑓𝑓 𝑊 𝑠 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝑊 𝑞

𝑐 = 𝐿 𝑠 − 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝜇 ⇒ 시설활용도 = 𝑐 𝑐
18.6 특별한 포아송 대기행렬모형 안정상태 성과척도들 Little’s Formula 𝐿 𝑠 = 𝜆 𝑒𝑓𝑓 𝑊 𝑠 , 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝑊 𝑞 𝜆 𝑒𝑓𝑓 = 시스템에 도착하는 유효도착률 = = 𝜆 ? < 𝜆 ? 𝑊 𝑠 = 𝑊 𝑞 + 1 ? ⇒ 𝐿 𝑠 = 𝐿 𝑞 + ? ? 𝑐 = 𝐿 𝑠 − 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝜇 ⇒ 시설활용도 = 𝑐 𝑐

18.6 특별한 포아송 대기행렬모형 예제 18.6.1 (Ozark 대학 방문객 주차장)
주차공간=5대, 도착률=시간당 평균 6대의 도착률 포아송 분포 주차시간=평균 30분인 지수분포, 임시 정차공간=최대 3대 시스템에 n대의 자동차가 있을 확률 𝑝 𝑛 방문객 주차장을 사용하는 자동차들의 유효도착률 주차장의 평균 자동차 수 임시 정차공간에서 기다리는 자동차의 평균 대기 시간 방문객 주차장의 점유된 주차공간의 평균 수 방문객 주차장의 평균 활용도

18.6 특별한 포아송 대기행렬모형 예제 (Ozark 대학 방문객 주차장) 𝑝 𝑛 구하기 𝜆 𝑛 =6대/시간, n = 0, 1, 2, …, 8 𝜇 𝑛 = 𝑛 =2𝑛 𝑛=1,2,3,4, =10 𝑛=6,7,8, 𝑝 𝑛 = 𝑛 𝑛! 𝑝 0 𝑛=1,2,3,4, 𝑛 5! 5 𝑛−5 𝑝 0 𝑛=6,7,8, 𝑝 0 + 𝑝 ! ! +⋯ ! ! ! ! =1 n 1 2 3 4 5 6 7 8 𝑝 𝑛 .14436 .21654 .16240 .09744 .05847 .03508 .02105

18.6 특별한 포아송 대기행렬모형 예제 18.6.1 (Ozark 대학 방문객 주차장) 유효도착률 𝜆 𝑒𝑓𝑓 구하기
유효도착률 𝜆 𝑒𝑓𝑓 구하기 𝜆 𝑒𝑓𝑓 율로 주차장으로 𝜆 𝑙𝑜𝑠𝑡 율로 다른 곳으로, 𝜆= 𝜆 𝑒𝑓𝑓 + 𝜆 𝑙𝑜𝑠𝑡 𝜆 𝑙𝑜𝑠𝑡 =𝜆 𝑝 8 =6ⅹ.2105=.1263대/시간, 𝜆 𝑒𝑓𝑓 =5.8737 𝐿 𝑠 = 𝑛=0 8 𝑛 𝑝 𝑛 =3.1286대

18.6 특별한 포아송 대기행렬모형 예제 (Ozark 대학 방문객 주차장) 유효도착률 𝜆 𝑒𝑓𝑓 구하기 𝑊 𝑞 = 𝑊 𝑠 − 1 𝜇 = 𝐿 𝑠 𝜆 𝑒𝑓𝑓 − 1 𝜇 = − 1 2 𝑐 = 𝐿 𝑠 − 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝜇 = 주차장의 활용도== 𝑐 𝑐

18.6 특별한 포아송 대기행렬모형 18.6.2 단일 서버모형 두 가지 단일 서버(c=1) 모형
① 시스템 최대 고객 수 무제한 (M/M/1):(GD/∞/∞) ② 시스템 최대 고객 수 제한 (M/M/1):(GD/N/∞) 고객들을 생성하는 모집단은 무한대라고 가정 시스템 도착률=시간당 λ명, 서비스율=시간당 μ명

18.6 특별한 포아송 대기행렬모형 18.6.2 단일 서버모형 (M/M/1):(GD/∞/∞)
𝜆 𝑛 =𝜆, 𝜇 𝑛 =𝜇, 𝑛=0,1,2,⋯, ρ= 𝜆 𝜇 𝑝 𝑛 = 𝜆 𝑛−1 𝜆 𝑛−2 ⋯ 𝜆 0 𝜇 𝑛 𝜇 𝑛−1 ⋯ 𝜇 1 𝑝 0 = 𝜌 𝑛 𝑝 0 , 𝑛=0,1,2,⋯ 𝑝 0 =1−𝜌, 𝜌<1 ⇒ 𝑝 𝑛 = (1−𝜌)𝜌 𝑛 , 𝑛=0,1,2,⋯ 𝜌<1 𝜌>1인 경우는 어떻게 될까?

18.6 특별한 포아송 대기행렬모형 18.6.2 단일 서버모형 (M/M/1):(GD/∞/∞)
𝐿 𝑠 = 𝑛=0 ∞ 𝑛 𝑝 𝑛 = 𝑛=0 ∞ 𝑛 1−𝜌 𝜌 𝑛 = 1−𝜌 𝜌 𝑑 𝑑𝜌 𝑛=0 ∞ 𝜌 𝑛 𝐿 𝑠 = 𝑊 𝑠 = 𝑊 𝑞 = 𝐿 𝑞 = 𝜌 1−𝜌 = 𝜆 𝜇−𝜆 𝐿 𝑠 𝜆 = 𝜆 𝜆(𝜇−𝜆) = 1 𝜇−𝜆 = 1 𝜇(1−𝜌) 𝑊 𝑠 − 1 𝜇 = 𝜌 𝜇(1−𝜌) 𝜆𝑊 𝑞 = 𝜌 2 (1−𝜌) 𝑐 = 𝐿 𝑠 − 𝐿 𝑞 =𝜌

18.6 특별한 포아송 대기행렬모형 𝜌= 4 6 , 𝐿 𝑠 = 𝜌 1−𝜌 =2, 𝑤 𝑠 = 𝐿 𝑠 𝜆 =0.5
예제 (Automata 세차장) 1대 세차 시설, 시간당 평균 4대 도착률 포아송 분포 차 1대 세차시간 평균 10분 지수분포 주차장 크기( s )를 결정하고자 하는 경영자 𝜆=4, 𝜇=6, 𝑐=1, 𝑆𝑦𝑠𝑡𝑒𝑚 𝐿𝑖𝑚𝑖𝑡=∞, 𝑆𝑜𝑢𝑟𝑐𝑒 𝐿𝑖𝑚𝑖𝑡=∞ 𝜌= 4 6 , 𝐿 𝑠 = 𝜌 1−𝜌 =2, 𝑤 𝑠 = 𝐿 𝑠 𝜆 =0.5 𝑊 𝑞 = 𝑊 𝑠 − 1 𝜇 =0.3333, 𝐿 𝑞 =𝜆 𝑊 𝑞 =1.3333

18.6 특별한 포아송 대기행렬모형 예제 18.6.2 (Automata 세차장) 주차장 크기( s )를 결정하고자 하는 경영자
주차공간을 찾을 확률 90% 이상 𝑝 0 + 𝑝 1 +⋯+ 𝑝 𝑠 ≥0.9 , 641페이지 그림 18.5에서 s = ( ? ) (1−𝜌)(1+𝜌+ 𝜌 2 +⋯+ 𝜌 𝑠 )≥0.9 ⇒ 1− 𝜌 𝑠+1 ≥0.9 ⇒ 𝑠≥ ln ln 𝜌 −1

18.6 특별한 포아송 대기행렬모형 단일 서버모형 ② (M/M/1):(GD/N/∞) 𝜆 𝑛 = 𝜆 ,𝑛=0,1,2,⋯,𝑁−1 0 ,𝑛=𝑁, 𝑁+1 , 𝜇 𝑛 =𝜇, 𝑛=0,1,2,⋯, ρ= 𝜆 𝜇 𝑝 𝑛 = 𝜌 𝑛 𝑝 0 𝑛≤𝑁 0 𝑛>𝑁 , 𝑝 0 1+𝜌+ 𝜌 2 +⋯+ 𝜌 𝑁 =1 𝑝 0 = 1−𝜌 1− 𝜌 𝑁+1 ,𝜌≠1 1 𝑁+1 ,𝜌=1 , 𝑝 𝑛 = (1−𝜌) 𝜌 𝑛 1− 𝜌 𝑁+1 ,𝜌≠1 𝜌 𝑛 𝑁+1 ,𝜌=1

18.6 특별한 포아송 대기행렬모형 단일 서버모형 ② (M/M/1):(GD/N/∞) 𝜆 𝑙𝑜𝑠𝑡 =𝜆 𝑝 𝑁 , 𝜆 𝑒𝑓𝑓 =𝜆− 𝜆 𝑙𝑜𝑠𝑡 =𝜆 1− 𝑝 𝑁 , 𝜆 𝑒𝑓𝑓 <𝜇 𝐿 𝑠 = 𝑛=1 𝑁 𝑛 𝑝 𝑛 = (1−𝜌) 1− 𝜌 𝑁+1 𝑛=0 𝑁 𝑛 𝜌 𝑛 = 1−𝜌 1− 𝜌 𝑁+1 𝑑 𝑑𝜌 ( 𝑛=0 𝑁 𝜌 𝑛 ) =644 페이지 식 참조 𝜌=1 ⇒ 𝐿 𝑠 = 𝑁 2

𝜌= 𝜆 𝜇 , 𝜌 𝑐 <1 ⇒ 𝑝 0 = 𝑛=0 𝑐−1 𝜌 𝑛 𝑛! + 𝜌 𝑐 𝑐! 1 1− 𝜌 𝑐 −1
18.6 특별한 포아송 대기행렬모형 다중 서버모형 (M/M/c):(GD/∞/∞) 𝜆 𝑛 =𝜆, 𝑛≥0, 𝜇 𝑛 = 𝑛𝜇 𝑛<𝑐 𝑐𝜇 𝑛≥𝑐 𝑝 𝑛 = 𝜆 𝑛 𝜇(2𝜇)(3𝜇)⋯(𝑛𝜇) 𝑝 0 = 𝜆 𝑛 𝑛! 𝜇 𝑛 𝑝 0 = 𝜌 𝑛 𝑛! 𝑝 0 ,𝑛<𝑐 𝜆 𝑛 ( 𝑖=1 𝑐 𝑖𝜇) (𝑐𝜇) 𝑛−𝑐 𝑝 0 = 𝜌 𝑛 𝑐! 𝑐 𝑛−𝑐 𝑝 0 ,𝑛≥𝑐 𝜌= 𝜆 𝜇 , 𝜌 𝑐 <1 ⇒ 𝑝 0 = 𝑛=0 𝑐−1 𝜌 𝑛 𝑛! + 𝜌 𝑐 𝑐! 1 1− 𝜌 𝑐 −1

𝐿 𝑞 = 𝑛=𝑐 ∞ 𝑛−𝑐 𝑝 𝑛 = 𝑘=0 ∞ 𝑘 𝑝 𝑘+𝑐 = 𝑘=0 ∞ 𝜌 𝑘+𝑐 𝑐 𝑘 𝑐! 𝑝 0
18.6 특별한 포아송 대기행렬모형 다중 서버모형 (M/M/c):(GD/∞/∞) 𝐿 𝑞 = 𝑛=𝑐 ∞ 𝑛−𝑐 𝑝 𝑛 = 𝑘=0 ∞ 𝑘 𝑝 𝑘+𝑐 = 𝑘=0 ∞ 𝜌 𝑘+𝑐 𝑐 𝑘 𝑐! 𝑝 0 = 𝜌 𝑐+1 𝑐!𝑐 𝑝 0 𝑘=0 ∞ 𝑘 ( 𝜌 𝑐 ) 𝑘−1 = 𝜌 𝑐+1 𝑐!𝑐 𝑝 0 𝑑 𝑑 𝜌 𝑐 𝑘=0 ∞ 𝜌 𝑐 𝑘 = 𝜌 𝑐+1 𝑐−1 ! 𝑐−𝜌 2 𝑝 0 𝜆 𝑒𝑓𝑓 =𝜆 ⇒ 𝐿 𝑠 = 𝐿 𝑞 +𝜌 𝑊 𝑠 𝑊 𝑞 = 𝐿 𝑠 𝜆 𝐿 𝑞 𝜆

18.6 특별한 포아송 대기행렬모형 예제 18.6.4 (택시회사) 2개 택시 회사 (택시 2대씩 보유), 시장 50%씩 점유
시간당 평균 8통씩 고객 호출전화, 포아송 분포 고객 평균 승차시간 12분, 지수 분포 각 회사 λ=8통/시간, μ=5명(탑승)/시간, (M/M/2):(GD/∞/∞) 합병 회사 λ=16통/시간, μ=5명(탑승)/시간, (M/M/4):(GD/∞/∞) TORA 이용한 결과 분석 – 648페이지

18.6 특별한 포아송 대기행렬모형 다중 서버모형 (M/M/c):(GD/N/∞) 𝜆 𝑛 = 𝜆, 0≤𝑛≤𝑁 0, 𝑛>𝑁 , 𝜇 𝑛 = 𝑛𝜇 0≤𝑛≤𝑐 𝑐𝜇 𝑐≤𝑛≤𝑁 𝑝 𝑛 = 𝜌 𝑛 𝑛! 𝑝 0 , 0≤𝑛≤𝑐 𝜌 𝑛 𝑐! 𝑐 𝑛−𝑐 𝑝 0 , 𝑐≤𝑛≤𝑁 𝑝 0 = 𝑛=0 𝑐−1 𝜌 𝑛 𝑛! + 𝜌 𝑐 1− 𝜌 𝑐 𝑁−𝑐+1 𝑐! 1− 𝜌 𝑐 −1 , 𝜌 𝑐 ≠1 𝑛=0 𝑐−1 𝜌 𝑛 𝑛! + 𝜌 𝑐 𝑐! 𝑁−𝑐+1 −1 𝜌 𝑐 =1

18.6 특별한 포아송 대기행렬모형 예제 18.6-5 (추가 택시 구매하지 않음)
경영자 대기 시간 감소 방안 – 대기행렬길이가 6이면 배차부서에서 새 고객에게 오래 기다릴 수 있다고 통보 즉 대기행렬 길이=6, N=6+4=10 λ=16, μ=5 ⇒ (M/M/4):(GD/10/∞) 𝑝 𝑛 = 𝜌 𝑛 𝑛! 𝑝 0 , 0≤𝑛≤𝑐 𝜌 𝑛 𝑐! 𝑐 𝑛−𝑐 𝑝 0 , 𝑐≤𝑛≤𝑁

18.6 특별한 포아송 대기행렬모형 18.6.4 기계 수리모형 - (M/M/R):(GD/K/K) K 대의 기계가 있는 공장
기계 1대 당 고장률은 단위시간당 λ 고장 수리공은 단위시간당 μ의 비율로 기계 수리 시스템에 n 대의 기계 ⇒ n 대의 기계 수리 중 𝜆 𝑛 = 𝐾−𝑛 𝜆, 0≤𝑛≤𝐾 𝜆 𝑛 = (𝐾−𝑛)𝜆, 0≤𝑛≤𝐾 0, 𝑛≥𝐾 , 𝜇 𝑛 = 𝑛𝜇 0≤𝑛≤𝑅 𝑅𝜇 𝑅≤𝑛≤𝑁

𝑝 0 = 𝑛=0 𝑅 𝐾! 𝑛! 𝐾−𝑛 ! 𝜌 𝑛 + 𝑛=𝑅+1 𝐾 𝐾! 𝑛! 𝐾−𝑛 ! 𝑛! 𝜌 𝑛 𝑅! 𝑅 𝑛−𝑅 −1
18.6 특별한 포아송 대기행렬모형 기계 수리모형 - (M/M/R):(GD/K/K) 𝑝 𝑛 = 𝐾! 𝑛! 𝐾−𝑛 ! 𝜌 𝑛 𝑝 0 , 0≤𝑛≤𝑅 𝐾! 𝑛! 𝐾−𝑛 ! 𝑛! 𝜌 𝑛 𝑅! 𝑅 𝑛−𝑅 𝑝 0 , 𝑅≤𝑛≤𝐾 𝑝 0 = 𝑛=0 𝑅 𝐾! 𝑛! 𝐾−𝑛 ! 𝜌 𝑛 + 𝑛=𝑅+1 𝐾 𝐾! 𝑛! 𝐾−𝑛 ! 𝑛! 𝜌 𝑛 𝑅! 𝑅 𝑛−𝑅 −1

18.6 특별한 포아송 대기행렬모형 예제 18.6-7 (Toolco 사) 22대의 기계가 있는 가공공장
매 2시간마다 기계 1대가 고장, 수리시간 평균 12분 적절한 수리공의 수 ? 기계생산성= 가용한 기계 대수−고장난 기계 대수 가용한 기계 대수 ×100= 22− 𝐿 𝑠 22 ×100 λ=0.5, μ=5, R=1, 2, 3, 4, System Limit=22, Source Limit=22 수리공 R 1 2 3 4 기계 생산성(%) 45.44 80.15 88.79 90.45 한계 증가값(%) - 34.71 8.64 1.66

𝐿 𝑠 =𝜆𝐸 𝑡 + 𝜆 2 𝐸 2 𝑡 +𝑣𝑎𝑟{𝑡} 2 1−𝜆𝐸{𝑡} , 𝜆𝐸 𝑡 <1 𝑝 0 =1−𝜆𝐸 𝑡 =1−𝜌
18.7 (M/G/1):(GD/∞/∞) 도착과 출발이 포아송 분포를 따르지 않는 대기행렬 모형 Simulation 서비스 시간 t⇒ 평균 E{t}, 분산 var{t} λ : 도착률, λE{t} < 1에서 복잡한 분석 𝐿 𝑠 =𝜆𝐸 𝑡 + 𝜆 2 𝐸 2 𝑡 +𝑣𝑎𝑟{𝑡} 2 1−𝜆𝐸{𝑡} , 𝜆𝐸 𝑡 <1 𝑝 0 =1−𝜆𝐸 𝑡 =1−𝜌 𝜆 𝑒𝑓𝑓 =𝜆 ⇒ 𝐿 𝑞 , 𝑊 𝑠 , 𝑊 𝑞 는 절에서 설명한 방법으로 구함.

𝐿 𝑠 =𝜆𝐸 𝑡 + 𝜆 2 𝐸 2 𝑡 +𝑣𝑎𝑟{𝑡} 2 1−𝜆𝐸{𝑡} =1.33대
18.7 (M/G/1):(GD/∞/∞) 예제 (예제 Automata 세차장, 서비스 시간=10분) 𝜆 𝑒𝑓𝑓 =𝜆=4대/시간, E{t}=10/60 𝐿 𝑠 =𝜆𝐸 𝑡 + 𝜆 2 𝐸 2 𝑡 +𝑣𝑎𝑟{𝑡} 2 1−𝜆𝐸{𝑡} =1.33대 𝑝 0 =1−𝜆𝐸 𝑡 =1−40/60=1/3 𝐿 𝑞 =1.333− =.667대

18.9 대기 행렬 의사결정모형들

대기행렬(Queuing theory) 18.1 왜 대기행렬을 공부해야 하는가? 18.2 대기행렬모형의 요소들 18.3 지수분포의 역할 18.4 순수 출생 및 사망모형들 18.5 일반 포아송 대기행렬모형 18.6 특별한 포아송 대기행렬들 18.7 (M/G/1):(GD/∞/∞)

Similar presentations

Similar presentations

About project

지원

로그인

Auth with social network:

대기행렬(Queuing theory) 18.1 왜 대기행렬을 공부해야 하는가? 18.2 대기행렬모형의 요소들 18.3 지수분포의 역할 18.4 순수 출생 및 사망모형들 18.5 일반 포아송 대기행렬모형 18.6 특별한 포아송 대기행렬들 18.7 (M/G/1):(GD/∞/∞)

Similar presentations

Similar presentations

About project

지원