1、Simulation Technology,John Shi Chaojian,Merchant Marine College Shanghai Maritime University,3. Modeling,PROBABILISTIC MODELSQueuing Theory,Queuing System Population, characterized by an arrival rate() and an arrival distribution. Queue, with finite or infinite size and the service discipline. Servi

2、ce facility, characterized by the number and configuration of servers, and by a service rate() and a distribution of service times.,Pop,Queue,Serv. F,PROBABILISTIC MODELSQueuing Theory,Standard Notation for Individual Queues A/B/m/n/p A: arrival process (e.g. M if it is Poisson, D if it is determini

3、stic and G if it is general). B: service time (e.g. M if it is exponential, D if it is deterministic and G if it is general). m: number of servers n: maximum number of jobs that can be stored in the queue. p: maximum number of jobs in the universe of the queue.,PROBABILISTIC MODELSQueuing Theory,The

4、 Poisson Process Consider a sequence of events S=(s1,s2,sn), and let t(si) denote when event si happens. The sequence is temporally ordered (i.e., 0t(s1)t(s2) t(sn). If S satisfies the following rules, R1. Prob(t(si)=t(sj)=0 ij. R2. The probability that an event occurs in the interval t,t+t) is give

5、n by t+O(t2) for some constant . It si said to be a Poisson Process,PROBABILISTIC MODELSQueuing Theory,Littles Law The average number of jobs EN in a queuing system is equal to the average arrival rate of the jobs into the system, E, multiplied by the average time spent in the system, ET. That is EN

6、=EET PASTA Theorem (Poisson Arrivals See Time Averages) If a queue under steady-state has jobs arriving according to Poisson process, the probability that an arriving job will find n jobs ahead of it in the system is the probability that there are n jobs in the system at any random moment.,PROBABILI

7、STIC MODELSQueuing Theory,Queuing Equations N= T Nq= Tq T=Tq+1/ N=expected number of units in the queuing system, including both waiting line and and service facility. =arrival rate in units per time T= expected time in the queuing system, including both waiting line and and service facility. Nq= ex

8、pected number of units in the waiting line Tq= expected time in the waiting line =service rate in units per time P(n)=probability that exactly n population units are in the queuing system, including both waiting line and and service facility.,PROBABILISTIC MODELSQueuing Theory,Single-Service Channel

9、 Exponential Service time,PROBABILISTIC MODELSQueuing Theory,Single-Service Channel Arbitrary Service time (Mean service time distribution 1/, and its variance, 2 must be known and /1),PROBABILISTIC MODELSQueuing Theory,Single-Service Channel Constant Service time (service time=1/, and its variance,

10、 2=0),PROBABILISTIC MODELSQueuing Theory,Example: Single Server Queuing System A customer who arrives and finds the server idel enters service immediately. A customer who arrives and finds the server busy joins the end of a single queue. Upon completing service for a customer, the server choose a cu

11、stomer from the queue (if any) in a FIFO manner. Suppose interarrival time and service time are independent and identically distributed(IID).,PROBABILISTIC MODELSQueuing Theory,Example: Arrival procedure,Example: Departure procedure,PROBABILISTIC MODELSQueuing Theory,PROBABILISTIC MODELSInventory Co

12、ntrol,Single Period Model-No Setup Cost Units are purchased at a cost of C dollars per item to be sold during a single period for S dollars per item. The salvage value of any leftover items at the end of the period is equal to M dollars per unit. The quantity purchased at the beginning of the period

13、 is Q items, and the number of units sold during the period is X, X represents demand for the items and is a random variable described by the distribution p(x),PROBABILISTIC MODELSInventory Control,Single Period Model-No Setup Cost Optimum order quantity is the largest Q for which,PROBABILISTIC MODE

14、LSInventory Control,Lost Size Reorder Point Model Reorder when reorder point reached. Safety stock can be added. SS determined by: 1) experiment, 2) statistics.,PROBABILISTIC MODELSInventory Control,Periodic Review Model Review interval is fixed and order quantity varies.,PROBABILISTIC MODELSInvento

15、ry Control,Example: Single Product Inventory System Times between demands 0.1 month Demand size 1,2,3,4 with probability 1/6,1/3,1/3,1/6 Order at beginning of each month. Z items cost=32+3*Z. if Z=0, cost=0. Arrival time 0.5 t0 1 month uniformly distributed. Use stationary policy (if Is, Z=S-I; else

16、 Z=0.) Holding cost 1/(itemmonth); backlog cost 5/(itemmonth).,PROBABILISTIC MODELSInventory Control,Example: Compare policies,19,Stochastic Processes,A stochastic process is a collection of random variables The index t is often interpreted as time. is called the state of the process at time t. The

17、set T is called the index set of the process. If T is countable, the stochastic process is said to be a discrete-time process. If T is an interval of the real line, the stochastic process is said to be a continuous-time process. The state space E is the set of all possible values that the random var

18、iables can assume.,20,Stochastic Processes,Examples: Winnings of a gambler at successive games of blackjack; T = 1, 2, ., 10, E = set of integers. Temperatures in Laurel, MD. on September 17, 2008; T = 12 a.m. Wed., 12 a.m. Thurs.), E = set of real numbers.,21,Markov Chains,A stochastic process is c

19、alled a Markov chain provided that for all states and all .,22,Markov Chains,We restrict ourselves to Markov chains such that the conditional probabilities are independent of n, and for which (which is equivalent to saying that E is finite or countable). Such a Markov chain is called homogeneous.,23

20、,Markov Chains,Since probabilities are non-negative, and the process must make a transition into some state at each time in T, then We can arrange the probabilities into a square matrix called the transition matrix.,24,Markov Matrix,Let P be a square matrix of entries defined for all Then P is a Markov matrix provided that Thus the transition matrix for a Markov chain is a Markov matrix.,25,Markov Matrix,Example: This Markov matrix corresponds to a