Chapter 1

Queueing Theory : An
Introduction

5
 6

1.1 Introduction

Queue or waiting line is a social phenomena common in any modern society, when the

available facilities are not sufficient to meet the immediate needs of the customers.

That is, a queue is a particular kind of collection in which the entities in the collection

are kept in order and the principal operation on the collection are the addition of the

entities to the rear terminal position and the removal of the entities from the front

terminal position. This is equivalent to the requirement that once an element is added,

all elements that were added before have to be removed before the new element can

be invoked. Queues provide services in computer science, transport and operations

research, where various entities such as data,object,persons or events are stored and

held to be processed later. In these contexts, the queue performs the function of

a buffer. The units in the queue, who demand service at the service center and

wait if the service is not prompt is called customers. The mechanism arranged to

provide service to the customers at the service center is called server. That is, queue

represents a certain number of customers waiting for service. If a queue is finite,

it can only hold a limited number of customers. Most queueing models assume an

infinite queue, even though this is almost certainly not strictly true in the majority

of applications of queueing theory. This assumption is made because it makes the

modeling process simpler. Also, if the maximum queue size is significantly larger than

the likely number of customers at any one time, then to all intents and purposes it is

infinite in size. The amount of time which is a customer waits in the queue for service

is called queueing time.

There are three main concepts in queueing theory, which are queue (waiting line),

customer and server. The queueing theory is the probabilistic study of waiting lines.
 7

Although it does not solve all types of waiting line problems,it provides useful and

vital informations by forcasting or predicting various characteristics and parameters

of the particular waiting line under study. Since the predictions about the waiting

times, the no. of waiting at any time, the time for which the server/servers remain

busy etc. rely heavily on the basic concept of stochastic processes, it can very well

be taken as an application of stochastic processes. Also, queueing theory is generally

considered as a branch of operational research became the resources needed to provide

service. Then queueing theory is an application of stochastic processes in operations

research.

Erlang, Agner Krarup (1909,1917), an engineer at Copenhagen telephone exchange

started to work on applying the theory of probabilities to problems of telephone traf-

fic. It is interesting to note here that only after the world war II, it was realized

that the queueing theory has widespread applications in various fields, such as indus-

trial problems (production, scheduling and maintenance), congestions in road traffic,

scheduling of air traffic at the airport, waiting in a hospital outpatient department,

inventory control, machines waiting to be serviced by repairmen, physical processes

(operation of a set of dams), epidemic process in biology, intelligent transportation

systems, call centers, networks, telecommunications terminals, advanced telecommu-

nication system etc. Since queueing theory is applied in different fields, also the

terms jobs and tasks are often used instead customers and service center is often

named processor or machine.

1.2 Queueing System

Queueing theory deals with the analysis of a queueing system.Gross and Harris (1974)

described the queueing system as customers arriving for service,waiting for service if

it is not immediate and if having waited for service, leaving the system after be-

ing served. There are several everyday examples that can be described as queueing

system, such as bank teller service, computer systems, manufacturing systems, main-

tenance systems, communication systems and so on. An accurate representation of a

queueing system require a detailed characterization of the underlying processes. The

following are the six basis characteristics of a queueing system.

1. Arrival pattern of customers : The arrival process consists of describing how

customers arrive to the system. The system may have either a limited or an unlimited

capacity for holding units. The source from which the units come may be finite or

infinite. A unit may arrive either singly or in a group (bulk arrival). The interval

between two consecutive arrival is called the inter arrival time or interval. The arrival

pattern of a system is measured in terms of the average number of arrivals per unit

time (mean arrival rate) or by the average time between successive arrivals (mean

inter-arrival time). If the arrival pattern is deterministic, then it is fully determined

by either the mean arrival rate or the mean inter-arrival time. On the other hand, if it

is probabilistic, then their mean values provide only measures of central tendency for

the arrival pattern, and further characterization is required in the form of the prob-

ability distribution associated with the random process. If the arrival pattern does

not change with time, then it is called a stationary arrival pattern, otherwise, it is

called non-stationary (transient). The commonly used input distributions are Poisson

distribution, Degenerate distribution (deterministic), Erlangian type with parameter

k(k=1,2,3...), Hyper exponential distribution and Phase type distribution.

Another factor to be considered regarding the arrival pattern is the reaction of the

customers in the queue. If the queue, is too long, a customer may decide not to enter

it upon arrival and in this situation he is said to have balked. On the other hand, a

customer may enter the queue, but after some time lose patience and decide to leave.

In this case, he is said to have reneged. In the event that there are more than one

queue, customers may switch from one to another, that is jockey for position. These

three situations are all examples of queues with impatient customers. If the arrival

pattern does not change with time, then it is called a stationary arrival pattern,

otherwise, it is called non-stationary.

2. Service pattern of servers : Much of the discussions concerning the arrival

pattern is appropriate in discussing service patterns. Service pattern can also be

described by the number of services per unit time (service rate) or by the time required

to service customer (service time). Service may also be in single or in batch, further

it can be stationary or non-stationary. One important difference between arrival

and service is that service rate or service time are conditioned on the fact that the

system is not empty, that is, if the system is empty, the server is idle. The servers

that become idle may leave the system for a random period of time called vacation.

These vacations may be utilized to perform additional work assigned to the servers.

The service rate may depend in the number of customers waiting for service. In this

situation, it is called state-dependent service. The problems of customer impatience

can be looked upon as ones of state-dependent arrivals.

3. Queue discipline : Queue discipline refers to the rule by which customers are

selected for service when a queue is formed. One of the most important and often
 10

practiced queue discipline is first in first out (FIFO). Some others in common usages

are last in first out (LIFO). Another queue discipline is service in random order (RSS).

In some cases, customers are given priorities up on entering the system, the ones

with higher priorities to be selected for service ahead of those with lower priorities,

regardless of their time of arrival to the system. There are two general situations

in priority discipline. In the first, which is called preemptive, a customer with the

highest priority is allowed to enter service immediately after suspending even the

service in progress to a customer with lower priority. In the non-preemptive case, the

highest priority customer goes to the head of the queue but cannot get into service

until the customer presently in service is completed.

4. System capacity : In some queueing process, there is a finite upper bound to the

queue size. In this situation, a customer is forced to balk if he arrives at a time when

queue size is at its limit. This is a simple case of balking, since it is known exactly

under what circumstance arriving customers must balk.

5. Service channels : The number of service channels refers to the number of

parallel service stations which can provide identical service facilities to the customers

simultaneously.

6. Stages of service : A service station may have several stages. That is, there may

exist a series of service stages through which each customer must progress prior to

leaving the system. They are called tandem queues.

1.3 Queueing processes

The analysis of queueing system with fixed (deterministic) inter-arrival and service

times does not present much difficulty. We shall be concerned with models or systems
 11

where one or both (inter-arrival and service times) are stochastic. Their analysis will

involve a stochastic description of the system and the related performance measures

as discussed below.

1. Distribution of the number of customers N(t) in the system or queue at time t.

2. Distribution of the waiting time in the queue or system,the time that an arrival

has to wait in the queue. If Wn denote the waiting time of the nth arrival, then of

interest is the distribution of Wn .

3. Distribution of the virtual waiting time W(t), the length of time an arrival has to

wait has he arrive at time t.

4. Distribution of the busy period.

It is clear that N (t), t ≥ 0, W (t), t ≥ 0 and Wn , n ≥ 0 are stochastic processes, the

first two being in continuous time and the third one in discrete time. It will be seen

that some of the queueing processes that can we would come across are Markovian

and some are Semi-Markovian. From some of the non-Markovian processes that arise,

Markov chains can extracted at suitable regeneration points and Semi-Markov pro-

cesses can be constructed there from. The theory of Markov chains and Semi-Markov

process thus plays an important role in the study of queueing processes. The problem

studied in queueing theory may be grouped as

1. Stochastic behavior of various r.v’s and evaluation of various performance mea-

sures.

2. Method of solution - exact, transform, algorithmic, asymptotic, numerical, approx-

imations etc.

3. Nature of solution - time dependent, limiting form etc.

4. Control and design of queues - comparison of behavior and performances under

various situations, as well as queue discipline, service rules strategies etc and

5. Optimization of specific objective functions involving performance measures, asso-

ciated cost functions etc.

1.4 Notations

The widely used notation to represent a queueing process was introduced by Kendall

(1953). According to him, a queueing process is described by the notation A/B/X/Y /Z,

where A is inter-arrival time distribution, B is the service time distribution, X is the

number of service channels, Y is the system capacity and Z is the queue discipline.

The commonly used inter-arrival time and service time distributions are

M - Poisson arrival and exponential service time distribution

D - Degenerate distribution (deterministic)

Ek - Erlangian type with parameter k (k=1,2,3...)

GI - General Independent

H - Hyper exponential distribution

P H - Phase type distribution.

The following are the definitions of certain terms connected with a queueing process

1. Queue length : The number of customers waiting in the queue.

2. System size : The number of customers waiting in the queue and the customers

in service.

3. Waiting time in the queue : The duration of time spent by a customer in the

queue before getting service.

4. Waiting time in the system : The time spent by a customer in the queue and

for service in the system before leaving.

5. Busy period : The time interval over which a server is continuously busy.

6. Idle period : The time interval during which the server is completely free.

1.5 Different Methods for the Analysis of a Queue-

The analysis of queueing models give light to the behavior and performance measures

of the queueing system such as expected queue length, average system size, average

waiting time, expected busy period etc. The transient and steady state probabil-

ity distributions have been used for finding the performance measures of a queueing

system. The solution of a queueing system depending on time is called transient

distribution. The steady state distribution is a balanced equilibrium solution, which

does not depend on time. An equilibrium state is the stable behavior of the system

attained after being in operation for sufficiently long time. That is, steady state distri-

bution is the limiting behavior of the queueing system. Transient results are, however,

more difficult to obtain, and not many such results are found in the literature. Morse

(1955) studied the M/M/1 queue and obtained the transient state probabilities of the

number in the system at time t. The problem was studied and a complete solution

was obtained in the 1950’s by several researchers using different methods. The steady

state behavior of the queueing system were primarily investigated by Erlang (1917)

and he obtain the steady state probabilities for M/M/1/∞. The main limitation

observed in the steady state distribution is that there may exist many stochastic pro-

cesses with the same stationary distribution. Whitt (1983) in the detailed study of

the queueing system GI/M/1, remarked the problem of using stationary distributions

alone for describing the stochastic behavior of a queue. Hence to see the stochastic
 14

nature of a queue, some transient behavior of the queueing system should also be

considered along with the stationary distribution. The method of Laplace transform

can be applied to obtain the transient distribution and the steady state probability

distribution (if exists) can be obtained by using the final value theorem on Laplace

transforms. The following are some of the methods for measuring the performances

of a queueing system.

1. Embedded Markov Chain Method : This is the widely used method in queue-

ing theory introduced by Kendall (1953). Under this method, a discrete time Markov

chain is extracted from a non-Markov process by using regeneration points due to

Palm (1943). The points of regenerations may be the service completion time, the

departure time of a customer, the arrival time of a customer etc. The transition prob-

ability matrix of the extracted markov chain can be used for finding the performance

measures of a queueing system.

2. The Supplementary Variable Method : The use of supplementary variable, as

a general technique, was introduced by Cox (1955). In fact, Kendall (1953) proposed

this concept by using the term ’augmentation’ instead of supplementary variable.

Cox (1955) analysed the M/G/1 queueing system using this technique. The method

is based on the treatment of the couplet (N(t),X(t)). Henderson (1972) considers the

couplet (N(t),Y(t)), where Y(t) is the remaining or residual service time of the cus-

tomer in service, if any. These methods involve inclusion of a supplementary variable

X(t) or Y(t).

3. Lindley’s Integral Equation Method : This method was introduced by Lind-

ley in 1952. In this method the customer arrival times are taken as the regeneration

points and considered the waiting time of the nth customer as the object of study.
 15

Other notable contributions and discussions on the integral equations can be seen in

Smith (1953), Prabhu (1965a), Gross and Harris (1974), Karlin and Tailor (1975),

Kleinrock (1975) etc.

4. The Method of Sample Path : The realization points of a stochastic pro-

cesses {X(t), t ∈ T } or the sequence of observations X(t) of a stochastic processes

{X(t), t ∈ T }, for each time point t ∈ T is generally known as sample path or trajec-

tory. The sample path may be defined for all t, by joining the path (t, xt ) by straight

line or the trajectory being so defined that it remains a constant except for jumps of

unit magnitude corresponding to those Xt which are equal to one. The graphical rep-

resentation of sample path shows movements of the outcome of the process or state

over time. By associating probability with the path, it is possible to estimate the

probability of events related to sample path. Thus the process related to the sample

path can be analyzed more effectively by using this technique. In queueing theory,

the sample path is a powerful method for the evaluation of the performance measures

and its relation ships. See sample path method by Stidham and Thaha (1995) for

more details.

5. The Matrix Analytic Method : Starting with the introduction of phase type

probability distributions, Marcel Neuts (1975) has developed an analysis technique

that extends and modifies the earlier transform method to multivariables and makes

it amenable for solution with the help of computers. See Neuts (1978,1981), Sengupta

(1989), and Ramaswami (1990,2001). The use of phase type distributions in the rep-

resentation of system elements and the matrix analytic method in their analysis has

significantly expanded the scope of queueing systems for which useable results can be

derived.
 16

1.6 History and Development of Queueing Theory

Queueing theory as a part of probability theory has been developed largely in the con-

text of telephone traffic engineering. In 1909 A.K.Erlang a Danish teletraffic engineer

published a paper called ”the theory of probabilities and telephone conversations”. In

the early 1920’s he developed the famous Erlang model to evaluate loss probabilities of

multi-channel point-to-point conversations. The Erlang model was extended to allow

for calculation in finite source input situations by Engset several years later leading to

the Engset model. In 1951 G.K.Kendall published his work about embedded Markov

Chains, which is the base for the calculation of queueing systems under fairly general

input conditions. He also defined a naming convention for queueing systems which

is still used. Nearly at the same time D.V.Lindely developed an equation allowing

for results of a queueing system under fairly general input and service conditions. In

1957 J.R.Jackson started the investigation of network queues thus leading to so called

queueing network models. With the appearance of computer and computer networks,

queueing systems and queueing networks have been identified as a powerful analysis

and design tool for various application.

The steady state solutions for queueing system were primarily investigated by Er-

lang (1917), where he obtained the steady state probabilities for a Markovian delay

model and a Markovian loss model. The investigation in the study of time depen-

dent solution of a queueing system began in 1930’s, however the credit for the first

transient solution goes to Bailey (1954b). He obtained time dependent solution for

an M/M/1 queueing system by using generating function to the partial differential

equations. Morse (1955) studies M/M/1 queue and obtained the transient state prob-

abilities of the queue size at different time point. Champernowne (1956) obtained the
 17

transient solution of M/M/1 queue by using combinatorial method. The transient

solution of M/M/1 queue using the method of difference equations have considered by

Conolly (1958) and Feller (1966). Pegden and Rosenshine (1982) and Hubbard et al

(1986) have studied M/M/1 queueing system with two dimensional state associated

with the number of arrivals and departures and obtained transient state solutions.

Cohen (1982) studied transient solution of the M/M/1 queue and obtained the re-

sult involving three integrals. Parthasarathi (1987) applied an alternative approach

and obtained transient solution of M/M/1 queue in terms of an integral and a fi-

nite series. Abate and Whitt (1987,1988) considered M/M/1 queue and studied its

transient behavior via Laplace transforms. The method of sample path is applied by

Bacceli and Messey (1989) to obtain the performance measure of an M/M/1 queueing

system. Mohanthy and Panni (1990) have used a discrete analogue of the M/M/1

queue and discussed its transient solutions. Conolly and Languris (1993) investigated

M/M/1 queue and obtained a formula for the transient state probabilities. Sharma

and Maneshwar (1993) considered the busy period of M/M/1 queueing systems With

infinite capacity and obtained performance measures. Sharma and Sharma (1993)

obtained an expression for the waiting time of a unit in an M/M/1 queue, where the

priority of a unit decrease with time. Sharma and Tarabia (2000) obtained transient

state probabilities of the queueing model M/M/1/N. Lalith A Kulkarni and San-gi

Li (1996) considered the transient behavior of queueing systems with correlated traf-

fic. Barbot and Sericola (2002) considered an infinite capacity buffer receiving fluid

at a rate depending on the states of an M/M/1 queue. Draief and Mairesse (2005)

analyzed the service times of customers in a stable M/M/1 queue in equilibrium de-

pending on their position in a busy period. Antunes et al. (2006) studied the impact
 18

of busy period of a M/M/1 queue of a small perturbation in the service rate. Kherani

(2006) considered an M/M/1 queue and obtained the distribution of sojourn times,

waiting time, busy period etc. Indra and Ruchi (2009) considered transient solution

of two-dimensional state M/G/1 queueing models with working vacations.

Multichannel (multiserver) queues constitute an important class of queueing pro-

cesses and have broad practical meaning. Examples of such systems may be found in

banks, telephone exchanges, hospital admission systems, seaports etc. Queueing sys-

tems with multiple channels have been studied by many researchers through various

methods. Disney (1962) analyzed two channel models with ordered entry having no

space for queue with same service rates and obtained steady state probabilities of the

waiting time distribution. Yao (1987) discussed the nature of the multi channel queue

with ordered entry. Mastsui and Fukuta (1997) obtained system size probabilities for

multi channel queue with ordered entry and heterogeneous server. Krishnamoorthi.B

(1963) considered on Poisson queue with two heterogeneous servers. G.S.Mokaddis,

C.H.Matta and M.M.El Genaidy (1998) considered on Poisson queue with three het-

erogeneous servers. The transient behavior of the multi server M/M/c queue has been

analyzed by Saaty (1960) and obtained its transient probability distribution. Jackson

and Henderson (1966) considered M/M/c queue and obtained transient probability

distribution by using Laplace transform and generating function. Chaudhary and

Templeton (1973) studied the multi server model M/M/c and derived the busy pe-

riod distribution. Koenigsberg (1980) considered M/M/N/N system (a multi server

with finite input source N) as an application problem to electronic and obtained sys-

tem probability distribution. Borthakur and Chaudhary (1999) discussed the steady

state behavior of an M/M/c queueing system with a general start up time under an
 19

N-policy. Margolious (2005) derived an integral equation for the transient probabil-

ities and expected number in the queue for the time dependent multi server Poisson

queue.

There are several remarkable contributions by various researchers in the field

of non-Markovian queueing systems. A queueing system in which the inter-arrival

time or service time or both does not posses the Markov property is known as non-

Markovian queueung system. Hence the Markov property cannot be applied directly

for the analysis of non-Markovian queueing models. The first paper on estimating

parameters in a non-Markovian system is by Goyal and Harris (1972), who used the

transition probabilities of the imbedded Markov chain to set up the likelihood func-

tion. Since then significant progress has occurred in adapting statistical procedures

to various systems. For instance, Basawa and Prabhu (1981,1988) considered the

problem of estimation of parameters in the queue GI/G/1; Rao et al.(1984) used a

sequential probability ratio technique for the control of M/Ek /1 and Ek /M/1; and

Armero (1994) used Bayesian techniques for inference in Markovian queues, to iden-

tify only a few. Medhi (2002) studied more general M/G/1 queue with a second

optional channel and obtained transient solution, busy period distribution and the

steady state Pollaczek-Khinchin formula. Kella et al.(2005) studied some time de-

pendent properties of symmetric M/G/1 queue.

1.6.1 Bulk Queues

A queueing system in which the arrivals or service or both occur in groups is known as

a bulk queueing system. In ordinary queueing problems, it is assumed that customers

arrive singly at a service facility. However, this assumption is violated in many real-

world queueing situations. Letters arriving at a post office, ships arriving at a port in
 20

convoy, people going to a theater, restaurant, and so on, are some of the examples of

queueing situations in which customers do not arrive singly but in bulk or in groups.

Also, the size of an arriving group may be a random variable or a fixed number.

Mathematically and also from practical point of view, the cases when the size of an

arriving group is a random variable, are more common, and also more difficult to

handle.

The study of bulk arrival queue may be said to have begun with Erlang’s solution of

the M/Ek /1 queue (Brockmeyer et al.1948). The Major contributions on bulk arrival

queues are made by many researchers. Sharada (1973) obtained the solution for a

queueing problem with batch arrivals and correlated departures. Indra and Sharada

(2004) obtained explicitly the probabilities of system with latest arrival run having

maximum effective length one. Madan et al.(2004) studied a single server queue with

batch arrivals and two types of heterogeneous service with different general service

time distributions. Schleyer and Furmans (2007) presented an analytical method to

calculate the waiting time distribution for the G/G/1 queueing system with batch

arrivals. Ahmed (2007) considered a multi-channel bi-level heterogeneous servers bulk

arrivals queueing system with Erlangian service time. Indra and Vijay (2010) analyzed

a two dimensional bulk arrival queueing model with exhaustive and non-exhaustive

service policy.

We now turn to queueing situations in which arrivals occur singly, but service is

in bulk. Bulk service queues have potential applications in loading and unloading

of cargoes at a sea port, in traffic signal systems, in computer networks where jobs

are processed in batches, manufacturing/production systems, in restaurants, cinema

halls and so on. Bailey (1954) introduced the concept of bulk service and the same
 21

was later studied by a number of researchers.

Sharada (1981) obtained results for a limited space correlated queueing problem

with departures in batches of variable size. Prem Chand (1988) obtained the explicit

time dependent probabilities of given number of arrivals and departures by a given

time of a FCFS single server queueing model in which arrivals are occurring singly

and are served in batches of variable sizes. Chaudhry and Templeton (1983) gave a

comprehensive treatment of single and multiserver systems with group arrivals and

individual service or individual arrivals and batch service. In 1964 Bhat analyzed a

single server bulk queues by the technique of imbedded Markov chain. After that,

bulk arrival and bulk departure queues were studied by Gupta and Goyal (1966).

Delbrouck (1970), Gaur (1973), Boathakur and Medhi (1974), Prabhu (1987) etc.

Suzuki (2007) studied approximate analysis for bulk arrival queueing system with

bulk service and the steady state probabilities of the system by using successive

approximation are evaluated.

1.6.2 Queueing Systems with Vacation

Queueing models with server vacation are useful for the systems in which a server

wants to utilize the idle time for different purposes. Application of server vacation

models can be found in manufacturing systems, designing of local area networks and

data communication system etc. Introducing vacation in the queueing models make

the model more realistic and flexible in studying real world queueing situation. Be-

cause of the wide application of vacation queueing models, considerable attention has

paid to analyze queueing system with vacation policies. Many researchers have ana-

lyzed vacation queueing problems for both Markovian and non-Markovian queueing

models. The Markovian models may be more appropriate in practice and may have
 22

certain advantages. Kella.O (1989) considered the threshold policy in the M/G/1

queue with server vacations. Chaudhary (1995) considered M/G/1 queueing system

with vacation and setup time. Boxma and Yechaiali (1997) introduced multiple types

of feedback gated vacations for M/G/1 queue. Lee et al.(2001) gave an analysis of

multiple class vacation queues with individual threshold.

The inclusion of vacation into bulk queueing models makes the model more feasible

to the practical situations. Some researchers have also paid their attention towards

this direction. Using matrix geometric method, Nadarajan and Subramaniyan (1984)

analyzed M/M (a,b) /1 queueing system with server’s vacation. Li and Zhu (1996) pro-

vided an explicit formula for the Laplace transform of the additional delay for M/G/1

queues with delayed vacations and exhaustive service discipline. Reddy and Anitha

(1998) determined the stationary distribution of the number of customers in queue

and waiting time distribution of an arriving customer for M/M (a,b) /1 queueing system

with multiple vacations and change over time.Reddy et al.(1998) presented analysis of

a bulk queue having the assumptions of N-policy, multiple vacations and setup times.

Chaudhary (2001) obtained the expected delay in services due to vacation period for

M/M/1 queueing system under N-policy and exponential setup time. Madhu Jain

and Poonam Singh (2005) considered the state dependent bulk service queue with

delayed vacation. P.Vijaya Laxmi, V Goswami and O.M.Yesuf (2010) considered a

finite buffer single vacation queue with accessible and non-accessible batch service.

1.6.3 Network Queueing System

A network of queues is a collection of service centers, which represent system re-

sources, and customers, which represent users or transactions. The term network of

queues describe the situation where the input for one queue is the output from one or
 23

more other queues. Queueing network models are widely used in diverse areas, such

as production and assembly lines, maintenance and repair operations, airport termi-

nals, communication networks, computer-sharing and multiprogramming systems and

health-care centers. A network queueing system constitute a central tool in modeling

and performance analysis of telecommunication and computer systems. A queueing

network is said to be open if customers enter from outside the network, circulate

among the service centers (or queues) for service, and depart from the network after

the service. That is, an open queueing network can receive customers from outside

the network. In the case of closed network a fixed number of customers circulated

indefinitely among the queues and no arrivals from outside of it. A network queue

is said to be mixed if some customers enter from outside the network and eventually

leave and if some customers always remain in the network.

The first article on queueing networks is by J.Jackson (1957). Mathematical

formulations for the analysis of queueing networks are due to Whittle (1967,1968)

and Kingman (1969), who treated them in the terminology of population processes.

Complex queueing network problems have been investigated extensively since the be-

ginning of 1970’s. Several survey papers and books summarize the major contribution

made in this area. These includes Basket (1973), Kelly (1979), Whitt (1983a,b) Dis-

ney and Kiessler (1987), Harrison and Nguyen (1990,1993) Ananthram et al.(1993)

and Dai (1998).

1.6.4 Discrete Time Queues

In discrete time queueing systems both the inter-arrival and service time distributions

are discrete. During the last two decades, discrete time queueing models have been ap-

plied to model digital communication systems and packet switches. Recently interests
 24

in the discrete time queues have increased due to their numerous applications in the

analysis of computer and communication systems such as asynchronous transfer mode

(ATM), multiplexers in the broad band integrated services digital net work (B-ISDN),

circuit- switched time-division multiple access (TDMA) systems, slotted carrier-sense

multiple access (CSMA), protocols and traffic concentrators in which the time axis is

divided in to slots. One of the reasons for this is that in discrete time queues t, the

slotted nature of telecommunication systems better than the continuous time counter-

parts, and hence they give more accurate performance measures of these systems. In

discrete time queues, the time axis is divided into fixed length time intervals referred

to as slots. Arrivals and services of customers can start or end at slot boundaries only,

so that the service time is an integer multiple of slots. These assumptions are suitable

for modeling ATM (Asynchronous Transfer Mode) networks. Discrete time queue-

ing process are better suited than continuous time models to evaluate performance

measures such as packet loss and packet delay in computer and telecommunication

networks, because of the clock driven operation of those systems. In real life, usually

we observe limited waiting space. So the study of finite buffer queueing models is

important. Bruneel.H. (1993) considered the performance of discrete time queueing

systems. Bruneel.H. and Kim.B. considered the discrete time models for communi-

cation systems including ATM. Guptha.U.C.and Goswami.V.(2002) considered the

performance analysis of finite buffer discrete time queue with bulk service. Lee.Y

(2001) considered the discrete time GeoX/G/1 queue with preemptive resume prior-

ity. Lee.Y and Lee.K.S (2003) considered the discrete time GeoX/G/1 queue with

preemptive repeat different priority. Lee.Y, Kim.H and Huh.J.D (2003) considered

GeoX/G/1 queue with non preemptive priority. Goswami.V and Samanta.S.K (2009)
 25

considered a discrete time single and batch service queue with accessibility to the

batches. C.Baburaj (2010) considered the performance measures of a discrete time

(a, c, d) policy bulk service queue.

1.6.5 Priority Queues

In many cases, it is desirable to give preferential treatment to certain classes of cus-

tomers for which the queue is ordered and the higher priority customers are served

first. 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 charac-

teristics, and FCFS rule is used with in each class to provide service. Treatment of

VIP’s in preference to other patients in a hospital is an example of priority service.

Priority queueing systems have been considered by many researchers in different con-

text. Jaiswal (1968) has given a detailed discussion on priority queues. Scharge and

Miller (1966) considered an M/G/1 queue with priority is assigned on the basis of

shortest processing time. Miller (1981) considered M/M/1 priority queues and ob-

tained steady state probabilities. Deng and Tan (2001) considered a single server

two-queue priority system with change over times and switching threshold. Harison

(2002) considered response time in M/M/1 queue with ageing priority and obtained

response time probability distribution via Laplace transform.

1.6.6 Retrial Queues

Queueing systems in which arriving customers who find all servers and waiting posi-

tions, if any, occupied, may retry for service after a period of time, are called retrial

queues or queues with repeated attempts. The most obvious example is provided by a

person who desires to make a phone call. If the line is busy, then he cannot queue up
 26

but tries again sometime later. Thus retrial queues are characterized by the following

feature: a customer arriving when all servers accessible for him are busy, leaves the

service area but after some random time repeats his demand. Retrial queues are a

type of network with re-servicing after blocking. Thus, this network contains two

nodes : the main node, where blocking is possible and a delay node for repeated

attempts. As for other networks with blocking, the investigation of such systems

presents great analytical difficulties. Neverthless, the main feature of the theory of

retrial queueing systems as an independent part of queueing theory are quite clearly

drawn. In particular, the nature of results obtained, methods of analysis and areas

of applications allow us to divide retrial queues into three large groups in a natural

way as single channel systems, multi channel fully available systems and structurally

complex systems. The standard queueing models do not take in to account the phe-

nomenon of retrials and therefore cannot be applied in solving a number of practically

important problems. Retrial queues have been introduced to solve these deficiency.

One of the earliest papers in retrial queues was On the Influence of Repeated Calls

in the Theory of Probabilities of Blocking by Kosten. In 1957, J.W.Kohan published

basic problems of telephone traffic theory and the influence of repeated calls in which

he considered the more general M/M/c retrial queue with impatient customers. In

1968, Keilson, Cozzolino and Young published the first result on M/G/1 retrial queue

using the method of supplementary variable. In 1990, Neuts and Rao suggested an

approximation with the help of the model where the retrial rate stays constant when

the number of customers in orbit exceeds some level. In 2004, Janos Roszic, Janos

Sztrik and Che-Soong Kim considered retrial queues in the performance modeling of

cellular mobile networks using mosel.

1.6.7 Design and Control of Queues

Queueing systems with control limit policy has many concrete applications and also

has the capability to narrate certain real life situations. There is increasing interest

in the subject of control of queueing systems. This is due to in large part to the wide

applicability of results in this area to the control of computers and communication

systems. There are many real life queueing situations in which jobs are served with

a control limit policy. For example, in some manufacturing systems it is possible to

process jobs manually or by a machine. Up to some control limit it may be profitable

to process the jobs manually one by one, and when the number of jobs exceeds that

control limit, processing in a batch by a machine may be cheaper. Here we assume

that some set up cost is needed to initiate a batch service and when a batch service is

started, no setup cost is required for the service of the successive batches and only the

service cost is required. So when a batch service is started the server may continue

to serve in batches, even when the queue size is less than the specified level but not

less than a secondary limit.

In a queueing system it is not possible to control the arrivals of customers to the

system, however, a control can be designed by regulating service mechanism. The

procedure of controlling a queueing system by control limit policy include the choice

of state dependent service rate, specification of limits to begin and stop services, suit-

able choice of vacation scheme to the servers and assigning cost structure to holding

customers in the queue and service etc. In the queueing system under N-policy the

server commences service only when the queue size reaches at least N(N ≥ 1). The

server serves the customer either one by one or in batches until the system becomes

empty or below a specified level (quorum). In each time, when the system becomes
 28

empty or below the quorum size, the server waits until the queue size become at

least N to commence the service. If the server continue the service until the system

become empty is called N-policy with exhaustive service. The first contribution to

the analysis of a queueing system with N-policy without vacation was due to yadin

and Naor (1963). Bhom (1992) analyzed an M/G/1 queue with N-policy and de-

rived transient distribution of the queue length. T-policy is another control policy,

according to which the service facility is turned off for a fixed period of time T, after

the service completion epoch of all customers present in the system. Heyman (1968)

considered an M/G/1 queueing system under T-policy. An M/M/1 queueing system

with control limit policies and exponential startup time is considered by Baker (1973).

In a queueing system with D-policy, after the service completion epoch of all the units

in the system, the server re-opens as and when the total accumulated work load ex-

ceed the critical level D. The queueing system under D-policy Was first studied by

Balachandran (1973). Sivazalin (1979) and Artilejo (2001,2002) have studied M/G/1

queueing system with D-policy. Lee and Beak (2005) considered queue length of the

queueing system with BMAP arrivals under D-policy.

An M/M/1 queue under (M,N) policy is considered by Bhom and Mohanthy

(1993), where the server begins service if the queue size is at least N and continue to

serve even when the queue size is less than M after a service completion epoch. Motir

and Ramy Khalid (2010) considered the random walk process in a bi-level (M,N)-

policy queue with multiple vacations. A single and batch service M/M/1 queue with

a control on the batch size was considered by C.Baburaj (1999). A controllable

bulk service queueing system under the policy (K,N,M) was considered by C.Baburaj

(2000). The single server bulk service rule introduced by Bailey (1954) is known as
 29

the usual bulk service rule, in which the server serves the customers in batches of size

not more than b, the capacity of the server. After a service completion epoch, if he

finds not more than b waiting, then he takes all of them in a batch for service and

the server is intermittently available. Neuts (1967) introduced a bulk service system,

where the server starts service only when at least a units in the system and serves

a maximum of b units at a time. If after a service completion epoch, the queue size

is less than a, the server waits till there are a units. This bulk service rule is called

general bulk service rule (GBSR). Borthakur (1971) considered the busy period of a

bulk queueing system with a general bulk service rule. Medhi and Borthakur (1972)

considered a two server Markovian queue with a general bulk service rule. Medhi

(1975) introduced the waiting time distribution in a Poisson queue with general bulk

service rule. Baburaj and Surendranath (2005) considered an M/M/1 bulk service

queue under the policy (a, c, d), where the server begins service only when the queue

size is at least a specified level c, and serves a maximum of d units in a batch. The

server continue to serve even when the queue size is less than the specified level c,

but not less than a secondary limit a (a ≤ c ≤ d), after a service completion epoch.

In many practical situations the arriving customers are considered for service with

current batch in service,with some limitation, for example, cinema hall, elevator etc.

That is, in the general service (a, b) rule, if a batch being served does not employ its

full capacity of service, late arrivals may join the ongoing service as long as the number

in that service batch is less than a pre-defined threshold d (a ≤ d < b). The service

time of the batch is not changed by inclusion of such arriving customers in course

of ongoing service. Such a batch is said to be an accessible batch (AB). However,

if the number in the service batch exceeds d, the batch becomes non-accessible for
 30

late arriving customers and such a batch is called non-accessible batch (NAB). This

has been considered by Kleinrock (1975). It may be noted that the accessible batch

service has more economic utilizations in providing better service to the queue. For

example in many shuttle transportation systems, we observe units being transported

according to accessibility rule with some limitations. Sivasami.R (1990) considered a

bulk service queue with accessible and non-accessible batches. Baburaj.C and T.M

Surendranath (2006) considered an (a, c, d) policy bulk service queue with accessible

and non-accessible batches. A discrete time single and batch service queues with

accessibility to the batches was considered by Goswami and Samantha (2009). A

finite buffer single vacation queue with accessible and non-accessible batch service

was considered by Vijayalaxmi, Goswami and Yesuf (2010).

1.7 An Overview of the Study

In this study we consider queueing models under different control limit policies. The

single server bulk service rule introduced by Bailey (1954) is known as the usual bulk

service rule. Neuts (1967)introduced the general bulk service rule (GBSR). Borthakur

(1971), Medhi (1975,1984,1994), Chaudhary and Templeton (1983) and many other

researchers studied similar models. Bhat (1964), Teghem (1986),Cohen (1969) etc.

have considered bulk queues with varying batch sizes. Baburaj and Surendranath

(2005) considered an M/M/1 bulk service queue under the policy (a, c, d), where the

server begins service only when the queue size is at least a specified level c, and serves

a maximum of d units in a batch. The server continue to serve even when the queue

size is less than the specified level c, but not less than a secondary limit a(a ≤ c ≤ d),

after a service completion epoch. Here we study the (a, c, d) policy queue under
 31

Bernoulli schedule, under the customer’s choice, with single and batch service in

discrete case, with state dependent service rates and with multiple vacations. Also

the performance measures of a controllable bulk service queueing system with two

servers are considered.

In chapter 2, we considered an (a, c, d) policy M/M/1 bulk service queue with

Bernoulli schedule. Here the server begins service only if the number of units in the

queue is at least c and serves a maximum of d units in a batch. If after a service

completion epoch, the queue size n is less than c but not less than a secondary limit

a (a ≤ c ≤ d), then with probability p, the server serves them altogether in a batch

and with probability 1 − p, the server becomes idle. The service time distribution

is assumed to be exponential with parameter µ and the arrival process is assumed

to be Poisson with parameter λ.The transient and steady state behavior is discussed

and obtained explicit expressions for the steady state probabilities, expected queue

length, expected busy period and expected waiting time in the queue.The optimality

problem is also discussed and obtained expressions for the optimal control limits a

and c.

An (a, c, d) policy bulk service queue with accessible batches under the customer’s

choice is considered in chapter 3, In this model the customers arrive according to

a poisson process with parameter λ. Here the server allows late arrivals to join the

ongoing service till the batch size is less than b (accessible batch) and the arriving unit

has a choice either to enter the accessible batch or to wait in the queue till the service

of the next batch begins. Here we assume that the arriving unit join the accessible

batch with probability p or with probability 1 − p he waits in the queue till the service

of the next batch begins. In this model the server continue to serve even when the
 32

queue size n is less than c but not less than a secondary limit a (a ≤ c ≤ b ≤ d),

after a service completion epoch. The service time distribution is assumed to be

exponential with parameter µ. In this chapter Section 2 provides the description of

the model. Section 3 presents the analysis of the model. The transient and steady

state behavior of the model is studied in sections 4. Explicit expressions for the

steady state distribution, expected queue length and expected busy period are given

in sections 5,6 and 7. In section 8 the method of determining the optimal control

limits a and c is discussed.

Chapter 4 deals with a state dependent M/M/1 single and batch service queue

under the policy (a, c, d). The arrival process is assumed to be Poisson with parameter

λ. Here the customers are served by a single server either one at a time or in batches

with different service rates depending on the number of units in the queue. In this

model if the number of units in the queue is less than a specified limit c, the server

serves the units manually according to FCFS rule and the service time distribution

is assumed to be exponential with parameter µ1 (Type I service). If n ≥ c, the server

serves a maximum of d units in a batch and the service time distribution is assumed

to be exponential with parameter µ2 (Type II service). If after a Type II service

completion epoch, the number of units in the queue is less than c but not less than a

secondary limit a, the server serves them altogether in a batch and the service time

distribution is assumed to be exponential with parameter µ3 , (a ≤ c ≤ d) (Type

III service). When n less than a, the server begins manual service. The transient

and steady state behavior of the model is discussed and explicit expressions for the

steady state probabilities, expected queue length and busy period are obtained. The

optimality problem is also discussed.

Chapter 5 explains the steady state probabilities, expected queue length, expected

busy period and optimality problem of a state dependent M/M/1 single and batch

service queue under the policy (a, c, d) with multiple vacations. Here the customers

are served by a single server either one at a time or in batches with different service

rates depending on the number of units in the queue and the arrival process is assumed

to be Poisson with parameter λ. In this model if the number of units in the queue is

less than a specified limit c,the server serves the units manually according to FCFS

rule and the service time distribution is assumed to be exponential with parameter

µ1 (Type I service). If n ≥ c, the server serves a maximum of d units in a batch and

the service time distribution is assumed to be exponential with parameter µ2 (Type

II service). If after a Type II service completion epoch, the number of units in the

queue is less than c but not less than a secondary limit a, the server serves them

altogether in a batch and the service time distribution is assumed to be exponential

with parameter µ3 , (a ≤ c ≤ d) (Type III service).When n less than a, the server

will go for a vacation which is assumed to be exponential with parameter β. After

a vacation, when he returns, if the queue length is less than c, he leaves for another

vacation and so on until he finds at least c customers in the queue.

A discrete time single and batch service queue under the policy (a, c, d) is discussed

in chapter 6. Here the customers are served by a single server. The inter-arrival

times are assumed to be independent and geometrically distributed. In this model

if the number of units in the queue is less than a specified limit c, the server serves

a single customer at a time and if the number of units in the queue exceeds the

specified limit c the server adopts batch service and serves a maximum of d units

in a batch. When a batch service is started, the server may continue to serve in
 34

batches even when the queue size is less than c, but not less than a secondary limit a

(a ≤ c ≤ d), after a service completion epoch. When the queue size is less than a, the

server begins manual service. The service times are also assumed to be independent

and geometrically distributed. Various characteristics of the queueing system are

presented in this Chapter.

Chapter 7 explains the transient and steady state behavior and some performance

measures of a controllable bulk service queueing system with accessible and non ac-

cessible batches. A controllable bulk service queueing system with two servers, where

the server I allows accessibility to the batches of ongoing service is considered is con-

sidered in this chapter. The arrival process is assumed to be Poisson and the service

rule is as follows: When the system size is less than or equal to the control limit b1 , the

server I is busy and he serves them altogether in a batch, incorporating accessibility

to the batches while the service is on progress and if the system size is more than b1 ,

then both the servers (server I and server II) are busy, where server I serves b1 units

in a batch and from the remaining server II serves a maximum of (b2 − b1 ), where

b2 > b1 units in a batch according to FCFS rule with out accessibility to the batches.

The service time distributions are assumed to be exponential.

Finally a concluding remarks is given in the last section.