\documentclass{article}
\title{{\bf Performance Modelling, Course 336 \\ P.G. Harrison \\
Outline Solutions to Coursework \\
March 2003}}
\date{}
\begin{document}
\maketitle
\section*{Coursework 1}
\begin{enumerate}
\item[(1)] 
\begin{enumerate}
\item[(a)] Demand per task depends only on workload and so the ordering
of nodes by workload by task satays the same as $K$ increases.  Hence
bottleneck stays in the same place.
\item[(b)] As $K \rightarrow \infty$ at least one node saturates and so
has utilisation 1.  This is the largest possible utilisation, so the
bottleneck must get utilisation 1.
\item[(c)] If there is a single bottleneck, the other nodes must get
utilisation $ < 1$, so have finite queues with probability 1
\item[(d)] The bottleneck, since its maximum throughput is its service
rate (utilisation approaches 1 as $K \rightarrow \infty$) and this limits
the performance of the rest of the network; this is clarified in the last
lecture's notes.
\item[(e)] You can always increase performance by upgrading the
bottleneck.  Hence optimum performance when all servers are equal
bottlenecks, i.e. all have the same demand ($\lambda_i / \mu_i$).
\end{enumerate}
\item[(2)] 
\begin{enumerate}
\item[(a)] Response time should halve, since, if it depends on no other
parameters, all we have done is to change the basic time unit -- counting
half seconds instead of seconds.
\item[(b)] Now we're not just changing the time unit.  When service times
are highly variable response time might increase or decrease for a
particular visit to the queue.  What do you think would happen to mean
response time?  Would you like to use a highly erratic system or a
consistent one?  Most people prefer the latter and this is backed up in
the M/G/1 queue analysis.
\item[(c)] Back to answer of (a), a special case in fact.
\end{enumerate}

\item[(3)]  Arrival rate = throughput in steady state, so $\lambda = $
utilisation $\times$ service rate.

\item[(4)] 
\begin{enumerate}
\item[(a)] Rate = repairs per hour so \\$P(T>0.5) = 1 - P(T\leq 0.5) =
e^{-2
\times 0.5} = 1/e$.
\item[(b)] By memoryless property, same answer
\end{enumerate}
\end{enumerate}

\section*{Coursework 2 (assessed)}
\begin{enumerate}
\item[(1)] Let probability distribution/density functions of $A$ by
$F_A$/$f_A$, $B$ similarly.
\begin{eqnarray*}
P(T_B<T_A) &=& \int_0^\infty P(T_B<u | T_A=u) f_A(u)du \\
&=& \int_0^\infty (1-e^{-\mu u}) \lambda e^{-\lambda u} du \\
&=& \int_0^\infty \lambda e^{-\lambda u} du -
\int_0^\infty e^{-\mu u} \lambda e^{-\lambda u} du \\
&=& 1 -  \lambda \int_0^\infty e^{-(\lambda + \mu) u} du \\
&=& 1 - \lambda/(\lambda + \mu) \\
&=& \mu/(\lambda + \mu)
\end{eqnarray*}
Makes no difference if $T_A$ had already started (provided it had not
finished) by memoryless property.

\item[(2)] $F_n(x) = P(T_n \leq x) = P($ at least $n$ arrivals
up to time $x$) \\$= 1 - P($ less than $n$ arrivals
up to time $x$) \\$= 1 - \sum_{k=0}^{n-1} P(k$ arrivals in interval of
length $x$)
\end{enumerate}


\section*{Coursework 3}
\begin{enumerate}
\item[(1)]  All delays are exponential so all state holding times are
exponential, hence Markov property holds at all times.

State 1 can always be reached since it is entered immediately
after an abort or completion at phase $M$.  Every state $i$, $1 \leq i
\leq M$ is reached by a job that does complete service, which happens
with probability $>0$.  Hence irreducible.

Flux into state $i (2 \leq i \leq M) = \pi_{i-1} \mu_{i-1} \alpha_{i-1} 
$

Flux out of state $i (2 \leq i \leq M) = \pi_{i} \mu_{i} $

Flux into state $1 = \sum_{k=2}^{M-1} \pi_{k} \mu_{k} (1 - \alpha_{k}) +
\pi_{M} \mu_{M}$

Flux out of state $1 = \pi_{1} \mu_{1} (1 - \alpha_{1})$

So $$\pi_i = \prod_{k=2}^i \frac{\mu_{k-1} \alpha_{k-1}}{\mu_k} \pi_1$$
Normalising, $$\pi_1 = \left[\sum_{j=1}^M \prod_{k=2}^j \frac{\mu_{k-1}
\alpha_{k-1}}{\mu_k} \right]^{-1}$$

Throughput of normal completions = $\pi_M \mu_M$, where $\pi_M$ defined as
above.

Throughput of aborted jobs = $$\sum_{k=1}^{M-1} (1-\alpha_k) \pi_k \mu_k$$
Check:  Throughput of aborted jobs should also be:
$$ \pi_1 \mu_1 - \pi_M \mu_M$$

\item[(2)] You can draw the diagram!
Balance equation for contour round states $1,2,\ldots,i$ is:
$$p_i \lambda / (i+1) = p_{i+1} \mu$$
so that $$p_{i} = \rho^i/i! p_0$$
Normalising, $p_0 = e^{-\rho}$, so steady state always exists.

Utilisation = $1-p_0 = 1-e^{-\rho}$.

Throughput = $(1-e^{-\rho})\mu$ since service rate is constant.

Mean queue length $L = \sum_{i=1}^\infty ip_i = p_0\sum_{i=1}^\infty
i\rho^i/i! \\=  p_0\rho\sum_{i=1}^\infty \rho^{i-1}/(i-1)! = \rho$

Mean response time $W = L/(1-e^{-\rho})\mu = \rho/(1-e^{-\rho})\mu =
\lambda/(1-e^{-\rho})\mu^2$

\item[(3)]  As in question 2,
$$p_i \lambda / (i+1)^b = p_{i+1} \mu (i+1)^c$$
i.e. $$p_{i+1} = p_i \rho / (i+1)^{b+c}$$
Thus $$p_{i} = \rho^i/(i!)^{b+c} p_0$$
$$p_0 = \left[ \sum_{k=0}^\infty \rho^k/(k!)^{b+c} \right]^{-1}$$
Same as previous question / IS queue when $b+c =1 $.

\item[(4)] Let $S$ denote a service time and $A$ an
interarrival time randm variable.  
\begin{eqnarray*} P(D \leq t) &=& \rho P(S \leq t) + (1-\rho) P(A+S \leq
t)\\
&=& \rho(1-e^{-\mu t}) + (1-\rho)\int_{u=0}^\infty P(A \leq t-S | S=u) \mu
e^{-\mu u} du\\
&=& \rho(1-e^{-\mu t}) + (1-\rho)\int_{u=0}^t (1-e^{-\lambda (t-u)}) \mu
e^{-\mu u} du\\
&=& 1-e^{-\mu t} - \mu(1-\rho)e^{-\lambda t}\int_{u=0}^t
e^{-(\mu-\lambda)u}du\\
&=& 1-e^{-\mu t} - e^{-\lambda t}(1-e^{-(\mu-\lambda)t}) \\
&=& 1-e^{-\lambda t}
\end{eqnarray*}
\end{enumerate}

\section*{Coursework 5}
\begin{enumerate}
\item[(1)] Network defined by the set  $V = \{x_i = e_i/\mu_i | 1
\leq i \leq M\}$ by Jackson's theorem.  Network with node $j$ removed is
that defined by the set $V_j = V \backslash \{x_j\}$ and that with nodes
$i,j$ removed by the set $V_{ij} =  V \backslash \{x_i,x_j\}$.

Let state space of network be $S(K) = \{{\bf n} | \sum_{k=1}^M n_k = K,
n_k \geq 0\}$, $G_j(K), G_{ij}(K)$ be normalising constants corresponding
to networks
$V_j(K), V_{ij}(K)$ respectively.
\begin{eqnarray*} 
P(N_j = h) &=& G^{-1} \sum_{{\bf n}\in S(K), n_j=h}\; \prod_{m=1}^M
x_m^{n_m} \\
&=& G^{-1}x_j^{h} \sum_{{\bf n}\in S(K), n_j=0}\; \prod_{m\neq j}
x_m^{n_m} \\
&=& G^{-1}x_j^{h} G_j(K-h) \mbox{~~~~~~~~{\bf with explanation as in
lectures}} \\
P(N_i=k,N_j = h) &=& G^{-1} \sum_{{\bf n}\in S(K), n_i=k,n_j=h}\;
\prod_{m=1}^M x_m^{n_m} \\
&=& G^{-1}x_i^{k} x_j^{h} \sum_{{\bf n}\in S(K), n_i=n_j=0}\; \prod_{m\neq
i,j} x_m^{n_m} \\
&=& G^{-1}x_i^{k} x_j^{h} G_{ij}(K-k-h) \mbox{~~~~~~~~{\bf with
explanation as in lectures}}
\end{eqnarray*}
Therefore $$P(N_i=k | N_j = h) = \frac{P(N_i=k,N_j = h)}{P(N_j = h)} =
\frac{x_i^{k} G_{ij}(K-k-h)}{G_j(K-h)}$$

\item[(2)] Implement if you get time!
\end{enumerate}


\end{document}