The N threshold policy for the GI/M/1 queue

We study a GI/M/1 queue with an N threshold policy. In this system, the server stops attending the queue when the system becomes empty and resumes serving the queue when the number of customers reaches a threshold value N. Using the embeded Markov chain method, we obtain the stationary distributions of queue length and waiting time and prove the stochastic decomposition properties.     

The service Erlangian machine interference model:M/E r /1k/N with balking and reneging

The aim of this paper is to derive the analytical solution of the quene:M/E _r /1/k/N for machine interference system with balking and reneging considering the discipline FIFO. Some measures of effectiveness and some special cases are obtained.     

The optimal strategy structure of an intermittently operated service channel

An analysis is made of the policy space structure for an intermittently operated M/M/1 queuing system. When the queue length builds up to limit N, the service channel is opened and service rendered until the queue length is reduced to some lower number, v, whereupon the channel is closed. Certain costs, namely these of lost customers, of giving service and of opening and closing the channel are imposed. A technique for dividing the policy space into regions of optimal {v, N} is developed so that the best strategy for any combination of costs is immediately visible to the decision maker.     

The Interarrival Hyperexponential Queues:Hk/M/c/N With Balking And Reneging

This paper treats the analytical solution of the truncated interarrival hyperexponential queue. H_k/M/c/N with balking and reneging for general values of k,c and N. The discipline considered here is FIFO. Some previously published results are shown to be special cases of the present results     

Busy period analysis for <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 queues with workload dependent balking

We consider an M/PH/1 queue with workload-dependent balking. An arriving customer joins the queue and stays until served if and only if the system workload is no more than a fixed level at the time of his arrival. We begin by considering a fluid model where the buffer content changes at a rate determined by an external stochastic process with finite state space. We derive systems of first-order linear differential equations for the mean and LST (Laplace-Stieltjes Transform) of the busy period in this model and solve them explicitly. We obtain the mean and LST of the busy period in the M/PH/1 queue with workload-dependent balking as a special limiting case of this fluid model. We illustrate the results with numerical examples.      

The M/G/1 FIFO Queue with Several Customer Classes

In this note we present short derivations of the joint queue length distribution in the M/G/1 queue with several classes of customers and FIFO service discipline.     

Steady state analysis of a bulk queue with multiple vacations,setup times with N-policy and closedown times

In this paper a M^X/G (a, b)/1 queueing system with multiple vacations, setup time with N-policy and closedown times is considered. On completion of a service, if the queue length is ξ, where ξ < a, then the server performs closedown work. Following closedown the server leaves for multiple vacations of random length irrespective of queue length. When the server returns from a vacation and if the queue length is still less than ‘N’, he leaves for another vacation and so on, until he finds ‘N’ (N > b) customers in the queue. That is, if the server finds at least ‘N’ customers waiting for service, then he requires a setup time ‘R’ to start the service. After the setup he serves a batch of ‘b’ customers, where b ⩾ a. Various characteristics of the queueing system and a cost model with the numerical solution for a particular case of the model are presented.     

带有止步和中途退出的优先权排队系统

研究了一个带有止步和中途退出的优先权排队系统,其中系统中有两类顾客,第一类顾客具有优先权,而且可能中途退出,第二类顾客可能止步和中途退出.首先,建立了系统稳态概率满足的方程组.其次,采用分块矩阵的方法得到了两类顾客的稳态分布,并且得到了系统中两类顾客的的平均队长、平均中途退出率等性能指标.最后,进行了相应的性能分析与比较,为系统的优化设计提供了参考.     

On a processor sharing queue that models balking

We consider the processor sharing M/M/1-PS queue which also models balking. A customer that arrives and sees n others in the system “balks” (i.e., decides not to enter) with probability 1−b _n . If b _n is inversely proportional to n + 1, we obtain explicit expressions for a tagged customer’s sojourn time distribution. We consider both the conditional distribution, conditioned on the number of other customers present when the tagged customer arrives, as well as the unconditional distribution. We then evaluate the results in various asymptotic limits. These include large time (tail behavior) and/or large n, lightly loaded systems where the arrival rate λ → 0, and heavily loaded systems where λ → ∞. We find that the asymptotic structure for the problem with balking is much different from the standard M/M/1-PS queue. We also discuss a perturbation method for deriving the asymptotics, which should apply to more general balking functions.     

Delay analysis of multiclass queues with correlated train arrivals and a hybrid priority/FIFO scheduling discipline

We analyze the delay experienced in a discrete-time priority queue with a train-arrival process. An infinite user population is considered. Each user occasionally sends packets in the form of trains: a variable number of fixed-length packets is generated and these packets arrive to the queue at the rate of one packet per slot. This is an adequate arrival process model for network traffic. Previous studies assumed two traffic classes, with one class getting priority over the other. We extend these studies to cope with a general number M of traffic classes that can be partitioned in an arbitrary number N of priority classes (1 ≤ N ≤ M). The lengths of the trains are traffic-class-dependent and generally distributed. To cope with the resulting general model, an (M × )∞-sized Markovian state vector is introduced. By using probability generating functions, moments and tail probabilities of the steady-state packet delays of all traffic classes are calculated. Since this study can be useful in deciding how to partition traffic classes in priority classes, we demonstrate the impact of this partitioning for some specific cases.     

Moment relationships for queues with Poisson input

This paper presents new relationships between the higher-order moments of the FIFO and LIFO disciplines. These relationships hold over a class of queueing models that includeM/G/1 queues with exceptional first service,M/G/1 queues with server vacations, andM/G/1 priority models. The results also generalize to a class of service disciplines that includes FIFO and LIFO as special cases.     

The M/G/c queue in light traffic

Under light traffic, we investigate the quality of a well‐known approximation for first‐moment performance measures for an M/G/c queue, and, in particular, conditions under which the approximation is either an upper or a lower bound. The approach is to combine known relationships between quantities such as average delay and time‐average work in system with direct sample‐path comparisons of system operation under two modes of operation: conventional FIFO and a version of preemptive LIFO. We then use light traffic limit theorems to show an inequality between time‐average work of the M/G/c queue and that of the approximation. In the process, we obtain new and improved approximations. This revised version was published online in June 2006 with corrections to the Cover Date.     

A note on the distributional Little’s law for discrete-time queues with D-MAP arrivals and its application

For a class of discrete-time FIFO queueing systems with D-MAP (discrete-time Markovian arrival process), we present a distributional Little’s law that relates the distribution of the stationary number of customers in system (queue) with that of the stationary number of slots a customer spends in system (queue). Taking the multi-server D-MAP/D/c queue as an example, we demonstrate how this relation can be utilized to get the desired distribution of the number of customers. Sample numerical results are presented at the end.     

Containment of socially optimal policies in multiple-facility Markovian queueing systems

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as ‘selfishly optimal’ and ‘socially optimal’. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.     

Size- and state-aware dispatching problem with queue-specific job sizes

We consider the dispatching problem in a size- and state-aware multi-queue system with Poisson arrivals and queue-specific job sizes. By size- and state-awareness, we mean that the dispatcher knows the size of an arriving job and the remaining service times of the jobs in each queue. By queue-specific job sizes, we mean that the time to process a job may depend on the chosen server. We focus on minimizing the mean sojourn time (i.e., response time) by an MDP approach. First we derive the so-called size-aware relative values of states with respect to the sojourn time in an M/G/1 queue operating under FIFO, LIFO, SPT or SRPT disciplines. For FIFO and LIFO, the size-aware relative values turn out to be insensitive to the form of the job size distribution. The relative values are then exploited in developing efficient dispatching rules in the spirit of the first policy iteration.     

A discrete queue with double thresholds policy and its application to SVC systems

A discrete time Geo/Geo/1 queue with (m, N)-policy is considered in this paper. There are three operation periods being considered: high speed, low speed service periods and idle periods. With double thresholds policy, the server begins to take a working vacation when the number of customers is below m after a service and there is one customer in the system at least. What’s more, if the system becomes empty after a service, the server will take an ordinary vacation. Otherwise, high speed service continues if the number of customers still exceeds m after a service. At the vacation completion instant, servers resume their service if the quantity of customers exceeds N. Vacations can also be interrupted when the system accumulate customers more than the prefixed threshold. Using the quasi birth-death process and matrix-geometric solution methods, we derive the stationary queue length distribution and some system characteristics of interest. Based on these, we apply the queue to a virtual channel switching system and present various numerical experiments for the system. Finally, numerical results are offered to illustrate the optimal (m, N)-policy to minimize cost function and obtain practical consequence on the operation of double thresholds policy.     

Joint distribution of sojourn time and queue length in the M/G/1 queue with (in) finite capacity

For the M/G/1 queue we study the joint distribution of the number of customers x present immediately before an arrival epoch and of the residual service time ζ of the customer in service at this epoch. The correlation coefficient ? (x, ζ) is shown to be positive (negative) when the service time distribution is DFR (IFR). The result for the joint distribution of x and ζ leads to the joint distribution of x, of the sojourn time s of the arriving customer and of the number of customers z left behind by this customer at his departure. ?(x, s), ?(z, s) and ?(x, z) are shown to be positive; ?(x, s) and ?(z, s) are compared in some detail.Subsequently the M/G/1 queue with finite capacity is considered; the joint distributions of x and ζ and of x and s are derived. These results may be used to study the cycle time distribution in a two-stage cyclic queue.     

An M/G/1 queue under hysteretic vacation policy with an early startup and un-reliable server

This paper considers the bi-level control of an M/G/1 queueing system, in which an un-reliable server operates N policy with a single vacation and an early startup. The server takes a vacation of random length when he finishes serving all customers in the system (i.e., the system is empty). Upon completion of the vacation, the server inspects the number of customers waiting in the queue. If the number of customers is greater than or equal to a predetermined threshold m, the server immediately performs a startup time; otherwise, he remains dormant in the system and waits until m or more customers accumulate in the queue. After the startup, if there are N or more customers waiting for service, the server immediately begins serving the waiting customers. Otherwise the server is stand-by in the system and waits until the accumulated number of customers reaches or exceeds N. Further, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We obtain the probability generating function in the system through the decomposition property and then derive the system characteristics     

Queues with hysteretic control by vacation and post-vacation periods

The paper investigates the queueing process in stochastic systems with bulk input, batch state dependent service, server vacations, and three post-vacation disciplines. The policy of leaving and entering busy periods is hysteretic, meaning that, initially, the server leaves the system on multiple vacation trips whenever the queue falls below r (⩾1), and resumes service when during his absence the system replenishes to N or more customers upon one of his returns. During his vacation trips, the server can be called off on emergency, limiting his trips by a specified random variable (thereby encompassing several classes of vacation queues, such as ones with multiple and single vacations). If by then the queue has not reached another fixed threshold M (⩽ N), the server enters a so-called “post-vacation period” characterized by three different disciplines: waiting, or leaving on multiple vacation trips with or without emergency. For all three disciplines, the probability generating functions of the discrete and continuous time parameter queueing processes in the steady state are obtained in a closed analytic form. The author uses a semi-regenerative approach and enhances fluctuation techniques (from his previous studies) preceding the analysis of queueing systems. Various examples demonstrate and discuss the results obtained. This revised version was published online in June 2006 with corrections to the Cover Date.