Mixed parallel processors with interdependent blocking

This paper studies a system of parallel service facilities or processors with mixed exponential and non-exponential queues, a non-exponential finite source input and interdependent arrival as well as departure blocking such as due to a common pool or shared resource. A concrete invariance condition upon the blocking protocol is provided. Under this condition the stationary busy source distribution is shown to be of an insensitive product form. The result unifies and extends known product form results as will be illustrated by several examples.     

Equivalence of Lyapunov stability criteria in a class of Markov decision processes

We are concerned with Markov decision processes with countable state space and discrete-time parameter. The main structural restriction on the model is the following: under the action of any stationary policy the state space is acommunicating class. In this context, we prove the equivalence of ten stability/ergodicity conditions on the transition law of the model, which imply the existence of average optimal stationary policies for an arbitrary continuous and bounded reward function; these conditions include the Lyapunov function condition (LFC) introduced by A. Hordijk. As a consequence of our results, the LFC is proved to be equivalent to the following: under the action of any stationary policy the corresponding Markov chain has a unique invariant distribution which depends continuously on the stationary policy being used. A weak form of the latter condition was used by one of the authors to establish the existence of optimal stationary policies using an approach based on renewal theory.This research was supported in part by the Third World Academy of Sciences (TWAS) under Grant TWAS RG MP 898-152.     

Interconnected networks of queues with randomized arrival and departure blocking

In this paper, we study two interconnected multiclass non-exponential queueing networks. Jobs can jump from one cluster to another, but subject to randomized blocking depending on the class occupancies. Such systems naturally arise in communication networks, like Metropolitan Area Networks. We present sufficient conditions for the existence of a product form equilibrium distribution under both the recirculate and the stop blocking protocol. A number of examples are given.     

A survey of product form queueing networks with blocking and their equivalences

Queueing network models have been extensively used to represent and analyze resource sharing systems, such as production, communication and information systems. Queueing networks with blocking are used to represent systems with finite capacity resources and with resource constraints. Different blocking mechanisms have been defined and analyzed in the literature to represent distinct behaviors of real systems with limited resources. Exact product form solutions of queueing networks with blocking have been derived, under special constraints, for different blocking mechanisms. In this paper we present a survey of product form solutions of queueing networks with blocking and equivalence properties among different blocking network models. By using such equivalences we can extend product form solutions to queueing network models with different blocking mechanisms. The equivalence properties include relationships between open and closed product form queueing networks with different blocking mechanisms.This work has been partially supported by CNR Project Research Funds Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo and by MURST Project Research Funds Performability hw/sw di sistemi distribuiti e paralleli.     

Linear programming formulation of MDPs in countable state space: The multichain case

We present an Linear Programming formulation of MDPs with countable state and action spaces and no unichain assumption. This is an extension of the Hordijk and Kallenberg (1979) formulation in finite state and action spaces. We provide sufficient conditions for both existence of optimal solutions to the primal LP program and absence of duality gap. Then, existence of a (possibly randomized) average optimal policy is also guaranteed. Existence of a stationary average optimal deterministic policy is also investigated.     

Derman’s book as inspiration: some results on LP for MDPs

In 1976 I was looking for a suitable subject for my PhD thesis. My thesis advisor Arie Hordijk and I found a lot of inspiration in Derman’s book (Finite state Markovian decision processes, Academic Press, New York, 1970). Since that time I was interested in linear programming methods for Markov decision processes. In this article I will describe some results in this area on the following topics: (1) MDPs with the average reward criterion; (2) additional constraints; (3) applications. These topics are the main elements of Derman’s book.     

On Jackson's product form with ‘jump-over’ blocking

It is shown that Jackson's product form is retained for queueing networks with capacity constraints under the assumption of a ‘jump-over’ blocking protocol.     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

Local balance in queueing networks with positive and negative customers

This paper investigates to what extent a recently developed new product form result for queueing networks with positive and negative customers fits into the class of product form queueing networks that satisfy a notion of partial or local balance. As such, this paper investigates whether this new product form is still a consequence of an appropriate notion of local balance. To this end, a new and non-standard type of local balance is introduced as an extension of standard local balance. This new type of local balance appears more restrictive and is no longer directly sufficient for global balance. Nevertheless, based on this new type of local balance, some extensions such as blocking phenomena for queueing networks with positive and negative customers can be concluded.     

Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers

This paper presents new mixed integer programming formulations for scheduling of a flexible flow line with blocking. The flexible flow line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. The line produces several different product types and each product must be processed by, at most, one machine in each stage. A product which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine a production schedule for all products so as to complete the products in a minimum time. The basic mixed integer programming formulations have been enhanced to model blocking scheduling with alternative processing routes where for each product a set of routes is available for processing. A reentrant flow line where a product visits a set of stages more than once is also considered. Numerical examples are presented to illustrate applications of the various models proposed.     

Blackwell optimality in the class of stationary policies in Markov decision chains with a Borel state space and unbounded rewards

This paper is the first part of a study of Blackwell optimal policies in Markov decision chains with a Borel state space and unbounded rewards. We prove here the existence of deterministic stationary policies which are Blackwell optimal in the class of all, in general randomized, stationary policies. We establish also a lexicographical policy improvement algorithm leading to Blackwell optimal policies and the relation between such policies and the Blackwell optimality equation. Our technique is a combination of the weighted norms approach developed in Dekker and Hordijk (1988) for countable models with unbounded rewards and of the weak-strong topology approach used in Yushkevich (1997a) for Borel models with bounded rewards.     

The G/M/1 queue revisited

The G/M/1 queue is one of the classical models of queueing theory. The goal of this paper is two-fold: (a) To introduce new derivations of some well-known results, and (b) to present some new results for the G/M/1 queue and its variants. In particular, we pay attention to the G/M/1 queue with a set-up time at the start of each busy period, and the G/M/1 queue with exceptional first service. Dedicated to Arie Hordijk on his 65th birthday, in friendship and admiration.     

Denumerable semi-Markov decision chains with small interest rates

In this paper we investigate denumerable state semi-Markov decision chains with small interest rates. We consider average and Blackwell optimality and allow for multiple closed sets and unbounded immediate rewards. Our analysis uses the existence of a Laurent series expansion for the total discounted rewards and the continuity of its terms. The assumptions are expressed in terms of a weighted supremum norm. Our method is based on an algebraic treatment of Laurent series; it constructs an appropriate linear space with a lexicographic ordering. Using two operators and a positiveness property we establish the existence of bounded solutions to optimality equations. The theory is illustrated with an example of aK-dimensional queueing system. This paper is strongly based on the work of Denardo [11] and Dekker and Hordijk [7].This research has partially been sponsored by the Netherlands Organization for Scientific Research (NWO).     

Monotonicity and error bounds for networks of Erlang loss queues

Networks of Erlang loss queues naturally arise when modelling finite communication systems without delays, among which, most notably are

1. classical circuit switch telephone networks (loss networks) and
2. present-day wireless mobile networks.

Performance measures of interest such as loss probabilities or throughputs can be obtained from the steady state distribution. However, while this steady state distribution has a closed product form expression in the first case (loss networks), it does not have one in the second case due to blocked (and lost) handovers. Product form approximations are therefore suggested. These approximations are obtained by a combined modification of both the state space (by a hypercubic expansion) and the transition rates (by extra redial rates). It will be shown that these product form approximations lead to

• upper bounds for loss probabilities and
• analytic error bounds for the accuracy of the approximation for various performance measures.

The proofs of these results rely upon both monotonicity results and an analytic error bound method as based on Markov reward theory. This combination and its technicalities are of interest by themselves. The technical conditions are worked out and verified for two specific applications:

• pure loss networks as under (i)
• GSM networks with fixed channel allocation as under (ii).

The results are of practical interest for computational simplifications and, particularly, to guarantee that blocking probabilities do not exceed a given threshold such as for network dimensioning.     

On the blocking process in queue networks

The blocking process in some particular exponential open queue networks is studied. The networks are in the form of two-stage and three-stage queue networks with finite intermediate waitingroom. FIFO scheduling is assumed. Blocking occurs when the flow of units through one queue is momentarily stopped owing to a capacity limitation of another queue have been reached. Exact and approximate bounds for the mean blocking time in these networks are obtained. The condition for stability in the two-stage networks is also derived. Finally the applicability of the results obtained is demonstrated through a case study.     

Blocking pairs of polyhedra arising from network flows

A study is made of blocking pairs of polyhedra (blocking pairs of matrices) that arise in (or can be transformed into) a network flow context. For example, the blocking polyhedron of the polyhedron generated by all integral feasible flows in a capacity-constrained supply-demand network (where all the data are integral) is explicitly determined, and a simple algorithm is described for solving the associated integral packing problem. Applications of these results to k-ways in directed graphs, to (0, 1)-matrices with prescribed row and column sums, and to flow arborescences are described.     

Blocking Probabilities in Mobile Communications Networks with Time-Varying Rates and Redialing Subscribers

Call-blocking probabilities are among the key performance measures in mobile communications networks. For their analysis, mobile networks can be modelled as networks of Erlang loss queues with common capacity restrictions dictated by the allocation of frequencies to the cells of the network. However, due to the time-varying load offered to the cells of such networks, blocking probabilities usually cannot be obtained in closed form. The relation between networks of Erlang loss queues and networks of infinite server queues, for which the time-dependent occupancy distribution is multidimensional Poisson, suggests to use that distribution as approximate distribution for the network of Erlang loss queues. This paper extends this so-called Modified Offered Load (MOL) approximation to networks of Erlang loss queues, and also allows subscribers that find their call blocked to redial to continue their call. For GSM networks operating under Fixed Channel Allocation, it is shown that blocking probabilities are increasing in the redial rates so that the MOL approximation that is most accurate for maximal redial rates turns out to be fairly accurate for the resulting upper bound for blocking probabilities. The accuracy is explicitly evaluated in an application of the results towards blocking probabilities in a hot spot travelling along a road through a GSM network.     

Exact analysis of queueing networks with multiple job classes and blocking-after-service

Two models of closed queueing networks with blocking-after-service and multiple job classes are analyzed. The first model is a network withN stations and each station has either type II or type III. The second model is a star-like queueing network, also called a central server model, in which the stations may have either type I or type IV, with the condition that the neighbors of these stations must be of type II or type III such that blocking will be caused only by this set of station types. Exact product form solutions are obtained for the equilibrium state probabilities in both models. Formulae for performance measures such as throughput and the mean number of jobs are also derived.This work was supported by the National Science Foundation (NSF) under Grant No. CCR-90-11981.     

Markovian network processes: Congestion-dependent routing and processing

A Markovian network process describes the movement of discrete units among a set of nodes that process the units. There is considerable knowledge of such networks, often called queueing networks, in which the nodes operate independently and the routes of the units are independent. The focus of this study, in contrast, is on networks with dependent nodes and routings. Examples of dependencies are parallel processing across several nodes, blocking of transitions because of capacity constraints on nodes, alternate routing of units to avoid congestion, and accelerating or decelerating the processing rate at a node depending on downstream congestion. We introduce a general network process representing the numbers of units at the nodes and derive its equilibrium distribution. This distribution takes the form of a product of functions of vectors in which the arguments of the functions satisfy an interchangeability property. This new type of distribution may apply to other multi-variate processes as well. A basic idea in our approach is a linking of certain micro-level balance properties of the network routing to the processing rates at the nodes. The link is via routing-balance partitions of nodes that are inherent in any network. A byproduct of this approach is a general characterization of blocking of transitions without the restriction that the process is reversible, which had been a standard assumption. We also give necessary and sufficient conditions under which a unit moving in the network sees a time average for the unmoved units (called the MUSTA property). Finally, we discuss when certain flows between nodes in an open network are Poisson processes.This research was sponsored in part by Air Force Office of Scientific Research contract 84-0367.     

On the existence of a cooperative solution for a coalitional game with externalities

This paper analyzes a game in coalitional form that is derived from a simple economy with multilateral externalities. Following Chander and Tulkens (1997) we assume that agents react to a blocking coalition by choosing individual best reply strategies. A non-empty core of this game is established by showing that the game is balanced. The proof relies only on standard convexity assumptions and, therefore, substantially generalizes the results in Chander and Tulkens (1997). Received June 2000/Revised version March 2001