2.2 Simulating the Psychiatrists Case
2.2 Simulating the Psychiatrists Case
In the previous section, we showed how to analyze a case with five psychiatrists acting as five parallel servers processing a queue of patients waiting for an intake. Moreover, we proposed a good rule to control the queue length. In this section, we discuss the algorithms used to produce Fig. 2.1.
Before accounting for holidays, the weekly capacities of the five psychiatrists under the unbalanced and balanced plans are, respectively,
\begin{align*} b^u & = (1,1,1,3,9), & b^b & = (2,2,3,4,4). \end{align*}To make the case with unbalanced capacity and spread holidays, we take
\begin{align*} c_{i,k}^{\mathrm{spread}} & =b_i^u\1{i\neq1+((k-1)\bmod5)}. \end{align*}For the case with unbalanced capacity and synchronized holidays, we take
\begin{align*} c_{i,k}^{\mathrm{sync}} & =b_i^u\1{(k-1)\bmod5\neq0}. \end{align*}The corresponding balanced schemes are obtained by replacing \(b^u\) in the two expressions above by \(b^b.\) In what follows, let \(c_{i,k}\) denote the capacity of psychiatrist \(i\) in week \(k\) for any one of these four scenarios.
We simulate \(n=1000\) weeks, with independent weekly arrivals \(a_k\sim\Pois{11.8}.\) For each capacity scenario, the initial queue length is \(L_0=0,\) and the total capacity in week \(k\) is \(c_k=\sum_{i=1}^{5}c_{i,k}.\) We use the same generated arrival sequence for all four scenarios. Combining the balanced and unbalanced plans with the spread and synchronized holiday patterns gives four capacity scenarios. Applying Alg. 2.2.1 to each scenario gives four queue-length trajectories. Their pointwise minimum and maximum are the two curves in the left panel of Fig. 2.1.
\begin{algorithm}
\caption{Compute the queue lengths.}
\begin{algorithmic}[1]
\State \textbf{Input:} arrivals \((a_1,\, \ldots,\, a_n),\) capacities \((c_1,\, \ldots,\, c_n),\) and initial queue length \(L_0\).
\State \textbf{Output:} the list \(L\) of queue lengths after each week.
\State \(L\gets\qb{}\)
\For{\(k=1,\, \ldots,\, n\)}
\State \(d_k\gets\Min{L_{k-1}+a_k,\, c_k}\)
\State \(L_k\gets L_{k-1}+a_k-d_k\)
\State \(L\gets\pr{Append}\rb{L,\, L_k}\)
\EndFor
\Return \(L\)
\end{algorithmic}
\end{algorithm}
For the controlled system in the right panel of Fig. 2.1, we use the capacity rule in (2.1.7). Alg. 2.2.2 implements the resulting simulation. We apply the control rule separately with \(e=1,\) \(e=2,\) and \(e=5.\) The resulting trajectories are shown in the right panel of Fig. 2.1.
\begin{algorithm}
\caption{Simulate the queue with state-dependent capacity.}
\begin{algorithmic}[1]
\State \textbf{Input:} arrivals \((a_1,\, \ldots,\, a_n),\) control size \(e,\) and initial queue length \(L_0\).
\State \textbf{Output:} the list \(L\) of queue lengths after each week.
\State \(L\gets\qb{}\)
\For{\(k=1,\, \ldots,\, n\)}
\If{\(L_{k-1}\geq48\)}
\State \(c_k\gets12+e\)
\ElsIf{\(L_{k-1}\leq24\)}
\State \(c_k\gets12-e\)
\Else
\State \(c_k\gets12\)
\EndIf
\State \(d_k\gets\Min{L_{k-1}+a_k,\, c_k}\)
\State \(L_k\gets L_{k-1}+a_k-d_k\)
\State \(L\gets\pr{Append}\rb{L,\, L_k}\)
\EndFor
\Return \(L\)
\end{algorithmic}
\end{algorithm}
TF 1.
A server with total capacity \(c_k\) in period \(k\) serves two parallel queues. Queue \(i\) has reserved capacity \(r^i,\) where \(r^1+r^2\leq c_k,\) and unused reserved capacity cannot be assigned to the other queue. Capacity beyond the reservations is assigned to queue 1 with priority. Jobs arriving in period \(k\) cannot be served until period \(k+1.\) Claim: The system is described by
\begin{align*} d_k^1 & = \Min{\L_{k-1}^1,c_k-r^2}, & c_k^2 & = c_k-d_k^1, \\ d_k^2 & = \Min{\L_{k-1}^2,c_k^2}, & \L_k^i & = \L_{k-1}^i+a_k^i-d_k^i,\qquad i\in\set{1,2}. \end{align*}Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. If \(d_k^1<r^1,\) the expression \(c_k-d_k^1\) incorrectly assigns unused capacity reserved for queue 1 to queue 2. The correct recursion is
\begin{equation*} c_k^2=c_k-\Max{r^1,d_k^1}. \end{equation*}The other recursions remain unchanged.
An example is the operation room of a hospital. There is a weekly capacity, part of which is reserved for emergencies. It might not be possible to assign this reserved capacity to other patient groups, because it should be available at all times for emergency patients. As a result, unused capacity is lost. In practice, it may not be as extreme as in the model, but part of the unused capacity is still lost. ’Use it, or lose it’ often applies to service capacity.
In the queueing systems we have analyzed up to now, the server is always present
to start serving jobs at the moment they arrive.1A queue under an
\(N\)-policy; the curve labeled \(I\) shows \(30I_k\).
. However, in cases in which there is a significant
cost associated with changing the server from idle to busy this condition is
typically not satisfied. To reduce the average cost, we can use an \(N\)-policy,
which works as follows.2\(N\)-policies are used to decide when to heat up a
large oven. As soon as the system becomes empty (and the server idle), the
server switches off. Then it waits until at least \(N\) jobs have arrived, and
then it switches on. The server processes jobs until the system is empty again,
then it switches off, and remains idle until \(N\) new jobs have arrived, and so on,
cycle after cycle. Note that under an \(N\)-policy, even though the load remains the
same, the server has longer busy and idle times.
Suppose it costs \(K\) Euro to set up the server, independent of the time it has been idle, and each job charges \(h\) Euros per unit time while in the system. The problem is to find a switching threshold \(N^{*}\) that minimizes the long-term average cost.
TF 2.
Claim: Under an \(N\)-policy, the long-run utilization \(\rho\) depends on the threshold \(N.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. In a stable system, flow balance implies that the long-run departure rate is \(\lambda,\) so \(\rho=\lambda\E S,\) independently of \(N.\) The threshold changes the lengths of the busy and idle periods, but not the long-run fraction of time spent serving jobs.
TF 3.
Claim: Compared with the same system whose server is always available, an \(N\)-policy reduces the average waiting time.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. Jobs that arrive while the server is off must wait until the queue reaches \(N.\) The policy trades longer waiting times for a lower long-run average switching cost.
TF 4.
Let \(I_k\) indicate whether the server is on in period \(k,\) and consider the recursion
\begin{equation*} I_k=\1{\L_{k-1}\geq N}+I_{k-1}\1{0<\L_{k-1}<N}. \end{equation*}Claim: If \(\L_{k-1}=0\) and \(I_{k-1}=1,\) then the server switches off, so \(I_k=0.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. When \(\L_{k-1} = 0,\) the first term is \(0\) (since \(0 < N\)) and the second term is \(I_{k-1} \cdot 0 = 0\) (since \(0 < \L_{k-1}\) is false). Hence \(I_k = 0.\)
TF 5.
Claim: Over periods \(1,\ldots,T,\) the number of switch-on events is
\begin{equation*} \sum_{k=1}^{T}\1{I_k>I_{k-1}}. \end{equation*}Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. Since \(I_k\in\set{0,1},\) the inequality \(I_k>I_{k-1}\) holds exactly when the state changes from off to on.
Exercise 6.
Derive recursions to model the situation in which jobs that arrive in period \(k\) can be served in that period. If the system length hits \(N\) (becomes empty) in period \(k\), the machine switches on (off) in period \(k + 1\). Assume the machine is off at \(k = 0\).
Hint
Introduce a variable \(I_k\in\set{0, 1}\) to keep track of the state of the server. Then, \(I_{k+1} = \1{\L_k\geq N} + I_k \1{0<\L_k<N}\) implements the \(N\) policy.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
The required recursions are
\begin{align*} I_k & = \1{\L_{k-1}\geq N}+I_{k-1}\1{0<\L_{k-1}<N}, \\ d_k & = \Min{\L_{k-1}+a_k,I_kc_k}, \\ \L_k & = \L_{k-1}+a_k-d_k. \end{align*}The first recursion implements the switching rule, while the factor \(I_k\) makes the available capacity zero whenever the server is off. Note that when arrivals cannot be served in the period in which they arrive, it might be that the system is never empty. For instance, if \(a_{k}\sim\Unif{(4, 10)},\) then \(L_{k}\geq a_{k} \geq 4\) for all \(k.\)
Exercise 7.
In the setting of the previous exercise, suppose each switch-on event costs \(K,\) each period in which the server is on costs \(\beta,\) and each customer in the system costs \(h\) per period. Express the total cost over periods \(1,\ldots,T\) in terms of \(I_k\) and \(\L_k.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
The total cost is
\begin{equation*} C_T=\sum_{k=1}^{T}\rb{\beta I_k+h\L_k+K\1{I_k>I_{k-1}}}. \end{equation*}The three terms are, respectively, the operating cost, the holding cost, and the switch-on cost.
Exercise 8.
Consider3Tandem networks. a production network with two production stations in tandem, that is, the jobs processed at station 1 move at the end of period\(k\) to station 2. What are the recursions?
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
Let \(a^1_k\) be the external arrivals at station 1, and the departures of station 1 are the arrivals at station 2: \(a_k^2 = d_{k}^1.\) Thus,
\begin{align*} d^i_k &= \min\{\L_{k-1}^i, c_k^i\}, & \L_k^i &= \L_{k-1}^i -d_k^i + a_k^i. \end{align*}% #+beginexercise % Consider4Splitting streams. a paint mixing machine that produces products for two downstream packaging machines\(A\) and\(B,\) each with its own queue. % In the simplest model, the content of the queue at the mixing machine is proportional to the demands \(\lambda^A\) and \(\lambda^B\) for the packaging machines. % Provide the recursions. % #+beginsolution % At the mixing machine \(d_k=\min\{L_k, c_k\}.\) Therefore, in this very simple model, \(a_k^A = d_k \lambda^A/(\lambda^A+\lambda^B),\) and likewise for the other downstream station. % #+endsolution % #+endexercise