Main menu
18 Dec 2017
While differential equations are the basis for modeling many types of physical and natural systems, many man-
Systems involving waiting lines, or queuing systems, can be seen everywhere in modern life. Let's consider one common example – the drive-
Figure -
In this system, cars (hungry customers) enter at the lower left and head to the order window where the driver places their order. After the order is placed, the car proceeds to the pickup window where the food is delivered. At that point the customer then leaves the system. This is the simplified view, which doesn't account for things like missing or wrong items, which would require the customer to park in the lot and go into the restaurant to try to correct the problem. Still, even with all of these simplifications, there is still quite a bit of complexity in the system, especially when we consider what happens when there is more than one customer in the system at once. Some issues that complicate the model are:
What happens if a lot of customers show up in quick succession at the order window? They have to form a line (queue) and have their orders taken one at a time, which increases the amount of time needed to get the food.
Once customers have their order taken, they have to line up at the pickup window. One complication with this queue, however, is that there is only a finite amount of lane between the order and pickup windows, and therefore only room for so many cars to be waiting. This is different from the case of the order window, which hypothetically could have cars backed up into the street and possibly nearby highways – giving the order window line an undefined and potentially very long wait.
If enough cars back up behind the pickup window, this could prevent cars from advancing from the order window and block the cars behind them – so even though he next customer in line is ready to place their order, and the order window clerk is ready to take it, this can't happen as the space in front of the window is blocked by the person who just placed their order.
And finally, the ability of the kitchen to process orders. If there is just one customer, the in-
With even the few the complications listed above, it becomes readily apparent that our Burger-
Building a Queuing System Model
The first step in trying to develop a simulation model is to break down the system into primitive elements with well-
Figure -
Queue Models
In its most basic form, the queue accepts abstract input tokens, which are held for some time, and then passed along downstream to the rest of the system. These abstract tokens may used in a simulation model to represent customers, orders, or a wide range of other entities which are to be processed by the system. Despite its function as a 'waiting area' there are quite a few possible variations, however, in how a queue manages incoming and previously queued entities. These variations in handling queued items are sometimes referred to as 'queueing discipline'. Some of the more commonly seen are:
Capacity
One of the key attributes of a queue is that of how many items can it hold -
Identity
Queues may treat incoming items as being anonymous, as having class distinction, or being uniquely identifiable. Anonymous items posses no information or properties which distinguish them from any other items. In the case items having class distinction, however, items in one class may be distinguished from those of another, but items of the same class are treated identically. Finally uniquely identifiable items may be thought of each having their own individual serial number stamped on them, and any item in the queue may be differentiated from any other item. The choice of what degree of item identification to support is highly dependent on the system being modeled. If one is modeling a process in which items really are identical – for example an assembly line making identical chocolate candies, then the anonymous approach might make sense. An example where supporting uniquely identifiable items would make sense would be in trying to model the patient intake and processing for a hospital emergency room. In this case, the tests and treatments to be applied to any given patient will vary dramatically based on the particular patient – a very different scenario than the candy assembly line.
Priority
In the case where queued items are anonymous, the notion of priority doesn't really mean anything; since all items are treated equally, which particular items enter and leave the queue doesn't matter. In contrast, consider the stereotypical case of the line in front of a trendy dance club. While people may line up in order of their arrival time, the bouncer decides who gets in based on his own criteria (and maybe how big a tip is presented) – and the exit order from the queue may be far different from the arrival order. For queuing systems in general, and not just of the night-
First-
Figure -
Last-
Figure -
Priority ordering: In a hypothetical ideal emergency room, the patients in the worst condition might be moved to the head of the line – someone with a gunshot wound will probably have a better chance of survival if they don't have to wait behind people with sprained ankles or the flu. Priority queues are also apparent at airport boarding areas – your boarding order does not depend when you show up, but rather on the 'boarding zone' number printed on your boarding pass. In a queue with a priority queuing discipline, items move to the exit faster or slower based on their identifying characteristics.
Figure -
Defection
While there are a wide range of possible additional behaviors a queue can support, one relatively common one is defection. If an item (customer) gets tired of waiting, the queue may allow them to exit and go somewhere else. In the case of the Burger-
Figure -
Queue States
Because is a dynamic model, in the sense that it has persistent memory over time, at any point in time a queue can be completely described in terms of its state. The state of a queue is simply its contents and their ordering, subject to any priority rules in effect. In addition to the detailed description of its contents, it also makes sense in some simulation models to define certain derived meta-
Empty – the condition in which the queue contains zero items. When a queue is empty, it can't provide exiting items to any downstream system elements.
Full – the condition in which the queue has reached its capacity. When a queue is full, it can't accept entering items from upstream system elements. Note that in the case where a queue has infinite capacity, it can never become full.
Partial – the condition where the queue is neither empty nor full. A queue which is partially full can both accept new items from upstream sources and provide exit items to downstream system elements.
Figure -
Server Models:
Servers are the other key element in queuing model systems. A server performs the following key operations:
1) Accepts or 'takes' an item from an upstream queue . It can only do this is an item is available – erg. The upstream queue is not 'empty'.
2) Spends some time 'processing' this item.
3) Sends the 'finished' item downstream to next queue or other precessing element. The server can only perform this operation if the downstream element can accept the item – eg The downstream queue is not 'full'.
4) Repeats from step 1.
In the most basic case, the above-
Figure -
In addition to the baseline behavior described above, there are a lot of possible variations on the basic server theme.
Processing time
The amount of time required by a server to process an item can be defined in many ways. Perhaps the most simple is when a constant processing time is assumed. In this case the server takes the same amount of time to process any given item regardless of the item type. While this may not be a bad assumption in an assembly line, it can be a pretty bad one in many other systems. For example, in the Burger-
Setup Time
There are many situations, particularly in manufacturing environments, where setup time between items is important. Setup time can be thought of as the amount of time required for a server to shift between performing one type of processing operation and a second processing operation. Setup time is not, however, needed between performing the same operation. Consider the case of a drill press at a machine shop. A drill press is used to drill holes in objects. To use one you have to install a drill bit of the desired size and clamp a holding fixture down to its work table to position the workpieces you want holes drilled in. Consider the case where you have buckets containing two types of items 'A' and 'B' which both need different sized holes and require different holding fixtures. If you set up the drill press for your 'A' type parts, drill them all, and then set up the press for the 'B' type parts, and drill them all, the work is going to go a lot faster than alternately drilling 'A' and 'B' parts and having repeat setups over and over. In many real-
Figure -
Item Transformation
Since it is possible to give items some degree of identity in a simulation model, one possible function of a server is identity transformation. At the Burger-
Figure -
Merging and Routing
A server can also perform merging and routing operations. This becomes important if the server has the choice of selecting items from a number of input queues (merging) or selecting which destination queue to send an item. There are a wide variety of possible protocols, of which some of the more simple are:
Random – the server selects a random queue to take or send the item to
Round-
Priority – Certain queues are used with a higher priority than others, with lower priority queues only used when the higher priority ones are empty or full.
Item-
Servers may merge several item streams for several upstream queues
Assembly and Disassembly Operations.
It is also possible for a server to assemble or disassemble items in the course of its processing. In a typical assembly operation, a server may take item type 'A' from one input queue, and item 'B' from another input queue, and produce an item 'C' which is sent to its output queue. A simple and concrete example of an assembly operation can be seen if we consider the kitchen at Burger-
Servers may also disassemble single items into multiple ones. Although this may not be a very common operation to perform on physical objects, it may be extremely useful when handling abstract items. For example, the order window can be considered as a server that 'disassembles' incoming customers into two separate items: (1) a customer who's order has been taken and (2) their order. The customer and the order are then routed respectively into the pickup queue and the kitchen queue.
One notable characteristic of an assembly operation is that the server needs all component items to begin its processing. This can make for more complex starving/blocking behavior. For example, if one of the queues feeding an assembly server is empty, and another queue feeding a different part is full, the empty queue not only starves the server, but because both pieces are needed it actively prevents the other queue from passing a piece along, and can block an upstream server. Similar types of behavior can also be seen in disassembly operations where a full output queue can effectively cause servers downstream from the disassembly operation to become starved.
Figure -
Next Installment -