An M/G/1-type queuing model with service times depending on queue length

A study is made of an M/G/1-type queuing model in which customers receive one type of service until such time as, at the end of a service, the queue size is found to exceed a given value N, N ≥ 1. Then a second type of service is put into effect and remains in use until the queue size is reduced to a fixed value K, 0 ≤ K ≤ N. Equations are derived for the stationary probabilities both at departure times and at general times. An algorithm is developed that allows the rapid computation of the mean queue length and some important probabilities.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

On the longest service time in a busy period of the M⧸G⧸1 queue

This paper considers the supremum m of the service times of the customers served in a busy period of the M?G?1 queueing system. An implicit expression for the distribution m(w) of m is derived. This expression leads to some bounds for m(w), while it can also be used to obtain numerical results. The tail behaviour of m(w) is investigated, too. The results are particularly useful in the analysis of a class of tandem queueing systems.     

A Markov-modulated M/G/1 queue I: Stationary distribution

We consider an M/G/1 queueing system in which the arrival rate and service time density are functions of a two-state stochastic process. We describe the system by the total unfinished work present and allow the arrival and service rate processes to depend on the current value of the unfinished work. We employ singular perturbation methods to compute asymptotic approximations to the stationary distribution of unfinished work and in particular, compute the stationary probability of an empty queue.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

Remarks on the remaining service time upon reaching a target level in the M/G/1 queue

In this note we establish connections between new and previous results on the remaining service time upon reaching a target level in the M/G/1 queue.     

Insensitive bounds for the moments of the sojourn time distribution in the M/G/1 processor-sharing queue

This paper studies the M/G/1 processor-sharing (PS) queue, in particular the sojourn time distribution conditioned on the initial job size. Although several expressions for the Laplace-Stieltjes transform (LST) are known, these expressions are not suitable for computational purposes. This paper derives readily applicable insensitive bounds for all moments of the conditional sojourn time distribution. The instantaneous sojourn time, i.e., the sojourn time of an infinitesimally small job, leads to insensitive upper bounds requiring only knowledge of the traffic intensity and the initial job size. Interestingly, the upper bounds involve polynomials with so-called Eulerian numbers as coefficients. In addition, stochastic ordering and moment ordering results for the sojourn time distribution are obtained. AMS Subject Classification: 60K25, 60E15 This work has been partially funded by the Dutch Ministry of Economic Affairs under the program ‘Technologische Samenwerking ICT-doorbraakprojecten’, project TSIT1025 BEYOND 3G.     

Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Continuous time control of the arrival process in an m/g/1 queue

The problem of continuously controlling the arrival process in an M/G/1 queue is studied. The control is exercised by keeping the facility open or closed for potential arrivals, and is based on the residual workload process. The reward structure includes a reward rate R when the server is busy, and a holding cost rate cx when the residual workload is x. The economic criterion used is long run average return. A control limit policy is shown to be optimal. An iterative method for calculating this control limit policy is suggested.     

Tail asymptotics for the queue length in an M/G/1 retrial queue

In this paper, we study the tail behavior of the stationary queue length of an M/G/1 retrial queue. We show that the subexponential tail of the stationary queue length of an M/G/1 retrial queue is determined by that of the corresponding M/G/1 queue, and hence the stationary queue length in an M/G/1 retrial queue is subexponential if the stationary queue length in the corresponding M/G/1 queue is subexponential. Our results for subexponential tails also apply to regularly varying tails, and we provide the regularly varying tail asymptotics for the stationary queue length of the M/G/1 retrial queue. AMS subject classifications: 60J25, 60K25     

Queue length and waiting time of the M/G/1 queue under the D-policy and multiple vacations

We study the steady-state queue length and waiting time of the M/G/1 queue under the D-policy and multiple server vacations. We derive the queue length PGF and the LSTs of the workload and waiting time. Then, the mean performance measures are derived. Finally, a numerical example is presented and the effects of employing the D-policy are discussed. AMS Subject Classifications 60K25 This work was supported by the SRC/ERC program of MOST/KOSEF grant # R11-2000-073-00000.     

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.     

The interdeparture-time distribution for each class in the ∑ i M i /G i /1 queue

A stationary queueing system is described in which a single server handles several competing Poisson arrival streams on a first-come first-served basis. Each class has its own generally distributed service time characteristics. The principal result is the Laplace-Stieltjes transform, for each class, of the interdeparture time distribution function. Examples are given and applications are discussed.     

The M/G/1 queue with disasters and working breakdowns

In this paper, we analyze the M/G/1 queueing system with disasters and working breakdown services. The system consists of a main server and a substitute server, and disasters only occur while the main server is in operation. The occurrence of disasters forces all customers to leave the system and causes the main server to fail. At a failure instant, the main server is sent to the repair shop and the repair period immediately begins. During the repair period, the system is equipped with the substitute server which provides the working breakdown services to arriving customers. After introducing the concept of working breakdown services, we derive the system size distribution and the sojourn time distribution. We also obtain the results of the cycle analysis. In addition, numerical works are given to examine the relation between the sojourn time and the some system parameters.     

Optimization of the T policy M/G/1 queue with server breakdowns and general startup times

This paper investigates the T$T$ policy M/G/1 queue with server breakdowns, and startup times. Customers arrive at the system according to a Poisson process. Service times, repair times, and startup times are assumed to be generally distributed. The server is turned on after a fixed length of time T$T$ repeatedly until at least one customer is present in the waiting line. The server needs a startup time before starting the service. We analyze various system performance measures and develop the total expected cost function per unit time in which T$T$ is a decision variable. We determine the optimum threshold T^∗$T^{\ast }$ and derive analytical results for sensitivity investigations. The sensitivity analysis is particularly valuable to the system analyst when evaluating future conditions. We also present extensive numerical computation for illustration purpose.     

The M/M/1+M queue with a utility-maximizing server

We consider an M/M/1+M queue with a human server, who is influenced by incentives. Specifically, the server chooses his service rate by maximizing his utility function. Our objective is to guarantee the existence of a unique maximum. The complication is that most sensible utility functions depend on the server utilization, a non-simple expression. We derive a property of the utilization that guarantees quasiconcavity of any utility function that multiplies the server’s concave (including linear) “value” of his service rate by the server utilization.     

A Markov-modulated M/G/1 queue II: Busy period and time for buffer overflow

We consider an M/G/1 queue where the arrival and service processes are modulated by a two state Markov chain. We assume that the arrival rate, service time density and the rates at which the Markov chain switches its state, are functions of the total unfinished work (buffer content) in the queue. We compute asymptotic approximations to performance measures such as the mean residual busy period, mean length of a busy period, and the mean time to reach capacity.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

Higher moments of the waiting time distribution in M/G/1 retrial queues

This work analyzes the waiting time distribution in the M/G/1 retrial queue. The first two moments of the waiting time distribution are known from the literature. In this work we obtain all the moments of the waiting time distribution.     

Conditioned limit theorem for virtual waiting time process of the GI/G/1 queue

We prove that in the queueing system GI/G/1 with traffic intensity one, the virtual waiting time process suitably scaled, normed and conditioned by the event that the length of the first busy period exceeds n converges to the Brownian meander process, as n .