A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

Optimal control of a single server in a finite-population queueing network

We study the optimal dynamic assignment of a single server to multiple stations in a finite-population queueing network. The objective is to maximize the long-run average reward/throughput. We use sample-path comparisons to identify conditions on the network structure and service time distributions under which the optimal policy is an index policy. This index policy assigns the server to the non-empty station where it takes the shortest amount of time (in some stochastic sense) to complete a job. For example, in a network of multiple parallel stations, the optimal policy assigns the highest priority to the fastest station if service times can be ordered in likelihood ratios. Finally, by means of a numerical study, we test the shortest-expected-remaining-service-time policy on parallel-series networks with three stations and find that this index policy either coincides with the optimal policy or provides a near-optimal performance.     

Waiting times in queueing networks with a single shared server

We study a queueing network with a single shared server that serves the queues in a cyclic order. External customers arrive at the queues according to independent Poisson processes. After completing service, a customer either leaves the system or is routed to another queue. This model is very generic and finds many applications in computer systems, communication networks, manufacturing systems, and robotics. Special cases of the introduced network include well-known polling models, tandem queues, systems with a waiting room, multi-stage models with parallel queues, and many others. A complicating factor of this model is that the internally rerouted customers do not arrive at the various queues according to a Poisson process, causing standard techniques to find waiting-time distributions to fail. In this paper, we develop a new method to obtain exact expressions for the Laplace–Stieltjes transforms of the steady-state waiting-time distributions. This method can be applied to a wide variety of models which lacked an analysis of the waiting-time distribution until now.     

A single server queue with cyclically indexed arrival and service rates

In this paper we consider a queueing model that results from at least two apparently unrelated areas. One motivation to study a system of this type results from a test case of a computer simulation factor screening technique calledfrequency domain methodology. A second motivation comes from manufacturing, where due to cyclic scheduling of upstream machines, the arrival process to downstream machines is periodic. The model is a single server queue with FIFO service discipline and exponential interarrival and service times where the arrival and/or service rates are deterministic cyclic functions of the customer sequence number. We provide steady state results for the mean number in the system for the model with cyclic arrival and fixed service rates and for the model with fixed arrival and cyclic service rates. For the model with both cyclic arrival and service rates, upper and lower bounds are developed for the steady state mean waiting time in the system. Throughout the paper various implications and/or insights derived from the results of this study are discussed for frequency domain methodology.The authors acknowledge the financial support of the CBA/GSB Faculty Research Committee of the College of Business Administration, The University of Texas at Austin.     

A single server queueing system with two phases of service subject to server breakdown and Bernoulli vacation

This paper deals with a single server M/G/1 queue with two phases of heterogeneous service and unreliable server. We assume that customers arrive to the system according to a Poisson process with rate λ. After completion of two successive phases of service the server either goes for a vacation with probability p(0 ? p ? 1) or may continue to serve the next unit, if any, with probability q(=1 ? p). Otherwise it remains in the system until a customer arrives. While the server is working with any phase of service, it may breakdown at any instant and the service channel will fail for a short interval of time. For this model, we first derive the joint distribution of state of the server and queue size, which is one of the chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally we obtain some important performance measures and reliability indices of this model.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints

Classical analyses of the dynamic control of multi-class queueing systems frequently yield simple priority policies as optimal. However, such policies can often result in excessive queue lengths for the low priority jobs/customers. We propose a stochastic optimisation problem in the context of a two class M/M/1 system which seeks to mitigate this through the imposition of constraints on the second moments of queue lengths. We analyse the performance of two families of parametrised heuristic policies for this problem. To evaluate these policies we develop lower bounds on the optimum cost through the achievable region approach. A numerical study points to the strength of performance of threshold policies and to directions for future research.     

Controlling arrivals for a queueing system with an unreliable server: Newton-Quasi method

This paper deals with the control policy of a removable and unreliable server for an M/M/1/K queueing system, where the removable server operates an F-policy. The so-called F-policy means that when the number of customers in the system reaches its capacity K (i.e. the system becomes full), the system will not accept any incoming customers until the queue length decreases to a certain threshold value F. At that time, the server initiates an exponential startup time with parameter γ and starts allowing customers entering the system. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. A matrix analytical method is applied to derive the steady-state probabilities through which various system performance measures can be obtained. A cost model is constructed to determine the optimal values, say (F^∗, μ^∗, γ^∗), that yield the minimum cost. Finally, we use the two methods, namely, the direct search method and the Newton-Quasi method to find the global minimum (F^∗, μ^∗, γ^∗). Numerical results are also provided under optimal operating conditions.     

A single server queue in a hard-real-time environment

We consider a single server first in first out queue in which each arriving task has to be completed within a certain period of time (its deadline). More precisely, each arriving task has its own deadline - a non-negative real number - and as soon as the response time of one task exceeds its deadline, the whole system in considered to have failed. (In that sense the deadline is hard.) The main practical motivation for analyzing such queues comes from the need to evaluate mathematically the reliability of computer systems working with real time constraints (space or aircraft systems for instance). We shall therefore be mainly concerned with the analytical characterization of the transient behavior of such a queue in order to determine the probability of meeting all hard deadlines during a finite period of time (the ‘mission time’). The probabilistic methods for analyzing such systems are suggested by earlier work on impatience in telecommunication systems [1,2].     

A logistics problem: a non-markovian queueing network model and algorithm

In this paper, a stochastic version of the classical deterministic balanced single commodity capacitated transportation network problem is presented. In this model, each arc of the network connects a supply node to a demand node and the flow of units forming along each arc of the network forms a stochastic process (i.e.G/M/1 queueing system with generally distributed interarrival time, a Markovian server, a single server, infinite capacity, and the first come first served queueing discipline). In this model, the total transportation cost is minimized such that the total supply rate is equal to the total demand rate, and the resulting probability of finding excessive congestion along each arc (i.e., the resulting probability of finding congestion inside the queueing system formed along each arc in excess of a fixed number) is equal to a desirable value     

Cost analysis of the unloader queueing system with a single unloader subject to breakdowns

In this paper, we deal with an unloader queueing model in which N identical trailers are unloaded by a single unloader. We consider two different types of a single unloader, which are subject to breakdowns. In type 1, the unloader can break down only when there is at least one trailer in the system, while in type 2, the unloader can break down even if no trailers are in the system. Analytic closed-form solutions of the unloader queueing system are derived. A cost model is developed in order to determine the optimal value of the number of trailers to be assigned to the unloader for both types. Under the optimal operating condition, numerical results are presented in which several system performance measures are evaluated based on assumed numerical values given to the system parameters. Sensitivity analysis is also investigated.     

Optimizing flow rates in a queueing network with side constraints

In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.     

Correction to: A probabilistic note on the Cauchy functional equation

Aequationes mathematicae - A formally correct expression at the end of Section 2 is, however, of awkward form, being not what was intended (due to my inattentiveness) and it may confuse a careful...     

Transient solution for a finite capacity M/G a,b /1 queueing system with vacations to the server

In this paper we consider a single server queueing system with Poisson input, general service and a waiting room that allows only a maximum of b customers to wait at any time. A minimum of a customers are required to start a service and the server goes for a vacation whenever he finds less than a customers in the waiting room after a service. If the server returns from a vacation to find less than a customers waiting, he begins another vacation immediately. Using the theory of regenerative processes we derive expressions for the time dependent system size probabilities at arbitrary epochs.     

Maximum entropy analysis to the N policy M/G/1 queueing system with a removable server

We study a single removable server in an M/G/1 queueing system operating under the N policy in steady-state. The server may be turned on at arrival epochs or off at departure epochs. Using the maximum entropy principle with several well-known constraints, we develop the approximate formulae for the probability distributions of the number of customers and the expected waiting time in the queue. We perform a comparative analysis between the approximate results with exact analytic results for three different service time distributions, exponential, 2-stage Erlang, and 2-stage hyper-exponential. The maximum entropy approximation approach is accurate enough for practical purposes. We demonstrate, through the maximum entropy principle results, that the N policy M/G/1 queueing system is sufficiently robust to the variations of service time distribution functions.