An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

Analysis of non-steady state operation of a queue with dependent service times

The paper is concerned with a M|G|1-type queue with dependent service times. An analysis of non-steady state operation of a queue is performed, the distribution of queue size is found at arbitrary times.     

Sojourn times in a processor sharing queue with service interruptions

We study the sojourn times of customers in an M/M/1 queue with the processor sharing service discipline and a server that is subject to breakdowns. The lengths of the breakdowns have a general distribution, whereas the on-periods are exponentially distributed. A branching process approach leads to a decomposition of the sojourn time, in which the components are independent of each other and can be investigated separately. We derive the Laplace–Stieltjes transform of the sojourn-time distribution in steady state, and show that the expected sojourn time is not proportional to the service requirement. In the heavy-traffic limit, the sojourn time conditioned on the service requirement and scaled by the traffic load is shown to be exponentially distributed. The results can be used for the performance analysis of elastic traffic in communication networks, in particular, the ABR service class in ATM networks, and best-effort services in IP networks.     

Discrete-time queue with Bernoulli bursty source arrival and generally distributed service times

In this contribution, a discrete-time single-server infinite-capacity queue with correlated arrivals and general service times is investigated. Arrivals of cells are modelled as an on/off source process with geometrically distributed on-periods and off-periods, which is called Bernoulli bursty source. Based on the probability generating function technique, closed-form expression of some performance measures of system, such as average buffer content, unfinished work, cell delay and so on, are obtained. Finally, the effects of system parameters on performance measures are illustrated by some numerical examples.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

A complete and simple solution for a discrete-time multi-server queue with bulk arrivals and deterministic service times

A complete distribution for the system content of a discrete-time multi-server queue with an infinite buffer is presented, where each customer arriving in a group requires a deterministic service time that could be greater than one slot. In addition, when the service time equals one slot, a complete distribution for the delay is also presented.     

A non-increasing Lindley-type equation

In this paper we study the Lindley-type equation W=max {0,B−A−W}. Its main characteristic is that it is a non-increasing monotone function in its main argument W. Our main goal is to derive a closed-form expression of the steady-state distribution of W. In general this is not possible, so we shall state a sufficient condition that allows us to do so. We also examine stability issues, derive the tail behaviour of W, and briefly discuss how one can iteratively solve this equation by using a contraction mapping. This research has been carried out when the author was affiliated with EURANDOM, The Netherlands.     

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.     

Queues with service times and interarrival times depending linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queue with unlimited waiting space and the first-in first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY _n+1=C _n Y _n +X _n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.     

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.     

Design of RLS fixed-lag smoother using covariance information in linear discrete stochastic systems

This paper newly designs the recursive least-squares fixed-lag smoother using the covariance information in linear discrete-time stochastic systems. It is assumed that the signal is observed with additive white observation noise and the signal is uncorrelated with the observation noise. The fixed-lag smoother uses the covariance function of the signal in the semi-degenerate kernel form and the variance of the observation noise. The proposed fixed-lag smoother is suitable for the estimations of stationary or non-stationary stochastic signals generally.     

A limiting absorption principle for scattering problems with unbounded obstacles

A generalized mode matching method that applies to a wide class of scattering problems is developed in the time harmonic two‐dimensional Helmholtz case. This method leads by variational means to an integro‐differential formulation whose unknown is the trace of the field on an unbounded one‐dimensional interface. The well‐posedness is proved after a careful study of the rather original functional framework. Owing to a fundamental density result—based upon some properties of a singular integral operator similar to the Hilbert transform—the limiting absorption principle related to this original formulation is established. Finally, two other situations are emphasized. Copyright © 2001 John Wiley & Sons, Ltd.     

Design of RLS Wiener fixed-lag smoother using covariance information in linear discrete stochastic systems

In this paper, we propose a new design for the recursive least-squares (RLS) Wiener fixed-lag smoother and filter in linear discrete-time wide-sense stationary stochastic systems. It is assumed that the signal is observed with additive white observation noise. The signal is uncorrelated with the observation noise. The estimators require knowledge of the system matrix, the observation matrix and the variance of the state vector. These quantities can be obtained from the auto-covariance function of the signal. In the estimation algorithms, moreover, the variance of the observation noise is assumed to be known, as a priori information.     

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.     

An optimal service rate in a Poisson arrival queue with two-stage service policy*

We consider a two-stage service policy for a Poisson arrival queueing system. The idle server starts to work with ordinary service rate when a customer arrives. If the number of customers in the system reaches N, the service rate gets faster and continues until the system becomes empty. Otherwise, the server finishes the busy period with ordinary service rate. After assigning various operating costs to the system, we show that there exists a unique fast service rate minimizing the long-run average cost per unit time.This work was supported by Korea Research Foundation Grant(KRF-2002-070-C00021).     

Design of recursive least-squares fixed-lag smoother using covariance information in linear continuous stochastic systems

This paper newly designs the recursive least-squares (RLS) fixed-lag smoother and filter using the covariance information in linear continuous-time stochastic systems. It is assumed that the signal is observed with additive white observation noise and the signal is uncorrelated with the observation noise. The estimators require the covariance information of the signal and the variance of the observation noise. The auto-covariance function of the signal is expressed in the semi-degenerate kernel form.     

An M/G/1 queue with second optional service

We study an M/G/1 queue with second optional service. Poisson arrivals with mean arrival rate (>0) all demand the first essential service, whereas only some of them demand the second optional service. The service times of the first essential service are assumed to follow a general (arbitrary) distribution with distribution function B(v) and that of the second optional service are exponential with mean service time 1/₂ (₂>0). The time-dependent probability generating functions have been obtained in terms of their Laplace transforms and the corresponding steady state results have been derived explicitly. Also the mean queue length and the mean waiting time have been found explicitly. The well-known Pollaczec–Khinchine formula and some other known results including M/D/1, M/E_k/1 and M/M/1 have been derived as particular cases.     

Two queues with alternating service and server breakdown

We consider a queueing system with two stations served by a single server in a cyclic manner. We assume that at most one customer can be served at a station when the server arrives at the station. The system is subject to service interuption that arises from server breakdown. When a server breakdown occurs, the server must be repaired before service can resume. We obtain the approximate mean delay of customers in the system.