Introduction to Queuing Theory
Introduction to Queuing Theory
What is Queuing Theory?
Queuing Theory, the mathematical study of queues, is a field of study that lies under the umbrella of Applied Mathematics and Operations Research. Generally speaking, the scope of Queuing Theory relates the effects that different queue policies/schedules give rise to in various scenarios and circumstances. Much of Queuing Theory has connections to (or can be equivalently expressed using) Markov Chains.
When Is Queuing Theory Useful?
Queues are useful when we deal with scenarios in which the limitation of resources requires objects, people, or tasks to wait until such a time that they are given the resources needed to accomplish whatever it is they are trying to do. Anytime you (or anything for that matter) have waited in line for some reason can be understood as examples of queues (e.g. waiting in line to buy food, waiting for a doctor’s appointment, a pile of homework assignments waiting to be graded by a sleep-deprived teacher, etc.). And while all of these may be examples of queues, not all of them function in the same way. In fact, there are different types of queues; certain queue types may be effective in one case, but not another. Queuing Theory consists of the mathematical study of these queues, usually with respect to the performance of these constructs (wait time, efficiency, task/job completion speed, etc.). Over the scope of this document, we will explore and compare a few different queue types, paying particular attention to how they work and their performance in the context of a simulated example.
Why is Queuing Theory Important?
Queuing Theory has applications in a variety of different fields today. For example, when you wait in line for food at a Fast Food Restaurant, you are usually served in what is known as First-In First-Out (FIFO) order (alternatively known as First-Come First-Serve). The number of employees that are working will have a large impact on the amount of time that you spend waiting for your food. Using Queuing Theory, it is possible to calculate the minimum number of employees that the restaurant needs to ensure that all customers that arrive during the lunch rush get their food no longer than 10 minutes after they order. Another application is in infrastructure. Suppose you are building a highway that is connecting a major suburb to the downtown area and you have demographic information that allows you to estimate the number of cars that the highway will need to be able to handle during rush hour. How many lanes do you need to build to ensure traffic never stagnates? Another application relates to the design and operation of computers. Computers have one or more processors that read and write the 0s and 1s of the digital world that enable your computer and the applications it runs to function. Suppose your computer has 2 processors and you have 10 different applications up and running. How is your computer capable of running those 10 applications simultaneously when it only has two processors? All of these questions can and have been solved using Queuing Theory.
Queue Implementation Examples
With that said, let’s jump straight into our example: Suppose that you are waiting at the DMV to get your license renewed. Suppose further that there is only one employee working at the moment [it certainly always feels that way]. There is a total of 25 people waiting for service (including yourself) - all with varying tasks that need to be completed. Some of the tasks that need to be completed will necessarily take much longer than others. To best account for this behavior, it will prove to be useful to assume that the duration of time required for each customer to complete their task with the employee(s) abides by an exponential distribution. This allows us to simulate customer task durations for the 25 customers that we will use to better understand the example at hand.
set.seed(100)
# Number of people waiting
num_people <- 25
# Number of working DMV employees
numDmvEmployees <- 1
# Draw the task durations for each customer using an exponential
# distribution with a rate parameter of 0.1 customers per minute [1/(10
# minutes per customer)]
expec_task_duration <- 10
dmv_wait <- data.frame(CustID = 1:num_people, Duration = rexp(num_people,
rate = 1/expec_task_duration))The histogram of the simulated task durations needed by the 25 people are shown below.
The histogram above does indeed visually depict the fact that some customers will need much more time to complete their tasks than others, thus ensuring that our construction of the task durations was done in a way that abides by the requirements of our premise (i.e. with a long tailed distribution).
First-In-First-Out (FIFO) Queue
The First-In-First-Out (FIFO) Queue (also referred to as “First-Come First-Serve”) is the simplest of all the queues, and is certainly the one that is the most popular when the objects doing the ‘waiting’ are people. Most likely this is due to its simplicity and procedural ‘fairness’. By this, I just mean that it treats each object that enters the queue identically. Now, if we assume that the DMV sees the customers in a “First-In First-Out” (FIFO) basis, then the customers will be seen by the DMV rep in the following fashion.
The colored bars represent the time that the given customer spends with the DMV rep to get their task finished. The gray space to the left of the colored bars represents the amount of remaining wait time that the given customer must experience before being called up. The length of remaining wait time is printed to the left of the gray bars. It should be obvious that it is impossible to change the total amount of time needed to satisfy all of the customers. However, as will be clear in a moment, it might be possible to reduce the total remaining wait time experienced by the 25 customers. You can visualize the total amount of remaining wait time experienced by the customers as the amount of gray space in the graph to the left of the colored bars. To be mathematically precise, it is exactly the area that this space encompasses.
## FIFO Total Remaining Wait Time: 2609.307 minutesThe remaining wait time distribution for the FIFO Queue process can be visualized below.
You should notice that the wait time distribution is not particularly organized. This is because it depends explicitly on both the customer task durations AND the order in which the customers are in line [i.e. their comparative arrival time], which itself is random.
Shortest-Job-First (SJF) Queue
The Shortest-Job-First (SJF) Queue differs from the FIFO Queue in that the order in which each job in the queue is taken care of depends explicitly on the resources necessary to complete the job. In our DMV case, this refers to the amount of time needed to complete a given person’s task. Specifically, those people who require the shortest amount of time to solve their problem are put at the front of the queue, while those who require larger amounts of time are put in the back. There are several strong reasons for why this might be preferrable in certain cases (though likely not with human participants if there is a physical line in which each person can see everyone else in the line). We will see some of these when we simulate this queue implementation with our DMV example.
I will now show the associated graph that would result if the DMV instead calls up customers on the basis of Shortest Job First (SJF).
NOTE: This example assumes that no other new customers arrive during the duration in which the 25 original customers are being helped. It also assumes that the DMV knows what task each customer needs completed, as well as its associated expected duration.
Notice that the amount of space to the left of the colored bars is much smaller now. This visually tells us that the total remaining wait time experienced by all 25 customers is much smaller. If we were to calculate the area of this space, then we would obtain the total remaining wait time.
## Comparison [ N = 25 ; 1 Reps ]:
## SJF Total Remaining Wait Time: 1249.231 minutes
## FIFO Total Remaining Wait Time: 2609.307 minutesNOTE: The schedule graphs for any SJF Queue can be understood as an instantiated discrete approximation of the integral of the quantile function of the task duration distribution times a scaling factor that is equal to the queue size.
\[ \begin{array}{c} \begin{array}{rcl} Q(x)&=&\text{Quantile Function of the Task Duration Distribution}\\ q_{size}&=&\text{Size of the Population in the Queue}\\ \end{array}\\ \begin{array}{ccccc} \text{SJF Schedule}(x)&\approx& \displaystyle\int_0^{\frac{x-1}{q_{size}}} Q(x') \space dx' \times q_{size} && \end{array} \end{array} \]
- \(x\) defines the order of the person in line whose wait time we want to calculate
- \(\frac{x}{q_{size}}\) gives the quantile associated with the x-th person in line
- If you took the entire line and defined the start and end of the line to be 0 and 1 respectively, the quantile is the position on the line where the specified person falls.
- It’s like the conversion between saying “I’m the 10th person in line in a line with 20 people” and “I’m at the halfway point in a line with 20 people”.
- In the same way that we divided the customer queue index (\(x\)) by the size of the line (\(q_{size}\)) to obtain the associated quantile value for the given index, multiplying through the quantile values by the size of the line (\(q_{size}\)) will transform the quantiles back into the customer queue index values.
- The function \(Q\) takes as an input the quantile value (a number between 0 and 1) and returns the duration that the person associated with that quantile needs to complete their task.
- As the \(q_{size}\) for the Schedule approaches infinity, this approximation becomes an equality.
\[ \begin{array}{c} \begin{array}{c} \text{Assuming the use of a SJF Queue where }q(k) = \text{duration needed for the }k^\text{th}\text{ customer,} \\ \text{the person who is x-th in the queue will have the following remaining wait time} \\ \text{Define: } \quad k'=\frac{k}{q_{size}} \quad;\quad Q(k') = Q\Big(\frac{k}{q_{size}}\Big)= q(k) \quad;\quad q(k) = q(k'\times q_{size}) = Q(k') \end{array} \\ \begin{array}{rclc} \text{SJF Schedule}(x) &=& \displaystyle \sum_{k=1}^{x-1} q(k) \\ \text{SJF Schedule}(x) &=& \displaystyle \sum_{k=1}^{x-1} q(k) \times 1 \\ \text{SJF Schedule}(x) &=& \displaystyle \sum_{k=1}^{x-1} q(k) \times \Delta k \quad,\quad \Delta k = 1 \\ \text{SJF Schedule}(x) &=& \displaystyle \sum_{k=1}^{x-1} q(k' \times q_{size}) \times \Delta (k' \times q_{size}) \\ \displaystyle \lim_{q_{size}\rightarrow \infty}\text{SJF Schedule}(x) &=& \displaystyle \lim_{q_{size}\rightarrow \infty}\Bigg(\int_{\frac{1}{q_{size}}}^{\frac{x-1}{q_{size}}} Q(k') \times d (k' \times q_{size})\Bigg) \\ \displaystyle \lim_{q_{size}\rightarrow \infty}\text{SJF Schedule}(x) &=& \displaystyle \lim_{q_{size}\rightarrow \infty}\int_{0}^{\frac{x-1}{q_{size}}} Q(k') \space dk' \times q_{size} \end{array} \end{array} \]
In the plot above, I have put the plot on its side and used the ranked queue indices as opposed to the quantiles to present a more intuitive visualization of the schedule.
This has mathematical and physical consequences that go further than just this though. An equivalent way of formulating/understanding this solution (The Shortest Job First Queue) is by demanding that at any given point in time, the maximum rate of customer task completion occurs. The rate of customer task completion at a given time can be understood as the instantaneous slope of the graph at any time.
This alternative understanding lends much more insight into the physical consequences that the SJF Queue solution provides. In this way, the SJF Queue can be thought of as the queue that provides the maximum instantaneous rate of customer task completion at the given time. This approach falls under the paradigm of greedy algorithms.
Greedy algorithms can be understood in a very simple fashion. The goal of a greedy algorithm is to provide the optimal global solution of something. To do so, they follow the basic problem solving heuristic of making the locally optimal choice at each stage in the hope that such choices will lead to the global optimum. In general, greedy strategies do not necessarily produce optimal solutions. In fact, it is very easy to come up with simple examples of scenarios in which greedy approaches do not lead to optimal solutions. Under certain conditions, however, they can approximate (and even find) the optimal solution desired.
We can see this in the context of the DMV problem above. If we assume that all customers arrive at the exact same time at the DMV (no additional customers arrive later), then the SJF Queue approach provides the global optimum solution that will minimize the total wait time experienced by the customers. This is not necessarily the case when customer arrivals are staggered. Consider the following simple example:
The DMV has only one working rep and is initially empty of customers. Bob then arrives with a task that will take 75 minutes to complete. As no one else is around, his waiting time is 0 minutes. 5 minutes later, Alice and Susan arrive, each with tasks that will take them 5 minutes. No other customers arrive that day. Then the total customer wait time using the SJF Queue approach is 145 minutes (0 [Bob] + 70 [Alice] + 75 [Susan]). However, if you instead let Bob wait at the beginning (even though no other customer is being served), and then see Alice when she arrives, and then Susan, and then finally Bob, then the total customer wait time is only 20 minutes (0 [Alice] + 5 [Susan] + 15 [Bob]). Thus, since seeing Alice, then Susan, and then Bob has a smaller total customer wait time, the SJF Queue approach cannot be the optimal solution (assuming the goal is to minimize the total customer wait time). In this case, this alternative solution I provided (in which we forced Bob to wait at the beginning) is the optimal solution that minimizes total customer wait time. Given that there are only \(3!=6\) possible (reasonable) solutions, this is relatively easy to prove using a proof by (exhaustive) cases. This is shown below.
\[ \begin{array}{rrcllcrlcrlc} (1)& 145 &=& 0&\text{[Bob]}&+&70&\text{[Alice]}&+&75&\text{[Susan]}&\text{x} \\ (2)& 145 &=& 0&\text{[Bob]}&+&70&\text{[Susan]}&+&75&\text{[Alice]}&\text{x}\\ (3)& 90 &=& 0&\text{[Alice]}&+&10&\text{[Bob]}&+&80&\text{[Susan]}&\text{x}\\ (4)& 90 &=& 0&\text{[Susan]}&+&10&\text{[Bob]}&+&80&\text{[Alice]}&\text{x}\\ (5)& 20 &=& 0&\text{[Alice]}&+&5&\text{[Susan]}&+&15&\text{[Bob]}&\checkmark\\ (6)& 20 &=& 0&\text{[Susan]}&+&5&\text{[Alice]}&+&15&\text{[Bob]}&\checkmark \end{array} \]
Note that there are technically two optimal solutions - this is because, according to the performance score of our optimization problem (i.e. wait time), Alice and Susan are indistinguishable. They both arrive at the DMV at the exact same time and they both need tasks that take the exact same duration. For a function that only cares about wait times, that’s as good as saying they are completely identical.
I should also note that there are many factors that will cause greedy algorithms to deviate from optimal solutions (even in the context of our simple DMV example). Returning back to our DMV problem, lets plot the distribution for the remaining wait time over the twenty-five DMV customers when the SJF Queue is being used.
Unlike the remaining wait time distribution obtained when using a FIFO Queue, this distribution depends solely on the distribution of the task durations that are required by the customers [When staggered arrivals are allowed, the rate of customer arrivals will also influence this distribution].
Comparing the FIFO and SJF Results
Shifting from a FIFO Queue to a SJF Queue may either reduce or increase a given customer’s remaining wait time. I would like to use the remaining wait time variable for each customer to better compare the two queue implementations. In this way, the comparison that follows is motivated by the following question:
- How does shifting from a FIFO Queue to a SJF Queue affect each customer’s remaining wait time?
- (Qualitative) Do more customers experience smaller remaining wait times comparatively? How many?
- (Quantitative) How much do the remaining wait times differ when a SJF Queue is used as opposed to a FIFO Queue?
We see from the graphs above that for 19 of the 25 customers waiting in the DMV, their remaining wait time would decrease if the DMV instead called up customers on the basis of Shortest Job First (SJF) as opposed to First-In First-Out (FIFO). The other 6 customers would be given longer remaining wait times than they would have had otherwise.
This holds true even as N grows larger. Suppose for example that we let \(N=150\). The effect becomes much more fleshed out in the plots below.
The premise at the heart of this approach is the supposition that if a customer no longer needs to wait after they have been serviced, then the best way to reduce overall wait time is to maximize the rate at which customers are serviced. Mathematically, the total remaining wait times can be calculated using the following formula.
\[ \begin{array}{c} \begin{array}{lllc} T_{rwt}&=&\text{Total Remaining Wait Time}\\ N_C&=&\text{Total Number of Customers}\\ d_i&=&\text{Duration Needed for Customer }i\\ r_i&=&\text{Number of Remaining Customers behind Customer }i\text{ in the Queue}\\ \end{array}\\ \begin{array}{cll} T_{rwt}\in\mathbb{R};\quad N_C\in\mathbb{N};\quad d_i\in\mathbb{R};\quad r_i\in\{1,2,...,N_C-1\} \\ \displaystyle T_{rwt}=\sum_{i=1}^{N_C}d_i \times r_i \end{array} \end{array} \]
Using this formula, we may understand with greater clarity the SJF approach. The queue reordering sets all customers \(i\) that have \(d_i\) large at the back of the queue because it is at the back of the queue that \(r_i\) is small. Such a choice minimizes \(d_i\times r_i\) for the given customer \(i\). Similarly, when choosing customers to put at the front of the line (where \(r_i\) is large), \(d_i\) is chosen to be small.
Extension to Multiple Working Employees
Let us now assume now that there is more than one employee working at the DMV (say 4 employees). We shall see the same characteristics that were evident in the case of one employee; after which we will assume that the conclusions we made in the preceding section will hold true for any positive integer choice of working employees.
# Simple code to simulate customer wait times using FIFO
# Assumptions: All reps are identical; no rep is more suited to handle a given call than another
simWaitTimes<-function(data, num_reps) {
# Initialize the available time for each rep
reps <- rep(0, num_reps)
# Index refers to a rep
index <- 1:num_reps
# Store the difference of each reps availability from the time when the call was made
rep_diff <- rep(0, num_reps)
# Add two columns to the table:
# 1) Rep assigned to the customer
data$assigned <- 1
# 2) Wait time for the customer
data$waittime <- 0
# Iterate over the dataset simulating a FIFO Queue
for (i in 1:length(data$time)) {
# Which rep is available to take the call
rep_diff <- data$time[i] - reps
best_rep_diff <- max(rep_diff)
index1 <- index[min(index[rep_diff == best_rep_diff])]
# Assign the call to the selected rep and calculate the wait time experienced by the customer
data$assigned[i] <- index1
data$waittime[i] <- max(-best_rep_diff, 0)
# Update the rep's availability
reps[index1] <- max(reps[index1], data$time[i]) + data$duration[i]
}
return(data)
}
The above chart shows the resulting schedule projection when the FIFO Queue is used. The label to the right of the colored bar for each respective customer denotes which rep the given customer was assigned to, ranging from R1 to R4. All reps are restricted to working with no more than a single customer at any given time.
Just like it did in the case with only a single rep working, the structure of the resulting schedule projection changes quite drastically when a SJF Queue is implemented instead.
Just like before, we can compare the total remaining wait time associated with each queue. We find that the total wait time using the SJF Queue is significantly less than that for the FIFO Queue.
## Comparison [ N = 25 ; 4 Reps ]:
## SJF Total Remaining Wait Time: 245.8977 minutes
## FIFO Total Remaining Wait Time: 511.2269 minutesAgain, when we look at the effect on each individual customer’s remaining wait time, there are many more customers whose remaining wait time improves (decreases) than there are those whose remaining wait time increases (gets worse) when the SJF queue is implemented.
Just like before, we see that many more customers would be given more favorable remaining wait times when the SJF Queue is implemented as opposed to the FIFO Queue. This effect remains true even as the number of customers increases.
When the number of working employees is greater than one, the formula to calculate the Total Remaining Wait Time changes only very slightly.
\[ \begin{array}{c} \begin{array}{lllc} T_{rwt}&=&\text{Total Remaining Wait Time}\\ N_C&=&\text{Total Number of Customers}\\ d_i&=&\text{Duration Needed for Customer }i\\ K&=&\text{Total Number of Working Employees}\\ k_i&=&\text{The Employee that Customer }i\text{ is assigned to} \\ r_{i,k_i}&=&\text{The Number of Remaining Customers behind Customer }i\text{ in the Queue that will be assigned to }k_i \end{array}\\ \begin{array}{cll} T_{rwt}\in\mathbb{R};\quad N_C\in\mathbb{N};\quad d_i\in\mathbb{R};\quad k_i\in\{1,2,...,K\};\quad r_{i,k_i}\in\{1,2,...,N_C-1\} \\ \displaystyle T_{rwt}=\sum_{i=1}^{N_C}d_i \times r_{i,k_i} \end{array} \end{array} \]
The SJF approach when \(K>1\) can easily be understood in the context of minimizing the Total Remaining Wait Time using the formula above and the same argument as before.
An important note to consider is that all of these conclusions so far have assumed that no new customers arrive in the time frame that we are considering. When this condition is relaxed, the resulting performance behavior will be altered slightly, though the core behavior will remain similar. However, due to the fact that relaxing this restriction makes some of these insights significantly less clear, combined with the fact that this document is intended to be a simple, high-level introduction to Queuing Theory, we have ratained this non-realistic condition up to now.
When this condition is relaxed (i.e. new customers are arrive at some stochastic rate), the SJF Queue solutions are liable to change rapidly, making the SJF Queue formulas that were used above far less useful. This is because the solutions that are produced at one moment would change before they actually have a chance to occur. The obvious example is that of a customer that needs a large amount of time for their task. However, every time it is almost his turn to be called up, a new customer that needs less time than he does shows up and is put in front of him in the line. As a result, he is never called up, despite waiting at the DMV for the entire workday. Each of the SJF Queue solutions provided him with a set wait time before he was to be called up, but because the solution kept on changing before he was called up, he never actually made it to the front of the line. The FIFO Queue solutions on the other hand do not change like the SJF Queue solutions do; they are simply extended.
This property of FIFO Queues, in which they are simply extended instead of re-written every time the queue is updated, is a very nice property, and can be thought of as a kind of ‘stability’ in the face of small adjustments. It is for this reason that it might be of interest to consider how a queue that lies on the spectrum in between these two extremes (FIFO and SJF) might look and behave (if we’re lucky, it might possess a sense of stability while still significantly reducing overall wait times).
Constructing a ‘Blended’ Queue
How would such a queue (that is, one that is partially FIFO-like and also partially SJF-like) work?
The way that I see it, the simplest way to devise a queue possessing both of these properties is to chain a standard SJF queue together with a standard FIFO queue. In this vein, the first \(k\) slots in the queue function according to a SJF queue (wherein which each customer’s order can be switched around to accommodate those with the Shortest Job First), and everywhere after the \(k\)-th slot functions according to a FIFO queue. By virtue of this definition alone, it can be guaranteed that no customer will ever be re-ordered (SJF-style) in such a way that their new position in the queue is more than \(k\) slots ahead or behind of their previous position. In other words, the extent to which the SJF re-ordering process continually modifies the entire queue schedule is limited (the extent to which can be controlled choosing an appropriate choice of \(k\)).
As a consequence, choosing \(k\) to be small gives rise to an overall queue implementation that is generally more FIFO-like than it is SJF-like, as only a small number of slots (\(k\)) abide by the principles of SJF re-ordering. It should be trivially clear that choosing \(k=1\) leads to nothing more than a standard FIFO queue (since any ‘re-ordering’ of a queue of length 1 will necessarily be the same as the original queue).
On the other hand, choosing \(k\) to be large gives rise to an overall queue implementation that is generally more SJF-like than it is FIFO-like. This follows due to the fact that \(k\) acts as an upper bound with respect to the extent to which the SJF queue re-orderings can modify the overall queue. By letting \(k\) be large, this bound is relaxed, giving greater leeway to re-order the overall queue on the basis of expected duration. Naturally, in the limit as \(k\) approaches infinity, the corresponding overall queue implementation approaches that of a standard SJF queue.
This family of queue implementations that are constructed in this fashion can be thought of as belonging on a spectrum of possible queue implementations that possess behaviors belonging to both the standard FIFO queue and the standard SJF queue. Furthermore, as we shall see shortly, this family provides a ‘bridge’ along which the performance metrics of interest will gradually shift from the expected result that arises when using the FIFO queue all the way to the expected result that arises when using the SJF queue.
It needs to be mentioned at this point that for an arbitrary FIFO queue (with only one working representative), the expected total wait time experienced by \(N\) customers waiting in the queue (assuming their duration times follow an exponential distribution with rate parameter \(\lambda\)) can be derived in the following way:
\[ \begin{array}{lll} E\big[\text{FIFO Total Wait}\big] &=& \displaystyle E\Bigg[\sum_{j=2}^N \sum_{i=1}^{j-1} x_i \Bigg] \\ E\big[\text{FIFO Total Wait}\big] &=& \displaystyle \sum_{j=2}^N\sum_{i=1}^{j-1} E\big[x_i\big] \\ E\big[\text{FIFO Total Wait}\big] &=& \displaystyle \sum_{j=2}^N \sum_{i=1}^{j-1} \lambda^{-1} \\ E\big[\text{FIFO Total Wait}\big] &=& \displaystyle \sum_{j=2}^N \Big(\lambda^{-1}(j-1) \Big) \\ E\big[\text{FIFO Total Wait}\big] &=& \displaystyle \lambda^{-1}\bigg(\frac{N(N+1)}{2}-1\bigg) - \lambda^{-1}(N-1) \\ E\big[\text{FIFO Total Wait}\big] &=& \displaystyle \lambda^{-1}\bigg(\frac{N(N+1)}{2}-N\bigg) \\ E\big[\text{FIFO Total Wait}\big] &=& \displaystyle \frac{N^2-N}{2\lambda} \end{array} \]
To summarize this relationship that is expected when using a FIFO queue in this context, the total and average wait times are the following.
\[ \begin{array}{c} \begin{array}{llll} \text{FIFO Queue} & N \text{ Customers} & 1 \text{ Working Representative} & X\sim exp(\lambda) \end{array} \\[.2cm] \begin{array}{lll} \begin{array}{lll} E\big[\text{Total Wait Time}\big] &=& \displaystyle \frac{N^2-N}{2\lambda} \end{array} && \begin{array}{lll} E\big[\text{Average Wait Time}\big] &=& \displaystyle \frac{N-1}{2\lambda} \end{array} \end{array} \end{array} \]
In much the same vein, the expected total and average wait time experienced by the \(N\) customers waiting in a SJF queue (with identical duration distribution as above) can also be derived and calculated. However, this derivation is a significantly more complicated, due to the fact that we require explicit integrals to compute it.
\[ \begin{array}{lll} E\big[\text{SJF Total Wait}\big] &=& \displaystyle \int_0^{\infty}\int_x^\infty\big((N-1)\lambda e^{-\lambda y} \big)\big(Nx\lambda e^{-\lambda x} \big)\,dy\,dx \\ E\big[\text{SJF Total Wait}\big] &=& \displaystyle N(N-1)\int_0^{\infty}\int_x^\infty\big(\lambda e^{-\lambda y} \big)\big(x\lambda e^{-\lambda x} \big)\,dy\,dx \\ E\big[\text{SJF Total Wait}\big] &=& \displaystyle N(N-1)\int_0^{\infty}e^{-\lambda x}\big(x\lambda e^{-\lambda x} \big)\,dx \\ E\big[\text{SJF Total Wait}\big] &=& \displaystyle N(N-1)\int_0^{\infty}x\lambda e^{-2\lambda x}\,dx \\ E\big[\text{SJF Total Wait}\big] &=& \displaystyle \frac{N^2-N}{4\lambda} \end{array} \]
Of particular note in the above derivation is the fact that the assumption regarding exponential duration times was explicitly utilized in the construction of the double integral. Thus, this formula is not a general formula, but rather only applies when the distribution of task durations follows that of an exponential distribution.
\[ \begin{array}{c} \begin{array}{llll} \text{SJF Queue} & N \text{ Customers} & 1 \text{ Working Representative} & X\sim exp(\lambda) \end{array} \\[.2cm] \begin{array}{lll} \begin{array}{lll} E\big[\text{Total Wait Time}\big] &=& \displaystyle \frac{N^2-N}{4\lambda} \end{array} && \begin{array}{lll} E\big[\text{Average Wait Time}\big] &=& \displaystyle \frac{N-1}{4\lambda} \end{array} \end{array} \end{array} \]
With these formulas in mind, let us examine the effect on the Total Wait Time when we select different choices of \(k\) to generate our desired queue implementation.
# Construct a chained FIFO/SJF Queue with specified choice of k
chainedQueue <- function(data, k, M = 1) {
if (k > 0) {
# The order customers are served in
data$order <- 0
# Iterate through the queue
for (i in 1:nrow(data)) {
# Remove customers that have already been served
tmp <- subset(data, order==0)
# Choose customer that has minimum duration in the first k slots
kk <- min(c(k, nrow(tmp)))
index <- tmp$CustID[which.min(tmp$duration[1:kk])]
# Label resulting order in line for chosen customer
data$order[index] <- i
}
# Re-order data according to the customer ordering that results
data <- data[order(data$order),]
data$order <- NULL
}
# Compute Customer Wait Times
if (M == 1) {
data$FinishTime <- cumsum(data$duration)
data$StartTime <- data$FinishTime - data$duration
} else {
data$time <- 0
data$StartTime <- simWaitTimes(data, num_reps = M)$waittime
}
return(data)
}
# Iterate over all choices of k assuming a given queue size N and expected task duration
calculateMixedOverallQWaitTimes <- function(N, expec_task_duration, M = 1, iterate = 15) {
set.seed(100)
itr <- rbind.fill(lapply(1:iterate, function(it) {
# Number of people waiting
num_people <- N
# Sample customer durations from exponential distribution
dmv_wait <- data.frame(CustID = 1:num_people, duration = rexp(num_people, rate = 1/expec_task_duration))
# Compute Total Experienced Wait Times for 100 possible choices of k
rbind.fill(lapply(round(seq(1,N,l=100)), function(ks) {
temp <- chainedQueue(dmv_wait, ks, M)
data.frame(k=ks, TotalWait = sum(temp[, ncol(temp)]))
}))
}))
# Average over all iteration results on k
plyr::ddply(itr, .(k), summarise, TotalWait = mean(TotalWait))
}The functions above will serve to help us better understand the relationship that the choice of \(k\) has on the total customer wait time. Now, let’s suppose that the queue size is \(N=100\) and the rate parameter for the exponential distribution that task durations are drawn from is \(\lambda = 0.2\). Note that the rate parameter for any exponential distribution is equivalent to the reciprocal of the first moment of the distribution (also known as the expected value), thus meaning that our distribution of task durations will have an expected value of \(5\).
Now that we’ve tested each queue implementation for every choice of \(k\) and recorded the total customer wait time, we shall visualize the results to better understand the exhibited relationship between \(k\) and total customer wait time when using chained queues in this way.
As you can see in the plot above, the Total Wait Time metric smoothly (though non-linearly) transitions from the expected FIFO Total Wait Time of \(0.5\lambda^{-1}(N^2-N)\) to the expected SJF Total Wait Time of \(0.25\lambda^{-1}(N^2-N)\) as \(k\) increases from 1 to \(N\).
If we were to increase the number of representatives working from \(1\) to (say) \(M\), then the formula relationships would only need be adjusted slightly. In the case of a FIFO Queue, the new relationships would instead abide by the following formulas:
\[ \begin{array}{c} \begin{array}{llll} \text{FIFO Queue} & N \text{ Customers} & M \text{ Working Representatives} & X\sim exp(\lambda) \end{array} \\[.2cm] \begin{array}{lll} \begin{array}{lll} E\big[\text{Total Wait Time}\big] &=& \displaystyle \frac{N^2-N}{2\lambda M} \end{array} && \begin{array}{lll} E\big[\text{Average Wait Time}\big] &=& \displaystyle \frac{N-1}{2\lambda M} \end{array} \end{array} \\[.3cm] \begin{array}{c} \text{Under the assumption that }M^2 << N \end{array} \end{array} \]
For the case when \(M^2\) is not much smaller than \(N\), then instead of being inversely proportional to \(M\), the relationships more closely follow that of one that is inversely proportional to \(M+2M^2N^{-1}\).
In an identical fashion, the new formulas that the SJF Queue would follow instead would be the following:
\[ \begin{array}{c} \begin{array}{llll} \text{SJF Queue} & N \text{ Customers} & M \text{ Working Representatives} & X\sim exp(\lambda) \end{array} \\[.2cm] \begin{array}{lll} \begin{array}{lll} E\big[\text{Total Wait Time}\big] &=& \displaystyle \frac{N^2-N}{4\lambda M} \end{array} && \begin{array}{lll} E\big[\text{Average Wait Time}\big] &=& \displaystyle \frac{N-1}{4\lambda M} \end{array} \end{array} \\[.3cm] \begin{array}{c} \text{Under the assumption that }M^2 << N \end{array} \end{array} \]
Again, we will choose to observe the relationship that arises when we let \(k\) vary and observe the affect on Total Wait Time. This time, we shall define the non-changing parameters of our test to be \(N=500\), \(M=4\), and \(\lambda=0.2\).
With the test results in hand, let’s take a look at the results. A question of particular interest here will be whether the relationship (w.r.t. \(k\)) that we found when we assumed \(M=1\) will match the relationship that we find here (where we have let \(M=4\)).
To conclude, the result for multiple working representatives is nearly identical to the case in which there was only a single working representative (at least with respect to the form of the relationship, since the scale of the two results differ noticeably).
Conclusion
In general, there are many different ways that one may construct a valid queue, and each will have different performance both in general and depending on the specifics at hand. In the example discussed throughout this document, we considered three different types of queues, two of which were standard, common queue implementations (FIFO and SJF). We examined how their performance differs when applied our DMV scenario, and used that to development conclusions regarding their performance in an abstract sense. However, many more queue implementations exist. Furthermore, just like how we constructed a blended queue implementation by combining two simpler queue implementations with some additional customization (conditional logic), so too can many other queue styles be constructed by using simpler implementations/protocols as building blocks. In this way performance can be tuned and optimized for specific purposes.
In the context of electric power distribution, this might be used to tailor outage maintenance schedules in such a way to minimize the total experienced outage time (number of homes affected multiplied by the amount of outage time), or instead to minimize overall outage response time. For IT-related tasks like data registration, ingestion, and management, or the more stereotypical Computer/Hardware Service Desk, similar approaches may be used to optimize a given performance metric. Such techniques are also instrumental in the context of Data Science and Mathematical Simulation. One very common example of this is parallel processing. Computational Algorithms (particularly data simulations) that require large amounts of calculations and tasks to complete often require extreme amounts of time in order to finish (because the processing unit running those calculations can only do one thing at a time). However, by spreading out the computational tasks to multiple computer servers/processors (so that calculations can be run in parallel), the time necessary to complete the algorithm/simulation can be reduced by several orders of magnitude. This principle is the core tenet behind supercomputers, GPUs, and Cluster Computing.
In conclusion, Queuing Theory is a very powerful tool when dealing with practical issues and limited resources. It has a wide range of applications, and can be used to optimize performance (however that is chosen to be defined). It is flexible, and is suitable for both virtual (e.g. graphics-rendering and internet servers) and non-virtual problems (airplane boarding, traffic, and telecommunications). Altogether, it is an incredibly interesting topic; and one that you likely encounter examples of every day.
## R Session Info:
## R version 3.5.1 (2018-07-02)
## Platform: x86_64-w64-mingw32/x64 (64-bit)
## Running under: Windows 10 x64 (build 19041)
##
## Matrix products: default
##
## locale:
## [1] LC_COLLATE=English_United States.1252 LC_CTYPE=English_United States.1252
## [3] LC_MONETARY=English_United States.1252 LC_NUMERIC=C
## [5] LC_TIME=English_United States.1252
##
## attached base packages:
## [1] grid stats graphics grDevices utils datasets methods base
##
## other attached packages:
## [1] plyr_1.8.4 reshape2_1.4.3 ggalluvial_0.9.0 alluvial_0.1-2 networkD3_0.4
## [6] DT_0.4 knitr_1.20 gridExtra_2.3 ggplot2_3.3.2
##
## loaded via a namespace (and not attached):
## [1] Rcpp_1.0.4.6 RColorBrewer_1.1-2 compiler_3.5.1 pillar_1.4.4 formatR_1.5
## [6] rmdformats_1.0.0 base64enc_0.1-3 tools_3.5.1 digest_0.6.15 evaluate_0.14
## [11] lifecycle_0.2.0 tibble_3.0.1 gtable_0.2.0 pkgconfig_2.0.2 rlang_0.4.5
## [16] igraph_1.2.2 yaml_2.2.0 xfun_0.13 withr_2.1.2 stringr_1.3.1
## [21] vctrs_0.2.4 htmlwidgets_1.5.1 rprojroot_1.3-2 tidyselect_1.0.0 glue_1.4.0
## [26] rmarkdown_1.10 bookdown_0.21 purrr_0.3.4 magrittr_1.5 backports_1.1.2
## [31] scales_1.0.0 ellipsis_0.3.0 htmltools_0.3.6 colorspace_1.3-2 labeling_0.3
## [36] stringi_1.1.7 munsell_0.5.0 crayon_1.3.4