February 10, 2022 3 min to read

DES Chapter 1-4 What is Deiscrete-Event Simulation?

Chapter 1-Overview of Computer Simulation

ReadMe

아래 내용은 최병규, 강동훈 저서인 Modeling and Simulation of discrete-event systems 책의 내용을 주로 다루고 있습니다.

해당 시리즈의 목차입니다. (챕터 목차는 제일 아래에 있습니다.)

Overview of Computer Simulation
Basics of Discrete-Event System Modeling and Simulation
Input Modeling for Simulation
Introduction to Event-Based Modeling and Simulation
Parameterized Event Graph Modeling and Simulation
Introduction to Activity-Based Modeling and Simulation
Simulation of ACD Models Using Arena
Output Analysis and Optimization
State-Based Modeling and Simulation
Advanced Topics in Activity-Based Modeling and Simulation
Advanced Event Graph Modeling for Integrated Fab Simulation
Concepts and Applications of Parallel Simulation (Here)

What is discrete-event simulation?

위 그림은 공장의 머신과 버퍼로 이루어진 하나의 싱글 서버 시스템을 얘기하고 있습니다. 시스템의 메커니즘에 대해서는 세가지로 설명할 수 있는데요. 하나는 inter-arrival 타임인 \(t_a\) 에 의해서 시스템에 job이 도착하고 그 job은 머신이 비가동중일 경우에 로딩됩니다. 만약 그렇지 않으면 버퍼에 들어가게 됩니다. 두 번째는 로딩된 job은 서비스 타임인 \(t_s\) 에 의해서 처리되고 언로딩됩니다. 끝으로, job이 언로딩될때, 버퍼가 비어있지 않으면 다음 job을 로딩합니다. 다시 위 그림을 보면 시스템의 상태 변수들은 \(q\) 와 \(m\) 이 있습니다. 여기서 \(q\) 는 버퍼에 들어간 job의 수를 의미하고 \(m\) 은 머신의 상태(비가동, 가동)을 의미합니다. 그리고 event는 도착(Arrive), 로드(Load), 언로드(Unload)로 정의합니다.

Description of System Dynamics

상태변수와 이벤트를 사용하면 싱글서버의 시스템 동작은 딱 잘라서 세 가지로 설명할 수 있습니다. 첫 번째는 도착 이벤트가 발생했을때, \(q\) 는 값이 하나가 올라가고, 다음 도착 이벤트가 언제 발생하는 지 \(t_a\) 에 계산되어 스케줄링됩니다. 그리고 로드 이벤트가 바로 스케줄링 되는데, 머신이 비가동인 조건입니다. 두 번째로 로드 이벤트가 발생할 때는 \(q\) 가 값이 하나 내려가고 \(m\) 이 1(가동)으로 바뀝니다. 그리고 언로드 이벤트가 \(t_s\) 에 의해서 스케줄링됩니다. 마지막으로 언로드 이벤트가 발생할 때는 \(m\) 이 다시 0(비가동)으로 변경되고 \(q\) 가 0보다 클 경우에 로드 이벤트를 즉시 스케줄링합니다. 싱글 서버 시스템의 동작은 그래프 아래 Fig. 1.6. 로서 표현할 수 있으며 이를 Event Graph라고 부릅니다.

Simulation Model Trajectory

시스템의 실행가능한 모델을 simulation model이라 부르고 모델의 상태 변수들을 추적하는 것을 simulation model trajectory라 부릅니다. \(\{a_k\},\ \{s_k\}\) 를 정의하자면 inter-arrival 시간 \(t_a\) 집합을 \(a_k\) 라 하고 서비스 타임 \(t_s\) 시간 집합을 \(s_k\) 로 얘기하겠습니다. 싱글 서버 시스템의 시뮬레이션 모델 궤적은 아래 Fig. 1.7.로 볼 수 있는데요. 여기서 \(t_i\) 들은 이벤트 시간들입니다. \(X(t)\) 는 입력 궤적이고 \(Q(t)=\{q(t),\ m(t)\}\) 는 시스템 상태 변수들의 궤적입니다.

여기서 얘기하는 시간은 표현하는 타겟 시스템이 시뮬레이션 되는 물리적 시간을 표현하기 위한 로지컬한 시뮬레이션 시간입니다. 위 Fig. 1.7. 에서 \(t_1(=a_1)\) 은 job \(J_1\) 이 비어있는 시스템에 도착하고 비가동 머신이 서비스 시간 \(s_1\) 를 기준으로 처리하기 위해 로딩되는 것을 의미합니다. 로딩되고 처리하는 동안 다른 Job \(J_2\) 가 \(t_2(=a_1+a_2)\) 에 도착했고 머신이 가동상태이기에 버퍼로 들어가게 됩니다. 버퍼는 \([t_2,\ t_3]\) 동안 하나의 job을 가지고 있습니다. \(t_3(t_1+s_1)\) 은 첫 번째 Job \(J_1\) 이 언로딩되고 버퍼에 들어간 두 번째 Job \(J_2\) 이 머신에 로딩됩니다. 이어서 \(t_4(t_3+s_2)\) 는 \(J_2\) 의 작업이 끝나고 언로딩되면서 시스템은 빈 채로 머신은 비가동으로 바뀌면서 끝납니다. \(t_5(=a_1+a_2+a_3)\) 는 다른 job \(J_3\) 가 시스템에 도착하면서 바로 머신에 로딩됩니다. 나머지는 위 설명의 반복입니다.

Collecting Statistics from the Model Trajectory

서비스 시스템을 시뮬레이션할 때는 큐의 길이, 대기시간 분배, 체류 시간, 서버 가동률 등을 고려해야 합니다. 싱글 서버 시스템의 경우에는 아래의 조건을 만족하는 정보를 수집할 수 있습니다.

큐의 길이 \(q(t)\) 는 해당 시간에 평균 큐 길이를 알 수 있습니다. \(t\ \in\ [t_0,\ t_{10}]:\) AQL(average queue length) Fig. 1. 7. 의 동작에 따라 계산하자면 \(\text{AQL}=\{(t_3-t_2)+(t_7-t_6)+2(t_8-t_7)+(t_9-t_8)+2(t_{10}-t_9)\}/t_{10}\) 으로 볼 수 있습니다.
대기 시간 \(\{W_j\}\) 는 평균 대기 시간(AWT: average waiting time)을 구할 수 있습니다. 똑같이 Fig. 1. 7.의 동작에 따라 계산하면 \(\text{AWT}=\{W_1+W_2+W_3+W_4\}/4=\{0+(t_3-t_2)+0+(t_8-t_6)\}/4=(t_3-t_2+t_8-t_6)/4\)
체류 시간 \(\{S_j\}\) 는 평균 체류 시간(AST: average sojourn time)을 구할 수 있습니다. 역시나 마찬가지로 Fig. 1.7.의 동작에 따라 계산하면 \(\text{AST}=\text{AWT}+\text{Average service time}=\text{AWT}+(s_1+s_2+s_3+s_4)/4\) 입니다.
서버 가동률

서버 가동률은 해당 시간동안의 평균 가동률을 알 수 있습니다.
\[t\ \in\ [t_0, t_{10}]:U(\text{utilization})\\ U=\{(t_4-t_1)+(t_{10}-t_5)\}/t_{10}\]