On the M/G/1 queue with feedback and optional server vacations based on a single vacation policy

We study a single server queue with batch arrivals and general (arbitrary) service time distribution. The server provides service to customers, one by one, on a first come, first served basis. Just after completion of his service, a customer may leave the system or may opt to repeat his service, in which case this customer rejoins the queue. Further, just after completion of a customer's service the server may take a vacation of random length or may opt to continue staying in the system to serve the next customer. We obtain steady state results in explicit and closed form in terms of the probability generating functions for the number of customers in the queue, the average number of customers and the average waiting time in the queue. Some special cases of interest are discussed and some known results have been derived. A numerical illustration is provided.     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

Questionnaire design improvement and missing item scores estimation for rapid and efficient decision making

In this paper we consider a single-server, cyclic polling system with switch-over times and Poisson arrivals. The service disciplines that are discussed, are exhaustive and gated service. The novel contribution of the present paper is that we consider the reneging of customers at polling instants. In more detail, whenever the server starts or ends a visit to a queue, some of the customers waiting in each queue leave the system before having received service. The probability that a certain customer leaves the queue, depends on the queue in which the customer is waiting, and on the location of the server. We show that this system can be analysed by introducing customer subtypes, depending on their arrival periods, and keeping track of the moment when they abandon the system. In order to determine waiting time distributions, we regard the system as a polling model with varying arrival rates, and apply a generalised version of the distributional form of Little??s law. The marginal queue length distribution can be found by conditioning on the state of the system (position of the server, and whether it is serving or switching).     

Randomly Interrupted GI-G-1 Queues: Service Strategies and Stability Issues

We consider a discrete-time queueing system subjected to random server interruptions. As customers arriving in the queue require generally distributed service times, the server can be interrupted during a customer's service. Therefore, nine different service strategies are proposed and analyzed using a probability generating functions approach. Performance measures under investigation include moments of steady-state buffer contents at random slot boundaries in equilibrium and moments of the customer delay. In particular we focus on the stability requirements for the strategies under consideration.     

A difference equation approach for analysing a batch service queue with the batch renewal arrival process

We consider an infinite buffer single server queue wherein customers arrive according to the batch renewal arrival process and are served in batches following the random serving capacity rule. The service-batch times follow exponential distribution. This model has been studied in the past using the embedded Markov chain technique and probability generating function. In this paper we provide an alternative yet simple methodology to carry out the whole analysis which is based on the supplementary variable technique and the theory of difference equations. The procedure used here is simple in the sense that it does not require the complicated task of constructing the transition probability matrix. We obtain explicit expressions of the steady-state system-content distribution at pre-arrival and arbitrary epochs in terms of roots of the associated characteristic equation. We also present few numerical results in order to illustrate the computational procedure.     

M/(G1, G2)/1 retrial queue under Bernoulli vacation schedules with general repeated attempts and starting failures

This paper investigates a batch arrival retrial queue with general retrial times, where the server is subject to starting failures and provides two phases of heterogeneous service to all customers under Bernoulli vacation schedules. Any arriving batch finding the server busy, breakdown or on vacation enters an orbit. Otherwise one customer from the arriving batch enters a service immediately while the rest join the orbit. After the completion of two phases of service, the server either goes for a vacation with probability p or may wait for serving the next customer with probability (1 − p). We construct the mathematical model and derive the steady-state distribution of the server state and the number of customers in the system/orbit. Such a model has potential application in transfer model of e-mail system.     

具有第二次可选服务的带反馈的N-策略Mx/G/1(E,MV)排队系统分析

研究N策略下的批量到达的具有第二次可选择服务且两次服务均可反馈的多重休假排队系统。建立了休假、反馈、可选服务多类型相结合的排队模型。本文采用补充变量法，首先建立了系统稳态下的状态转移方程，通过求解得到了稳态下系统队长的概率母函数，进而计算出稳态下系统的平均队长。对稳态队长进行分析之后，我们又给出了稳态队长的随机分解定理，其中给出了附加队长的明确概率解释。     

Analysis of the BMAP/G/1 retrial system with search of customers from the orbit

We consider a single server retrial queuing model in which customers arrive according to a batch Markovian arrival process. Any arriving batch finding the server busy enters into an orbit. Otherwise one customer from the arriving batch enters into service immediately while the rest join the orbit. The customers from the orbit try to reach the service later and the inter-retrial times are exponentially distributed with intensity depending (generally speaking) on the number of customers on the orbit. Additionally, the search mechanism can be switched-on at the service completion epoch with a known probability (probably depending on the number of customers on the orbit). The duration of the search is random and also probably depending on the number of customers in the orbit. The customer, which is found as the result of the search, enters the service immediately if the server is still idle. Assuming that the service times of the primary and repeated customers are generally distributed (with possibly different distributions), we perform the steady state analysis of the queueing model.     

Class clustering destroys delay differentiation in priority queues

This paper considers a discrete-time priority queueing model with one server and two types (classes) of customers. Class-1 customers have absolute (service) priority over class-2 customers. New customer batches enter the system at the rate of one batch per slot, according to a general independent arrival process, i.e., the batch sizes (total numbers of arrivals) during consecutive time slots are i.i.d. random variables with arbitrary distribution. All customers entering the system during the same time slot (i.e., belonging to the same arrival batch) are of the same type, but customer types may change from slot to slot, i.e., from batch to batch. Specifically, the types of consecutive customer batches are correlated in a Markovian way, i.e., the probability that any batch of customers has type 1 or 2, respectively, depends on the type of the previous customer batch that has entered the system. Such an arrival model allows to vary not only the relative loads of both customer types in the arrival stream, but also the amount of correlation between the types of consecutive arrival batches. The results reveal that the amount of delay differentiation between the two customer classes that can be achieved by the priority mechanism strongly depends on the amount of such interclass correlation (or, class clustering) in the arrival stream. We believe that this phenomenon has been largely overlooked in the priority-scheduling literature.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.      

Geometric equilibrium distributions for queues with interactive batch departures

Gelenbe et al. [1, 2] consider single server Jackson networks of queues which contain both positive and negative customers. A negative customer arriving to a nonempty queue causes the number of customers in that queue to decrease by one, and has no effect on an empty queue, whereas a positive customer arriving at a queue will always increase the queue length by one. Gelenbe et al. show that a geometric product form equilibrium distribution prevails for this network. Applications for these types of networks can be found in systems incorporating resource allocations and in the modelling of decision making algorithms, neural networks and communications protocols.In this paper we extend the results of [1, 2] by allowing customer arrivals to the network, or the transfer between queues of a single positive customer in the network to trigger the creation of a batch of negative customers at the destination queue. This causes the length of the queue to decrease by the size of the created batch or the size of the queue, whichever is the smallest. The probability of creating a batch of negative customers of a particular size due to the transfer of a positive customer can depend on both the source and destination queue.We give a criterion for the validity of a geometric product form equilibrium distribution for these extended networks. When such a distribution holds it satisfies partial balance equations which are enforced by the boundaries of the state space. Furthermore it will be shown that these partial balance equations relate to traffic equations for the throughputs of the individual queues.     

Geo/G/1 queues with disasters and general repair times

This paper discusses discrete-time single server Geo/G/1 queues that are subject to failure due to a disaster arrival. Upon a disaster arrival, all present customers leave the system. At a failure epoch, the server is turned off and the repair period immediately begins. The repair times are commonly distributed random variables. We derive the probability generating functions of the queue length distribution and the FCFS sojourn time distribution. Finally, some numerical examples are given.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

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.     

On a BMAP/G/1 G-queue with setup times and multiple vacations

In this paper, we consider a BMAP/G/1 G-queue with setup times and multiple vacations. Arrivals of positive customers and negative customers follow a batch Markovian arrival process (BMAP) and Markovian arrival process (MAP) respectively. The arrival of a negative customer removes all the customers in the system when the server is working. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. By using the supplementary variables method and the censoring technique, we obtain the queue length distributions. We also obtain the mean of the busy period based on the renewal theory.     

A single-server batch arrival queue with returning customers

We consider a new class of batch arrival retrial queues. By contrast to standard batch arrival retrial queues we assume if a batch of primary customers arrives into the system and the server is free then one of the customers starts to be served and the others join the queue and then are served according to some discipline. With the help of Lyapunov functions we have obtained a necessary and sufficient condition for ergodicity of embedded Markov chain and the joint distribution of the number of customers in the queue and the number of customers in the orbit in steady state. We also have suggested an approximate method of analysis based on the corresponding model with losses.     

Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience

In this paper we introduce the adaptive MMAP[K] arrival process and analyze the adaptive MMAP[K]/PH[K]/1 queue. In such a queueing system, customers of K different types with Markovian inter-arrival times and possibly correlated customer types, are fed to a single server queue that makes use of r thresholds. Service times are phase-type and depend on the type of customer in service. Type k customers are accepted with some probability a_i,k if the current workload is between threshold i − 1 and i. The manner in which the arrival process changes its state after generating a type k customer also depends on whether the customer is accepted or rejected.     

Some results on a generalized M/G/1 feedback queue with negative customers

This paper deals with a generalized M/G/1 feedback queue in which customers are either “positive" or “negative". We assume that the service time distribution of a positive customer who initiates a busy period is G _e (x) and all subsequent positive customers in the same busy period have service time drawn independently from the distribution G _b (x). The server is idle until a random number N of positive customers accumulate in the queue. Following the arrival of the N-th positive customer, the server serves exhaustively the positive customers in the queue and then a new idle period commences. This queueing system is a generalization of the conventional N-policy queue with N a constant number. Explicit expressions for the probability generating function and mean of the system size of positive customers are obtained under steady-state condition. Various vacation models are discussed as special cases. The effects of various parameters on the mean system size and the probability that the system is empty are also analysed numerically. AMS Subject Classification: Primary: 60 K 25 · Secondary: 60 K 20, 90 B 22     

Analysis of a Two‐Phase Queueing System with Vacations and Bernoulli Feedback

Abstract

We consider a two‐phase queueing system with server vacations and Bernoulli feedback. 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. Each customer who completes the individual service returns to the tail of the second phase service queue with probability 1 ? σ. If the system becomes empty at the moment of the completion of the second phase services, the server takes vacations until he finds customers. This type of queueing problem can be easily found in computer and telecommunication systems. By deriving a relationship between the generating functions for the system size at various embedded epochs, we obtain the system size distribution at an arbitrary time. The exhaustive and gated cases for the batch service are considered.