Closed polling models with failing nodes

Closed polling systems with station breakdowns, under the gated, exhaustive or globally gated services regimes, are studied and analyzed. Multi-dimensional sets of probability generating functions of the system's state are derived. They are further utilized to obtain an approximate solution for the mean number of jobs residing in the system's various queues at polling instants. The analysis is then concentrated on the case of cyclic Bernoulli polling. Explicit formulae for the mean number of jobs, as well as for the expected cycle duration and system utilization, are derived. Comparison of the throughputs of the three regimes concludes the paper. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exponents for the tails of distributions in some polling models

The tail asymptotics of the distribution of the waiting-time W in some polling models is investigated. When this is of the form P[W > ϰ] ∼ αϰ^βe ^-ηϰ for some α,β,η, we show how to calculate the exponents β and η, and we establish the extent and form of their dependence on the distributions of the service-time and switchover-time. The exponents are expressed in terms of the fixed points and Lyapunov exponents of a dynamical system which we associate with the recursion which is used to calculate the moment generating functions of the waiting time. This revised version was published online in June 2006 with corrections to the Cover Date.     

Monotonicity and stability of periodic polling models

This paper deals with the stability of periodic polling models with a mixture of service policies. Customers arrive according to independent Poisson processes. The service times and the switchover times are independent with general distributions. The necessary and sufficient condition for the stability of such polling systems is established. The proof is based on the stochastic monotonicity of the state process at the polling instants. The stability of only a subset of the queues is also analyzed and, in case of heavy traffic, the order of explosion of the queues is given. The results are valid for a model with set-up times, and also when there is a local priority rule at the queues.This work was supported in part by a Fellowship of the Netherlands Organization for Scientific Research NWO-ECOZOEK.     

Ergodicity of a polling network

The polling network considered here consists of a finite collection of stations visited successively by a single server who is following a Markovian routing scheme. At every visit of a station a positive random number of the customers present at the start of the visit are served, whereupon the server takes a positive random time to walk to the station to be visited next. The network receives arrivals of customer groups at Poisson instants, and all customers wait until served, whereupon they depart from the network. Necessary and sufficient conditions are derived for the server to be able to cope with the traffic. For the proof a multidimensional imbedded Markov chain is studied.     

Threshold start-up control policy for polling systems

A threshold start-up policy is appealing for manufacturing (service) facilities that incur a cost for keeping the machine (server) on, as well as for each restart of the server from its dormant state. Analysis of single product (customer) systems operating under such a policy, also known as the N-policy, has been available for some time. This article develops mathematical analysis for multiproduct systems operating under a cyclic exhaustive or globally gated service regime and a threshold start-up rule. It pays particular attention to modeling switchover (setup) times. The analysis extends/unifies existing literature on polling models by obtaining as special cases, the continuously roving server and patient server polling models on the one hand, and the standard M/G/1 queue with N-policy, on the other hand. We provide a computationally efficient algorithm for finding aggregate performance measures, such as the mean waiting time for each customer type and the mean unfinished work in system. We show that the search for the optimal threshold level can be restricted to a finite set of possibilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

A discrete model of a large polling system

For a network with Poisson incoming flow of customers (particles) and unit time of the motion of servers (annihilators), we obtain the limit distribution of the number of customers at the node for a fixed general number of nodes.     

Stability conditions for a pipeline polling scheme in satellite communications

This paper considers the unknown stability conditions of a pipeline polling scheme proposed for satellite communications. This scheme is modelled as a cyclic-service system with limited service and reservation. The walk times and the maximum number of services to be performed during each polling are dependent on the queue lengths of the stations. The main result is the derivation of the necessary and sufficient stability conditions of the system. Our approach is to map the multi-dimensional stability problem into many 1-dimensional stability problems through the concept of the least stable queue. The least stable queue is one that will become unstablefirst when the system load increases in some parameter region. The stability of the least stable queue thus implies stability of the system. The stability region for the whole system is then the union of the queue stability regions of all the least stable queues that are obtained through dominant systems and Loynes' theorem. We also propose a computable sufficient condition that is tighter than the existing result and present some numerical results.     

Ergodicity of a polling network with an infinite number of stations

A Markov polling system with infinitely many stations is studied. The topic is the ergodicity of the infinite-dimensional process of queue lengths. For the infinite-dimensional process, the usual type of ergodicity cannot prevail in general and we introduce a modified concept of ergodicity, namely, weak ergodicity. It means the convergence of finite-dimensional distributions of the process. We give necessary and sufficient conditions for weak ergodicity. Also, the “usual” ergodicity of the system is studied, as well as convergence of functionals which are continuous in some norm. This revised version was published online in June 2006 with corrections to the Cover Date.     

The polling system with a stopping server

This paper analyzes the polling system in which, unlike nearly all previous studies, the server comes to a stop when the system is empty rather than continuing to cycle. The possibility of server stopping permits a rich variety of alternatives for server behavior; we consider threestopping rules, governing server behavior when the system is emptied, and twostarting rules, governing server behavior when an arrival occurs to an idle system. The Laplace-Stieltjes Transforms and means for the waiting time andserver return time (the interval from an arrival at an unserved queue until the server returns to that queue) are determined. For the special case of zero changeover times and strictly cyclic service, explicit results are obtained.     

Benders decomposition for a class of variational inequalities

This paper examines Benders decomposition for a useful class of variational inequality (VI) problems that can model, e.g., economic equilibrium, games or traffic equilibrium. The dual of the given VI is defined. Benders decomposition of the original VI is derived by applying a Dantzig–Wolfe decomposition procedure to the dual of the given VI, and converting the dual forms of the Dantzig–Wolfe master and subproblems to their primal forms. The master problem VI includes a new cut at each iteration, with information from the latest subproblem VI, which is solved by fixing the “difficult” variables at values determined by the previous master problem. A scalar parameter called the convergence gap is calculated at each iteration; a negative value is equivalent to the algorithm making progress in that the last master problem solution is made infeasible by the new cut. Under mild conditions, the convergence gap approaches zero in the limit of many iterations. With a more restrictive condition that still admits many useful models, a zero value of the convergence gap implies that the master problem has found a solution of the VI. A small model of competitive equilibrium of three commodities in two regions serves as an illustration.     

Relating polling models with zero and nonzero switchover times

We consider a system ofN queues served by a single server in cyclic order. Each queue has its own distinct Poisson arrival stream and its own distinct general service-time distribution (asymmetric queues), and each queue has its own distinct distribution of switchover time (the time required for the server to travel from that queue to the next). We consider two versions of this classical polling model: In the first, which we refer to as the zero-switchover-times model, it is assumed that all switchover times are zero and the server stops traveling whenever the system becomes empty. In the second, which we refer to as the nonzero-switchover-times model, it is assumed that the sum of all switchover times in a cycle is nonzero and the server does not stop traveling when the system is empty. After providing a new analysis for the zero-switchover-times model, we obtain, for a host of service disciplines, transform results that completely characterize the relationship between the waiting times in these two, operationally-different, polling models. These results can be used to derive simple relations that express (all) waiting-time moments in the nonzero-switchover-times model in terms of those in the zero-switchover-times model. Our results, therefore, generalize corresponding results for the expected waiting times obtained recently by Fuhrmann [Queueing Systems 11 (1992) 109—120] and Cooper, Niu, and Srinivasan [to appear in Oper. Res.].Research supported in part by the National Science Foundation under grant DDM-9001751.     

A functional central limit theorem for a class of urn models

We construct an independent increments Gaussian process associated to a class of multicolor urn models. The construction uses random variables from the urn model which are different from the random variables for which central limit theorems are available in the two color case.     

A new algorithm for decomposition of graphical models

In this paper, we combine Leimer’s algorithm with MCS-M algorithm to decompose graphical models into marginal models on prime blocks. It is shown by experiments that our method has an easier and faster implementation than Leimer’s algorithm.     

A stability criterion via fluid limits and its application to a polling system

We introduce a generalized criterion for the stability of Markovian queueing systems in terms of stochastic fluid limits. We consider an example in which this criterion may be applied: a polling system with two stations and two heterogeneous servers. This revised version was published online in June 2006 with corrections to the Cover Date.     

An index heuristic for transshipment decisions in multi-location inventory systems based on a pairwise decomposition

In multi-location inventory systems, transshipments are often used to improve customer service and reduce cost. Determining optimal transshipment policies for such systems involves a complex optimisation problem that is only tractable for systems with few locations. Consequently simple heuristic transshipment policies are often applied in practice. This paper develops an approximate solution method which applies decomposition to reduce a Markov decision process model of a multi-location inventory system into a number of models involving only two locations. The value functions from the subproblems are used to estimate the fair charge for the inventory provided in a transshipment. This estimate of the fair charge is used as the decision criterion in a heuristic transshipment policy for the multi-location system. A numerical study shows that the proposed heuristic can deliver considerable cost savings compared to the simple heuristics often used in practice.     

Solving two-stage stochastic programming problems with level decomposition

We propose a new variant of the two-stage recourse model. It can be used e.g., in managing resources in whose supply random interruptions may occur. Oil and natural gas are examples for such resources. Constraints in the resulting stochastic programming problems can be regarded as generalizations of integrated chance constraints. For the solution of such problems, we propose a new decomposition method that integrates a bundle-type convex programming method with the classic distribution approximation schemes. Feasibility and optimality issues are taken into consideration simultaneously, since we use a convex programming method suited for constrained optimization. This approach can also be applied to traditional two-stage problems whose recourse functions can be extended to the whole space in a computationally efficient way. Network recourse problems are an example for such problems. We report encouraging test results with the new method.      

A decomposition algorithm for quadratic programming

A decomposition algorithm using Lemke's method is proposed for the solution of quadratic programming problems having possibly unbounded feasible regions. The feasible region for each master program is a generalized simplex of minimal size. This property is maintained by a dropping procedure which does not affect the finiteness of the convergence. The details of the matrix transformations associated with an efficient implementation of the algorithm are given. Encouraging preliminary computational experience is presented.     

A decomposition algorithm for limiting average Markov decision problems

We consider a Markov decision process (MDP) under average reward criterion. We investigate the decomposition of such MDP into smaller MDPs by using the strongly connected classes in the associated graph. Then, by introducing the associated levels, we construct an aggregation-disaggregation algorithm for the computation of an optimal strategy for the original MDP.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.