Discrete NT-policy single server queue with Markovian arrival process and phase type service

We consider a discrete time single server queueing system in which arrivals are governed by the Markovian arrival process. During a service period, all customers are served exhaustively. The server goes on vacation as soon as he/she completes service and the system is empty. Termination of the vacation period is controlled by two threshold parameters N and T, i.e. the server terminates his/her vacation as soon as the number waiting reaches N or the waiting time of the leading customer reaches T units. The steady state probability vector is shown to be of matrix-geometric type. The average queue length and the probability that the server is on vacation (or idle) are obtained. We also derive the steady state distribution of the waiting time at arrivals and show that the vacation period distribution is of phase type.     

M/M/∞ Queues in series with non-homogeneous inputs

This paper studies the transient behaviour of tandem queueing system consisting of an arbitrary number r of queues in series with infinite server service facility at each queue. Poisson arrivals with time dependent parameter and exponential service times have been assumed. Infinite server queues realistically describe those queues in which sufficient service capacity exist to prevent virtually any waiting by the customer present. The model is suitable for both phase type service as well services in series. Very elegant solutions have been obtained and it has been shown that if the queue sizes are initially independent and Poisson then they remain independent and Poisson for all t.     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Sojourn and waiting times in a single-server system with state-dependent mean service rate

A birth-death queueing system with asingle server, first-come first-served discipline, Poisson arrivals and state-dependent mean service rate is considered. The problem of determining the equilibrium densities of the sojourn and waiting times is formulated, in general. The particular case in which the mean service rate has one of two values, depending on whether or not the number of customers in the system exceeds a prescribed threshold, is then investigated. A generating function is derived for the Laplace transforms of the densities of the sojourn and waiting times, leading to explicit expressions for these quantities. Explicit expressions for the second moments of the sojourn and waiting times are also obtained.     

On the optimal control problem of a single-server queueing system

For a single-server queueing system (with a finite waiting room) with phase type arrivals and exponential service times, an optimal control for the service rate is derived. This generalizes the result of Scott and Jefferson for theM/M/1/1 queueing model.     

A model for setting services on auxiliary bus lines under congestion

In this paper, a mathematical programming model and a heuristically derived solution is described to assist with the efficient planning of services for a set of auxiliary bus lines (a bus-bridging system) during disruptions of metro and rapid transit lines. The model can be considered static and takes into account the average flows of passengers over a given period of time (i.e., the peak morning traffic hour). Auxiliary bus services must accommodate very high demand levels, and the model presented is able to take into account the operation of a bus-bridging system under congested conditions. A general analysis of the congestion in public transportation lines is presented, and the results are applied to the design of a bus-bridging system. A nonlinear integer mathematical programming model and a suitable approximation of this model are then formulated. This approximated model can be solved by a heuristic procedure that has been shown to be computationally viable. The output of the model is as follows: (a) the number of bus units to assign to each of the candidate lines of the bus-bridging system; (b) the routes to be followed by users passengers of each of the origin–destination pairs; (c) the operational conditions of the components of the bus-bridging system, including the passenger load of each of the line segments, the degree of saturation of the bus stops relative to their bus input flows, the bus service times at bus stops and the passenger waiting times at bus stops. The model is able to take into account bounds with regard to the maximum number of passengers waiting at bus stops and the space available at bus stops for the queueing of bus units. This paper demonstrates the applicability of the model with two realistic test cases: a railway corridor in Madrid and a metro line in Barcelona.     

Analysis of M/M/S queues with 1-limited service

In this paper, a multiple server queue, in which each server takes a vacation after serving one customer is studied. The arrival process is Poisson, service times are exponentially distributed and the duration of a vacation follows a phase distribution of order 2. Servers returning from vacation immediately take another vacation if no customers are waiting. A matrix geometric method is used to find the steady state joint probability of number of customers in the system and busy servers, and the mean and the second moment of number of customers and mean waiting time for this model. This queuing model can be used for the analysis of different kinds of communication networks, such as multi-slotted networks, multiple token rings, multiple server polling systems and mobile communication systems.     

Performance analysis of a batch service queue arising out of manufacturing system modelling

In this paper, we present an exact analysis of a queueing system with Poisson arrivals and batch service. The system has a finite numberS of waiting places and a batch service capacityb. A service period is initialized when a service starting thresholda of waiting customers has been reached. The model is denoted accordingly byM/G ^[a,b] /1–S. The motivation for this model arises from manufacturing environments with batch service work stations, e.g. in machines for computer components and chip productions. The method of embedded Markov chain is used for the analysis, whereby a representation of the general service time is obtained via a moment matching approach. Numerical results are shown in order to illustrate the dependency of performance measures on special sets of system parameters. Furthermore, attention is devoted to the issues of starting rules, where performance objectives like short waiting time, small blocking probability and minimal amount of work in progress are taken into account.     

A queueing model of a production system with two machines,one operator and priorities

This paper studies a priority queueing model of a production system in which one operator serves two types of units with overlapping service times. The two types of units arrive in independent Poisson processes. There are two machines in the system. Units of type 1 receive two consecutive types of services at machine #1: the handwork performed by the operator and the automatic machining without the operator. Units of type 2 receive only the handwork performed by the operator at machine #2. The operator attends the two machines according to a strict-priority discipline which always gives units of type 2 higher priority than units of type 1. At each machine the handwork times have a general distribution, and at machine #1 the machining times have an exponential distribution. The Laplace-Stieltjes transform of the queue-size distributions and the waiting time distributions for a stationary process are obtained.     

Insensitivity of multiclass systems with general dynamic preemptive resume queueing disciplines

We are concerned with the insensitivity of the stationary distributions of the system states inM/G/s/m queues with multiclass customers and with LIFO preemptive resume service disciplines. We introduce general entrance and exit rules into and from waiting positions, respectively, for the behaviour of waiting customers whose service is interrupted. These rules may, roughly speaking, depend on the number of customers in the system. It is shown that the stationary distribution of the system state is insensitive not only with respect to the service time distributions but also with respect to the general entrance and exit rules. As well as the insensitivity of the service scheme, our results are obtained for a special form of state and customer type dependent arrival and service rates. Some further results are concluded related to insensitivity like the formula for the conditional mean sojourn time and the property of transformation of a Poisson input into a Poisson output by the systems.     

A heuristic algorithm for the optimization of a retrial system with Bernoulli vacation

In this study, we consider an M/M/c retrial queue with Bernoulli vacation under a single vacation policy. When an arrived customer finds a free server, the customer receives the service immediately; otherwise the customer would enter into an orbit. After the server completes the service, the server may go on a vacation or become idle (waiting for the next arriving, retrying customer). The retrial system is analysed as a quasi-birth-and-death process. The sufficient and necessary condition of system equilibrium is obtained. The formulae for computing the rate matrix and stationary probabilities are derived. The explicit close forms for system performance measures are developed. A cost model is constructed to determine the optimal values of the number of servers, service rate, and vacation rate for minimizing the total expected cost per unit time. Numerical examples are given to demonstrate this optimization approach. The effects of various parameters in the cost model on system performance are investigated.     

An Iterative Algorithm for a Multiple Finite-source Queueing Model with Dynamic Priority Scheduling

A multiple finite source queueing model with a single server and dynamic, non-preemptive priority service discipline is studied in this paper. The times the customers spend at the corresponding sources are exponentially distributed. The service times of the customers can follow exponential, Erlang or hyperexponential probability density function. By using results published earlier and an extension of mean value analysis, an iterative algorithm was developed to obtain approximate values of the mean waiting times in queues for the priority classes. The mean number of waiting customers and the server utilization of each class are obtained using the result of this algorithm and Little's formula. The algorithm is preferable to the earlier method, because it does not increase in complexity as the number of customer classes increases.     

具有第二次多选择服务的M[X]/G/1排队系统

本文研究成批到达的具有第二次多选择服务的单服务员排队系统．顾客的到达形成一广义泊松过程，不同批的顾客按先到先服务的规则，而同一批的顾客按随机次序接受服务．两次服务的服务时间都是一般分布且相互独立．本文采用补充变量法，求得在瞬态和稳态情况下系统队长的概率母函数，然后又计算出顾客的平均队长和平均等待时间．     

Approximation of M/M/s/K retrial queue with nonpersistent customers

We consider the M/M/s/K retrial queues in which a customer who is blocked to enter the service facility may leave the system with a probability that depends on the number of attempts of the customer to enter the service facility. Approximation formulae for the distributions of the number of customers in service facility, waiting time in the system and the number of retrials made by a customer during its waiting time are derived. Approximation results are compared with the simulation.     

Optimal Operating Policy for a Random Additional Service Facility

This paper studies the steady state behaviour of a Markovian queue wherein there is a regular service facility serving the units one by one. A search for an additional service facility for the service of a group of units is started when the queue length increases to K (0 < K < L), where L is the maximum waiting space. The search is dropped when the queue length reduces to some tolerable fixed size L - N. The availability time of an additional service facility is a random variable. The model is directed towards finding the optimal operating policy (N,K) for a queueing system with a linear cost structure.     

Queueing models for appointment-driven systems

Many service systems are appointment-driven. In such systems, customers make an appointment and join an external queue (also referred to as the “waiting list”). At the appointed date, the customer arrives at the service facility, joins an internal queue and receives service during a service session. After service, the customer leaves the system. Important measures of interest include the size of the waiting list, the waiting time at the service facility and server overtime. These performance measures may support strategic decision making concerning server capacity (e.g. how often, when and for how long should a server be online). We develop a new model to assess these performance measures. The model is a combination of a vacation queueing system and an appointment system.     

Bilevel control of degraded machining system with warm standbys, setup and vacation

In this paper, we study (N, L) switch-over policy for machine repair model with warm standbys and two repairmen. The repairman (R₁) turns on for repair only when N-failed units are accumulated and starts repair after a set up time which is assumed to be exponentially distributed. As soon as the system becomes empty, the repairman (R₁) leaves for a vacation and returns back when he finds the number of failed units in the system greater than or equal to a threshold value N. Second repairman (R₂) turns on when there are L(>N) failed units in the system and goes for a vacation if there are less than L failed units. The life time and repair time of failed units are assumed to be exponentially distributed. The steady state queue size distribution is obtained by using recursive method. Expressions for the average number of failed units in the queue and the average waiting time are established.     

Markov-modulated queueing systems

Markov-modulated queueing systems are those in which the primary arrival and service mechanisms are influenced by changes of phase in a secondary Markov process. This influence may be external or internal, and may represent factors such as changes in environment or service interruptions. An important example of such a model arises in packet switching, where the calls generating packets are identified as customers being served at an infinite server system. In this paper we first survey a number of different models for Markov-modulated queueing systems. We then analyze a model in which the workload process and the secondary process together constitute a Markov compound Poisson process. We derive the properties of the waiting time, idle time and busy period, using techniques based on infinitesimal generators. This model was first investigated by G.J.K. Regterschot and J.H.A. de Smit using Wiener-Hopf techniques, their primary interest being the queue-length and waiting time.     

An approximation of known accuracy for single server queues with inhomogeneous arrival rate and continuous service time distribution

A practical method for obtaining approximate results for single server queues with inhomogeneous queues and continuous service time distribution is presented. The method is based on a discrete approximation to the continuous service time distribution. Exact results can be obtained for the corresponding queueing system with discrete service time distribution. These results are then corrected, and the likely accuracy of the corrected results is estimated. Four measures of performance are considered, idleness probability, mean and variance of number of customers in the system and virtual waiting time.