Module 8. Queuing theory

Lesson 16

INTRODUCTION AND CLASSIFICATION OF QUEUES

16.1  Introduction

The study of waiting lines, called queuing theory is one of the oldest and most widely used Operations Research techniques.  Waiting lines are the most frequently encountered problem in our daily life. The queuing theory, also called the waiting line theory, owes its development to A. K. Erlang’s efforts to analyze telephone traffic congestion with a view to satisfying the randomly arising demand for the services of the Corpenhagen automatic telephone system, in the year 1909. The theory is applicable to situation where the ‘customers’ arrive at some ‘service stations’ for some service; wait (occasionally not); and then leave the system after getting the service.

A flow of customers from finite/ infinite population towards the services facility form a queue (waiting line) on account of lack of capability to serve them all at a time. The queues may consist of customers for buying milk and other milk products at a milk parlour, machines waiting to be repaired, trucks or vehicles waiting at the milk plant, patients in a hospital who need treatment and so on. In the absence of a perfect balance between the service facilities and the customers, waiting is required either of the services facilities or for the customer’s arrival. In general a queue is formed when either units requiring services-commonly referred as customers, wait for service or the service facilities, stand idle and wait for customers. The queuing models are basically relevant to service oriented organizations and suggest ways and means to improve the efficiency of the service. Queuing methodology indicates the optimal usage of existing manpower and other resources to improve the service. Waiting lines can’t be eliminated completely but suitable techniques can be used to reduce the waiting line of an object in the system.

16.2  Queuing System

The mechanism of a queuing process is very simple. Customers arrive at services counter are attended by one or more of the servers. As soon as a customer is served, he departs from the system. Thus a queuing system can be described as composed of customers arriving for service, waiting for service if it is not immediate, and if having wanted for service, leaving the system after being served.

16.3  Component of a Queuing System

A queuing system can be described by the following components:

16.3.1  Input process (or Arrival pattern)

This is considered with the pattern in which the customers arrive and join the system. An input source is characterized by

a) Size of the calling population.

b) Pattern of arrivals at the system.

c) Behaviour of the arrivals.

Customers requiring service are generated at different times by an input source, commonly known as population. The rate at which customers arrive at the service facility is determined by the arrival process.

16.3.1.1  Size of the calling population

The size represents the total number of potential customers who will require service. The source of customers can be either finite or infinite. It is considered infinite if the number of people being very large e.g. all people of a city or state (and others) could be the potential customers at a milk parlour. Whereas there are many situations in industrial conditions where we cannot consider the population to be infinite—it is finite. The customers may arrive for service individually or in groups. Single arrivals are illustrated by a customer visiting a milk parlour, students arriving at a library counter etc. On the other hand, families visiting restaurants, ships discharging cargo at a dock are examples of bulk or batch arrivals.

16.3.1.2  Pattern of arrivals at the system

Customers arrive in the system at a service facility according to some known schedule (for example one patient every 15 minutes or a candidate for interview every half hour) or else they arrive randomly. Arrivals are considered at random when they are independent of one another and their occurrence cannot be predicted exactly. The queuing models wherein customers’ arrival times are known with certainty are categorized as deterministic models and are easier to handle. On the other hand, a substantial majority of the queuing models are based on the premise that the customers enter the system stochastically, at random points in time. The arrival process (or pattern) of customers to the service system is classified into two categories: static and dynamic. These two are further classified based on the nature of arrival rate and the control that can be exercised on the arrival process.

In static arrival process, the control depends on the nature of arrival rate (random or constant). Random arrivals are either at a constant rate or varying with time. Thus to analyze the queuing system, it is necessary to describe the probability distribution of arrivals. From such distributions average time between successive arrivals, is obtained also called inter-arrival time (time between two consecutive arrivals), and the average arrival rate (i.e. number of customers arriving per unit of time at the service system).

The dynamic arrival process is controlled by both service facility and customers. The service facility adjusts its capacity to match changes in the demand intensity, by either varying the staffing levels at different timings of service, varying service charges (such as telephone call charges at different hours of the day or week) at different timings, or allowing entry with appointments. Frequently in queuing problems, the number of arrivals per unit of time can be estimated by a probability distribution known as the Poisson distribution, as it adequately supports many real world situations

16.3.2  Service Mechanism (or Service Pattern)

The service is provided by a service facility (or facilities). This may be a person (a bank teller, a barber, a machine (elevator, gasoline pump), or a space (airport runway, parking lot, hospital bed), to mention just a few. A service facility may include one person or several people operating as a team. There are two aspects of a service system

a) the configuration of the service system

b) the speed of the service.

16.3.2.1  Configuration of the service system

The customers’ entry into the service system depends upon the queue conditions. If at the time of customers’ arrival, the server is idle, then the customer is served immediately. Otherwise the customer is asked to join the queue, which can have several configurations. By configuration of the service system we mean how the service facilities exist. Service systems are usually classified in terms of their number of channels, or numbers of servers.

i) Single Server – Single Queue -- The models that involve one queue – one service station facility are called single server models where customer waits till the service point is ready to take him for servicing. Students arriving at a library counter are an example of a single server facility.

ii) Single Server – Several Queues – In this type of facility there are several queues and the customer may join any one of these but there is only one service channel.

iii) Several (Parallel) Servers – Single Queue – In this type of model there is more than one server and each server provides the same type of facility. The customers wait in a single queue until one of the service channels is ready to take them in for servicing.

iv) Several Servers – Several Queues – This type of model consists of several servers where each of the servers has a different queue. Different cash counters in an electricity office where the customers can make payment in respect of their electricity bills provide an example of this type of model. Different ticket issue encounters in a trade fair and different boarding pass encounters at an airport are also other possible examples of this type of model.

v) Service facilities in a series – In this, a customer enters the first station and gets a portion of service and then moves on to the next station, gets some service and then again moves on to the next station. …. and so on, and finally leaves the system, having received the complete service. For example in a milk plant packaging of milk pouches consist of boiling, pasteurization, cooling and packaging operations, each of which is performed by a single server in a series.

16.3.2.2  Speed of service

In a queuing system, the speed with which service is provided can be expressed in either of two ways—as service rate and as service time.  The service rate describes the number of customers serviced during a particular time period and the service time indicates the amount of time needed to service a customer. Service rates and times are reciprocal of each other and either of them is sufficient to indicate the capacity of the facility. Thus if a cashier can attend, on an average 5 customers in an hour, the service rate would be expressed as 5 customers/hour and service time would be equal to 12 minutes/customer. Generally, we consider the service time only. If these service times are known exactly, the problem can be handled easily. But, as generally happens, if these are different and not known with certainty, we have to consider the distribution of the service times in order to analyze the queuing system. Generally, the queuing models are based on the assumption that service times are exponentially distributed about some average service time.

16.3.3  Queue discipline

In the queue structure, the important thing to know is the queue discipline. The queue discipline is the rule determining the formation of queue, manner in which customers form the queue are selected for service. There are a number of ways in which customers in the queue are served. Some of these are:

16.3.3.1 Static queue disciplines

These are based on the individual customer's status in the queue. The most common queue disciplines are:

i) First-Come-First-Served (FCFS): If the customers are served in the order of their arrival, then this is known as the FCFS service discipline. For example, this type of queue discipline is observed at a milk parlour, railway station etc. FCFS is also known as First In First Out (FIFO).

ii) Last-Come-First-Served (LCFS): Sometimes, the customers are serviced in the reverse order of their entry so that the ones who join the last are served first and the system is referred to as LCFS. For example, in a big godown the items which come last are taken out first. Similarly, the people who join an elevator last are the first ones to leave it.

16.3.3.2 Dynamic queue disciplines

These are based on the individual customer attributes in the queue. Few of such disciplines are:

i) Service in Random Order (SIRO): Under this rule customers are selected for service at random, irrespective of their arrivals in the service system. In this, every customer in the queue is equally likely to be selected. The time of arrival of the customers is, therefore, of no relevance in such a case.

ii) Priority Service: Under this rule customers are grouped in priority classes on the basis of some attributes such as service time or urgency or according to some identifiable characteristic, and FCFS rule is used within each class to provide service. Treatment of VIPs in preference to other patients in a hospital is an example of priority service.

16.3.4  Customer’s behaviour

Another thing to consider in the queuing structure is the behaviour or attitude of the customers entering the queuing system. On this basis, the customers may be classified as being patient, or impatient. If a customer, on arriving at the service system stays in the system until served, no matter how much he has to wait for service is called a patient customer whereas the customer, who waits for a certain time in the queue and leaves the service system without getting service due to certain reasons such as a long queue in front of him is called an impatient customer. The customers generally behave in four ways

i) Balking: A customer may leave the queue because the queue is too long or the estimated waiting time is too long or waiting space is inadequate, for desired service and may decide to return for service at a later time. In queuing theory this is known as balking.

ii) Reneging: A customer, after joining the queue, waits for some time and leaves the service system due to intolerable delay or due to impatience.

iii) Jockeying: A customer who switches from one queue to another, hoping to receive service more quickly, is said to be jockeying.

iv) Priorities: In certain applications some customers are served before others regardless of their order of arrival. These customers have priority over others.