In
order to model queuing systems, we first need to be a bit more precise about
what constitutes a queuing system. The three basic elements common to all
queuing systems are:
- Arrival
Process or patterns
- Service
process or patterns
- Queuing
discipline
1. Arrival Process or Patterns
Any
queuing system must work on something − customers, parts, patients, orders,
etc. We generally called them as entities or customers. Before entities
can be processed or subjected to waiting, they must first enter the system.
Depending on the environment, entities can arrive smoothly or in an
unpredictable fashion. They can arrive one at a time or in clumps (e.g., bus
loads or batches). They can arrive independently or according to some kind of
correlation.
A
special arrival process, which is highly useful for modeling purposes, is the Markov
arrival process. Both of these names refer to the situation where entities
arrive one at a time and the times between arrivals are exponential random
variables. This type of arrival process is memory less, which means that
the likelihood of an arrival within the next t minutes is the same no
matter how long it has been since the last arrival.
Examples
where this occurs are phone calls arriving at an exchange, customers arriving
at a fast food restaurant, hits on a web site, and many others.
2. Service Process or Patterns
Once
entities have entered the system they must be served. The physical meaning of
“service” depends on the system. Customers may go through the checkout process.
Parts may go through machining. Patients may go through medical treatment.
Orders may be filled. And so on. From a modeling standpoint, the operational
characteristics of service matter more than the physical characteristics.
Specifically, we care about whether service times are long or short, and
whether they are regular or highly variable. We care about whether entities are
processed in first-come-first-serve (FCFS) order or according to some kind of
priority rule. We care about whether entities are serviced by a single server
or by multiple servers working in parallel etc
Markov Service Process
A
special service process is the Markov service process, in which entities
are processed one at a time in FCFS order and service times are independent and
exponential. As with the case of Markov arrivals, a Markov service
process is memory less, which means that the expected time until an entity is
finished remains constant regardless of how long it has been in service.
For
example, in the Marcrohard example, a Markov service process would imply that the
additional time required to resolve a caller’s problem is 15 minutes, no matter
how long the technician has already spent talking to the customer. While this
may seem unlikely, it does occur when the distribution of service times looks
like the case shown in Figure 1. This depicts a case where the average service
time is 15 minutes, but many customers require calls much shorter than 15
minutes (e.g., to be reminded of a password or basic procedures) while a few
customers require significantly more than 15 minutes (e.g., to perform complex
diagnostics or problem resolution). Simply knowing how long a customer has been
in service doesn’t tell us enough about what kind of problem the customer has
to predict how much more time will be required.
3. Queuing Discipline:
The
third required component of a queuing system is a queue, in which entities wait
for service.
The
number of customer can wait in a line is called system capacity.
The
simplest case is an unlimited queue which can accommodate any number of
customers. It is called system with
unlimited capacity.
But
many systems (e.g., phone exchanges, web servers, call centers), have limits on
the number of entities that can be in queue at any given time.
Arrivals
that come when the queue is full are rejected (e.g., customers get a busy
signal when trying to dial into a call center). Even if the system doesn't have
a strict limit on the queue size,
The
logical ordering of customer in a waiting line is called Queuing discipline and
it determines which customer will be chosen for service. We may say that
queuing discipline is a rule to chose the customer for service from the waiting
line.
The
queuing discipline includes:
i. FIFO (First in
First out)
: According to this rule, Service is offered on the basis of arrival time of
customer. The customer who comes first will get the service first. So in other
word the customer who get the service next will be determine on the basis of
longest waiting time.
ii. Last in First
Out(LIFO):
It is usually abbreviated as LIFO, occurs when service is next offered to the
customer that arrived recently or which have waiting time least. In the crowded
train the passenger getting in or out from the train is an example of LIFO.
iii. Service in
Random order (SIRO):
it means that a random choice is made between all waiting customers at the time
service is offered. I.e a customer is picked up randomly form the waiting queue
for the service.
iv. Shortest
processing time First (SPT): it means that the customer with shortest service
time will be chosen first for the service. i.e. the shortest service time
customer will get the priority in the selection process.
v. Priority: a
special number is assigned to each customer in the waiting line and it is
called priority. Then according to this number, the customer is chosen for
service.
