Chapter 8

Process Modeling Using Queuing Theory and Simulation

In our everyday life, there are many so-called “waiting line systems”; for example, customers waiting in the checkout line in a grocery store, passengers waiting in line to go through the security checkpoint at an airport, and customers calling customer service and waiting in a queue to be answered in the order received. If the demand for processing exceeds the capacity of serving units, we often encounter a “wait line” system. If you look at these systems, it is not difficult to find the common features involved in these systems; (1) there is a demand for service and the demand is stochastic, that is to say, the time when a customer arrives is somewhat random and unpredictable; (2) there are limited resources (or servers) to fulfill the demand; when there are more customers than the available servers, waiting occurs and the order of being served follows a predetermined rule, usually the first-in-first-out (FIFO) order. In systems operations and processes, it is very common to observe the characteristics of waiting line systems, such as in manufacturing systems; raw materials waiting in the queue to be processed, machines in queues to be serviced, and finished products waiting in line to be shipped out; in service systems, entities (such as customers) forming a line, waiting for their turn to be served. As system designers, we are tasked to control the length of the waiting line; on the one hand, entities that request processing and service need to have shorter waiting times, but, on the other hand, we need to control the number of process/service channels to make sure they provide enough capacity with the most cost efficiency. In waiting line system design, the objective is to optimize the number of service channels to achieve the desired systems performance. The mathematical models addressing the waiting line system behaviors are called queuing theory and models.

In this chapter, we will review the fundamental concepts of queuing theory and its application in systems engineering; more specifically, we will

1. Define queuing systems and the related decision factors that are involved in a queuing system
2. Introduce the basic queuing theory model, describe the birth-death process, and study the M/M/1 and M/M/c systems, deriving the basic parameters for these models
3. Introduce the application of queuing models in systems design
4. Introduce simulation-based queuing systems analysis; namely, we will use discrete event simulation (DES) to investigate queuing models with more complexity

8.1 Basic Queuing Theory

Queuing theory was originally developed by Agner Krarup Erlang in 1909. Erlang was a Danish engineer who worked in the Copenhagen telephone exchange. When studying the telephone traffic problem, he used a Poisson process as the arrival mechanism and, for the first time, modeled the telephone queues as an M/D/1 queuing system. Ever since the first queuing model, queuing theory has been well developed and extended to many complex situations, even with complicated queuing networks. These models, together with the advancement of computer technology, have been used widely now in many fields and have shown significant benefits in optimizing behavior within these systems. In this chapter, we will introduce the most fundamental queuing theory and models to make readers familiarized with the concepts of queuing theory and its application in system design. For a more detailed review of the subject of queuing theory, readers can refer to any other book on stochastic processes or advanced queuing theory.

8.1.1 Queuing System

A typical queuing system (waiting line system) is illustrated in Figure 8.1. The dotted line indicates the boundary of a waiting line system, hereafter referred to as a queuing system. In a queuing system, generated from a source, or a population, individual customers arrive randomly at the queuing system and request service from one of the service channels (or servers). If the service channels are all busy, then the arriving customers wait in a line for their turn to be served; the order to be served is based on the predetermined waiting rule (e.g., first in, first out, or FIFO).

In general, the entities that request services are called customers, and the processes that provide services and fulfill customers’ needs are called service channels. It is obvious that the capacity is the key factor in influencing system behaviors. If the service channels have less capacity that cannot satisfy customer demand, then the waiting line will form, and, systems will become more and more crowded; thus, the quality of service will be degraded and many customers may choose to leave the system before getting served. From the standpoint of customers, the more service channel capacity the better; this implies less time to wait to be served and a high service quality is perceived. On the other hand, if the service channels have more capacity than needed, then from the service provider’s perspective, more service channels mean more investment, capital expenditure, and human labor involved, which increases the operations cost of the service or the manufacturing process. So, one of the most important purposes of studying queuing theory is to find a balance between these two costs, the waiting cost and the service cost. If the customer waits for too long, he/she may not be happy with the service, thus might not return in the future, causing loss of potential profit; or, parts may be waiting too long, increasing production cycle time, again losing potential sales and profits. These costs are considered to be waiting costs. Service costs are those that increase service capacity such as salary paid to the servers. Queuing theory application balances these two costs by determining the right level of service so that the total cost of the operations (waiting cost + service cost) can be optimized.

From Figure 8.1, it is easily seen that a queuing system consists of three processes that interact and regulate each other’s behavior.

8.1.1.1 Arrival Process

Customers arrive from a population. To simplify the model at the beginning, we first need to make the following two assumptions:

1. Population size is infinite. There is no doubt that any population is finite in size. For example, the number of customers at a local market is subject to the population size of the area, which obviously is finite. However, if the departure rate is small relative to the population size, then the change of the population size due to the service (i.e., returning the customer back to the population) is negligible. Under this assumption, we can have a constant arrival rate in the queuing model, which is much easier to formulate and study. In some cases, the service portion is too large relative to the population size to be ignored; we cannot treat the population size as infinite as it will not reflect the true behavior of the queuing system. For example, if we have a population of 30 trucks and if one truck needs maintenance, it will be removed from the population and wait to be serviced. In this case, the impact of service on the population size cannot be ignored; thus, the arrival rate of the trucks in the service center will be affected by how many trucks are actually being serviced and how many are in operation. In this case, a finite queuing model can be used to study the behavior of such a system.
2. One customer arrives at a time. In a queuing system, we usually assume that at any given time, there is only one customer arriving; bulk arrival is not considered. We might argue that in real life there are cases of bulk arrival; to make the model simple, we can always increase the precise unit of time, so that no two arrivals occur at the exact same time. Bulk arrival will be addressed in Section 8.3 using simulation. For this reason, a queuing system is also called a discrete event system, as customers arrive at discrete time points, not continuously like the flow of water.
3. Customer arrivals are independent of each other. In other words, the arrival of one individual customer is entirely independent, and does not rely on other customers’ behavior.
4. The arrival process is stationary. That is, we assume that the parameters of the arrival mechanism, such as the probability distribution function (p.d.f.), the mean arrival rate, usually denoted as λ, and the variance remain unchanged during operations; they do not vary with time, and are not independent of the time of the operations. If these parameters change with time, then the arrival process is considered nonstationary; for example, a restaurant may have an hour of peak customer arrival at lunchtime and dinnertime; the arrival parameters are not the same in the peak hour as in the other time periods. In the mathematical models of queuing theory, we assume a stationary arrival process, and will introduce the concept of the nonstationary arrival in Section 8.3 using simulation.

8.1.1.2 Queue

When the arriving customer finds all the servers (or service channels) are busy, this customer has to enter an area/place to form a line to wait, waiting for his/her turn; this waiting line is called a queue. There are many types of rules involving the queue, depending on the real-world situation the queuing system is modeling. The most commonly used queue rule is that customers wait in a first-in-first-out (FIFO) queue. We can observe this rule almost everywhere in our daily life; it seems to be a fair process for all customers/units. However, there are some other types of priority rules that can be utilized; for example, sometimes a last-in-first-out (LIFO) rule is used for a parking lot system, airplane boarding, or, sometimes, the stacking order of computer data structure. In some other cases, when each customer does not have the same priority, then the ranking of the queue is determined by some type of priority attribute. For example, in an airport boarding process, the VIP passengers always get placed in the front of the boarding queue when they arrive. What priority rule to use to model the queue is solely dependent on the nature of the system being studied.

The above rule assumes that there are unlimited spaces in the buffer area for every unit arriving to wait (of course, for a stable queuing system, the queue length will not tend to infinity; we will talk about this condition in Section 8.1.2), so every customer chooses to wait when all servers are busy. There are occasions when customers see that the queue too long and they do not want to wait; instead, they leave the system immediately. This customer behavior is called reneging and the queue has a lost mechanism. There are some queuing systems that have a mixed model of waiting and lost mechanisms, depending on the customers’ tolerance levels. For example, if waiting for period of time x, a customer will choose to leave; or, if the queue length exceeds y, then newly arriving customers will depart immediately. This mostly occurs in queuing systems with limited waiting areas, as seen at many drive-through service windows.

Besides the different priority rules used in the queuing system, there are some other variations of waiting mechanisms in a queue. The most common mechanism is a single queue; there are also multiple queues and recurring queues. Again, this depends on the nature of the systems being modeled.

8.1.1.3 Service Process

The service process is the process in which activities are performed by the server with the customer, to fulfill the needs of the customer; once the needs of the customer are fulfilled, the customer leaves the system. For this reason, the service process is also called the output process of the queuing system. Similarly to customer arrival, the service process also presents random behavior (think about the experience one has at a store checkout; some customers have only one or two items, but some have a full shopping cart). Thus, the service time for each customer is random, usually following a particular probability distribution. The service quality is measured by the time taken to complete the service. The service provided by the queuing system is measured by its capacity, or the number of service channels available. In queuing models, the arrangement of the service channels is usually either in a series structure or a parallel structure. The series queuing structure is addressed by the queuing network model and the parallel structure is handled by multiple service channel models (assuming all the channels are identical). As mentioned earlier, the service process is where the decision factors are; decision makers control the number of service channels (i.e., the number of clerks to hire for the checkout process) to control the output rate for customer needs, increasing/decreasing the service cost to decrease/increase the cost incurred in customer waiting.

To facilitate the introduction of the different queuing models, we shall use a unified system of notation, as follows:

t: Time period of the system

x: Number of units of customers in the system

λ: Arrival rate; measures the mean number of units arrives per time period

μ: Service rate; measures the mean number of units completed per time period per service channel

With this notation, we can easily derive some other parameters of interest. For example, 1/λ is the mean interarrival time between two customer arrivals and 1/μ is the mean service time. For a queuing system to be stable (i.e., the queue length does not grow infinitely), we usually require that λ < μ, or that the service rate is faster than the arrival process. We will see why this is a necessary condition in Section 8.1.2 when we talk about the M/M/1 and M/M/c queues. A general convention for a queuing system uses a format of six symbols in total: X/Y/Z/A/B/C; specifically,

X: indicates the time distribution of the arrival process. Some of the most commonly used arrival processes include M, indicating the Poisson arrival process (we will explain this process shortly); D means the arrival process is deterministic; Ek is an Erlang(k) distribution of arrival process; G means a general distribution for the arrival process (other than Erlang, deterministic, or Poisson).

Y: indicates the time distribution of the service process. For example, M implies an exponential distribution of the service time, while G means a general distribution.

Z: indicates the number of service channels.

A: indicates the queuing system capacity. A default value for the capacity is infinity, ∞.

B: indicates the population size. A default value for the population size is infinity, ∞.

C: indicates the queuing rules, such as FIFO.

So an M/M/1/∞/∞/FIFO queue refers to a Poisson arrival process, exponential service time distribution, one server, infinite queue capacity, and infinite population size, and the waiting line rule is FIFO. In the next section, we will investigate this system, as it represents the most fundamental queuing model.

8.1.2 M/M/1 Queuing System

8.1.2.1 Exponential Time Arrival and Poisson Process

As mentioned earlier, M/M/1/∞/∞/FIFO is considered to be the basic queuing structure and since infinity and FIFO are the default values for the capacity and queuing rules, we just use M/M/1 to simplify the representation. In an M/M/1 queuing system, the arrival process is a Poisson process, as mentioned earlier. If you have studied probability theory, you will recall that the Poisson process is a counting process of random arrivals, with the interarrival time following an exponential distribution.

Let us look at the exponential distribution. The reason an exponential distribution is used to model the queuing arrival process is due to its memoryless (or no-memory) property. Stated in plain language, this implies that any individual customer’s arrival time does not depend on any other customer’s arrival time. To state this property mathematically, if x is the exponentially distributed random variable for the interarrival time between two consecutive customer arrivals, we have the following relationship:

$P\left(x>s+t\text{|}x>s\right)=P(x>t)$ (8.1)

The above conditional probability expresses the no-memory property of the exponential distribution, and it can be proven that no distribution except the exponential distribution has this property (Winston 1995).

To demonstrate this property, let us take a look at the exponential distribution first. An exponential distribution with parameter λ has the following density function:

$f\left(x\right)=\{{}_{0,otherwise}^{\lambda e^{-\lambda x},x\ge 0}$ (8.2)

and f(x) is illustrated in Figure 8.2.

Since we know the cumulative probability,

$P\left(x>t\right)=\underset{t}{\overset{\infty }{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x=1-\underset{0}{\overset{t}{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x$ (8.3)

This is easy to understand, since

$1=\underset{0}{\overset{\infty }{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x=\underset{0}{\overset{t}{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x+\underset{t}{\overset{\infty }{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x$

It is easy to derive the integral

$\underset{0}{\overset{t}{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x=1-e^{-\lambda t}$

(Readers can refer to any calculus book to review the basic integral.)

So, for Equation 8.3, we have the following results:

$P\left(x>t\right)=1-\underset{0}{\overset{t}{{\displaystyle \int }}}\lambda e^{-\lambda x}\text{d}x=1-(1-e^{-\lambda t})=e^{-\lambda t}$ (8.4)

That is to say, the probability that the interarrival time is greater than t is e−λt if the interarrival time is exponentially distributed. It is not difficult to derive the mean and variance for f(x):

$E\left(x\right)=\frac{1}{\lambda }$ (8.5)

and

$\text{Var} \left(x\right)=\frac{1}{{\lambda }^2}$ (8.6)

The mean value of E(x) is the mean value for the interarrival time, and is the reciprocal of λ, so λ is the mean value of the arrival rate. You might find this concept of rate a little confusing; if you think about the units of the interarrival time and arrival rate, it will be easier to understand. λ, as the mean arrival rate, describes the numbers of arrival per time period, and, of course, the reciprocal 1/λ is the average time per arrival, which is the mean interarrival time. We have to be clear about the difference between time and rate; you will also see that understanding these concepts is very critical in modeling and simulations.

Now we can easily prove the memoryless property of the exponential distribution:

Proof:

$P\left(x>s+t\text{|}x>s\right)=\frac{P(x>s+t, x>s)}{P(x>s)}=\frac{P(x>s+t)}{P(x>s)}$

According to Equation 8.4, we know that

$P\left(x>s+t\right)=e^{-\lambda \left(s+t\right)}$

and

$P\left(x>s\right)=e^{-\lambda s}$

So, we have

$P\left(x>s+t\text{|}x>s\right)=\frac{e^{-\lambda \left(s+t\right)}}{e^{-\lambda s}}=e^{-\lambda t}=P(x>t)$ ∎

It needs to be noted here that

1. The exponential distribution is the only distribution that has this no-memory property; no other distribution functions possess this property.
2. The no-memory (or memoryless) property is very important for modeling queuing systems. It implies that the distribution of each individual arrival is totally independent of any other, and to predict the arrival time of the next arrival, we do not need to rely on when the last arrival occurred.

When the interarrival time follows an exponential distribution, the arrivals follow a Poisson process, and their relationships are defined as follows (Winston 1994):

If the inter-arrival time follows an exponential distribution with parameter λ, if and only if the random variable of numbers of arrivals within time period of t follows a Poisson distribution with parameters of λt.

To express this more particularly in mathematical format, a discrete random variable N follows a Poisson distribution with parameter λ, if for N = 0, 1, 2, …,

$P\left(N=n\right)=\frac{e^{-\lambda }{\lambda }^n}{n!}$ (8.7)

It can easily be shown that the mean of N, E(N) = λ. So, for an arrival time following an exponential distribution with a mean of λ, the number of arrivals Nt within time t follows a Poisson distribution with the parameter of λt, expressed as follows:

$P\left(N_t=n\right)=\frac{e^{-\lambda t}{\left(\lambda t\right)}^n}{n!},n=0,1,2,\dots$ (8.8)

and obviously E(Nt) = λt.

Regarding the service time in an M/M/1 system, we also assume that each individual customer’s service time is totally independent of any other and has no memory of any other. Thus, we use the exponential distribution to model the random variable for the service time. That is, if the random variable y for the service time is exponentially distributed, the probability density function is given by f(y) = μe−μy, the mean service time equals 1/μ, and μ is called the service rate (i.e., the number of service tasks completed per time period). In the next section, we will show how M/M/1 is modeled using the Poisson process and exponential distribution, by using a birth-death process.

8.1.2.2 Birth-Death Process

The birth-death process is an important tool to model the steady-state behavior of the queuing system. As commonly seen in most queuing systems, if a steady state of the system exists, its steady-state behavior will be stabilized. Just imagine a large grocery store; in the morning when it first opens, there are no customers in the store. Customers start to arrive (customer arrival) and the store starts to serve the customers (customer departure). If the arrival rate λ and the service rate (or departure rate) μ do not change over time, and λ < μ (i.e., service rate is faster than arrival rate—why? We will explain this later), then soon the store will reach a state where the distribution of the numbers of customers in the store N(t) will remain unchanged; we call this a steady-state behavior. The steady-state behavior represents the true characteristics of the queuing system (i.e., the average time a customer spends in the system, and the average length of the queue); thus, when studying a queuing system, we need to know the behavior of its steady state. In other words, under the steady state, the probability that there are j customers in the queuing system at the time t, given the initial number of the customers in the system i, denoted as Pij(t), will not depend on the initial state and current time; Pij(t) will converge to an equilibrium probability of Pj. So, if we can derive the value of Pj, j = 1, 2, 3, … n,…, then we can completely describe the behavior of M/M/1 queuing system.

In deriving the probability of Pj, we can use the birth-death process to describe the transition relationships between different system states; here, we define the system state as the number of customers in the system at time t, N(t) = i, i = 0, 1, 2, …. There are basically two events involved in the queuing system: arrival (the birth process) and departure (the death process). If we assume that only one customer can arrive at any time, then for a small time period t + Δt from t, only one of the following three events could happen (one can make the value of Δt small enough to ensure one of these will happen and exclude other events):

1. There is one customer arrival and no customer departure; system moves from state “i” to “i + 1”.
2. There is no customer arrival and there is one customer departure; system moves from state “i” to “i − 1”.
3. There is one arrival and one departure; system remains at state i.

These three events are illustrated graphically in Figure 8.3.

A detailed mathematical illustration of these transition probabilities can be found in Winston (1995); if readers are interested in the proof of these state transition diagrams, we suggest they read chapter 20 of Winston (1994). Based on the same principle, we can derive the complete birth-death process for an M/M/1 queue as shown in Figure 8.4.

If the system is in the steady state, the probability of being in any system state n, n = 0, 1, 2, … remains unchanged; this implies from the birth-death process diagram above that the chances of an incoming event to state n equals the chances of an outgoing event from state n. For state n, n ≥ 1, incoming events are from state “n − 1” to state n and from state “n + 1” to state n; the probability of entering n is λPn−1 + μPn+1. The outgoing events are from state n to state “n − 1” and state “n + 1” to state n; the outgoing probability is λPn + μPn. So, under the steady state, the outgoing probability equals the incoming probability, that is,

$\lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_n,n=1,2,\dots$ (8.9)

For n = 0, since this value only has one state to connect to the birth-death process, the steady-state transition function is

$\lambda P_0=\mu P_1$ (8.10)

So, we obtain the complete set of transition functions for the steady states of the M/M/1 queue:

$\lambda P_0=\mu P_1$

$\lambda P_0+\mu P_2=(\lambda +\mu )P_1$

$\lambda P_1+\mu P_3=(\lambda +\mu )P_2$

$\dots \dots$

$\lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_n$

$\dots \dots$

With these transition functions, we can easily derive the value for Pn:

From Equation 8.10, we have

$P_1=\frac{\lambda }{\mu }{P}_0$

If we let

$\rho =\frac{\lambda }{\mu }$

then we can rewrite the above equation as

$P_1=\rho P_0$ (8.11)

From the birth-death equations, for n = 1, we have

$\lambda P_0+\mu P_2=(\lambda +\mu )P_1$

Substituting P1 = ρP0 into the above equation, we can obtain the relation between P0 and P2, as follows:

$\lambda P_0+\mu P_2=(\lambda +\mu )P_1=\left(\lambda +\mu \right)\rho P_0$

Dividing by μ on both sides of the equation, we obtain

$\frac{\lambda }{\mu } P_0+P_2=\left(\frac{\lambda }{\mu }+1\right)P_1=\left(\frac{\lambda }{\mu }+1\right)\rho P_0$

or

$\rho P_0+P_2={\rho }^2{P}_0+ \rho P_0$

Canceling ρP0, we obtain the following equation

$P_2={\rho }^2{P}_0$ (8.12)

We repeat the same procedure for the next equation of the steady-state equations; we will derive the following:

$P_1={\rho }^1{P}_0$

$P_2={\rho }^2{P}_0$

$P_3={\rho }^3{P}_0$

$P_4={\rho }^4{P}_0$

$\dots \dots$

$P_n={\rho }^n{P}_0$

$\dots \dots$

Since all the probabilities are mutually exclusive,

${\displaystyle \sum }_{i=0}^{\infty }{P}_i=1$ (8.13)

so we can easily obtain P0 as

$P_0\left(1+\rho +{\rho }^2+{\rho }^3+\cdots +{\rho }^n+\cdots \right)=1$

So, if we know the sum of 1 + ρ + ρ2 + ρ3 + ⋯ + ρn + ⋯, then we can obtain the value of P0.

Let us denote G = 1 + ρ + ρ2 + ρ3 + ⋯ + ρn + ⋯, then P0 = 1/G. Solving for G is quite straightforward; if you have had basic algebra, it should be easy for you to understand. Let us see how to use some simple procedures to work out G.

$G={\displaystyle \sum _{i=0}^{\infty }{\rho }_i}=1+\rho +{\rho }^2+{\rho }^3+\cdots +{\rho }^n+ \cdots$ (8.14)

Multiplying by ρ on both sides of Equation 8.14, we obtain

$\begin{array}{c}\rho G=\rho {\displaystyle \sum }_{i=0}^{\infty }{\rho }_i=\rho \left(1+\rho +{\rho }^2+{\rho }^3+\cdots +{\rho }^n+\cdots \right)\\ =\rho +{\rho }^2+{\rho }^3+\cdots +{\rho }^n+\cdots \end{array}$ (8.15)

Subtracting Equation 8.15 from Equation 8.14, we have

$\left(1-\rho \right)G=\left(1+\rho +{\rho }^2+{\rho }^3+\cdots +{\rho }^n+\cdots \right)-\left(\rho +{\rho }^2+{\rho }^3+\cdots +{\rho }^n+\cdots \right)$ (8.16)

We assume ρ = (λ/μ) < 1, then $\underset{n\to \infty }{\lim }{\left(\rho \right)}^n=0$ , so on the right-hand side of Equation 8.16, everything is canceled except 1, that is,

$\left(1-\rho \right)G=1$

or

$G=\frac{1}{1-\rho }=\frac{1}{1-\frac{\lambda }{\mu }}=\frac{\mu }{\mu -\lambda }$ (8.17)

So, we obtain P0 as

$P_0=\frac{1}{G}=\frac{\mu -\lambda }{\mu }$ (8.18)

Readers should now have some idea why we mentioned that a necessary condition for a stabilized queuing system is that μ > λ. From Equation 8.18, this condition is necessary for P0 to be solved, so that a steady-state probability Pi can be found.

Using Equation 8.18, we can obtain all the probabilities for the steady state of an M/M/1 queue:

$P_n={\rho }^n{P}_0={\left(\frac{\lambda }{\mu }\right)}^n\frac{\mu -\lambda }{\mu },n=1,2,\dots$ (8.19)

8.1.2.3 Measures of M/M/1 Queue

Based on the results from Equation 8.19, we can easily derive the main measures of the M/M/1 queue. The main measures for M/M/1 include

LS: Mean number of customers in system

LQ: Mean number of customers in queue

WS: Mean time that customers spend in system (including waiting time and service time)

WQ: Mean time that customers spend in the queue

LS is the mean (expected) number of customers in system, so according to the definition of the mean value,

$L_S={\displaystyle \sum }_{n=0}^{\infty }n{P}_n={\displaystyle \sum }_{n=0}^{\infty }n\left(1-\rho \right){\rho }^n$ (8.20)

This can be rewritten as

$\begin{array}{c}{\displaystyle \sum }_{n=0}^{\infty }n\left(1-\rho \right){\rho }^n={\displaystyle \sum }_{n=0}^{\infty }n{\rho }^n-{\displaystyle \sum }_{n=0}^{\infty }n{\rho }^{n+1}=\left({\rho }^1+2{\rho }^2+3{\rho }^3+4{\rho }^4+\cdots \right)\\ -\left({\rho }^2+2{\rho }^3+3{\rho }^4+4{\rho }^5+\cdots \right)=\rho +{\rho }^2+{\rho }^3+{\rho }^4+\cdots =\left(1+\rho +{\rho }^2+{\rho }^3+{\rho }^4+\cdots \right)-1\end{array}$

From Equation 8.14 we already know that

$1+\rho +{\rho }^2+{\rho }^3+{\rho }^4+\cdots =\frac{1}{1-\rho }$

So

$L_S=\frac{1}{1-\rho }-1=\frac{\rho }{1-\rho }=\frac{\lambda }{\mu -\lambda }$ (8.21)

Since, for the M/M/1 queuing system, the queue length is one fewer than the number of customers in the system, we can obtain LQ as

$L_Q={\displaystyle \sum }_{n=0}^{\infty }\left(n-1\right)P_n={\displaystyle \sum }_{n=0}^{\infty }n{P}_n-{\displaystyle \sum }_{n=0}^{\infty }{P}_n=L_S-{\displaystyle \sum }_{n=0}^{\infty }{P}_n$ (8.22)

We know that

$L_S=\frac{\lambda }{\mu -\lambda }$

and

${\displaystyle \sum }_{n=0}^{\infty }{P}_n=1-P_0=\rho =\frac{\lambda }{\mu }$

So

$L_Q=\frac{\lambda }{\mu -\lambda }-\frac{\lambda }{\mu }=\frac{{\lambda }^2}{\mu \left(\mu -\lambda \right)}$

Often, we are interested in knowing the time a customer spends in the system. To derive the mean time spent in the system WS and the mean time spent in waiting in the queue WQ, we need to derive the distribution of the time in the system, which can be proven to follow an exponential distribution with a parameter of –(μ – λ); another way to solve for the time in the system and the queue is to use LS and LQ by applying the powerful Little’s law:

For any queuing system in which the steady state exists, the following relationship is true

$L=\lambda W$ (8.23)

where:

L is the length (or number of customers) in the queuing system (or subsystem)

λ is the arrival rate of the queuing system

W is the time spent in the corresponding system (or subsystem).

So, intuitively, we can derive the following two equations:

$L_S=\lambda W_s$

$L_Q=\lambda W_Q$

Little’s law tells us that it is true regardless of the number of servers, as long as the steady state can be achieved. By using Little’s law, we can derive the formulas for WS and WQ as follows:

$W_S=\frac{L_S}{\lambda }=\frac{\frac{\lambda }{\mu -\lambda }}{\lambda }=\frac{1}{\mu -\lambda }$ (8.24)

$W_Q=\frac{L_Q}{\lambda }=\frac{\frac{{\lambda }^2}{\mu \left(\mu -\lambda \right)}}{\lambda }=\frac{\lambda }{\mu \left(\mu -\lambda \right)}$ (8.25)

From the above formula, we can observe that as ρ→1, that is, λ→μ, the waiting time WQ will approach infinity, and if ρ→0, WS→1/?, which implies that the time the customer spends in the system is only the service time (approximately).

We will give an example to show how to use these formulas to measure the performance of the queuing system.

Example 8.1: A product service center has only one technician to provide a repair service. It is known that the arrival of customers follows a Poisson process, with two arrivals per hour on average; the service time follows an exponential distribution with a mean of 12 min. Assuming that there are unlimited spaces for customers to wait:

1. What is the probability that the technician is idle (i.e., not busy)?
2. What is the probability that there are three customers in the store?
3. What is the probability that there is at least one customer in the store?
4. What is the average number of customers in the store?
5. On average, how long does one customer spend in the store?
6. What is the average number of customers waiting in the queue?
7. What is the average time that a customer waits in the queue?

   Solution: This is an M/M/1 queuing system; from the information given, we know that λ = 2/h and μ = 1/12 per min = 5/h (please note here that we need to convert everything into the same units [in this case, hours]). So, ρ = λ/μ =0.4.

8. If the server is idle, this means that there is no customer in the store, so the probability of the server being idle is

   $P_0=1-\rho =1-0.4=0.6$

9. The probability of three customers in the store is

   $P_3={\rho }^3\left(1-\rho \right)={\left(0.4\right)}^3\left(1-0.4\right)=0.038$

10. The probability that there is at least one customer in the store is

    $1-P_0=1-0.6=0.4$

11. The average number of customers in the store, LS, according to Equation 8.21, can be obtained as

    $L_S=\frac{\lambda }{\mu -\lambda }=\frac{2}{5-2}=0.67\left(\text{person}\right)$

12. The average time a customer spends in the system, WS, can be found using Equation 8.23:

    $W_S=\frac{1}{\mu -\lambda }=\frac{1}{5-2}=\frac{1}{3}\left(\text{h}\right)=20 \left(\text{min}\right)$

    We can also derive this by applying Little’s law:

    $W_S=\frac{L_S}{\lambda }=\frac{0.67}{4}\left(\text{h}\right)=20\left(\text{min}\right)$

13. The average number of customers waiting in the queue is, according to Equation 8.21,

    $L_Q=\frac{{\lambda }^2}{\mu \left(\mu -\lambda \right)}=\frac{{\left(2\right)}^2}{5\left(5-2\right)}=\frac{4}{15}=0.267\left(\text{persons}\right)$

14. The average waiting time of a customer in the queue is

$W_Q=\frac{\lambda }{\mu \left(\mu -\lambda \right)}=\frac{2}{5\left(5-2\right)}=\frac{2}{15}\left(\text{h}\right)=8 \left(\text{min}\right)$

8.1.3 Multiserver Queuing Systems

Now let us look at a more complicated queuing system with multiple servers. In multiserver systems, we assume customers still arrive independently and individually; the arrival process for each customer is still a Poisson process with a parameter of λ, the same as in the single-server system. When a customer arrives and there is at least one server idle (i.e., not busy), then this customer receives service immediately; if all servers are busy, customers wait in one single queue and follow the rules of FIFO to be served. The service time for each individual customer is the same as the single-server system, that is, exponential with a rate of μ. This system is often seen in service systems such as banks and post offices; we denote such a system as M/M/s/∞, with s being the number of service channels in the system.

In solving the multiserver system, we can also use the birth-death process, and derive the probability distribution for Pn.

Let

$\rho =\frac{\lambda }{s\mu }$ (8.26)

It is easy to see that the necessary condition for the system to achieve a steady state is ρ < 1; that is to say, the arrival rate has be less than the overall service rate, otherwise, the system will increase to infinity. If ρ < 1, we can derive the steady-state probability as follows:

$P_0=\frac{1}{{{\displaystyle \sum }}_{i=0}^{s-1}\frac{{\left(s\rho \right)}^i}{i!}+\frac{{\left(s\rho \right)}^s}{s!\left(1-\rho \right)}}$ (8.27)

and

$P_n=\{\begin{array}{cc}\frac{{\left(s\rho \right)}^n{P}_0}{n!}, & n\le s\\ \frac{{\left(s\rho \right)}^n{P}_0}{s!s^{n-s}}, & n>s\end{array}$ (8.28)

From Equation 8.28, it is easy to show that the probability that all servers are busy is

$P\left(j\ge s\right)=\frac{{\left(s\rho \right)}^s{P}_0}{s!\left(1-\rho \right)}$

One thing to keep in mind is that Little’s law still applies here. We can use Little’s law to derive the average number in the system, LS, the average waiting time in the system, WS, the average number in the queue, LQ, and the average waiting time in the queue, WQ. The Little’s law relations still hold for LS/WS and LQ/WQ as in Equation 8.23; that is to say,

$L_S=\lambda W_S$

$L_Q=\lambda W_Q$

It can be shown that (Winston 1994)

$L_Q=\frac{P\left(j\ge s\right)\rho }{1-\rho }$ (8.29)

So, using Little’s law,

$W_Q=\frac{L_Q}{\lambda }=\frac{P\left(j\ge s\right)}{s\mu -\lambda }$ (8.30)

Since the average service time is 1/μ, then we know that the average time a customer spends in the system is given by

$W_S=W_Q+\frac{1}{\mu }=\frac{P\left(j\ge s\right)}{s\mu -\lambda }+\frac{1}{\mu }$ (8.31)

and, by Little’s law, we can obtain the average number in the system, LS, by

$L_S=\lambda W_S=\frac{P\left(j\ge s\right)\rho }{1-\rho }+\frac{\lambda }{\mu }$ (8.32)

Let us use an example to illustrate how to use Equations 8.26 through 8.32.

Example 8.2: A bank has three service windows. Assume that customers arriving to the windows follow a Poisson process, with mean interarrival time of 1 min. The service time follows an exponential distribution, with mean service time of 2.5 min. Customers wait in one queue if all the servers are busy, the queue rule is FIFO.

1. What is the probability that the bank is idle?

   From the question we know that λ = 1 min, μ = 0.4 min, s = 3 so

   $\rho =\frac{\lambda }{s\mu }=\frac{1}{1.2}=0.833<1$

   and

   $s\rho =3\left(0.833\right)=2.5$

   So, the probability that the bank is idle (i.e., there is no customer in the bank) is, according to Equation 8.27,

   $\begin{array}{l}{P}_0=\frac{1}{{{\displaystyle \sum }}_{i=0}^{s-1}\frac{{\left(s\rho \right)}^i}{i!}+\frac{{\left(s\rho \right)}^s}{s!\left(1-\rho \right)}}\\ ={\left[\frac{{\left(2.5\right)}^0}{0!}+\frac{{\left(2.5\right)}^1}{1!}+\frac{{\left(2.5\right)}^2}{2!}+\frac{{\left(2.5\right)}^3}{3!\left(1-0.833\right)}\right]}^{-1}=0.045\end{array}$

2. What is the average number of customers waiting in the queue and the average number of customers in the bank?

   $P\left(j\ge 3\right)=\frac{{\left(s\rho \right)}^s{P}_0}{s!\left(1-\rho \right)}=\frac{{\left(2.5\right)}^3\left(0.045\right)}{3!\left(1-0.0833\right)}=0.131$

   then, according to Equation 8.29,

   $L_Q=\frac{P\left(j\ge s\right)\rho }{1-\rho }=\frac{0.131\left(0.833\right)}{1-0.833}=0.653$

   The average number of customers in the bank system is given by

   $L_S=\frac{P\left(j\ge s\right)\rho }{1-\rho }+\frac{\lambda }{\mu }=L_Q+\frac{\lambda }{\mu }=0.653+2.5=3.153$

3. What is the average time that a customer will wait in the queue? How long does each customer spend in the bank? (All times in minutes.)

   Using Little’s law, we can obtain the average waiting time as follows:

$W_Q=\frac{L_Q}{\lambda }=\frac{0.653}{1}=0.653$

and

$W_S=W_Q+\frac{1}{\mu }=0.653+\frac{1}{0.4}=3.153$

A multiserver system with one single waiting line is more efficient than one with individual waiting lines for each of the servers. As you can imagine, a single queue for multiple servers will balance the workload for all of them; as the customers follow a FIFO rule, they will always choose the next available server. This selection process is “fairer” than individual waiting line systems, not just for the servers, but for the customers as well, as it truly follows the FIFO rule; while with an individual waiting line, it follows FIFO for that line, but considering all the queues together, the FIFO rule might not be followed. If you choose a “wrong” queue with a customer who takes a long time ahead of you, you may get served after people arriving after you, if they choose a faster queue. The difference between the two different queuing systems can be verified by comparing the average time a customer waits in the queue and the average queue length. Using the previous example, if customers form a separate queue for each server, then the arrival rate for each server becomes λ′ = λ/3 and the service rate is still the same, μ. We leave this as homework in the Problem section for readers to practice and compare with the results from Example 8.2.

8.1.4 Queuing Systems with Finite Population

In the previous section, we stated that one of the assumptions that we made is to assume that we have unlimited population. This assumption is necessary for a constant arrival rate λ to simplify the problems. As we discussed earlier, although a queuing system with infinite population may never be found, however, if the departure rate is relatively small enough compared to the population, the small changes in the arrival rate can be ignored so the assumption is valid. That is the assumption we used to solve the M/M queuing systems problems above.

In some real-world queuing systems, however, the population size is so small that it has very significant effects on the individual arrival rate; assuming an infinite population size will no longer make the model valid. For example, a company has 15 trucks; each truck may fail at any time, and if the trucks are identical with identical failure rates, then the failure occurrence rate (if you think of failure as a “customer,” a failure occurs as a “customer” arrives for repair service) with all 15 trucks running would be triple the arrival rate if only five trucks were operational and running. In cases like this, we can no longer treat population size as unlimited, but rather need to consider the population size in the formulation.

Let us denote the following:

N: Population size

λ: Individual arrival rate

λn: Actual arrival rate to the service when there are n customers in the service, n = 0, 1, 2, …, N

M: Number of service channels

μ: Individual service rate per service channel

μn: Actual service rate when there are n customers in the service, n = 0, 1, 2, …, N

Pn: Probability that there are n customers in the service, n = 0, 1, 2, …, N

It is easy to see that

${\lambda }_n=\lambda \left(N-n\right),n=0,1,2,\dots ,N$

and

${\mu }_n=\{\begin{array}{ll}n\mu ,\hfill & n\le M\hfill \\ M\mu ,\hfill & n>M\hfill \end{array}$

using the steady-state birth-death process, similar to Figure 8.4, we can establish the steady-state relationships; that is, in any of the steady states, the probability of incoming to that state (i.e., n) from other states (i.e., from state “n − 1” and state “n + 1”) equals the probability of leaving that state (i.e., from state n to state “n − 1” or “n + 1”). So we have

$\lambda P_0=\mu P_1$

For n ≤ M − 1, we have

$\left(N-n+1\right)\lambda P_{n-1}+\left(n+1\right)\mu P_{n+1}=\left[\left(N-n\right)\lambda +n\mu \right]P_n$

For M ≤ n ≤ N − 1, we have

$\left(N-n+1\right)\lambda P_{n-1}+M\mu P_{n+1}=\left[\left(N-n\right)\lambda +M\mu \right]P_n$

and for n = N, we have the special relationship

$\lambda P_{N-1}=M\mu P_N$

plus the mutually exclusive relations for all the probabilities

${\displaystyle \sum }_{i=0}^N{P}_i=1$

We can solve for the distribution of Pn as follows (Blanchard and Fabrycky 2006):

Let

$\rho =\frac{\lambda }{\mu }$

Denote

$C_n=\{\begin{array}{ll}\frac{N!}{\left(N-n\right)!n!}{\rho }^n\hfill & n=1,2,\dots , M\hfill \\ \frac{N!}{\left(N-n\right)!M!M^{n-M}}{\rho }^n,\hfill & n=M+1,\dots , N\hfill \end{array}$ (8.33)

So, we obtain the distribution of Pn as follows:

$P_n=\{\begin{array}{ll}\frac{N!}{\left(N-n\right)!n!}{\rho }^n{P}_0\hfill & n=1,2,\dots , M\hfill \\ \frac{N!}{\left(N-n\right)!M!M^{n-M}}{\rho }^n{P}_0,\hfill & n=M+1,\dots , N\hfill \end{array}$ (8.34)

with

$P_0={\left[{\displaystyle \sum }_{i=0}^{M-1}\frac{N!}{\left(N-i\right)!i!}{\rho }^i+{\displaystyle \sum }_{j=M}^N\frac{N!}{\left(N-j\right)!M!M^{j-M}}{\rho }^j\right]}^{-1}$ (8.35)

The mean performance parameters are given as follows:

Average number waiting in the service queue:

$L_Q={\displaystyle \sum }_{i=M}^N\left(i-M\right)P_i$ (8.36)

Average number in the system (waiting + being served):

$L_S=L_Q+{\displaystyle \sum }_{i=0}^{M-1}i{P}_i+M\left(1-{\displaystyle \sum }_{j=0}^{M-1}{P}_j\right)$ (8.37)

For M = 1 (single service channel), it is easy to show that

$L_S=L_Q+\left(1-P_0\right)=N-\frac{\mu }{\lambda }\left(1-P_0\right)$

With an average of LS customers in the system, there are still N − LS customers outside of the system, so the effective arrival rate of the customers, or λe, is

${\lambda }_e=\lambda \left(N-L_S\right)$ (8.38)

So, using Little’s law, we can obtain the average time waiting and average time spent in the system as

$W_S=\frac{L_S}{{\lambda }_e}$ (8.39)

and

$W_Q=\frac{L_Q}{{\lambda }_e}$ (8.40)

Let us use an example to see how these formulas can be used to solve the queuing system problem with a finite population.

Example 8.3: Assume there is one repair man to service five machines. Every machine’s operation time follows an exponential distribution with a mean of 12 min. When the machine fails, the repair man fixes the problem, taking a time following an exponentially distributed time of 10 min.

1. What is the probability that the repair man is idle?
2. What is the mean number of machines that are not operational?
3. What is the average number of machines that are waiting to be serviced?
4. When a failure occurs, what is the average time that a machine has to wait until it becomes operational again?
5. What is the average time that each failed machine has to wait before being serviced?

Solutions: From the problem description, we know that λ = 1/12 (per min), μ = 1/10 (per min), ρ = λ/μ = 0.833, N = 5, and M = 1.

1. If and only if there is no machine failure, then the repair man is idle. So the probability that the repair man is idle is, according to Equation 8.34,

$\begin{array}{c}{P}_0={\left[{\displaystyle \sum }_{i=0}^{M-1}\frac{N!}{\left(N-i\right)!i!}{\rho }^i+{\displaystyle \sum }_{j=M}^N\frac{N!}{\left(N-j\right)!M!M^{j-M}}{\rho }^j\right]}^{-1}\\ ={\left[\frac{5!}{5!}{\left(\text{0}\text{.833}\right)}^0+\frac{5!}{4!}{\left(\text{0}\text{.833}\right)}^1+\frac{5!}{3!}{\left(\text{0}\text{.833}\right)}^2+\frac{5!}{2!}{\left(\text{0}\text{.833}\right)}^3+\frac{5!}{1!}{\left(\text{0}\text{.833}\right)}^4+\frac{5!}{0!}{\left(\text{0}\text{.833}\right)}^5\right]}^{-1}\\ =0.0073\end{array}$

1. The mean number of machines that are not operational equals the mean number of machines that are in the service system LS. According to Equation 8.36, with M = 1,

$L_S=L_Q+\left(1-P_0\right)=N-\frac{\mu }{\lambda }\left(1-P_0\right)=5-\frac{1}{\text{0}\text{.833}}\left(1-\text{0}\text{.0063}\right)=\text{3}\text{.81}$

1. The average number in the waiting line is

$L_Q=L_S-\left(1-P_0\right)=\text{3}\text{.81}-\left(1-\text{0}\text{.0063}\right)=\text{2}\text{.82}$

1. The average time that a machine waits until it becomes operational again is actually the average time a failed machine spends in the service system, so according to Little’s law,

$W_S=\frac{L_S}{{\lambda }_e}=\frac{L_S}{\lambda \left(N-L_S\right)}=\frac{\text{3}\text{.81}}{\frac{1}{12}\left(5-3.76\right)}=\text{38}\text{.42}\left(\text{min}\right)$

1. The average time that each failed machine has to wait before getting serviced can also be obtained by Little’s law, using Equation 8.39:

$W_Q=\frac{L_Q}{{\lambda }_e}=\frac{\text{2}\text{.82}}{\frac{1}{\text{12}}\left(5-\text{3}\text{.81}\right)}=\text{28}\text{.44}\left(\text{min}\right)$

There are many other types of queuing systems, such as systems with limited space s (customers will leave if there are already s customers in the system; for example, at the drive-through window of a fast-food restaurant); queuing systems with varying arrival rates (i.e., some customers might choose to leave the system when they find that the system already has many customers waiting); queuing systems with non-Poisson arrival or nonexponential service time distributions (usually indicated as G/G/c queues, as G indicates a nonexponential distribution). Also, there are different types of queuing networks (such as a series of different queuing systems connected in a series or parallel structure). For more information about queuing theory, readers may refer to a specialized queuing theory textbook for a more in-depth review.

8.2 Application of Queuing Theory

Queuing theory may be used in systems design and process optimization. By formulating the system (subsystem) processes as queuing systems, one can analyze and control the process parameters to optimize the output of the system; often, the objective of the queuing output is its total cost per time period. This is also called the static optimization of queuing systems.

The goal of process design is to increase the efficiency of the operation at minimum cost. In queuing systems, as we mentioned above, the cost incurred primarily comes from two sources: the waiting cost and the service cost. There is a trade-off between these two costs; the waiting cost occurs when customers spend time in the queuing system. They are either waiting to be served or actually being served. The loss of time of the customers in the queuing system is considered as waiting cost; the longer time they spend in the system, the higher the waiting cost. The only way to reduce waiting cost is to increase more service capacity, either by adding more service channels or increasing the service rate per channel (i.e., hiring more experienced employees to provide faster service); this greater capacity leads to a higher service cost. When the service cost is increased, then customers wait less time in the system and the waiting cost is reduced, and vice versa. Through the trade-offs between service cost and waiting cost, the total cost of the queuing system can be minimized. Let us use an M/M/1 queue as an example to illustrate how the total cost is optimized.

Let

z = total cost of queuing system per time period

cW = waiting cost per customer per time period

cs = service cost per serving customer per time period

Then we have

z = service cost + waiting cost = cs × (number of customers served per time period) + cW (average number of customers in the system).

So

$z\left(\mu \right)=c_S\mu +c_W{L}_S=c_S\mu +c_W\frac{\lambda }{\mu -\lambda }$

z(μ) is a function of μ, since the service rate is our only decision variable. To minimize z, using the necessary conditions for an unconstrained optimization problem, we have

$\frac{\text{d}z}{\text{d}\mu }=c_S-c_W\lambda \frac{1}{{\left(\mu -\lambda \right)}^2}=0$

Solving this, we can obtain the optimal service rate as

$\mu *=\lambda +\sqrt{\frac{c_W}{c_S}}\lambda$ (8.41)

We can verify this is truly a minimum by deriving the second-order derivative, that is

$\frac{{\text{d}}^{2}z}{\text{d}{\mu }^2}=2c_W\lambda \frac{1}{{\left(\mu -\lambda \right)}^3}>0$

Example 8.4: Machines come to a service center for a regular checkup service. The arrival process is a Poisson process with an arrival rate of 5/h. Each machine can make $100 profit/h. The service charge is $75/h/machine. What should the service rate be to minimize the total cost?

Solution: λ = 5/h, cW = $100/h and cs = $75/h/machine. According to Equation 8.40, the optimal service rate μ* is

$\mu \text{*}=\lambda +\sqrt{\frac{c_W}{c_S}}\lambda =5+\sqrt{\frac{100}{75}}5=10.77\cong 11$

So, the average service rate is roughly 11 machines/h. The total cost per hour is minimized, which can be obtained as follows:

$c_S\mu +c_W\frac{\lambda }{\mu -\lambda }=75\left(5\right)+100\frac{5}{11-5}\cong 458.33$

The minimum cost per hour is $458.33.

For a simple system like the one above, the analytical method is sufficient to optimize the system performance. However, if the queuing system is complex and dynamic, involving many variables and a large degree of uncertainty, it is very difficult, sometimes even impossible, to solve it by using the analytical model. In this case, a simulation-model-based solution is more appropriate. In the following section, we will introduce the basic concept of simulation and illustrate how a simulation model can be used to solve a complex queuing system empirically.

8.3 Queuing System Analysis Using Discrete Event Simulation (DES)

As shown above, for queuing systems such as the M/M/c queue, the analytical models are well developed and we can predict their steady-state performance without too much difficulty. We made many assumptions (i.e., Poisson arrival process) about the analytical queuing models in the previous sections, to simplify the problem so that a mathematical model could be formulated. However, in the real world, the situation becomes more dynamic and complicated than those mathematical models can handle; even though queuing network models are available, many situations are simply beyond the capabilities of the analytical mathematical model. To give some examples, employees in a manufacturing facility work on different shifts and they have coffee breaks every 2 h and a 1 h lunch break for every 8 h shift; a restaurant opens from 8 a.m. to 8 p.m., and customers’ arrival rate is not stationary throughout the day (i.e., peak hours at lunchtime and dinnertime). When modeling these systems, information such as the shift patterns, lunch breaks, machine breakdowns, arrival rate, and so forth cannot be ignored, as they will have significant impacts on system performance; also, some systems might never arrive at a steady state and do not operate on a 24/7 basis. So, it is nearly impossible to study these types of systems using queuing theory and models; a theoretical solution for those queuing systems would be difficult to obtain. An alternative to the mathematical model is to use the simulation model instead.

8.3.1 Introduction to Simulation

Simulation, generally speaking, is the replication or imitation of the operation of a real-world process or system over time (Bank et al. 2001). It can be regarded as a process of modeling that represents complex systems from the real world. By investigating systems empirically, modeling and simulation can provide insight into systems behavior, as well as allowing testing of alternative solutions through system experimentation.

With the advance of computer technology, simulation is a widely used and increasingly popular method for studying complex systems. Some advantages to simulation that may account for its growing popularity include (Law and Kelton 2000):

• Mathematical models cannot accurately describe complex and dynamic stochastic elements in a system; as mentioned above, these elements are difficult to quantify.
• Simulation allows the estimation of performance of an existing system under different operating conditions, through a valid representation model. Through a validated simulation model, the various operating conditions can be investigated even if such a condition does not exist in the real-world situation.
• Support of alternative comparison and experimental designs. With a validated simulation model, different design/redesign alternatives can be compared in a very efficient way.
• Simulation offers better control over experimental conditions compared to experimenting with the system itself, especially as direct manipulation is costly or unfeasible, or the system may not even yet exist.
• Simulation allows the study of a system over a long time frame in compressed time. Since the simulation model computes the events, and does not actually “replicate” events in the real time frame.

However, there are also disadvantages to modeling and simulation:

• Stochastic simulations only produce estimates of how the real system will perform; most of the time the results are not generalizable, since simulation models are constructed based on individual systems.
• Complex simulations can be time consuming and expensive to develop, especially when there are large numbers of processes and variables involved.
• The large volume of data that is produced by the simulation can sometimes place greater confidence in the study’s results than is justified. Especially when the model is not valid, the data produced can be misleading.
• Simulation modeling can be used to compare alternatives, but not to find the optimal solution to a problem.

8.3.2 Discrete Event Simulation (DES)

Despite these issues, simulation is still one of the most popular methods used to solve real-world systems problems. Particularly for simulating queuing systems, discrete event simulation (DES) has been used widely as the primary simulation method. DES, as the name indicates, uses a sequence of discrete events occurring to simulate the events (i.e., arrival and departure) in the queuing system in the real world; it is a technique for the study of systems whose state changes at discrete points in time. The fundamental concepts in DES are that a system is composed of objects, known as entities (such as customers in the queuing system), and each entity has unique properties called attributes. The system state is a collection of attributes that represent the entities of the system; by investigating the systems variables and analysis using statistics, the performance of the queuing system can be studied and optimized.

Typical procedures (Figure 8.5) include:

1. Formulate the problem and plan the simulation study. Here, the real-world problem is that the issues that need to be addressed by the model are defined so that the level of detail adequately reaches the model’s objectives.
2. Collect data on the system of interest and determine the model’s logic. The data is analyzed and represented in a proper format; this format has be validated to represent the true system parameters from the real world. Validating input data is very important to ensure it is complete, correct, and consistent. Data analysis and validation should occur before any coding begins to avoid reprogramming the model. We will review some of the data analysis techniques in Section 8.3.3.
3. Develop the computer simulation model and verify the model. Check and debug the model to make sure it is error free. As mentioned earlier in the book, a verified model is not the same as a validated model; a verified model means that the model is error free and is doing what the developer wants it to do, or doing things right, but sometimes a verified model does not necessarily perform in the same way as the real-world system. In that case, we need to validate the model to make sure it is doing the right things.
4. Validate the DES model. Statistical analysis that compares the model’s output to actual system data will ensure that the model is valid and performs similarly to the actual system.
5. Experiment with the valid model. This is where alternative designs are developed. Comparative results should be documented, presented, and implemented.

8.3.3 Data Analysis Using Goodness of Fit

Simulation is considered empirical; in other words, the model depends on the actual data collected from the real world, and a distribution function is developed to represent the nature of the data collected. In the real world, data present a large degree of variability, and we cannot assume that the data follows a certain distribution without analyzing it first. As a matter of fact, an accurate estimation of the distribution to represent the data is critical, as this distribution will be used by the simulation model to generate simulation events, as it is well known that “garbage in, garbage out”; without an accurate data model, one cannot produce valid simulation results.

With collected data, the first thing to do is plot the histogram of the data to observe the pattern of the distribution; based on the observed pattern, a hypothesis is made. For example, if one observes a symmetrical bell shape, then a normal distribution is reasonably hypothesized; if no particular shape can be concluded from the histogram, one always can use an empirical fit for the data. We will talk about this later in this section.

With the hypothesized distribution function, a maximum likelihood estimation (MLE) method is used to estimate the parameters of the distribution. An MLE is a method to estimate the parameters of a statistical model. The idea behind the MLE method is that for the collected data set and the hypothesized underlying model for the data, the distribution parameters are sought to maximize the likelihood function, which can be defined as follows:

Suppose there is a sample of n independent and identically distributed (IID) observations, x1,x2,…,xn; then, the likely function is the joint density function, which can be defined as

$ℒ\left(\theta ;x_1, x_2, \dots , x_n\right)=f\left(x_1, x_2, \dots , x_n\text{|}\theta \right)=f\left(x_1\text{|}\theta \right)\times f\left(x_2\text{|}\theta \right)\times \cdots f(x_n|\theta )$

with θ being the parameter for the distribution functions. The MLE method determines the parameter θ such that L(θ;x1, x2, …, xn) or sometimes the log-likelihood function ln(L(θ;x1, x2, …, xn)) is maximized. Due to the nature of this book, we are not going to delve into the details of MLE methods; for more information, readers can refer to any advanced statistics book such as Pfanzagl (1994).

Once the parameters have been estimated, the next step is to test if the fitted distribution model from the estimated parameters truly represents the data. A commonly used test is the goodness-of-fit test. Specifically, goodness-of-fit tests allow for the testing of the null hypothesis of the data fitting a particular distribution. The null hypothesis is as follows:

H0: The xi’s are random variables with distribution function ${ }_F^{^}$

The goodness-of-fit test verifies the null hypothesis, that is, whether or not that the hypothesized theoretical distribution is a good fit for the actual data (or, in other words, that there is no difference between the actual and proposed distributions). A popularly used statistics test for the hypothesis is to use chi-square testing, illustrated in Equation 8.42:

${\chi }^2={{\displaystyle \sum }}^{\text{}}\frac{{\left(O-E\right)}^2}{{\sigma }^2}$ (8.42)

where:

σ2 is the variance of the observed data

O is the observed data frequency count

E is the fitted data frequency count from the theoretical model if the null hypothesis is true

Chi-square testing is also called “nonparametric” statistics as it does not depend on the assumption of normality, but rather compares the frequencies of the occurrence.

A larger corresponding p-value for the goodness-of-fit tests indicates a good fit. A rule of thumb is that the p-value should be 0.15 or higher for a theoretical distribution to be used. If the p-value is less than 0.15, this implies that the hypothesized model is not really a good fit for the data, so the null hypothesis above cannot be accepted. In this case, an empirical distribution should be used.

Distributions in simulation models fall into two main types: theoretical and empirical. Theoretical distributions use mathematical formulas to generate samples (such as the normal distribution or the exponential distribution), while empirical distributions simply divide the actual data into groups and calculate the proportion of values in each group. Law and Kelton (2000) explain that if a theoretical distribution can be found to fit the actual data reasonably well, this is preferable to using an empirical distribution for the following reasons:

• Theoretical distributions “smooth out” irregularities found in empirical distributions.
• It is not possible to generate values outside of the range of the observed data in the simulation using an empirical distribution.
• The theoretical distribution is a more compact way of representing a set of data values.
• A theoretical distribution is easier to change.

Equation 8.42 gives a continuous, piecewise-linear distribution function F by first sorting the X(i)’s into increasing order, letting X(i) denote the ith smallest member of the data set so that X(1) ≤ X(2) ≤ ⋯ ≤ X(n). Then, the empirical distribution F is given by:

$F\left(x\right)=\{\frac{1}{n-1}\left(i\begin{array}{l}0,\hfill \\ +\frac{x-X_{(i)}}{X_{(i+1)}-X_{(i)}}\hfill \\ 1,\hfill \end{array}\right),\begin{array}{l}if x< X_{(1)}\hfill \\ if X_{(i)}<x<X_{(i+1)},\hfill \\ if x\ge X_{(n)}\hfill \end{array}$

As we can see, F(x) is actually a cumulative distribution function to generate a random value from the distribution. For example, if we found that the service time x of an operator has the following cumulative empirical distribution distribution (see Figure 8.6). Then we can generate a uniform random number in [0, 1], mapping to the x axis to generate a random number in xi.

These distribution functions, either theoretical or empirical, will be used as input to the simulation model to generate random numbers to create the event for the model. In the next section, we use an example using Arena software to illustrate how a DES model can be constructed.

8.3.4 DES Model Using Arena

Here we use a DES software package, Rockwell Automation’s Arena v.14 computer simulation software, to give an example of how a DES simulation is built. Arena is a graphical user interface (GUI)-based DES software package, which allows us to easily and logically model real-world queuing systems in an intuitive way, by using the appropriate process blocks (Kelton et al. 2010). With a short learning curve, almost any user can easily learn to build a model, without going through long learning lessons; meanwhile, Arena also offers options for advanced users who prefer to use basic code to build the system from the nuts-and-bolts level. Moreover, Arena provides the ability to experiment on a system, either by creating or manipulating certain processes or entities involved in the system’s operations and analyzing the results (Rockwell Automation 2011). For example, new operational techniques, new machines, altered schedules, or “what if” scenarios can be implemented into the system without disturbing the current operational flow, using unnecessary resources, or putting the system and its components in danger.

Before illustrating the Arena simulation model, let us first review the elements/concepts that are used in Arena.

8.3.4.1 Entity

Entities are the “players” of simulation systems; they correspond to the customers in queuing systems. In DES models, entities are created at the beginning of the simulation; they pass through the model, trigger the occurrence of events (i.e., entity arrives, waits in a queue, departs the system, etc.), and when these events occur, systems update their status through variables and attributes, so that the performance of the queuing systems can be recorded and measured.

8.3.4.2 Attribute

Attributes are the properties of the entities; they characterize the entity to track/record its behaviors. For example, the entity’s name, type, arrival time, and even pictures of it are all instances of entity attributes.

8.3.4.3 Resources

Resources are the servers in the queuing systems, as mentioned in the previous sections, since all the resources (service channels) have limited capacity (number of service channels), so entities compete for the resources. Resources have four states; busy, idle, inactive, and failed. When a resource is not available (either busy, inactive, or failed), customers wait in a queue until the resource is available again, so that they can be served.

8.3.4.4 Queue

Queues are the places for the entities to wait for service from the resources. A queue has a rule, the default rule is FIFO; there are also other rules that can be applied to the queue, such as LIFO or by priority (e.g., as defined in some attribute of the entity; it could be the lowest value of that attribute first, or the highest value first).

8.3.4.5 Variable

Variables record the behaviors of the queuing systems; comparing attributes, variables are global while attributes are “private” to each entity. For example, the number of entities within the system is a variable; it is not tied to any entity. Although entities’ behavior could may change the value of a variable, the copy of the variable exists at system level, while the copies of attributes only coexist with the entity. When there is no entity in the system, there will be no attributes, but the variable will still exist.

Let us use a simple example to illustrate how to build a model using Arena.

Example 8.5: Parts arrive at a manufacturing facility to be processed (drilled). Data shows that parts arrive according to a Poisson process, with a mean interarrival time of 6 min, and one part arrives at a time. When parts arrive, they will wait in a queue to be processed in a first-come-first-served basis. Currently, the facility has one drilling machine available. The processing time per part follows a triangular distribution, with a minimum possible time of 4 min, maximum possible time of 6 min, and most likely processing time of 5 min. When the drilling is completed for a particular part, it is shipped out if it is of good quality. However, the data shows that about 15% of the parts will have defects that prevent them from being shipped out. If parts are defective, they will be sent to a station for rework. Currently, there is one employee available to carry out the manual rework, which takes an exponential distributed time with a mean of 10 min; after the rework, all the parts will be salvaged and shipped out. We want to know the average cycle time for completed parts and salvaged parts (the time in the system), the average time parts wait to be processed, the average time parts wait to be reworked, and the utilization (i.e., the percentage of time that the drilling machine and the rework station are busy).

As you can see from the example description above, it is quite challenging to solve the problem analytically, as it involves a nonexponential time distribution and other complexities such as the rework rate. This problem is very suitable for the use of a simulation model to solve it empirically.

Let us use Arena as the simulation software to illustrate how to build a simulation model to solve this problem.

1. A good start would be to sketch the problem using a flow chart; in this way, the logic is easily visualized, as the simulation model will look like the flow chart. The flow chart for the above example is illustrated in Figure 8.7.
2. Build the Arena model. Building the model is very straightforward; for simple problems like Example 8.5, we can just use the basic process module, as shown in Figure 8.8.

   Modules are pre-packaged basic modeling units, which will satisfy the most fundamental needs for model development. The Arena software has a typical window style interface; all the modules in the different levels of the template will fulfill the modeling needs of the simulation models. Arena has also provided the basic “block” and “element” for advanced users, enabling them to build the model from a near-scratch level, providing maximum flexibility and capabilities for different kinds of modeling needs. For a more detailed description of Arena blocks and elements, readers can refer to Kelton et al. (2009).

   Figure 8.7

   

   Flow chart sketch for Example 8.4.

   Figure 8.8

   

   The Arena basic process module. (Courtesy of Rockwell Automation, Inc. Milwaukee, WI)

   Let us use modules from the “basic process” template to build the simulation model for Example 8.5.

   8.3.4.6 Step 1: Generate Parts Arrival and Assign Parts Attributes

   To generate the arrival of the parts according to the Poisson process, with the interarrival time following the exponential distribution with a mean of 6 min, we use the “create” module. Drag and drop a “create” module on the working area (the big white area in the middle), and double-click on the “create” to change the parameters, as seen in Figure 8.9.

   Figure 8.9

   

   Illustration of “Create” module. (Courtesy of Rockwell Automation, Inc.)

   One thing that readers have to keep in mind is that Arena does not allow two items to have the exact same name, so, when entering names for each module, or for anything defined within the model, it is a good idea to make the name unique and meaningful. This is extremely useful when debugging the model, and, later, an easy-to-understand name will make the reading of the model much easier.

   Once the parts enter the system, before carrying out any other action, it is a good idea to assign some “attributes” to facilitate the recording of entity behavior. In this example, we want to collect the average time that each entity (customer) stays in the system. To collect this information, we need to record, for each of the entities, the times that they arrive and depart; the time interval between the departure and arrival is the time spent in the system. Because each customer arrives and departs at different times, it is not feasible for the model to setup an observer to keep track of all these different times. It is more efficient for each of the customers to carry their own arrival time value themselves and, just as they depart, we can look at the current time, subtract the arrival time (attribute) they carry with them, and thus obtain the time in the system for each customer. Attributes are attached to each individual entity; each entity carries a copy of the attribute. When this entity departs the system, its copy of the attribute will be deleted with the entity’s departure. You will find using the attributes very handy and convenient when collecting tally statistics for the entities. Arena has predefined some of the attributes, including the entity number, entity picture, and so on. To add a new attribute, drag and drop an “Assign” module connect after the “Create,” and double-click on it, change the name, and click on the “Add” button; then select “Attribute” in the type drop-down list, and type the new attribute name “Time Arrival,” and in the new value field, type the value “TNOW.” (This is the system variable to record the current simulation clock. Beginners who do not know this variable can point their mouse to the new value field and right-click, and then choose “Build expression,” and a pop-up window will appear, allowing them to find the right variable.) Figure 8.10 illustrates the “Assign” module parameters.

   Figure 8.10

   

   Illustration of “Assign” module. (Courtesy of Rockwell Automation, Inc.)

   8.3.4.7 Step 2: Drilling Process

   After the entities arrive and are assigned attributes, they then move on to the drilling process. Drag and drop a “process” module and connect it to the “Assign” module. The parameters in the “Process” module are illustrated in Figure 8.11. In the logic drop-down list, choose “Seize delay release”; since there is a limited resource (one person), only one entity can be processed at a time. So each entity needs to “Seize” the resource (thus making it unavailable for other entities), “Delay” a processing time (according to the triangular distribution [4, 5, 6] minutes) and then “Release” the resource for the section, click on the “Add” button and a new resource window will pop up. In the new window, type the name of the resource “Machine 1” with a quantity of 1. (Please pay attention here that this quantity is not the capacity of the resource, but the number of resources needed to complete service for one entity. If you need to change the capacity of the resource, you need to change it in the “Resource” data element in the Basic Process Template.)

   Figure 8.11

   

   Illustration of “Process” module. (Courtesy of Rockwell Automation, Inc.)

   8.3.4.8 Step 3: Decide for Rework

   A “Decide” module is needed to branch off the parts that need rework from the rest. Figure 8.12 shows the screen shot of the “Decide” module. Note that “2-way by Chance” is chosen as the branch type, and the value of the percentage of the portion being reworked, “15,” is entered. Since this is a percentage value, we put “15” instead of “15%” in the field.

   Figure 8.12

   

   Illustration of “Decide” module. (Courtesy of Rockwell Automation, Inc.)

   The “Process” module for rework is illustrated in Figure 8.13. It is similar to the “Drilling” process, except the names and parameters are different.

   Figure 8.13

   

   “Rework process” module details. (Courtesy of Rockwell Automation, Inc.)

   8.3.4.9 Step 4: Collect Time in System and System Exit

   When entities complete the service, before they exit the system, we need to collect the time they have spent in the system. For this purpose, a “Record” module is needed. The detailed information for the “Record” module is shown in Figure 8.14. We choose “Time Interval” as the type, and in the attribute name drop-down list, we choose the attribute “Time Arrival,” which is defined earlier in the “Assign” module. Arena maintains the list of all the defined attributes; we just need to choose it from the drop-down list, instead of the typing the name ourselves. In this way, some typo errors can be avoided.

   Figure 8.14

   

   “Record” module details. (Courtesy of Rockwell Automation, Inc.)

   On leaving the “Record” module, we use “Dispose” to have the entity depart the system. The final model structure is illustrated in Figure 8.15.

   Figure 8.15

   

   Example 8.5 final model structure. (Courtesy of Rockwell Automation, Inc.)

   8.3.4.10 Step 5: Execute the Model and Obtain Results

   From the Arena menu, go to “Run,” then choose “Setup” from the menu, and choose the “Replication parameters” tab in the menu window, as shown in Figure 8.16.

   Figure 8.16

   

   Setup window for model parameters. (Courtesy of Rockwell Automation, Inc.)

   As seen in Figure 18.16, we want to change the replication length to 800 h and also change the hours per day from 24 to 8 h, and change the base time units from hours to minutes, as all the time data we used in the model are in units of minutes.

   Once the run parameters are set, run the model if there is no error within it. The results of the model can be found in the “Report” section, as seen in Figure 8.17.

   Figure 8.17

   

   Illustration of model reports. (Courtesy of Rockwell Automation, Inc.)

   Clicking through the different sections of the “Report,” we will find the results we need, as seen in Figure 8.18 and Table 8.1 and Table 8.2.

   Table 8.1

   Queue Detail Summary

   	Waiting Time
   Drilling process queue	11.46
   Rework process queue	2.47

   Not e: This time can be found in the “Queue” category of the report.

   Table 8.2

   Resource Detail Summary

   	Usage
   	Inst Util	Num Busy	Num Sched	Num Seized	Sched Util
   Machine 1	0.82	0.82	1.00	7,860.00	0.82
   Worker	0.25	0.25	1.00	1,197.00	0.25

   Note: The utilization (i.e., the percentage of time that drilling machine and rework station are busy) for Machine 1 is 82% and worker (rework resource) is 25%.

   Figure 8.18

   

   Average cycle time for completed parts and salvaged parts (time spent in the system); for completed parts, the average time is 16.5350 min, and for salvaged parts, this time is 28.6120 min. (Courtesy of Rockwell Automation, Inc.)

   This example demonstrates how to use simulation to solve a complex queuing system problem; the basic steps are presented. However, for real-world problems, the simulation model needs to be validated before the results can be used to draw any conclusions. For more details about DES model validation, readers can refer to Kelton et al. (2009).

   8.4 Summary

   In this chapter, we reviewed queuing theory and its application in systems engineering. In systems design, since the resources are always limited, in many situations we have to deal with a waiting line system. Queuing theory studies the behavior of the waiting line system to optimize its behavior. We started with the M/M/1 queue; by using the birth-death process, we derived the distribution of the M/M/1 queue, and obtained its fundamental statistics, including the average number of customers in the system, the average number waiting in the queue, the average time spent in the system, and the average time spent in the queue. Little’s law (L = λW) is very useful to describe the relationships between average numbers (L) and average times (W) spent within the system and queues, and this law is universal for all types of queuing systems, regardless of the distributions of the arrival time and process time. We also briefly introduced the multiserver M/M/c queue and gave some examples to illustrate how to use Little’s law to solve for the basic statistics.

   In the last section of the chapter, we described how to use simulation to solve more complex queuing system problems. Some basic simulation concepts were introduced followed by a simulation demonstration using Arena software. The simulation method is very useful if the queuing system is dynamic and involves many factors that make an analytical approach impossible.

   Problems

3. Compare the performance of the separate waiting line systems in Example 8.2, comparing the average queue length, the average number of customers in the system, the average waiting time spent waiting in the queue, the average time spent in the system, and the probability that a customer has to wait. What is your conclusion based your results?
4. Customers arrive at a service shop following a Poisson process with a mean arrival rate of 6/h; the service time per customer is exponentially distributed with a mean service time of 8 min. Assuming there is enough space for customers to wait,
   1. What is the probability that the shop has no customer in it?
   2. What is the probability that there are four customers in the shop?
   3. What is the probability that there is at least one customer in the shop?
   4. What is the mean number of customers in the shop?
   5. What is the mean number of customers waiting in the queue?
   6. What is the mean waiting time in the queue?
5. A service center has customers arriving in a Poisson process, and the service time is exponentially distributed with a mean of 15 min. If customers spend more than 1.25 h in the center on average, the manager will consider hiring additional service resources. What is the maximum arrival rate of customers to make the hiring decision?
6. In a manufacturing facility, machines break down at an exponential rate of 4/h. There is one service person who repairs these machines at an exponential rate of 5/h. The cost of losing production for these failed machines is $30/h/machine. What is the average cost rate ($/h) for the factory due to these machine failures?
7. Machines come to a service center for a regular repair service; the arrival process is a Poisson process with an arrival rate of 10/h. Each machine can make $500 profit/h and the service charge is $200/h/machine. What should the service rate should be to minimize the total cost? What is the minimum cost?
8. At a post office, a newly hired person works at a rate of 10 customers/h exponentially; an experienced employee works at a rate of 20 customers/h. It has been estimated that customer waiting time is worth $5/h, and customers arrive at a Poisson process at a rate of 6 customers/h. If the new employee is paid $10/h, what is the pay rate for the experienced employee so that the average cost would break even between novice and experienced employees?
9. Simulate Problem 2 using Arena and obtain the results for (d), (e), and (f). Compare the results obtained from Problem 2. Discuss the differences between the two sets of results.
10. Students at a university come to the bursar’s office entrance following a Poisson process, with a mean interarrival time of 5 min (the first student arrives at Time 0). After entering the door, there is a hallway that takes students uniformly between 1.5 and 2 min to walk to the service window. Upon arrival at the service window, students wait in a single queue to be served by one of the three clerks; the service time per student is distributed in a triangular distribution with a minimum of 3 min, maximum of 5 min, and most likely 5 min. Upon completion of the service, students leave the window and walk back to the door and exit. Using ARENA, simulate for 16 h, obtain the average number of students completing the service, the average time students spend in the office, and the average number of students waiting in the waiting line.
11. Parts arrive at a cleaning facility for processing. The arrival of parts follows a Poisson distribution, with a mean of 1 min (first arrival occurs at Time 0). Upon arrival, parts are processed in the cleaning station with one machine; the cleaning time is triangularly distributed (minimum 30 s, maximum 90 s, and most likely 1 min). After cleaning, 80% pass inspection and are shipped out directly; 20% are considered defective and sent to a rework station (with one machine) to be fixed. Assume 100% of the rework is successful and the rework time is exponentially distributed with a mean of 5 min. Use ARENA to simulate the process for 1000 min and find the average time good parts and salvaged parts spend in the system and the queue length for the two workstations and utilizations.