Search

This paper considers the two-stage cyclic queueing model consisting of one general (G) and one exponential (M) server. The strong connection between the present model and the M/G/1 model (with finite waiting room) is exploited to yield the joint distribution of the successive response times of a customer at the G queue and the M queue. This result reveals a surprising phenomenon: in general there is a difference between the joint distribution of the two successive response times at (first) the G queue and (then) the M queue, and the joint distribution of the two successive response times at (first) the M queue and (then) the G queue. Another associated result is an expression for the cycle-time distribution. Special consideration is given to the case that the number of customers in the system tends to ∞, while the mean service times tend to 0 at an inversely proportional rate.

Single-served, multiqueue systems with cyclic service in discrete time are considered. Nonzero switchover times between consecutive queues are assumed; the service strategies at the various queues may differ. A decomposition for the amount of work in such systems is obtained, leading to an exact expression for a weighted sum of the mean waiting times at the various queues. >

This paper considers the problem of obtaining approximate expressions for the first moment WGs of the stationary waiting time distribution in an M/G/s queueing system. Special attention is paid to the case G ≡ D, i.e., constant service times. Most known approximations are in fact heavy traffic approximations which have rather large relative errors in the light traffic case. In the present study both the light traffic and heavy traffic behavior of WGs (WDs) are taken into account. In order to obtain mean waiting time approximations it appears to be useful to introduce a quantity (the “normed cooperation coefficient”) which is inversely proportional to WGs and which is in some sense a measure for the “cooperation” between the servers of the service facility. A part of the paper is devoted to the analysis of this normed cooperation coefficient.

This paper is devoted to two types of stochastic scheduling problems, one involving a single machine and the other involving a flow shop consisting of an arbitrary number of machines. In both problem types, all jobs to be processed have due dates, and the objective is to find a job sequence that minimizes the expected weighted number of tardy jobs. For the single-machine case, sufficient optimality conditions for job sequences are derived for various choices of due date and processing time distributions. For the case of a flow shop with an arbitrary number of machines and identically distributed due dates for all jobs, we prove the following intuitively appealing results: (i) when all jobs have the same processing time distributions, the expected weighted number of tardy jobs is minimized by sequencing the jobs in decreasing order of the weights, (ii) when all weights are equal, the jobs should be sequenced according to an increasing stochastic ordering of the processing time distributions.

A network of service stations Q 0 Q 1,...,QM is studied. Requests arrive at the centers according to independent Poisson processes; they travel through (part of) the network demanding amounts of service, with independent and negative exponentially distributed lengths, from those centers which they enter, and finally depart from the network. The waiting rooms or buffers at each service station in this exponential service system are finite. When the capacity at Q i is reached, service at all nodes which are currently processing a request destined next for Q i is instantaneously interrupted. The interruption lasts until the service of the request in the saturated node Q i is. completed. This blocking phenomenon makes an exact analysis intractable and a numerical solution computationally infeasible for most exponential systems. We introduce an approximation procedure for a class of exponential systems with blocking and show that it leads to accurate approximations for the marginal equilibrium queue length distributions. The applicability of the approximation method may not be limited to blocking systems.

This paper is devoted to the practical implications of the theoretical results obtained in Part I [1] for queueing systems consisting of two single-server queues in series in which the service times of an arbitrary customer at both queues are identical. For this purpose some tables and graphs are included. A comparison is made—mainly by numerical and asymptotic techniques—between the following two phenomena: (i) the queueing behaviour at the second counter of the two-stage tandem queue and (ii) the queueing behaviour at a single-server queue with the same offered (Poisson) traffic as the first counter and the same service-time distribution as the second counter. This comparison makes it possible to assess the influence of the first counter on the queueing behaviour at the second counter. In particular we note that placing the first counter in front of the second counter in heavy traffic significantly reduces both the mean and variance of the total time spent in the second system.

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.

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.

The evolution of queueing theory is sketched from its origin in Teletraffic, via its growth to maturity as a mathematical discipline in Operations Research, to its present position as an indispensable tool in the performance analysis of complex computer—and communication networks. The Dutch postwar contributions to this evolution receive some special attention, on the occasion of the celebration of the Dutch Society for Statistics and ‘Operations Research’ fourth decennium.

This paper considers single-server, multi-queue systems with cyclic service. Non-zero switch-over times of the server between consecutive queues are assumed. A stochastic decomposition for the amount of work in such systems is obtained. This decomposition allows a short derivation of a ‘pseudo-conservation law' for a weighted sum of the mean waiting times at the various queues. Thus several recently proved conservation laws are generalised and explained.

In this paper we consider an M/G/1 queueing model, in which each customer is fed back a fixed number of times. For the case of negative exponentially distributed service times at each visit, we determine the Laplace-Stieltjes transform of the joint distribution of the sojourn times of the consecutive visits. As a by-result, we obtain the (transform of the) total sojourn time distribution; it can be related to the sojourn time distribution in the M/D/l queue with processor sharing. For the case of generally distributed service times at each visit, a set of linear equations is derived, from which the mean sojourn times per visit can be calculated.

As the use of wireless sensor networks increases, the need for efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper, we analyze the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. We show that the broadcasting process of a network using Trickle can be modeled by a Markov chain and that this chain falls under a class of Markov chains, closely related to residual lifetime distributions. It is then shown that this class of Markov chains admits a stationary distribution of a special form. These results are used to analyze the Trickle algorithm and its message count. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period., Comment: arXiv admin note: substantial text overlap with arXiv:1407.6034

In this paper we study the stationary workload distribution of a fluid tandem queue in heavy traffic. We consider different types of Lévy input, covering compound Poisson, (Formula presented.)-stable Lévy motion (with (Formula presented.)), and Brownian motion. In our analysis, we separately deal with Lévy input processes with increments that have finite and infinite variance. A distinguishing feature of this paper is that we do not only consider the usual heavy traffic regime, in which the load at one of the nodes goes to unity, but also a regime in which we simultaneously let the load of both servers tend to one, which, as it turns out, leads to entirely different heavy traffic asymptotics. Numerical experiments indicate that under specific conditions the resulting simultaneous heavy traffic approximation significantly outperforms the usual heavy traffic approximation.

Mean waiting-time approximations are derived for a single-server multi-queue system with nonexhaustive cyclic service. Nonzero switchover times of the server between consecutive queues are assumed. The main tool used in the derivation is a pseudo-conservation law recently found by Watson (1984). The approximation is simpler and, as extensive simulations show, more accurate than existing approximations. Moreover, it gives very good insight into the qualitative behaviour of cyclic-service queueing systems.

We consider a series of queues with Poisson input. Each queueing system contains an infinite number of service channels. The service times in each channel have a general distribution.For this M/G∞ tandem model we obtain the joint time-dependent distribution of queue length and residual service times at each queue. This leads to an expression for the joint stationary distribution of the number of customers in various queues at the arrival epochs of a tagged customer at those queues.

This study is devoted to mean waiting-time approximations in a single-server multi-queue model with cyclic service and zero switching times of the server between consecutive queues. Two different service disciplines are considered: exhaustive service and (ordinary cyclic) nonexhaustive service. For both disciplines it is shown how estimates of the mean waiting times at the various queues can be obtained when no explicit information on arrival intensities and service-time distributions is available, while only the utilizations at the queues and the lengths of the busy periods of the system can be measured. In the exhaustive case, a known mean waiting-time approximation is shown to be suitable for our purposes; in the nonexhaustive case, a new approximation has been derived which is simple and yet more accurate than existing approximations. Extensive simulation validates the approximation methods.

This paper considers the supremumm of the service times of the customers served in a busy period. For theG/G/s queue the tail behaviour of the distributionm (w) ofm is compared with that of the service time distribution. For theE k /G/1 queue an expression for the joint distribution ofm and of the number of customers served in the busy period is derived. Finally some detailed results for theM/M/1 queue are mentioned. Diese Arbeit befaßt sich mit dem Supremumm der Bedienungszeiten der in einer Arbeitsperiode bedienten Kunden. Im Falle des BedienungssystemsG/G/s werden die Wahrscheinlichkeiten für große Werte vonm verglichen mit den Wahrscheinlichkeiten für große Bedienungszeiten. Im Falle vonE k /G/1 wird ein expliziter Ausdruck für die gemeinsame Verteilung vonm und der Anzahl der in der Arbeitsperiode bedienten Kunden gewonnen. Einige Resultate fürM/M/1 bilden den Abschluß.

The principle of work conservation has in the past proven to be very useful in the analysis of queueing systems with a non-FCFS service discipline. When no work is created or destroyed within the system, the amount of work present should not depend on the order of service - and hence should equal the amount of work in the ‘corresponding’ system (same total arrival process and service requirements) with FCFS service discipline. If, moreover, the queueing discipline selects customers in a way that is independent of (any measure of) the service time, then the distribution of the number of customers in the system is also independent of the order of service. But even if this is not the case, as in priority systems with different service requirements for different classes of customers, the principle of work conservation yields a useful expression for a weighted sum of the mean queue lengths; hence (by using Little’s formula) a weighted sum of mean waiting times can be obtained.

This paper studies the traffic flow in a virtual circuit of a computer communication network with window flow control. Due to finite buffer capacity, overflow of data packets is possible. Lost packets have to be retransmitted. To maintain the original order of the packets, subsequently sent packets also have to be retransmitted, causing a deterioriation of throughput.

Mean waiting-time approximations are derived for a single-server multi-queue system with nonexhaustive cyclic service. Non-zero switch-over times of the server between consecutive queues are assumed. The main tool used in the derivation is a pseudo-conservation law recently found by Watson. The approximation is simpler and, as extensive simulations show, more accurate than existing approximations. Moreover, it gives very good insight into the qualitative behavior of cyclic-service queueing systems.

Let (T1,…,Tn) denote and ordered list of n tasks, which have to be served on m=2 parallel processors. X1 denotes the service time of Ti (X1,…,Xn) is a set of independent, identically distributed stochastic variables. Service of the tasks on each processor is non-preemptive. The tasks are served according to a list schedule: Serve the tasks in their order T1,…,Tn;start serving T1…,Tm, and whenever a processor completes a service, let it take as its next task the one which is at the head of the remainder of the list. denotes the makespan of the list schedule for , i.e., the time required to complete the service of all tasks. If the exact values of X1,…,Xn were known in advance, the makespan might be reuced by reordering the tasks in advance in an optimal way. Let denote the minimal makespan which can thus be obtained. The present study is devoted to a probabilistic analysis of the ratio for the case that the Xi have an Erlang distribution. In particular, bounds for the mean and distribution of are obtained. The results also apply to the heuristic Lowest-Fit rule in bin-packing.

No abstract.