EEL6507 Spring 2009, Lecture 35, Monday 2009/04/13 (Notes created by Adam Flynn)

Agenda: Idle/Busy: Time, Distribution

Idle Time Distribution

Below, $I$ represents Idle Time.

$Prob[I \le y] = F(y)$

For M/G/1, the probability of $k$ arrivals in a time interval y is: $\frac{(\lambda y)^k}{k!} e^{-\lambda y}$ .

Also, if we are idle for a time period y, we know that 0 arrivals have occurred.

Therefore,

$Prob[I > y] = Prob[no \ arrivals \ in \ y] = e^{-\lambda y}$

$Prob[I \le y] = 1 - e^{-\lambda y}$

Hence, idle time is Markovian!

Busy Time Distribution

Observation: If we only care about total work/busy time, the order jobs are served doesn't matter.

If we were concerned with minimizing the number of jobs in the queue, we would want to serve the shortest jobs first.

Since we only care about the total work/busy time, we can model the queue as a stack instead (last-come, first-served).

Busy time illustration

Define the following:

$Χ i$ = RV to describe the time required to solve $C i$ and all customers that arrive before we serve $C i - 1$ .

$Χ i$ is independent of $Χ j$

Busy Period and $Χ i$

$Prob[Busy \ Period] \le x] = Prob[\Chi_1 \le x]$

What is $Χ i$ ?

In the example above, there are 3 arrivals while $C 1$ is in service
$Χ 1 = x 1 + Χ 4 + Χ 3 + Χ 2$
- $B^*_i(s)$ is Laplace Transform of busy time, $\ B^*(s)$ is Laplace Transform of service time

Derivation of general $B^*_1(s)$

Note: Errors may have occurred during transcription of derivation presented in lecture, please update if needed ...

$E[e^{-s \Chi_1} | x_1 = x, v = k] = e^{-s x} E[e^{-s \Chi_1}] ... E[e^{-s \Chi_k}]$

Since $E[e^{-s \Chi_i}] = B^*_1(s)$ ,

$E[e^{-s \Chi_1} | x_1 = x, v = k] = e^{-s x} [B^*_1(s)]^k$

$E[e^{-s \Chi_1} | x_1 = x] = \sum_{k}{Prob[k \ arrivals \ in \ x]} E[e^{-s \Chi_1} | x_1 = x, v = k] = \sum_{k}{e^{-\lambda x} \frac{(\lambda x)^k}{k!} e^{-s x} (B^*_1(s))^k}$