A note on conservation laws for a multiclass service queueing system with setup times

This paper derives a conservation law for mean waiting times in a single-server multi-class service queueing system (M ^X/G/1 type queue) with setup times which may be dependent on multiple customer classes and its arrival batch size by using the work decomposition property in the queueing system with vacations.     

Analyzing the finite buffer batch arrival queue under Markovian service process: GIX/MSP/1/N

We consider a batch arrival finite buffer single server queue with inter-batch arrival times are generally distributed and arrivals occur in batches of random size. The service process is correlated and its structure is presented through Markovian service process (MSP). The model is analyzed for two possible customer rejection strategies: partial batch rejection and total batch rejection policy. We obtain steady-state distribution at pre-arrival and arbitrary epochs along with some important performance measures, like probabilities of blocking the first, an arbitrary, and the last customer of a batch, average number of customers in the system, and the mean waiting times in the system. Some numerical results have been presented graphically to show the effect of model parameters on the performance measures. The model has potential application in the area of computer networks, telecommunication systems, manufacturing system design, etc.      

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.     

Analyzing the discrete-timeG (G)/Geo/1 queue using complex contour integration

In this paper, a discrete-time single-server queueing system with an infinite waiting room, referred to as theG ^(G)/Geo/1 model, i.e., a system with general interarrival-time distribution, general arrival bulk-size distribution and geometrical service times, is studied. A method of analysis based on integration along contours in the complex plane is presented. Using this technique, analytical expressions are obtained for the probability generating functions of the system contents at various observation epochs and of the delay and waiting time of an arbitrary customer, assuming a first-come-first-served queueing discipline, under the single restriction that the probability generating function for the interarrival-time distribution be rational. Furthermore, treating several special cases we rediscover a number of well-known results, such as Hunter's result for theG/Geo/1 model. Finally, as an illustration of the generality of the analysis, it is applied to the derivation of the waiting time and the delay of the more generalG ^(G)/G/1 model and the system contents of a multi-server buffer-system with independent arrivals and random output interruptions.Both authors wish to thank the Belgian National Fund for Scientific Research (NFWO) for support of this work.     

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

Asymptotic expansions for waiting time probabilities in an M/G/1 queue with long-tailed service time

We consider anM/G/1 queue with FCFS queue discipline. We present asymptotic expansions for tail probabilities of the stationary waiting time when the service time distribution is longtailed and we discuss an extension of our methods to theM ^[x]/G/1 queue with batch arrivals.     

Work-Conserving Tandem Queues

Consider a tandem queue of two single-server stations with only one server for both stations, who may allocate a fraction α of the service capacity to station 1 and 1−α to station 2 when both are busy. A recent paper treats this model under classical Poisson, exponential assumptions.Using work conservation and FIFO, we show that on every sample path (no stochastic assumptions), the waiting time in system of every customer increases with α. For Poisson arrivals and an arbitrary joint distribution of service times of the same customer at each station, we find the average waiting time at each station for α = 0 and α = 1. We extend these results to k ≥ 3 stations, sample paths that allow for server breakdown and repair, and to a tandem arrangement of single-server tandem queues.This revised version was published online in June 2005 with corrected coverdate     

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.     

Main Probability Characteristics of the Queuing System Gκ|G|1

For the queuing system G |G|1 with batch arrivals of calls, we present the distributions of the following characteristics: the length of a busy period, queue length in transient and stationary modes of the queuing system, total idle time of the queuing system, virtual waiting time to the beginning of the service, input stream of calls, output stream of served calls, etc.     

Further results for the M/M(a, ∞)/N batch-service system

A multi-server Markovian queueing system is considered such that an idle server will take the entire batch of waiting customers into service as soon as their number is as large as some control limit. Some new results are derived. These include the distribution of the time interval between two consecutive commencements of service (including itsrth moment) and the actual service batch size distribution. In addition, the average customer waiting time in the queue is derived by a simple combinatorial approach. This is an expanded version of “Combinatorial analysis of batch-service queues” which was presented at the ORSA/TIMS meeting, Orlando, Florida, November 1983.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

Analysis of a Batch Service Polling System in a Multi-phase Random Environment

In this paper, we consider a single-server multi-queue polling system with unlimited-size batch service (so called ‘Israeli queue’) operating in a multi-phase random environment. The polling system consists of a service region and a waiting region, and the external environment evolves through time, i.e., when the external environment is in state i, after a period time, it stays in this state or makes a transition from this state to its adjacent ones. By using matrix analytic method and spectral expansion method, stationary probabilities are derived for computations of performance measures and the conditional waiting times of customers in waiting region. In addition, some numerical examples are presented to show the impact of parameters on performance measures.     

Queue lengths in the GIX/MR/∞ service system

Service systems with queueing often have both batch arrivals and batch services. This paper focuses on the number of busy servers and waiting customers in theGI ^X/M^R/ system. For the number of busy servers, we obtain a recursive relation for the partial binomial moments in terms of matrices and explicit expressions for the marginal binomial moments. Special cases are also discussed to provide a more heuristic understanding of the model.This research has been supported in part by the Natural Science and Engineering Council of Canada through Grant A5639.     

An <Emphasis Type="Italic">M</Emphasis><Superscript>[<Emphasis Type="Italic">X</Emphasis>]</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1 retrial queue with server breakdowns and constant rate of repeated attempts

We consider an M ^[X]/G/1 retrial queue subject to breakdowns where the retrial time is exponential and independent of the number of customers applying for service. If a coming batch of customers finds the server idle, one of the arriving customers begins his service immediately and the rest joins a retrial group (called orbit) to repeat his request later; otherwise, if the server is busy or down, all customers of the coming batch enter the orbit. It is assumed that the server has a constant failure rate and arbitrary repair time distribution. We study the ergodicity of the embedded Markov chain, its stationary distribution and the joint distribution of the server state and the orbit size in steady-state. The orbit and system size distributions are obtained as well as some performance measures of the system. The stochastic decomposition property and the asymptotic behavior under high rate of retrials are discussed. We also analyse some reliability problems, the k-busy period and the ordinary busy period of our retrial queue. Besides, we give a recursive scheme to compute the distribution of the number of served customers during the k-busy period and the ordinary busy period. The effects of several parameters on the system are analysed numerically. I. Atencia’s and Moreno’s research is supported by the MEC through the project MTM2005-01248.     

M x /G/1 Queue with Multiple Vacations

Abstract

In this article, we study a queueing system M ^x /G/1 with multiple vacations. The probability generating function (P.G.F.) of stationary queue length and its expectation expression are deduced by using an embedded Markov chain of the queueing process. The P.G.F. of stationary system busy period and the probability of system in service state and vacation state also are obtained by the same method. At last we deduce the LST and mean of stationary waiting time in the service order FCFS and LCFS, respectively.     

Stochastic comparisons for bulk queues

We consider two important classes of single-server bulk queueing models: M^(X)/G^(Y)/1 with Poisson arrivals of customer groups, and G^(X)/m^(Y)1 with batch service times having exponential density. In each class we compare two systems and prove that one is more congested than the other if their basic random variables are stochastically ordered in an appropriate manner. However, it must be recognized that a system that appears congested to customers might be working efficiently from the system manager's point of view. We apply the results of this comparison to (i) the family {M/G^(s)/1,s 1} of systems with Poisson input of customers and batch service times with varying service capacity; (ii) the family {G^(s)/1,s 1} of systems with exponential customer service time density and group arrivals with varying group size; and (iii) the family {M/D/s,s 1} of systems with Poisson arrivals, constant service time and varying number of servers. Within each family, we find the system that is the best for customers, but this turns out to be the worst for the manager (or vice versa). We also establish upper (or lower) bounds for the expected queue length in steady state and the expected number of batches (or groups) served during a busy period. The approach of the paper is based on the stochastic comparison of random walks underlying the models.This research was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

Analysis of a two-phase queueing system with a fixed-size batch policy

We consider a single-server, two-phase queueing system with a fixed-size batch policy. Customers arrive at the system according to a Poisson process and receive batch service in the first-phase followed by individual services in the second-phase. The batch service in the first-phase is applied for a fixed number (k) of customers. If the number of customers waiting for the first-phase service is less than k when the server completes individual services, the system stays idle until the queue length reaches k. We derive the steady state distribution for the system’s queue length. We also show that the stochastic decomposition property can be applied to our model. Finally, we illustrate the process of finding the optimal batch size that minimizes the long-run average cost under a linear cost structure.     

A matrix-analytic solution for the DBMAP/PH/1 priority queue

Priority queueing models have been commonly used in telecommunication systems. The development of analytically tractable models to determine their performance is vitally important. The discrete time batch Markovian arrival process (DBMAP) has been widely used to model the source behavior of data traffic, while phase-type (PH) distribution has been extensively applied to model the service time. This paper focuses on the computation of the DBMAP/PH/1 queueing system with priorities, in which the arrival process is considered to be a DBMAP with two priority levels and the service time obeys a discrete PH distribution. Such a queueing model has potential in performance evaluation of computer networks such as video transmission over wireless networks and priority scheduling in ATM or TDMA networks. Based on matrix-analytic methods, we develop computation algorithms for obtaining the stationary distribution of the system numbers and further deriving the key performance indices of the DBMAP/PH/1 priority queue. AMS subject classifications: 60K25 · 90B22 · 68M20 The work was supported in part by grants from RGC under the contracts HKUST6104/04E, HKUST6275/04E and HKUST6165/05E, a grant from NSFC/RGC under the contract N_HKUST605/02, a grant from NSF China under the contract 60429202.