Queue is a common phenomenon. It occurs in all aspects of life. Queue involves waiting in line. We wait in line in our cars in traffic jams or at toll booths; we wait on hold for an operator to pick up our telephone calls; we wait in line at supermarkets to check out; we wait in line at fast-food restaurants; and we wait in line at banks and post offices. Customers do not, in generally, like these situations, and the managers of the establishments at which they wait also do not like it since it can lead to loss of business through customer dissatisfaction. Why then do we have waiting-in-line?
Gross et al.  provides an answer to the question. According to him, demands for services are usually more than facilities available for service delivery. This is due to many factors. Some of the factors are shortage of available servers, inability of a business to provide the level of service necessary to prevent waiting-in-line, limitation of space for service facilities and poor arrangement of servers and number of stages a customer would have to pass through before he/she complete service in the system may be another factors.
1.1. Multistage Queue System/Network
Multistage queue system is a queue in which customers are served at more than one station, arranged in a network structure. It is a collection of nodes connected by a set of paths. In a queue network, a group of servers operating from the same facility is identified as a node or a station. Examples of multi stage queues are found in Computer programming, communication, banks and manufacturing systems. In a multi stage queue network, customers demand service from more than one server. Queue networks better represents the real world situation than a single system. A multi stage network is represented diagrammatically as shown in Figure 1.
1.2. Characteristics of a Queue System
Queue processes are describe by six basic characteristics, which provide adequate representation of the queue system. The characteristics are 1) arrival pattern of customers, 2) service pattern of servers, 3) queue discipline, 4) system capacity, 5) number of service channels, and 6) number of service stages  .
Sundarapandian  gave the followings as the basic characteristics of a queue system. 1) the input or arrival pattern 2) the service mechanism 3) the queue discipline and 4) the system capacity. Nevertheless, these two researchers are talking about the same thing. Gross et al.  provides an excellent explanation of
Figure 1. Multistage queue network with n stations.
these basic characteristics.
1.3. Performance Measures of a Queue System
In this work we study a multistage queue system with a certain number of independent parallel servers and multiple queues at all or some of the stages. i.e. multiple waiting lines with independent parallel servers in series. This research work reviews the application of queue theory in analyzing performance measures of this type of system and develop discrete-event simulation of customers’ flows in the system purposely to carry out what-if-scenario analysis to improve efficiency of the system.
There are various performance measures of a multistage queue system. The ones we are interested in are the total expected number of customers in the system, total expected waiting time of an arbitrary customer in the queues formed at all the stages and the total expected waiting time or lead time (cycle time) that an arbitrary customer would spend in the system.
The main aim of this study is to analyze the customer-service situation in a multistage queue system.. The problem arose in a restaurant in the city of Ibadan, south-western Nigeria that serves three classes of local delicacies during lunch/ dinner services. Because of limited space and large customer pool, congestions frequently occur in the restaurant. A multistage queue model was designed for the restaurant. The three-stage queue model has 3 service points in stage 1 and single service point in each of the remaining two stages. Figure 2 shows the diagrammatic illustration of the system.
The multistage queue system consists of various stations through which a customer requiring service from such system would have to pass. This contains networks of queues which can be described as a group of nodes (say, k of them) that is we have k number of nodes, where each node represents a service facility
Figure 2. Diagrammatic illustration of the three-stage queue model for the restaurant.
of some kind with servers at node . In the most general cases, customers may arrive from outside the system at any node and may depart from the system from any node. Thus customers may enter the system at some node, traverse from node to node in the system, and depart from some node. Not all customers necessarily enter and leave at the same nodes, or take the same path once they entered the system. Customers may return to nodes previously visited, skip some nodes entirely, and even choose to remain in the system forever  .
A multistage queue system or queues in series as described in  are open networks where
since the nodes can be viewed as forming a series system with flow always in a single direction from node to node. This is supported by a remarkable theorem propounded by Jackson  that if 1) inter-arrival times for a series queue system are exponential with rate γ 2) service times for each stage j server are exponential and 3) each stage has an infinite-capacity waiting room, then inter-arrival times to each stage of the queue system are exponential with rate γ, the arrival rate of each customer from node to node.
2.1. Operating Parameters and Notations
The following system operating parameters and notations were used in this research work.
N = total number of customers in the system.
β = mean arrival rate at a single-channel, single server queue.
𝜏 = mean service rate of a single channel, single server queue.
𝜌 = system intensity or load, utilization factor.
P0 = steady-state probability of an idle server.
Pn = steady-state probability of exactly n customers in the system.
βi = mean arrival rate of customers at the ith queue of the first stage.
γj = effective mean or expected arrival rate of customers at the jth stage.
πi = probability that an arbitrary customer joins the ith queue at the first stage.
τi = mean service rate of the ith queue server at the first stage.
αj = mean service rate of the jth stage server.
ρj = system utilization factor of the jth stage server.
v = total number of customers in the first stage of the queue system.
ωi = system utilization factor of the ith queue server at the first stage.
= transition probability of a customer after completing service at the (j − 1)th stage, proceeding to the jth stage.
T = waiting time of a customer in the multistage queue system.
Tq = total waiting time of a customer in queues formed at different stages.
Tqi = waiting time of a customer in the ith queue of the first stage.
Tqj = waiting time of a customer in queue at the jth stage.
Wq = expected total waiting time of customers in queues formed at different stages.
Wqi = average or expected waiting time of a customer in the ith queue at the first stage.
Wqj = average or expected waiting time of a customer at the jth stage.
Ws = expected waiting time of a customer in the multistage queueing system.
Pc = probability that there are exactly C customers at 2-k stages.
Pv = probability that there are exactly V customers at the first stage.
2.2. The Multi-Stage Queue Model
We assume there are k stages in the queue model and stage 1 has h parallel single-server queues which are assumed to be independent. That is, they offer different services. It is also assumed that there is no balking, reneging or jockeying in the system; the queue follows a M/M/1 queue system; the system is a feed-forward queue network and bypassing is not allowed. Let the arrival rate at the queue be and the service rate be . Suppose the probability that an arriving customer joins queue i is . We want to determine the effective rate of arrival and service in the first stage.
Let = expected customer arrival rate into stage 1. Then
We estimate using , ,
The general traffic intensity for stage one is given as .
The arrival rate to stage 2 is given by . This holds since the system is a feed-forward network and bypassing is not allowed. Recursively,
The joint equilibrium distribution of the number of customers in the system is
The total expected number of customers in the system is
The total expected waiting time of an arbitrary customer in the queues formed at all stages (Wq) is
The total expected waiting time of an arbitrary customer in the system (Ws) is derived as
For details of the derivations of these measures go to Appendix.
Simulation is a powerful tool for the analysis of new system designs, retrofits to existing systems and proposed changes to operating rules. Conducting a valid simulation is both an art and a science  .
Stewart  defines simulation as imitation of real-world scenario systems. The system might be manufacturing system, communication system, health-care system, restaurant system etc. There are many types and kinds of simulation namely: Monte Carlo-type simulation, discrete-event simulation to mention but few. In this research work, we limit ourselves to discrete, stochastic process oriented simulation i.e. a discrete-event simulation.
Simulation models are abstractions of a real-world, or proposed real-world, system. In other words, the models do not contain every aspect and detail of the system that they are attempting to imitate  .
The majority of simulation models could be described as being visual interactive simulations (VIS). This was a concept first introduced in  . The idea is that the model provides a visual display showing an animation of the model as it runs.
We use SIMUL8, a software package fortified with dynamic, powerful Graphical User Interface (GUI) to carry out a visual interactive discrete-event simulation of customers flow in the multistage queue system. The what-if scenario analysis to compare a number of system alternatives was also performed. It allows for the identification of problems, bottlenecks and design shortfalls before building or modifying a system.
3. Results and Discussion
Data used for the analysis of the model were collected from Iyaduuni Restaurant in the city of Ibadan Nigeria. The restaurant has about 25 tables and chairs for customers and more than 10 servers work on shift basis. At least 5 servers are on duty per shift. There are 4 to 5 waiters and waitresses whose jobs are to secure comfortable places for customers to seated and clean the tables when customers leave.
Data were collected on customer arrival time on each of the three starting queues in the first stage and the other queues in the second and third stages. The time service begins and time service ends in all the queues were also recorded. The queues are assumed to be infinite capacity and customers visit all the stages. Data were collected for 5 days. The average arrival rates of customers and average service rates, together with the utilization factors of servers are displayed in Table 1 and Table 2 respectively.
Total expected number of customers in the system is computed using (2.4) as
The total expected waiting time of an arbitrary customer for a complete service in the system who joined 1st, 2nd or 3rd queue at the first stage is obtained using (2.6) as Ws = (10.014 mins, 5.874 mins, 3.594 mins) respectively.
3.1. Simulation Runs
A simulation model was fitted to the system using the inter arrival times and the service times. Both are exponentially distributed. The basic model as displayed in Figure 3 was simulated for a time equivalent of 2 weeks of operation. The average or expected waiting time of customers at each node and average or expected lead-time were obtained and displayed in Table 3.
Based on a two-week simulation run of the restaurant system, the average time spent on the 1st queue at stage 1 for local delicacy 1 (Amala) by an arbitrary customer was 46 mins, likewise 3 mins on the 2nd queue for local delicacy 2 and 2
Table 1. Mean arrival rates of customers into the system and mean service rates at the queues.
Table 2. Utilization factors of servers.
Figure 3. A Visual Interactive display of the simulation for the basic model.
mins on the 3rd queue for local delicacy 3. There were lumps or bottlenecks on the 1st queue of the 1st stage and last stage (Paypoint) of the system.
3.2. Performing What-If Scenario Analysis
We noticed that there were bottlenecks at category I (local delicacy group 1) service point of stage I and Paypoint service point. We, therefore, perform a what-if scenario analysis to compare alternatives and reduce both time spent in queues and time spent in the system as a whole. This was done by shifting the server attending to customers interested in local delicacy 3, being the least utilized activity to join the one at Paypoint where a bottleneck was observed. The server at local delicacy 2 service centre was assigned to attend to those who would be interested in local delicacy 2. The model is shown in Figure 4.
The summary of the analysis is given Table 4.
The average time spent in the system has been reduced from 543.02 mins to 42.81 mins and the average queue time at Paypoint has also been reduced (Table 4). This is a great improvement but we observed that large queue still occurred at local delicacy 1 service point. Time spent here is still 46 min. To improve on this we used the configuration in Figure 5.
The average time spent by a customer in the system has reduced further to
Table 3. Result of the simulation for the basic model.
Figure 4. A visual interactive simulation run for the first what-if scenario analysis.
Table 4. Average queueing time the first what if scenario analysis.
Figure 5. A visual interactive simulation run for the second what if scenario analysis.
Table 5. Average queueing time after the second what-if scenario analysis.
13.47 mins (Table 5). Also local delicacy 1 now enjoys zero waiting time.
The analytical results show that at any point in time as many as 76 customers are present in the system. The utilization factors for the five queues in the system range from 70% to 97% (Table 2). The time spent by customers on queue, starting from stage 1 and ending in stage 3 from any of the three queues of stage 1 are respectively 10.4 minutes for local delicacy 1, 5.87 minutes for local delicacy 2 and 3.594 minutes for local delicacy 3. Customers requiring local delicacy 1
Figure 6. Decrease in average time spent in the system.
spend longer time on queue, reflecting the high demand for this meal. The utilization factor for this queue stands at 97% which is the highest.
The simulation study provides different operation scenarios to the management of the restaurant. Through the study the average time spent by customers in the system reduced from 543.02 minutes to as little as 13.47 minutes. This was achieved by considering different configurations of servers in the system without adding or subtracting any server. This means the reduction was achieved with no additional cost to management. Yet as customers spend less time in the restaurant more space are freed for addition customers to enjoy the services of the restaurant. This will translate to higher profit, improved customer satisfaction and customer goodwill. This improvement is illustrated in Figure 6.
This study has shown an application of queue theory in analyzing a multistage queue system consisting of M/M/1 (Poisson arrivals, exponential service times, a single server and infinite room capacity) queue models. Evaluation of performance measures for the queues were done after deriving expressions for the effectiveness measures. We assessed the level of service delivery through utilization factors of each M/M/1 queue. We found out that majority of the servers are well utilized as revealed by the values of the utilization factors obtained. Also, discrete-event simulation that gave close imitation of the system was developed and run to visualize and ascertain the feasible operations of the system. What-if scenario analysis was carried out in order to make vital and necessary suggestions for decision-making that will improve the efficiency of the system. The method led to significant reduction in the waiting time of an arbitrary customer in the system by resolving areas where bottlenecks were observed in the system. It akso provides an effective mean of managing the queues for maximum customer satisfaction at no additional cost.
Derivation of the Joint Equilibrium Distribution of the Number of Customers in the System
The joint probability of N customers in the system is given by
Let , for
Recall that , Therefore,
where is a normalizing constant.
From a single channel M/M/1 queue model,
Following this, Equation (3) becomes
Using normalizing condition,
Since each term of the denominator is a geometric series,
Substituting RHS of Equation (8) for in Equation (7)
The Total Expected Number of Customers in the System
This is done by decomposing the system into k individual stages. Let be the expected number of customers at the jth stage. Therefore,
Let be the expected number of customers at the first stage. Remember that
where is the probability of customers in the ith queue of the first stage.
Since each of the remaining stages has a single server with single queue, then
Therefore, the total expected number of customers in the system is
Total Expected Waiting Time of an Arbitrary Customer in the Queues Formed at All Stages (Wq)
Starting with the first stage having x independent M/M/1queues, we evaluate average or expected waiting time of an arbitrary customer in the ith queue of the first stage using the following relation:
= the waiting time of an arbitrary customer in the ith queue.
= the expected waiting time of an arbitrary customer in the ith queue.
= the waiting time of the yth customer in the ith queue.
= expected waiting time of yth customer in the ith queue.
= expected service time of the yth customer in the ith queue.
= expected interarrival time between the yth customer and (y + 1)st customer in the ith queue
We assume that there are Vi customers in the ith ( ) queue and that service has started before the arbitrary customer joins the ith queue.
Let be the queue length or expected number of customers in the ith queue of stage 1
Let and substitute in the summation.
Thus, it follows that
Hence we have,
By Little’s formulae,
Substituting these three terms into the relation, we get the expected waiting time of an arbitrary customer in the ith queue of the first stage as:
At the jth stage, the arbitrary customer is the nth customer in the jth queue ( ) station. Therefore, , the queue length of nth customer in the jth queue is given as:
where is the probability of nj customers at the jth stage.
It follows from equation * that
The total average waiting time of an arbitrary customer in the queues formed at all the stages is obtained as
The total expected waiting time of an arbitrary customer in the system (Ws)
We obtained equation for the expected lead-time E(T) (or cycle time) for an arbitrary customer, including waiting times and service times spent in the system from the first arrival until the final departure.
By Little’s formulae, the expected waiting time of a customer in a single channel system is given as: