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

Slides:



Advertisements
Similar presentations
1 Lect. 2 : Introduction II Are you ready to begin?
Advertisements

Product Lifecycle Management © 2003 IBM Corporation PLM Definition Product Lifecycle Management.
현재 시제 과거 시제 2-1. 한국어의 과거시제 : 영어 과거시제 + 현재완료 한국어의 과거시제는 영어의 과거 시제와 현재완료의 개념을 포함한다. I hate him. He is rich 현재의 일 I enjoy listening to music. I take.
Grammar. Today... We will learn about Present Perfect.
폭력. 폭력이란 무엇인가 우상의 눈물 물리적인 폭력 ( 최기표 ) VS 지능적인 폭력 ( 임형우, 담임선생님 )
행복한 그리스도인의 양성 민족의 지도자 양성 왕의 아이들은 여호와를 경외하는 것이 지식의 근본이다 ( 잠 9|10) 왕의 아이들 교훈 왕의 아이들 기도 1. 하나님을 바로 알게 하소서 ! 2. 하나님을 기쁘시게 하는 거룩한 삶을 살게 하소서 ! 3. 하나님의 영광을.
Mechanical clocks were invented in the northern hemisphere by inventors who were trying to make models of the sun's movement in the sky. To watch the.
Spring in North Korea, a time for farmers to harvest their crops 농부들이 추수를 하는 봄의 계절이 왔다.
1 박 2 일 !!! 인천마장초등학교 유수아. 1 박 2 일 멤버 인기순 위 1 위 이승기 2 위 엄태웅 3 위 은지원 4 위 김종민, 이수근 ※인터넷에서 본것이기 때문에 사람에따라 서 다를 수 있다. ※
Theory of Financial Structure
석관중앙교회 5남전도회 석 관 중 앙 교 회 회원 소식 통권 05-04호 발행일 : 2005년 04월 회 장 : 장진호 집사
전남행복수업 design 독서ㆍ토론 수업 지원 자료 활용 목포유달초등학교 김미향.
전남행복수업 design, 독서·토론수업 연구의 개요를 말씀드리겠습니다..
2008년 10월 12일 주일 예배 설교 Sunday Worship Service: Oct. 12, 2008
지역사회복지론 1조. 요양보호시설에 대해서 황성국 임재형 이동영
English Communication R/W
Sources of the Magnetic Field
Unit 4. Making Inferences
SNS의 개인행위 특성요인이 사용의도에 미치는 영향
존엄사 는 허용되어야 한다. 4조 지식정보학부 조우연 역사문화학부 정시형
I 문학의 개념과 역할 1. 문학의 개념 (1) 언어 예술로서의 문학 (2) 소통 활동으로서의 문학
4. 목적론적 윤리와 의무론적 윤리 01. 경험주의와 이성주의 01. 경험주의와 이성주의 02. 결과론적 윤리와 공리주의
Internet Computing KUT Youn-Hee Han
Linux를 이용한 Embedded 장비 개발
오토메타 형식언어 2003년도 제 2학기.
CHAPTER 21 UNIVARIATE STATISTICS
Chap 3. 표본조사 3.1 표본추출(Sampling)의 기초 3.2 단순임의표본추출 3.3 표본으로부터 모집단 추정
좋은 공학논문 작성을 위해서는 무엇이 필요한가?
제 14 장 거시경제학의 개관 PowerPoint® Slides by Can Erbil
Lecture #3 프로세스(Process).
제 1 장 경영과학의 기초 경영과학의 개념 발달과정 경영과학의 특성 적용절차와 적용분야 한밭대학교 산업경영공학과.
Cognitive radio Either a network or a wireless node changes its transmission or reception parameters to communicate efficiently avoiding interference with.
Internet traffic modeling and network design
유비쿼터스 컴퓨팅 프로젝트 소개 창병모
이산수학(Discrete Mathematics)
POWER POINT TEMPLATE 뭘 넣을까요 ㅋ THE BIZCAM SEND 조땡 OO 대학교 OO학과 00학번
4-1 Gaussian Distribution
제 5 장 상황이론(Contingency Theory) - Case Study -
여는 장 큰제목과 조원이름은 늘 가로중앙선에 중심을 맞춰주세요.
Systems Engineering 충북대학교 토목공학부 토목시스템공학전공 정보기술기반 건설경영연구실
개항기 조선과 동아시아 박 범 한국역사입문Ⅱ.
생산운영관리 입문 CHAPTER01 (Introduction to Operations Management)
Cpt.4 제품과 서비스의 설계 Product and Service Design 생산운영관리.
이산수학(Discrete Mathematics)
The Practice of KM operations
Management of Waiting Lines
수납형계단 & 바닥수족관 이다영 김수지 김은지 진윤정.
‘BSC기반 전략실행전문가 과정’+’The 6 Boxes Model’
대구의 부도심 대구의 주요축 동대구 부도심 4조 강민석 / 박성균 / 최은지/ 황재현/김예지.
전략적 원가관리 (7) (원가절감) Wisdom21 Management Consulting
Chatpter 09 입출력 시스템과 디스크 관리 01 입출력 시스템 관리 02 디스크의 구조와 스케줄링 03 RAID 요약
사도행전 13장 22절 말씀 –아멘 다 윗 을 왕 으 로 세 우 시 고 증 언 하 여 이 르 시 되 내 가 이 새 의 아 들
제4장 생산경영 계량모델 1. 생산의사결정과 모델 2. 선형계획 모델 3. 대기행렬 모델 4. 시뮬레이션 모델
품질(Quality), 시간(Time), 제약자원이론(Theory of Constraints)
Traffic Rules.
창의적 공학 설계 < 기술보고서의 작성 및 설계목적계통도의 이해 >
(제작자: 임현수)모둠:임현수,유시연,유한민
경찰행정과 세미나 결과를 공개해야한다. VS 비공개로 해야한다. 경찰의 근무성적평정 제도.
성전기공식(안) 식 순 1. 기공미사 2. 기 공 식 3. 축 하 연 천주교 수원교구 퇴촌성당.
1.예수 거룩한 주 예수 생명의 11.예수 권능의 주 예수 19.그 누구도 그 누구도 21.It's all about you.
한국리서치 web research noet 노익상
CHAPTER 1 OPERATIONS MANAGEMENT
성경의 맥을 잡아라 박소원
제4장 CPU 스케쥴링 운영체제 1-C반 박소라.
성공하는 사람들의 7가지 습관 T I M E.
가톨릭관동대학교 휴먼재활서비스학부 (언어재활상담전공)
창의적 공학 설계 < 발명과 특허 > : Creative Engineering Design
[도입 사례] 스타벅스의 인간중심 경영 스타벅스는 처음부터 인간에게 중심을 둔 기업이념을 확고히 한 기업이었다. 물론 혼란도 있었다. 이 회사는 지나친 확장정책으로 인하여 지난 2007년 어려움에 빠지게 되었다. 이때 스타벅스는 ‘인간중심의 경영’, ‘직원 사랑’의 이념을.
합리적 의사결정이론(rational decision-making theory)
11월 고등부 공과설교 업드림? 업드림! 갈라디아서 6:9-10.
Presentation transcript:

대기행렬(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) 모형 18.4.1 순수 출생모형 𝑝 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×60 12 = 120명 일 연간 신생아 수 = 𝜆𝑡 = 120ⅹ365=43,800명/년

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

18.4 순수 출생 및 사망모형들 예제 18.4.1 (대도시 신생아 출생모형) 신생아들 출생 비율=12분 1명, 출생시간 간격은 지수분포 어떤 3시간 기간 중의 처음 2시간 동안 40건의 출생증명서를 발급한 상태에서 충 3시간 동안 50건의 출생 증명서를 발급할 확률 𝑝 10 1 = ( 60 12 ×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,⋯,𝑁 18.4.2 순수 사망모형 𝑝′ 𝑁 𝑡+ℎ = −𝜇𝑝 𝑁 𝑡 𝑝′ 𝑛 𝑡 =−𝜇 𝑝 𝑛 𝑡 +𝜇 𝑝 𝑛+1 𝑡 , 0<𝑛<𝑁 𝑝′ 0 𝑡 =𝜇 𝑝 1 (𝑡) ⇒ 𝑝 𝑛 𝑡 = 𝜇𝑡 𝑁−𝑛 𝑒 −𝜇𝑡 𝑁−𝑛 ! , 𝑛=1,2,⋯,𝑁 𝑝 0 𝑡 =1− 𝑛−1 𝑁 𝑝 𝑛 (𝑡)

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

18.4 순수 출생 및 사망모형들 예제 18.4.2 (슈퍼마켓 화원 장미 판매) 주 중에 장미를 주문할 확률 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 더즌 예제 18.4.2 (슈퍼마켓 화원 장미 판매) 매주 말 (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,6 15 고객/시간 𝑛=7,8,⋯

18.5 일반 포아송 대기행렬모형 예제 18.5-1 (BBK 슈퍼마켓 – 3개의 계산대 운영) 𝑝 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 ) 3 10 10 𝑝 0 =8 𝑝 0 , 𝑝 5 = 𝑝 6 =8 𝑝 0 𝑝 𝑛≥7 = ( 10 5 ) 3 10 10 ( 10 15 ) 𝑛−6 𝑝 0 =8 ( 2 3 ) 𝑛−6 𝑝 0

18.5 일반 포아송 대기행렬모형 예제 18.5-1 (BBK 슈퍼마켓 – 3개의 계산대 운영) 𝑝 0 + 𝑝 0 2+4+8+8+8+8+8 2 3 +8 ( 2 3 ) 2 +8 ( 2 3 ) 3 +⋯ =1 𝑝 0 31+8(1+ 2 3 + 2 3 2 + 2 3 3 +⋯) =1 𝑝 0 31+8( 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 특별한 포아송 대기행렬모형 18.6.1 안정상태 성과척도들 Little’s Formula 𝐿 𝑠 = 𝜆 𝑒𝑓𝑓 𝑊 𝑠 , 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝑊 𝑞 𝜆 𝑒𝑓𝑓 = 시스템에 도착하는 유효도착률 = = 𝜆 ? < 𝜆 ? 𝑊 𝑠 = 𝑊 𝑞 + 1 ? ⇒ 𝐿 𝑠 = 𝐿 𝑞 + ? ? 𝑐 = 𝐿 𝑠 − 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝜇 ⇒ 시설활용도 = 𝑐 𝑐

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

18.6 특별한 포아송 대기행렬모형 예제 18.6.1 (Ozark 대학 방문객 주차장) 𝑝 𝑛 구하기 𝜆 𝑛 =6대/시간, n = 0, 1, 2, …, 8 𝜇 𝑛 = 𝑛 60 30 =2𝑛 𝑛=1,2,3,4,5 5 60 30 =10 𝑛=6,7,8, 𝑝 𝑛 = 3 𝑛 𝑛! 𝑝 0 𝑛=1,2,3,4,5 3 𝑛 5! 5 𝑛−5 𝑝 0 𝑛=6,7,8, 𝑝 0 + 𝑝 0 3 1! + 3 2 2! +⋯+ 3 5 5! + 3 6 5!5 + 3 7 5! 5 2 + 3 8 5! 5 3 =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 특별한 포아송 대기행렬모형 예제 18.6.1 (Ozark 대학 방문객 주차장) 유효도착률 𝜆 𝑒𝑓𝑓 구하기 𝑊 𝑞 = 𝑊 𝑠 − 1 𝜇 = 𝐿 𝑠 𝜆 𝑒𝑓𝑓 − 1 𝜇 = 3.1286 5.8737 − 1 2 𝑐 = 𝐿 𝑠 − 𝐿 𝑞 = 𝜆 𝑒𝑓𝑓 𝜇 = 5.8737 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 예제 18.6.2 (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 0.1 ln 𝜌 −1

18.6 특별한 포아송 대기행렬모형 18.6.2 단일 서버모형 ② (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 특별한 포아송 대기행렬모형 18.6.2 단일 서버모형 ② (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 특별한 포아송 대기행렬모형 18.6.3 다중 서버모형 (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 특별한 포아송 대기행렬모형 18.6.3 다중 서버모형 (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 특별한 포아송 대기행렬모형 18.6.3 다중 서버모형 (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 특별한 포아송 대기행렬모형 18.6.4 기계 수리모형 - (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−𝜌 𝜆 𝑒𝑓𝑓 =𝜆 ⇒ 𝐿 𝑞 , 𝑊 𝑠 , 𝑊 𝑞 는 18.6.1절에서 설명한 방법으로 구함.

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

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