Queueing and Simulation

Introduction: In many retail stores and banks, management has tried to reduce the frustration of customers by somehow increasing the speed of the checkout and cashier lines. Although most grocery stores seem to have retained the multiple line/multiple checkout system, many banks, credit unions, and fast food providers have gone in recent years to a queuing system where customers wait for the next available cashier. The frustrations of "getting in a slow line" are removed because that one slow transaction does not affect the throughput of the remaining customers. Wal-Mart and McDonald's are other examples of companies that open up additional lines when there are more than about three people in line. In fact, Wal-Mart has roaming clerks now who can total up your purchases and leave you with a number that the cashier enters to complete the financial aspect of your sale. Disney is another company where they face thousands of people a day. One method to ameliorate the problem has been to use queuing theory. It has been proved that throughput improves and customer satisfaction increases when queues are used instead of separate lines. Queues are also used extensively in computing---web servers and print servers are now common. Banks of 800 service phone numbers are a final example I will cite. Queuing theory leads one directly to the Poisson distribution, named after the famous French mathematician Simeon Denis Poisson (1781-1840) who first studied it in 1837. He applied it to such morbid results as the probability of death in the Prussian army resulting from the kick of a horse and suicides among women and children. As hinted above, operations research has applied it to model random arrival times.

Characteristics of a queuing system that impact its performance, for example, queuing requirements of a restaurant will depend upon factors like:

How do customers arrive in the restaurant? Are customer arrivals more during lunch and dinnertime (a regular restaurant)? Or is the customer traffic more uniformly distributed (a cafe)?

How much time do customers spend in the restaurant? Do customers typically leave the restaurant in a fixed amount of time? Does the customer service time vary with the type of customer?

How many tables does the restaurant have for servicing customers?

The above three points correspond to the most important characteristics of a queuing system. They are explained below:

Arrival Process: The probability density distribution that determines the customer arrivals in the system. In a messaging system, this refers to the message arrival probability distribution.

Service Process: The probability density distribution that determines the customer service times in the system. In a messaging system, this refers to the message transmission time distribution. Since message transmission is directly proportional to the length of the message, this parameter indirectly refers to the message length distribution.

Number of Servers: Number of servers available to service the customers. In a messaging system, this refers to the number of links between the source and destination nodes.

Based on the above characteristics, queuing systems can be classified by the following convention:

A/S/n Where A is the arrival process, S is the service process and n is the number of servers. A and S are can be any of the following:

M (Markov) Exponential probability density D (Deterministic) All customers have the same value G (General) any arbitrary probability distribution

Examples of queuing systems that can be defined with this convention are:

M/M/1: This is the simplest queuing system to analyze. Here the arrival and service time are negative exponentially distributed (Poisson process). The system consists of only one server. This queuing system can be applied to a wide variety of problems as any system with a very large number of independent customers can be approximated as a Poisson process. Using a Poisson process for service time however is not applicable in many applications and is a good (i.e., conservative) approximation.

Simulation in general is to pretend that one deals with a real thing while really working with an imitation. In operations research the imitation is a computer model of the simulated reality. A flight simulator on a PC is also a computer model of some aspects of the flight: it shows on the screen the controls and what the "pilot" (the youngster who operates it) is supposed to see from the "cockpit" (his armchair).

Why to use models? To fly a simulator is safer and cheaper than the real airplane. For precisely this reason, models are used in industry commerce and military: it is very costly, dangerous and often impossible to make experiments with real systems. Provided that models are adequate descriptions of reality (they are valid), experimenting with them can save money, suffering and even time.

When to use simulations? Simulation is a useful tool for any systems that change with time, such as a gas station where cars come and go, (called dynamic systems) and involve randomness. Nobody can guess at exactly which time the next car should arrive at the station, are good candidates for simulation. Modeling complex dynamic systems theoretically need too many simplifications and the emerging models may not be therefore valid. Simulation does not require that many simplifying assumptions, making it the only tool even in absence of randomness.

How to simulate? Suppose we are interested in a gas station. We may describe the behavior of this system graphically by plotting the number of cars in the station; the state of the system. Every time a car arrives the graph increases by one unit while a departing car causes the graph to drop one unit. This graph (called sample path), could be obtained from observation of a real station, but could also be artificially constructed. Such artificial construction and the analysis of the resulting sample path (or more sample paths in more complex cases) consist of the simulation.

Types of simulations: Discrete event. The above sample path consisted of only horizontal and vertical lines, as car arrivals and departures occurred at distinct points of time, what we refer to as events. Between two consecutive events, nothing happens - the graph is horizontal. If the number of possible events is finite, we call the simulation "discrete event."

In some systems the state changes all the time, not just at the time of some discrete events. For example, the water level in a reservoir with given in and outflows may change all the time. In such cases "continuous simulation" is more appropriate, although discrete event simulation can serve as an approximation.

Discrete event systems (DES) are dynamic systems which evolve in time by the occurrence of events at possibly irregular time intervals. Examples of DES include traffic systems, flexible manufacturing systems, computer-communications systems, production lines, coherent lifetime systems, and flow networks. Most of these systems can be modeled in terms of discrete events whose occurrence causes the system to change from one state to another. In designing, analyzing and operating such complex systems, one is interested not only in performance evaluation but also in sensitivity analysis and optimization.

System Dynamics and Discrete Event Simulation: The modeling techniques used by system dynamics and discrete event simulations are often different at two levels: The modeler way of representing systems might be different; the underlying simulators' algorithms are also different. Each technique is well tuned to the purpose it is intended. However, one may use a discrete event approach to do system dynamics and vice versa.

Traditionally, the most important distinction is the purpose of the modeling. The discrete event approach is to find, e.g., how many resources the decision maker needs such as how many trucks, and how to arrange the resources to avoid bottlenecks, i.e., excessive of waiting lines, waiting times, or inventories. While the system dynamics approach is to prescribe for the decision making to, e.g., timely respond to any changes, and how to change the physical structure, e.g., physical shipping delay time, so that inventories, sales, production, etc.

System dynamics is the rigorous study of problems in system behavior using the principles of feedback, dynamics and simulation. In more words system dynamics is characterized by:

• It allows searching for useful solutions to real problems, especially in social systems, e.g., businesses, schools, governments, and the environment.
• Using computer simulation models to understand and improve such systems.
• It helps basing the simulation models on mental models, qualitative knowledge and numerical information.
• Using methods and insights from feedback control engineering and other scientific disciplines to assess and improve the quality of models.
• Seeking improved ways to translate scientific results into achieved implemented improvement.
• Systems dynamics approach looks at systems at a very high level so is more suited to strategic analysis. Discrete event approach may look at subsystems for a detailed analysis and is more suited, e.g., to process re-engineering problems.
• Systems dynamics is indicative, i.e., helps us understand the direction and magnitude of effects (i.e., where in the system do we need to make the changes), whereas discrete event approach is predictive (i.e., how many resources do we need to achieve a certain goal of throughout).
• Systems dynamics analysis is continuous in time and it uses mostly deterministic analysis, whereas discrete event process deals with analysis in a specific time horizon and uses stochastic analysis.

Some interesting and useful areas of system dynamics modeling approach are:

Short-term and long term forecasting of agricultural produce with special reference to field crops and perennial fruits such as grapes, which have significant processing sectors of different proportions of total output where both demand and supply side perspectives are being considered.

Long term relationship between the financial statements of balance sheet, income statement and cash flow statement balanced against scenarios of the stock market's need to seek a stable/growing share price combined with a satisfactory dividend and related return on shareholder funds policy. Managerial applications include the development and evaluation of short-term and long-term strategic plans, budget analysis and assessment, business audits and benchmarking.

A modeler must consider both as complementary tools to each other. Systems dynamic is to study at the high level problem and identify areas which need more detailed analysis. Then, use discrete event modeling tools to analyze (and predict) the specific areas of interest.

What Is Social Simulation? Social scientists have always constructed models of social phenomena. Simulation is an important method for modeling social and economic processes. In particular, it provides a "middle way" between the richness of discursive theorizing and rigorous but restrictive mathematical models. There are different types of computer simulation and their application to social scientific problems.

Faster hardware and improved software have made building complex simulations easier. Computer simulation methods can be effective for the development of theories as well as for prediction. For example, macro-economic models have been used to simulate future changes in the economy; and simulations have been used in psychology to study cognitive mechanisms.

The WinQsb Queuing Analysis (QA) and Simulation Module

This program solves the performance of queuing systems. The queuing system has major elements including a customer population, a queue, and single or multiple servers (channels). Customer population can be limited or unlimited (infinity) with a specified arrival pattern (distribution); queue can be limited or unlimited length; and multiple servers are assumed to be identical with a specified service time distribution. Queuing system is evaluated according to popular measures such as average number of customers in the system, average number of customers in the queue, average number of customers in the queue for a busy system, average time customer spends in the system, average time customer spends in the queue, average time customer spends in the queue for a busy system, the probability that all servers are idle, the probability an arriving customer waits, average number of customers being balked per unit time, total cost of busy server per unit time, total cost of idle server per unit time, total cost of customer waiting per unit time, total cost of customer being served per unit time, total cost of customer being balked per unit time, total queue space cost per unit time, and total system cost per unit time.

Two methods are included to evaluate M/M/1 each queuing situation: close form formula, and simulation. The idea is that if no close form is available for a particular queuing problem, you may specify simulation to solve it.

Specific capabilities of QA include:

• Queuing performance analysis for M/M/1
• Sensitivity analysis for system parameters
• Capacity analysis for queuing and service capacity
• Simulation - alternative for performance evaluation
• Showing queuing performance and cost analysis

Queuing Systems: An OverView

Modern Simulation: An OverView

PowerPoint Presentations:

Queuing Systems

System Simulation

Assignments:

Read sections 9.1, 9.2, 9.3, 9.4 from Ch. 9 and sections 10.1, 10.2, 10.6, and 10.8 from Ch. 10, and the course lecture notes. Do problem 9.8 on page 544 by hand and WinQSB QA Module both analytical and simulation (for the cost parameters in QA, set them all at zero level, in order to compare the three different methodologies to understand their scopes and limitations: hand computation, computer, and simulation). Do the same for the homework problem in the Lecture Notes.
Notice that in this module letter M stands for unlimited capacity.