The M/G/1 processor-sharing model: transient behavior

This paper deals with the M/G/1 model with processor-sharing service discipline. LetL ^* (t, x) denote the number of jobs present at timet whose attained service time is not greater thanx,x0, andV ₀(t,z) the sojourn time of a tagged job placed in the system at timet and requiringz units of service. Explicit analytical expressions are obtained for the joint distribution ofL ^*(t, ·) andV ⁰(t, ·) under various initial conditions in terms of the Laplace transform with respect tot. It is shown that for initial conditions of special kind (there is one job or none) the results can be expressed in a closed form.     

Sojourn times in (discrete) time shared systems and their continuous time limits

We study the mean sojourn times in two M/G/1 weighted round-robin systems: the weight of a customer at any given point in time in the first system is a function of its age (imparted service), while in the second system the weight is a function of the customer’s remaining processing time (RPT). We provide a sufficient condition under which the sojourn time of a customer with large service requirement (say, x) and that arrives in the steady state is close to that of a customer which starts a busy period and has the same service requirement. A sufficient condition is then provided for continuity of the performance metric (the mean sojourn time) as the quanta size in the discrete time system converges to 0. We then consider a multi-class system and provide relative ordering of the mean sojourn times among the various classes.     

Strong approximations for priority queues; head-of-the-line-first discipline

In this paper, we obtain strong approximation theorems for a single server queue withr priority classes of customers and a head-of-the-line-first discipline. By using priority queues of preemptive-resume discipline as modified systems, we prove strong approximation theorems for the number of customers of each priority in the system at timet, the number of customers of each priority that have departed in the interval [0,t], the work load in service time of each priority class facing the server at timet, and the accumulated time in [0,t] during which there are neither customers of a given priority class nor customers of priority higher than that in the system.Research supported by the National Natural Science Foundation of China.     

Variance of the throughput of an N-station production line with no intermediate buffers and time dependent failures

In this study, the variance of the throughput of an N-station production line with no intermediate buffers and time dependent failures is analytically determined. Time to failure and time to repair distributions are assumed to be exponential. The analytical method yields a closed-form expression for the variance of the throughput. The method is based on determining the limiting variance of the total residence (sojourn) time in a specific state of an irreducible recurrent Markov process from the probability of visiting that state at time t given an initial state. This probability function is the instantaneous availability of a production system in the reliability context. A production line with no interstation buffers and time-dependent failures is basically a series system with hot standby. The same procedure can be applied to determine the variance of the throughputs of various arrangements of workstations including series, parallel, series-parallel systems provided that the instantaneous availabilities of these systems can be written explicitly. Numerical experiments show that, although the expected throughput decreases monotonically, the variance of the throughput may increase and then decrease as the number of stations in the line increases depending on the system parameters. Numerical experiments that investigate this phenomenon and also the dependence of the coefficient of variation on the number of stations are also presented in this study.     

Queues with system disasters and impatient customers when system is down

Consider a system operating as an M/M/c queue, where c=1, 1<c<∞, or c=∞. The system as a whole suffers occasionally a disastrous breakdown, upon which all present customers (waiting and served) are cleared from the system and lost. A repair process then starts immediately. When the system is down, inoperative, and undergoing a repair process, new arrivals become impatient: each individual customer, upon arrival, activates a random-duration timer. If the timer expires before the system is repaired, the customer abandons the queue never to return. We analyze this model and derive various quality of service measures: mean sojourn time of a served customer; proportion of customers served; rate of lost customers due to disasters; and rate of abandonments due to impatience.      

A self-correcting point process

Suppose a point process is attempting to operate as closely as possible to a deterministic rate ρ, in the sense of aiming to produce ρt points during the interval (0,t] for all t. This can be modelled by making the instantaneous rate of t of the process a suitable function of n-ρt, n being the number of points in [0, t]. This paper studies such a self-correcting point process in two cases: when the point process is Markovian and the rate function is very general, and when the point process is arbitrary and the rate function is exponential. In each case it is shown that as t→∞ the mean number of points occuring in (0, t] is ρt+O(1) while the variance is bounded further, in the Markov case all the absolute central moments are bounded. An application to the outputs of stationary D/M/s queues is given.     

Application of the method of collective marks to someM/G/1 vacation models with exhaustive service

We use the Method of Collective Marks to analyze some time-dependent processes in theM/G/1 queue with single and multiple vacations. With the server state specified at a fixed timet>0, the Laplace transforms with respect tot of mixed transforms for the joint distribution of the number of departures by timet, the queue length, the virtual waiting time, the elapsed and remaining service/vacation times at timet are derived by means of probabilistic interpretations. The Laplace-Stieltjes transform of the virtual waiting time at timet is also given. Some well known results are special cases.This research was supported by the University of Amsterdam.     

An M/G/1 queueing model with vacation times

This paper deals with an M/G/1 queueing system with finite capacity for the workload, where the workload at timet is defined as the total amount of work in the system at timet. When the server provides service he will continue servicing until the system becomes empty, after which he leaves the system for a stochastic period of time, which will be called a vacation. When the server, returning from a vacation, finds the system still empty, he leaves for another vacation, otherwise he immediately starts servicing again.Using an embedding approach several characteristics of this system are derived amongst which the joint stationary distribution of the workload and the stage of the server.

---

Zusammenfassung Diese Arbeit befaßt sich mit einem M/G/1 Wartesystem, das hinsichtlich der anstehenden Arbeit eine endliche Kapazität hat. Wenn der Bediener tätig ist, bleibt er es solange, bis das System leer ist. Danach ist er während einer stochastischen Pausenzeit nicht verfügbar. Ist am Ende einer Pausenzeit das System immer noch leer, so schließt sich eine weitere Pausenzeit an; ansonsten wird unverzüglich die Bedienung am Ende der Pausenzeit wieder aufgenommen.Unter Verwendung eines eingebetteten Prozesses werden mehrere Kenngrößen des Systems ermittelt, darunter z.B. die gemeinsame Verteilung von anstehender Arbeit und Zustand des Bedieners.

     

On a duel with time lag and arbitrary accuracy functions

This paper deals with a two-person zero-sum game called duel with the following structure: Each of two players I and II has a gun with one bullet and he can fire his bullet at any time in [0, 1], aiming at his opponent. If I or II fires at timex, he hits his opponent with probabilityp (x) orq(x), respectively. The gun of I is silent, and hence, II does not know whether his opponent has fired or not, and the gun of II is noisy with time lagt, wheret is a positive constant,i.e., if II fires at timex then I knows it at timex +t. Further, if I hits II without being hit himself before, the payoff is 1; if I is hit by II without hitting II before, the payoff is ?1; if they hit each other at the same time or both survive, the payoff is 0. This paper gives optimal strategy for each player and the value of the game.     

Stochastic clearing systems

A stochastic clearing system is characterized by a non-decreasing stochastic input process $\text{{Y(t), t ≧ 0}}$, where Y(t) is the cumulative quantity entering the system in [0, t], and an output mechanism that intermittently and instantaneously clears the system, that is, removes all the quantity currently present. Examples may be found in the theory of queues, inventories, and other stochastic service and storage systems. In this paper we derive an explicit expression for the stationary (in some cases, limiting) distribution of the quantity in the system, under the assumption that the clearing instants are regeneration points and, in particular, first entrance times into sets of the form {y: y>q}. The expression is in terms of the sojourn measure W associated with $\text{{Y(t), t ≧ 0}: W{A} =}\text{E}${time spent in A by Y(t), 0 ≤ t < ∞}. The results are applied to compound input processes and processes with stationary independent increments. In particular, we show that, contrary to a wide-spread belief, the uniform stationary distribution characteristic of deterministic models does not usually carry over to genuinely stochastic models.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

Stabilization of statistics in wave and Klein-Gordon equations with mixing. Scattering theory for infinite energy solutions

We consider wave and Klein-Gordon equations in the whole space ?ⁿ with arbitraryn≥2. We assume initial data to be homogeneous random functions in ?ⁿ with zero expectation and finite mean density of energy. Moreover, we assume initial data fit mixing condition of Ibragimov-Linnik type. We consider the distributions of the random solution at the moment of timet. The main results mean the convergence of this distribution to some Gaussian measure ast→∞. This is a central limit theorem for wave and Klein-Gordon equations. The limit Gaussian measures are invariant measures for equations considered. Corresponding stationary random solutions are ergodic and mixing in time. The results are inspired by mathematical problems of statistical physics.     

Additive functionals with application to sojourn times in infinite-server and processor sharing systems

We deal with additive functionals of stationary processes. It is shown that under some assumptions a stationary model of the time-changed process exists. Further, bounds for the expectation of functions of additive functionals are derived. As an application we analyze virtual sojourn times in an infinite-server system where the service speed is governed by a stationary process. It turns out that the sojourn time of some kind of virtual requests equals in distribution an additive functional of a stationary time-changed process, which provides bounds for the expectation of functions of virtual sojourn times, in particular bounds for fractional moments and the distribution function. Interpreting the GI(n)/GI(n)/∞ system or equivalently the GI(n)/GI system under state-dependent processor sharing as an infinite-server system where the service speed is governed by the number n of requests in the system provides results for sojourn times of virtual requests. In the case of M(n)/GI(n)/∞, the sojourn times of arriving and added requests equal in distribution sojourn times of virtual requests in modified systems, which yields several results for the sojourn times of arriving and added requests. In case of positive integer moments, the bounds generalize earlier results for M/GI(n)/∞. In particular, the mean sojourn times of arriving and added requests in M(n)/GI(n)/∞ are proportional to the required service time, generalizing Cohen’s famous result for M/GI(n)/∞.     

M/M/c Retrial Queue with Multiclass of Customers

We consider the M/M/c retrial queues with multiclass of customers. We show that the stationary joint distribution for the number of customers in service facility and orbit converges to those of the ordinary M/M/c with discriminatory random order service (DROS) policy as retrial rate tends to infinity. Approximation formulae for the distributions of the number of customers in service facility, the mean number of customers in orbit and the sojourn time distribution of a customer are presented. The approximations are compared with exact and simulation results.     

Waiting times for M/M systems under state-dependent processor sharing

We consider a system where the arrivals form a Poisson process and the required service times of the requests are exponentially distributed. The requests are served according to the state-dependent (Cohen’s generalized) processor sharing discipline, where each request in the system receives a service capacity which depends on the actual number of requests in the system. For this system we derive systems of ordinary differential equations for the LST and for the moments of the conditional waiting time of a request with given required service time as well as a stable and fast recursive algorithm for the LST of the second moment of the conditional waiting time, which in particular yields the second moment of the unconditional waiting time. Moreover, asymptotically tight upper bounds for the moments of the conditional waiting time are given. The presented numerical results for the first two moments of the sojourn times in M/M/m?PS systems show that the proposed algorithms work well.     

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     

A Queue with Semi-Markovian Batch Plus Poisson Arrivals with Application to the MPEG Frame Sequence

We consider a queueing system with a single server having a mixture of a semi-Markov process (SMP) and a Poisson process as the arrival process, where each SMP arrival contains a batch of customers. The service times are exponentially distributed. We derive the distributions of the queue length of both SMP and Poisson customers when the sojourn time distributions of the SMP have rational Laplace–Stieltjes transforms. We prove that the number of unknown constants contained in the generating function for the queue length distribution equals the number of zeros of the denominator of this generating function in the case where the sojourn times of the SMP follow exponential distributions. The linear independence of the equations generated by those zeros is discussed for the same case with additional assumption. The necessary and sufficient condition for the stability of the system is also analyzed. The distributions of the waiting times of both SMP and Poisson customers are derived. The results are applied to the case in which the SMP arrivals correspond to the exact sequence of Motion Picture Experts Group (MPEG) frames. Poisson arrivals are regarded as interfering traffic. In the numerical examples, the mean and variance of the waiting time of the ATM cells generated from the MPEG frames of real video data are evaluated.     

Sojourn times in a processor sharing queue with multiple vacations

We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are identically distributed, with a general distribution. When the service requirements are exponentially distributed we determine the sojourn time distribution of an arbitrary customer. We also show how the same approach can be used to determine the sojourn time distribution in an M/M/1-PS queue of a polling model, under the following constraints: the service discipline at that queue is exhaustive service, the service discipline at each of the other queues satisfies a so-called branching property, and the arrival processes at the various queues are independent Poisson processes. For a general service requirement distribution we investigate both the vacation queue and the polling model, restricting ourselves to the mean sojourn time.     

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.     

A sample path relation for the sojourn times in G/G/1−PS systems and its applications

For the single server system under processor sharing (PS) a sample path result for the sojourn times in a busy period is proved, which yields a sample path relation between the sojourn times under PS and FCFS discipline. This relation provides a corresponding one between the mean stationary sojourn times in G/G/1 under PS and FCFS. In particular, the mean stationary sojourn time in G/D/1 under PS is given in terms of the mean stationary sojourn time under FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of these results suggest an approximation of the mean stationary sojourn time in G/GI/1 under PS in terms of the mean stationary sojourn time under FCFS. Mathematics Subject Classification (MSC 2000) 60K25· 68M20· 60G17· 60G10 This work was supported by a grant from the Siemens AG.