31:T406,u_vs_m = { const svg = d3.select(DOM.svg(width, height)); const bar = svg.append("g") .attr("fill", "steelblue") .selectAll("rect") .data(data_u_vs_m) .enter().append("rect") .attr("x", (d, i) => x(i+1)) .attr("width", 50) .attr("y", (d, i) => y_u_vs_m(d)) .attr("height", (d, i) => (height - margin.bottom - y_u_vs_m(d))); svg.append("g") .call(xAxis); svg.append("g") .call(yAxis_u_vs_m); svg.append("text") // x-axis label .attr("transform", "translate(" + (width/2) + " ," + height + ")") .style("text-anchor", "middle") .style("font", "12px sans-serif") // .attr("dx", "0.75em") .text("Number of servers"); svg.append("text") // y-axis label .attr("transform", "rotate(-90)") .attr("y", 0) .attr("x",0 - (height / 2)) .attr("dy", "0.75em") .style("font", "12px sans-serif") .style("text-anchor", "middle") .text("Utilization rate"); return svg.node(); }32:T414,util_vs_m = { const svg = d3.select(DOM.svg(width, height)); const bar = svg.append("g") .attr("fill", "steelblue") .selectAll("rect") .data(data_util_vs_m) .enter().append("rect") .attr("x", (d, i) => x(i+1)) .attr("width", 50) .attr("y", (d, i) => y_util_vs_m(d)) .attr("height", (d, i) => height - margin.bottom - y_util_vs_m(d)); svg.append("g") .call(xAxis); svg.append("g") .call(yAxis_util_vs_m); svg.append("text") // x-axis label .attr("transform", "translate(" + (width/2) + " ," + height + ")") .style("text-anchor", "middle") .style("font", "12px sans-serif") // .attr("dx", "0.75em") .text("Number of servers"); svg.append("text") // y-axis label .attr("transform", "rotate(-90)") .attr("y", 0) .attr("x",0 - (height / 2)) .attr("dy", "0.75em") .style("font", "12px sans-serif") .style("text-anchor", "middle") .text("Utilization factor"); return svg.node(); }33:T414,tq_vs_m = { const svg = d3.select(DOM.svg(width, height)); const bar = svg.append("g") .attr("fill", "steelblue") .selectAll("rect") .data(data_tq_vs_m) .enter().append("rect") .attr("x", (d, i) => x(i+1)) .attr("width", 50) .attr("y", (d, i) => y_tq_vs_m(d)) .attr("height", (d, i) => height - margin.bottom - y_tq_vs_m(d)); svg.append("g") .call(xAxis); svg.append("g") .call(yAxis_tq_vs_m); svg.append("text") // x-axis label .attr("transform", "translate(" + (width/2) + " ," + height + ")") .style("text-anchor", "middle") .style("font", "12px sans-serif") // .attr("dx", "0.75em") .text("Number of servers"); svg.append("text") // y-axis label .attr("transform", "rotate(-90)") .attr("y", 0) .attr("x",0 - (height / 2)) .attr("dy", "0.75em") .style("font", "12px sans-serif") .style("text-anchor", "middle") .text("Average waiting time in queue"); return svg.node(); }34:[] 2f:{"title":"A visual introduction to queueing theory","cells":[{"id":0,"value":"md`# A visual introduction to queueing theory`","pinned":false,"hidden":false,"mode":"ojs"},{"id":86,"value":"md`\\`NOTE: This is very much a work in progress! It is as much an introduction to queueing theory for you and me as it is an experiment in learning d3.js for me.\\``","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"md`## A single-stage queue\n\nWe begin by defining the key parameters that come into play in the simplest queueing model: a single-stage queue. These are:\n1. *p* is the __average service time__, and is associated with the __coefficient of variation in service__ of *CV_p*\n2. *a* is the __average interarrival time__, and is associated with the __coefficient of variation in arrivals__ of *CV_p*\n3. *m* is the number of (identical) __servers__.\n\nGiven these parameters, we can define the __utilization rate__ *u* of the system to be`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"tex.block`u(p, a, m) = \\dfrac{p}{a \\cdot m}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":90,"value":"md`The utilization rate is well-defined only if it does not exceed 1. This translates into the restriction`","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"tex.block`p \\leq a \\cdot m.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":114,"value":"u = function (p, a, m) { \n if (p > a * m) {\n return NaN;\n } else {\n return p / (a * m);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"md`We can rewrite this expression for *u* in terms of the __average arrival *rate*__ (which is simply the reciprocal of the average interarrival time) as follows:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"tex.block`u = \\underbrace{\\left( \\dfrac{1}{a} \\right)}_{\\text{arrival rate}} \\cdot \\underbrace{\\left( \\dfrac{p}{m} \\right)}_{\\text{cycle time}}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":45,"value":"md`Ok, enough with these equations! Let's come up with some values for these parameters and compute the utilization rate.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":47,"value":"viewof p = {\n const div = html`

\n \n \n\tp (in minutes)\n

`;\n const range = div.querySelector(\"[type=range]\");\n const number = div.querySelector(\"[type=number]\");\n div.value = range.value = number.value = 29.8;\n range.addEventListener(\"input\", () => number.value = div.value = range.valueAsNumber);\n number.addEventListener(\"input\", () => range.value = div.value = number.valueAsNumber);\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"viewof a = {\n const div = html`

\n \n \n\ta (in minutes)\n

`;\n const range = div.querySelector(\"[type=range]\");\n const number = div.querySelector(\"[type=number]\");\n div.value = range.value = number.value = 30.1;\n range.addEventListener(\"input\", () => number.value = div.value = range.valueAsNumber);\n number.addEventListener(\"input\", () => range.value = div.value = number.valueAsNumber);\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"viewof m = {\n const div = html`

\n \n \n\tm (identical servers)\n

`;\n const range = div.querySelector(\"[type=range]\");\n const number = div.querySelector(\"[type=number]\");\n div.value = range.value = number.value = 2;\n range.addEventListener(\"input\", () => number.value = div.value = range.valueAsNumber);\n number.addEventListener(\"input\", () => range.value = div.value = number.valueAsNumber);\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":57,"value":"tex.block`\\implies u(p, a, m) = \\frac{p}{a \\cdot m} = ${Math.round((u(p, a, m) + 0.0000001) * 10000) / 100}\\%.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"md`We can also use these parameters to calculate the arrival rate and cycle time. These are, respectively:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":246,"value":"arrival_rate = function (a) {\n return 1/a;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"cycle_time = function (p, m) {\n return p / m;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"tex.block`\\text{arrival rate} = \\dfrac{1}{a} = ${Math.round((arrival_rate(a) + 0.0000001) * 10000) / 10000}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"tex.block`\\text{cycle time} = \\frac{p}{m} = ${Math.round((cycle_time(p, m) + 0.0000001) * 10000) / 10000} \\,\\text{minutes}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":128,"value":"md`### The utilization rate\n\nUsing these sliders, we can see how the utilization rate changes as we alter these parameters. It may, however, be easier to see these changes on a chart. Since we may or may not have control over the arrival and service rates, let us focus on plotting the utilization rate *u* against the number of servers *m*.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":154,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":404,"value":"md`## Waiting time\n\nNow that we have the utilization rate, we may turn to computing the **average waiting time in queue** _T_q_ and the closely related **average length of queue** _I_q_. \n\nThere is, unfortunately, no analytic formula for an exact value of _T_q_, but there is a fairly good approximation that holds for small values of _m_ and for large values of _u_ (close to 1, that is):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":406,"value":"tex.block`T_q = \\underbrace{\\left( \\frac{p}{m} \\right)}_{\\text{cycle time}} \\cdot \\underbrace{\\left( \\frac{u^{\\sqrt{2(m+1)} - 1}}{1 - u} \\right)}_{\\text{utilization factor}} \\cdot \\underbrace{\\left( \\frac{CV_a^2 + CV_p^2}{2} \\right)}_{\\text{variability factor}}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":411,"value":"md`We have already computed the cycle time above, and so can also compute the utilization factor and variability factor separately before computing the average waiting time.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":428,"value":"md`### Utilization Factor\n\nThe __utilization factor__ is a measure of the impact of the utilization rate and the number of servers on the average waiting time. Intuition suggests that, as the utilization rate increases, the time spent in the queue should increase: this is because there is less “slack” available to the servers to take people off the queue, and so it should take longer for someone to get through the queue.\n\nThe nonlinearity of the utilization factor means that its value increases extremely rapidly as the utilization rate nears 1. Note, however, that the utilization factor is undefined for a utilization rate of 1: At that point, people are taken off the queue at exactly the same rate that they are being added to it.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":413,"value":"util_factor = function (u, m) {\n\tvar numerator = Math.pow(u, Math.sqrt(2 * (m+1)) - 1);\n \tvar denominator = 1 - u;\n return numerator/denominator;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":531,"value":"md`For the above values of *u* and *m*, we find that the utilization factor is`","pinned":false,"hidden":false,"mode":"ojs"},{"id":532,"value":"tex.block`\\mathcal{U}(u(p, a, m), m) = ${Math.round((util_factor(u(p, a, m), m) + 0.0000001) * 10000) / 10000}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":499,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":426,"value":"md`### Variability Factor\n\nComputing the variability factor requires us to turn our attention to something we have ignored so far: stochastic variations in the interarrival time and in the service time. We have been working with averages so far, but in order to capture this stochasticity, we must capture some notion of variability or the other.\n\nWe can use the standard deviations of the interarrival time and of the service time to get a sense of the likelihood of obtaining times that differ from the average. We can also use the coefficients of variation of these two parameters, which are in any case fully determined by knowing the mean and the standard deviation.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":437,"value":"viewof cva = {\n const div = html`

\n \n \n\tCV_a (in minutes)\n

\n \n \n\tCV_p (in minutes)\n

`;\n\n const cv_range = div.querySelector(\"[type=range]\");\n const cv_number = div.querySelector(\"[type=number]\");\n\n div.value = cv_range.value = cv_number.value = 1;\n \n cv_range.addEventListener(\"input\", () => cv_number.value = div.value = cv_range.valueAsNumber);\n cv_number.addEventListener(\"input\", () => cv_range.value = div.value = cv_number.valueAsNumber);\n \n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":424,"value":"variability_factor = function (cva, cvp) {\n\treturn 0.5 * (cva * cva + cvp * cvp);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":540,"value":"md`For the sake of simplicity, we frequently assume that both the interarrival time and the service time follow the exponential distribution, in which case their coefficients of variation are both equal to 1 and so their variability factor is also 1.\n\nNote also, however, that if both processes are fully deterministic, with no variation whatsoever, then their coefficients of variation are both 0, as is their variability factor, and hence the average waiting time as well. This makes sense: given that we are looking at *capacity-constrained* systems, in which the cycle time is less than the arrival time, there would be no wait whatsoever if there was no randomness. Put differently: *the genesis of a queue is entirely due to the variability in arrival and service time.*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":469,"value":"tex.block`\\mathcal{V}(CV_a, CV_p) = ${Math.round((variability_factor(cva, cvp) + 0.0000001) * 10000) / 10000}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":460,"value":"md`### Average Waiting Time in Queue\n\nWe now know enough to compute the average waiting time in the queue, given by the formula above.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":408,"value":"tq = function (p, a, m, cva = 1, cvp = 1) {\n return cycle_time(p, m) * util_factor(u(p, a, m), m) * variability_factor(cva, cvp);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"md`For the parameters entered above, we can therefore compute the average waiting time in queue to be`","pinned":false,"hidden":false,"mode":"ojs"},{"id":545,"value":"tex.block`T_q(p, a, m, CV_a, CV_b) = ${Math.round((tq(p, a, m, cva, cvp) + 0.0000001) * 10000) / 10000} \\,\\text{minutes}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":597,"value":"md`It is instructive to plot the average waiting time against some of these parameters. Let us first look at changes caused by the addition of new servers.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":610,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":613,"value":"md`We can see that the average waiting time is __*massively*__ non-linear: the first additional server added (when the process is capacity-constrained) has a truly enormous effect on reducing the average waiting time, but subsequent additions have a progressively lower impact.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":483,"value":"md`### Average Length of Queue\n\nGiven the value of *T_q*, we can use Little's Law to compute *I_q* (the average length of the queue):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":487,"value":"tex.block`I_q = R_{\\text{arrival}} \\times T_q = \\frac{T_q}{a}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":490,"value":"iq = function (tq, a) {\n return a * tq;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":558,"value":"md`With the parameters defined above, we get an average queue length of`","pinned":false,"hidden":false,"mode":"ojs"},{"id":559,"value":"tex.block`I_q = ${Math.round((tq(p, a, m, cva, cvp)/a + 0.0000001) * 10000) / 10000}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":481,"value":"md`## Under the hood`","pinned":false,"hidden":false,"mode":"ojs"},{"id":664,"value":"md`\\`WARNING: ¡¡¡¡¡FIDDLING WITH THESE CELLS MAY BREAK THE CHARTS ABOVE!!!!!\\``","pinned":false,"hidden":false,"mode":"ojs"},{"id":666,"value":"md`Warning aside, you may wish to alter this one parameter to control the maximum number of servers you wish to plot:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":667,"value":"max_m = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":133,"value":"ms = Array.from(Array(max_m), (e,i)=>i+1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":259,"value":"data_u_vs_m = ms.map(m => u(p, a, m))","pinned":false,"hidden":false,"mode":"ojs"},{"id":492,"value":"data_util_vs_m = ms.map(m => util_factor(u(p, a, m), m))","pinned":false,"hidden":false,"mode":"ojs"},{"id":599,"value":"data_tq_vs_m = ms.map(m => tq(p, a, m, cva, cvp))","pinned":false,"hidden":false,"mode":"ojs"},{"id":141,"value":"x = d3.scaleLinear()\n .domain([1, ms.length + 1]).nice()\n .range([margin.left, width - margin.right])","pinned":false,"hidden":false,"mode":"ojs"},{"id":143,"value":"y_u_vs_m = d3.scaleLinear()\n .domain([0, 1]).nice()\n .range([height - margin.bottom, margin.top])","pinned":false,"hidden":false,"mode":"ojs"},{"id":495,"value":"y_util_vs_m = d3.scaleLinear()\n .domain([0, Math.max(...(data_util_vs_m.filter(Boolean)))]).nice()\n .range([height - margin.bottom, margin.top])","pinned":false,"hidden":false,"mode":"ojs"},{"id":602,"value":"y_tq_vs_m = d3.scaleLinear()\n .domain([0, Math.max(...(data_tq_vs_m.filter(Boolean)))]).nice()\n .range([height - margin.bottom, margin.top])","pinned":false,"hidden":false,"mode":"ojs"},{"id":149,"value":"xAxis = g => g\n .attr(\"transform\", `translate(0,${height - margin.bottom})`)\n .call(d3.axisBottom(x).tickSizeOuter(0))\n .call(g => g.append(\"text\")\n .attr(\"x\", width - margin.right)\n .attr(\"y\", -4)\n .attr(\"fill\", \"#000\")\n .attr(\"font-weight\", \"bold\")\n .attr(\"text-anchor\", \"end\")\n .text(ms.x))","pinned":false,"hidden":false,"mode":"ojs"},{"id":152,"value":"yAxis_u_vs_m = g => g\n .attr(\"transform\", `translate(${margin.left},0)`)\n .call(d3.axisLeft(y_u_vs_m))\n .call(g => g.select(\".domain\").remove())","pinned":false,"hidden":false,"mode":"ojs"},{"id":497,"value":"yAxis_util_vs_m = g => g\n .attr(\"transform\", `translate(${margin.left},0)`)\n .call(d3.axisLeft(y_util_vs_m))\n .call(g => g.select(\".domain\").remove())","pinned":false,"hidden":false,"mode":"ojs"},{"id":607,"value":"yAxis_tq_vs_m = g => g\n .attr(\"transform\", `translate(${margin.left},0)`)\n .call(d3.axisLeft(y_tq_vs_m))\n .call(g => g.select(\".domain\").remove())","pinned":false,"hidden":false,"mode":"ojs"},{"id":135,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":137,"value":"margin = ({top: 20, right: 20, bottom: 30, left: 40})","pinned":false,"hidden":false,"mode":"ojs"},{"id":138,"value":"height = 500","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}