Information theoretic analysis for a general queueing system at equilibrium with application to queues in tandem

Summary In this paper, information theoretic inference methology for system modeling is applied to estimate the probability distribution for the number of customers in a general, single server queueing system with infinite capacity utilized by an infinite customer population. Limited to knowledge of only the mean number of customers and system equilibrium, entropy maximization is used to obtain an approximation for the number of customers in the G¦ G¦1 queue. This maximum entropy approximation is exact for the case of G=M, i.e., the M¦M¦1 queue. Subject to both independent and dependent information, an estimate for the joint customer distribution for queueing systems in tandem is presented. Based on the simulation of two queues in tandem, numerical comparisons of the joint maximum entropy distribution is given. These results serve to establish the validity of the inference technique and as an introduction to information theoretic approximation to queueing networks.This work was supported under a Naval Research Laboratory Fellowship under Grant N00014-83G-0203 and under an ONR Grant N00014-84K-0614 Former address:Westinghouse Defense and Electronics Center, Baltimore, MD, USA     

Alternating priority queues with non-zero switch rule

There are two queues and a single server. The server serves the two queues alternately according to a non-zero switch rule. That is, the server continues to serve without interruption in queue i until k_i customers are served or until the queue there becomes empty, whichever happens first, i = 1, 2. Customers arrive at the two queues according to two independent Poisson processes. The service times of the customers in each queue have a general distribution. In this paper, distributions of busy periods and waiting times are studied and pointed out the difficulties to obtain an explicit analytic expression for the mean waiting time. The non-zero switch rule is compared with the zero switch rule (k₁ = k₂ = ∞), in terms of the mean waiting times. Since an analytic comparison of waiting times is found to be difficult, a numerical comparison is done by means of simulation. The simulation results show also, how the waiting times are sensitive to the switch parameters k₁ and k₂.     

On a batch arrival Poisson queue with a random setup time and vacation period

The single server queue with vacation has been extended to include several types of extensions and generalisations, to which attention has been paid by several researchers (e.g. see Doshi, B. T., Single server queues with vacations — a servey. Queueing Systems, 1986, 1, 29–66; Takagi, H., Queueing Analysis: A Foundation of Performance evaluation, Vol. 1, Vacation and Priority systems, Part. 1. North Holland, Amsterdam, 1991; Medhi, J., Extensions and generalizations of the classical single server queueing system with Poisson input. J. Ass. Sci. Soc., 1994, 36, 35–41, etc.). The interest in such types of queues have been further enhanced in resent years because of their theoretical structures as well as their application in many real life situations such as computer, telecommunication, airline scheduling as well as production/inventory systems. This paper concerns the model building of such a production/inventory system, where machine undergoes extra operation (such as machine repair, preventive maintenance, gearing up machinery, etc.) before the processing of raw material is to be started. To be realistic, we also assume that raw materials arrive in batch. This production system can be formulated as an M^x/M/1 queues with a setup time. Further, from the utility point of view of idle time this model can also be formulated as a case of multiple vacation model, where vacation begins at the end of each busy period. Besides, the production/inventory systems, such a model is generally fitted to airline scheduling problems also. In this paper an attempt has been made to study the steady state behavior of such an M^x/M/1 queueing system with a view to provide some system performance measures, which lead to remarkable simplification when solving other similar types of queueing models.This paper deals with the steady state behaviour of a single server batch arrival Poisson queue with a random setup time and a vacation period. The service of the first customer in each busy period is preceded by a random setup period, on completion of which service starts. As soon as the system becomes empty the server goes on vacation for a random length of time. On return from vacation, if he finds customer(s) waiting, the server starts servicing the first customer in the queue. Otherwise it takes another vacation and so on. We study the steady state behaviour of the queue size distribution at random (stationary) point of time as well as at departure point of time and try to show that departure point queue size distribution can be decomposed into three independent random variables, one of which is the queue size of the standard M^x/M/1 queue. The interpretation of the other two random variables will also be provided. Further, we derive analytically explicit expressions for the system state (number of customers in the system) probabilities and provide their appropriate interpretations. Also, we derive some system performance measures. Finally, we develop a procedure to find mean waiting time of an arbitrary customer.     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

Markovian bulk service queue with delayed vacations

An M/M(a, b)/1 queueing system with multiple vacations is studied, in which if the number of customers in the queue is a - 1 either at a service completion epoch or at a vacation completion point, the server will wait for an exponential time in the system which is called the changeover time. During this changeover time if there is an arrival the server will start service immediately, otherwise at the end of the changeover time the server will go for a vacation. The duration of vacation is also exponential. This paper is concerned with the determination of the stationary distribution of the number of customers in the queue and the waiting time distribution of an arriving customer. The expected queue length is also obtained. Sample numerical illustrations are given.     

On efficient implementation of an approximation algorithm for the Steiner tree problem

Summary This paper studies the design and implementation of an approximation algorithm for the Steiner tree problem. Given any undirected distance graph G and a set of Steiner points S, the algorithm produces a Steiner tree with total weight on its edges no more than 2(1–1/L) times the total weight on the optimal Steiner tree, where L is the number of leaves in the optimal Steiner tree. Our implementation of the algorithm, in the worst case, makes it run in 0(¦E _g¦+¦V _g–S¦log¦V _g–S¦+¦S¦log ¦S¦) time for general graph G and in 0(¦S¦ log¦S¦+M log (M,¦V _g–S¦)) time for sparse graph G, where E _g is the set of edges in G, V_g is the set of vertices in G, M = min {¦E _g, (¦V _g–S¦–1)²/2} and (x,y) = min {i¦log⁽ⁱ⁾ y x/y}.The implementation is not likely to be improved significantly without the improvement of the shortest paths algorithm and the minimum spanning tree algorithm as the algorithm essentially composes of the computation of the multiple sources shortest paths of a graph with ¦V _g¦ vertices and ¦E _g¦ edges and the minimum spanning tree of a graph with ¦V _g–S¦ vertices and M edges.     

Achieving prescribed mean waiting times in a single-server queueing system

A new queueing discipline is proposed, which achieves any prescribed mean waiting time under stationary conditions in the GI|G_n|1 queue. Mean waiting times for customers of each type are obtained for the HM|G_n|1 and GI|HM_n|1 queues. A polynomial-time algorithm is described to determine the parameters of the queueing discipline given the mean waiting times.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 97–101, November–December, 1991.     

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG = (V, E) with ¦E¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k ²¦V¦^1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k ³¦V¦^3/2,k ²¦V¦²}).The first author was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of the Ministry of Education, Science and Culture of Japan and by the subvention to young scientists by the Research Foundation of Electrotechnology of Chubu.     

Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.     

Some explicit formulas for mixed exponential service systems

We present some explicit formulas for queue length and waiting time distributions of customers in the M/HE_m/1 queue. The formulas are obtained with the aid of roots of quadratic, cubic, and quartic polynomials constructed from a recurrence equation. With an example, we demonstrate that the formulas for queueing distributions are extremely accurate, while the corresponding infinite history M/GI/1 recurrence equation is not. Applications include computation of queueing distributions, accurate tail probabilities, and in systems where exponentiality can be replaced by hyperexponentiality. The explicit solutions are easier to use than the problem-specific partial fraction expansions of the Pollachek-Khinchin transform.     

Analysis of GI/M/s/c queues using uniformisation

We combine uniformisation, a powerful numerical technique for the analysis of continuous time Markov chains, with the Markov chain embedding technique to analyze GI/M/s/c queues. The main steps of the proposed approach are the computation of

• (1)the mixed-Poisson probabilities associated to the number of arrival epochs in the uniformising Poisson process between consecutive customer arrivals to the system; and
• (2)the conditional embedded uniformised transition probabilities of the number of customers in the queueing system immediately before customer arrivals to the system.

To show the performance of the approach, we analyze queues with Pareto interarrival times using a stable recursion for the associated mixed-Poisson probabilities whose computation time is linear in the number of computed coefficients. The results for queues with Pareto interarrival times are compared with those obtained for queues with other interarrival time distributions, including exponential, Erlang, uniform and deterministic interarrival times. The obtained results show that much higher loss probabilities and mean waiting times in queue may be obtained for queues with Pareto interarrival times than for queues with the other mentioned interarrival time distributions, specially for small traffic intensities.     

Queue length analysis of batch arrival queues under bilevel threshold control with early set-up

The queue length process of M^X/G/1 queues under bilevel threshold control and early set-up withlwithout server vacations is outlined. The stationary probability generating functions of the queue length distributions under a unified framework are also derived. Also derived are the mean queue length of each system.     

On the efficiency of maximum-flow algorithms on networks with small integer capacities

The performance of maximum-flow algoirthms that work in phases is studied as a function of the maximum arc capacity,C, of the network and a quantity we call thetotal potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tightO(min{C ^1/3¦V¦^2/3,P ^1/2, ¦V¦}) upper bound on the number of phases. AnO(min{P log¦V¦,C¦V¦^3/2, ¦V¦²¦E¦}) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on ¦V¦ and ¦E¦ alone. We present an application of our bounds to the maximum subgraph density problem.     

A pseudoconservation law for a time-limited service polling system with structured batch poisson arrivals

We consider a cyclic-service queueing system (polling system) with time-limited service, in which the length of a service period for each queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then proceeds to the next queue. The customer whose service is interrupted due to the timer expiration is attended according to the nonpreemptive service discipline. For the cyclic-service system with structured batch Poisson arrivals (M^x/G/1) and an exponential timer, we derive a pseudoconservation law and an exact mean waiting time formula for the symmetric system.     

Maximum Remaining Service Time in Infinite-Server Queues

We study the maximum remaining service time in infinite-server queues of type M|G|∞ (at a given time and in a stationary regime). The following cases for the arrival flow rate are considered: (1) time-independent, (2) given by a function of time, (3) given by a random process. As examples of service time distributions, we consider exponential, hyperexponential, Pareto, and uniform distributions. In the case of a constant rate, we study effects that arise when the average service time is infinite (for power-law distribution tails). We find the extremal index of the sequence of maximum remaining service times. The results are extended to queues of type M^X|G|∞, including those with dependent service times within a batch.     

A faster approximation algorithm for the Steiner problem in graphs

Summary We present an algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The set V-S is traditionally denoted as Steiner vertices. The total distance on all edges of this Steiner tree is at most 2(1–1/l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(¦E¦log¦V¦) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph. It improves dramatically on the best previously known bound of O(¦S¦¦V¦²), unless the graph is very dense and most vertices are Steiner vertices. The essence of our algorithm is to find a generalized minimum spanning tree of a graph in one coherent phase as opposed to the previous multiple steps approach.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T.J. Watson Research Center.On leave from: Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6380, D-7500 Karlsruhe, Federal Republic of Germany     

Queueing analysis and optimal control of and systems

We first consider a finite-buffer single server queue where arrivals occur according to batch Markovian arrival process (BMAP). The server serves customers in batches of maximum size ‘b’ with a minimum threshold size ‘a’. The service time of each batch follows general distribution independent of each other as well as the arrival process. We obtain queue length distributions at various epochs such as, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue length, mean waiting time, probability of blocking, etc. have been obtained. Total expected cost function per unit time is also derived to determine the optimal value N^* of N at a minimum cost for given values of a and b. Secondly, we consider a finite-buffer single server queue where arrivals occur according to BMAP and service process in this case follows a non-renewal one, namely, Markovian service process (MSP). Server serves customers according to general bulk service rule as described above. We derive queue length distributions and important performance measures as above. Such queueing systems find applications in the performance analysis of communication, manufacturing and transportation systems.     

On a single server queue with two-stage heterogeneous service and deterministic server vacations

We analyse a single server queue with Poisson arrivals, two stages of heterogeneous service with different general (arbitrary) service time distributions and binomial schedule server vacations with deterministic (constant) vacation periods. After first-stage service the server must provide the second stage service. However, after the second stage service, he may take a vacation or may decide to stay on in the system. For convenience, we designate our model as M/G ₁, G ₂/D/1 queue. We obtain steady state probability generating function of the queue length for various states of the server. Results for some particular cases of interest such as M/E_{k 1} , E_{k 2} /D/1, M/M ₁, M ₂/D/1, M/E _k /D/1 and M/G ₁, G ₂/1 have been obtained from the main results and some known results including M/E_k /1 and M/G/1 have been derived as particular cases of our particular cases.     

Approximating queue lengths inM(t)/G/1 queue using the maximum entropy principle

Using the discrete time approach a model is developed for obtaining the expected queue length of theM(t)/G/1 queue. This type of queue occurs in different forms in transportation and traffic systems and in communications and manufacturing systems. In order to cut down the very high computational efforts required to evaluate the performance measures in such queues by exact methods, the Maximum Entropy Principle is used to approximate the expected queue length which is one of the most commonly used performance measures. A procedure is then developed for reducing the error encountered when this approximation is adopted. The results from this paper will encourage the practitioners to use the appropriate time-varying queueing models when the need arises instead of resorting to very poor approximations.     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.