User:Tqzhang1010/sandbox

brief: We will add something to the existing page.

topic: M/D/1 queue

Contents

• 1Model definition:
• Add transition matrix; add classic performance matrix and steps proving the equations.
• 2Stationary distribution
• 3Delay
• 4Busy period
• 5Finite capacity
  • 5.1Stationary distribution
  • 5.2Transient solution Add equations about this section according to the reference paper.
• Add 6. Application
• 7 References

Model definition[edit]

• An M/D/1 queue is a stochastic process whose state space is the set {0,1,2,3,...} where the value corresponds to the number of customers in the system, including any currently in service.
  • Arrivals occur at rate λ according to a Poisson process and move the process from state i to i + 1.
  • Service times are deterministic time D (serving at rate μ = 1/D).
  • A single server serves customers one at a time from the front of the queue, according to a first-come, first-served discipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.
  • The buffer is of infinite size, so there is no limit on the number of customers it can contain.

Classic performance matrix:

File:Basic matrix for md1.png

Example:

Customers arrive a Starbucks line at a rate of 20 per hour, and follows an exponential distribution. There is only one server, the service rate is at a constant of 30 per hour.

Arrival Rate: 20 per hour

Service Rate: 60 per hour

ρ=20/30=2/3

Using the queueing theory equations, the results are as following:

Average number in line= 0.6667

Average number in system: 1.333

Average time in line: 0.033

Average time in system: 0.067

Stationary distribution[edit]

• The number of jobs in the queue can be written as an M/G/1 type Markov chain and the stationary distribution found for state i (written π_i) in the case D = 1 to be^[4]

Delay[edit]

• Define ρ = λ/μ as the utilization; then the mean delay in the system in an M/D/1 queue is^[5]

  and in the queue:

Busy period[edit]

• The busy period is the time period measured from the instant a first customer arrives at an empty queue to the time when the queue is again empty. This time period is equal to D times the number of customers served. If ρ < 1, then the number of customers served during a busy period of the queue has a Borel distribution with parameter ρ.^[6][7]

Finite capacity[edit]

Stationary distribution[edit]

• A stationary distribution for the number of customers in the queue and mean queue length can be computed using probability generating functions.^[8]

Transient solution[edit]

• The transient solution of an M/D/1 queue of finite capacity N, often written M/D/1/N, was published by Garcia et al in 2002.^[9]

(Adding equations below according to the reference.)

The mean number of customers in M/D/1/N queue presented in Garcia et al. 2002 is as follows:

File:Mean number of customers.png

The mean waiting time W N in the M/D/1/N queuing system presented in Garcia et al. 2002 is as follows:

File:Mean waiting time.png