Erik Winands, Technische Universiteit Eindhoven
A Two-Queue Model with Alternating Limited Service and State-Dependent Setups

We consider a two-queue model with state-dependent setups, i.e., a setup is incurred for a queue only when it is non-empty, in which the single server serves the high-priority queue exhaustively and the low-priority queue according to the k-limited service strategy. Under this k-limited strategy the server continues working at a queue until either a predefined number of k customers is served or until the queue becomes empty, whichever occurs first.

The motivation for the present study is two-fold. The first one is application-oriented. In particular, in many stochastic multi-product single-capacity make-to-stock production systems considerable setup times are incurred, i.e., the so-called stochastic economic lot scheduling problem (SELSP). A second motivation for the present work is the fact that, so far, hardly any exact results for multi-queue systems with the k-limited service policy have been obtained. For general k, an exact evaluation is only available for very few special two-queue cases.

In this model, we obtain the transforms of the queue length and sojourn time distributions under the assumption of Poisson arrivals and generally distributed service and setup times. Furthermore, it is shown how the results of this analysis can be applied in the evaluation of a stochastic two-item single-capacity production system.

This is joint work with I.J.B.F. Adan and G.J. van Houtum.

Maria Vlasiou, Technische Universiteit Eindhoven
On a non-increasing Lindley-type equation

We shall talk about an alternating service model that is described by the Lindley-type equation $W=\max\{0, B - A - W\}.$ The most striking characteristic or this equation is that it is a non-increasing monotone function in its main argument $W.$ Our main goal is to derive a closed-form expression of the steady-state distribution of $W.$ In general this is not possible, so we shall state a sufficient condition that allows us to do so. We also examine stability issues, derive the tail behaviour of $W$, and briefly discuss how one can iteratively solve this equation by using a contraction mapping.

Bram Kranenburg, Technische Universiteit Eindhoven
Cost optimization in the (S-1,S) lost sales inventory model with priority demand classes

We consider a single-item single-location model with several demand classes having Poisson demand. For each demand class, a penalty cost is given, which has to be paid for each demand that is not fulfilled (this demand is lost). For each demand class, a critical level is defined. Demand of a particular demand class is only fulfilled if the physical stock is above this critical level. Replenishment is done one-by-one.

For this model, we present two heuristic algorithms that, at given base stock level S, aim to find optimal values for the critical levels. The first algorithm is based on local search and uses an extensive neighborhood structure. The second algorithm considers only one neighbor at a time. In a numerous numerical experiment, both algorithms always find an optimal solution.

We apply methods based on our algorithms to cost optimization problems to find the critical levels and base stock level that minimize inventory holding and penalty costs. We compare the performance of these methods to an existing exact (enumeration) method and an existing heuristic method.

This is joint work with Geert-Jan van Houtum.

Paul Enders, Technische Universiteit Eindhoven
A Mixed Lost-Sales Backordering Inventory Problem with Two Customer Classes

Original Equipment Manufacturers of complex technical systems typically operate a service network of local warehouses which are close to the end-users. One or more central warehouses form the backbone of the service network. Such a central warehouse has to deliver service parts as a replenishment of stock at the local warehouses or as emergency delivery when customers experience a machine-down and the part is not locally available. These two demand flows are considered customer classes.

In this presentation we consider a single stockpoint where a single product is kept on stock. There are two customer classes, class 1 and class 2. Class 1 has the highest priority and demand from this class is lost if it cannot be satisfied from stock. Class 2 has lower priority and demand from this class is backordered as soon as inventory is at or below a critical level. A continuous review basestock policy is used for replenishments.

To evaluate the performance of this policy we develop an exact Markovian evaluation procedure. We also develop an exact optimization algorithm. In a numerical study the performance of this policy is compared with the situation where no differentiation is made.

This is joint work with I.J.B.F. Adan and G.J. van Houtum.

Laurens Debo, Carnegie Mellon University
Herding and Congestion

In this talk, we study the signalling role that a queue can play when there exist uncertainty about the quality of a product or service for which the queue is developed. We consider the situation where each agent arriving to a market has some imperfect, but private information about the quality. The decision whether to buy the product or service (i.e. whether to join the queue) is made based on the private information. The queue length reflects thus to subsequently arriving agents the private information that earlier arriving agents have received. We develop and analyze a model in which agents arrive to a market according to a Poisson process. Service time is exponentially distributed. We analyze steady state equilibrium of the queue that is developed. We show that it may be possible that the number of agents purchasing the product or service increases as the service rate decreases, due the a herding-like effect.

This is joint work with Christine Parlour and Uday Rajan.

Geert-Jan van Houtum, Technische Universiteit Eindhoven
The Use of Queueing Theory in Inventory Problems

In many of my research projects on inventory systems, there is an evaluation problem and an optimization problem. Often, we can apply queueing analysis for the evaluation of a given policy. Sometimes the queueing analysis is standard, but often advanced methods are needed which require that a queueing specialist is involved (think of the work with Andrei Sleptchenko, but we also have it now with Paul Enders). Further, often analytical evaluation is not possible and thus computational evalation procedures are developed. Speed is then very important as the evaluation procedure is a subprocedure in the optimization. The optimization problems may have a continuous or a discrete solution space, and have to do with the optimization of basestock levels and other control parameters. For the optimization problems, we are often faced with new, complicated problems (Bram Kranenburg is faced with these problems for his multi-item spare parts problems).

In short, I see a great connection between queueing theory and inventory problems. The theory on queueing has a long history and is well developed. In the past few years, the queueing theorists have worked a lot on communication networks and this will go on for several more years. This work has a high scientific and practical relevance. I see inventory networks/chains as an other fruitful area where a high scientic and practical relevance can be reached. The area is not really new. What is new however is that several companies are interested in this type of research nowadays. They have better information systems now, and quite some companies realize that they need a more professional approach for their planning problems. We see this increased interest in the area of spare parts (where we work extensively with ASML, and we start new projects with several other companies). Paul and Bram are active in this area. Another example BASF. Erik Winands works on the Stochastic Economic Lot-Sizing Problem, and he has just started a project with BASF where they have this problem in their practice.

Carnegie Mellon / Eindhoven Collaborative Center Discussion

Bert Zwart, Technische Universiteit Eindhoven
Fluid approximation of a processor sharing queue with impatient customers

Motivated by obtaining a better understanding of the impact of reneging (e.g. aborting the download of a webpage) behavior in communication networks, we consider the GI/GI/1 PS queue where customers may leave after a certain amount of time before their service is finished. Under the PS service discipline, such behavior is very undesirable, since it implies that some work is done for nothing.

By considering a fluid scaling, we show that the process describing the number of customers this Processor Sharing queue can be approximated by a delay-differential equation. We analyze this equation in detail; in particular we show convergence to a simple fixed-point equation. This equation enables us to do performance analysis and to obtain approximations for the fraction of customers that reneg and the fraction of waisted bandwidth.

This talk is based on work with Christian Gromoll (Stanford) and Philippe Robert (INRIA).

Urtzi Ayesta, Centrum voor Wiskunde en Informatica
Mean Delay Analysis of Multilevel Processor Sharing

Multilevel Processor-Sharing (MLPS) scheduling disciplines permit to model a wide variety of non-anticipating scheduling disciplines. Such disciplines have recently attracted attention in the context of the Internet as an appropriate flow level model for the bandwidth sharing obtained when priority is given to short TCP connections. In this talk we compare the mean delay in an M/G/1 queue among MLPS disciplines when the hazard rate of the service time distribution is decreasing. Our main result states that, given an MLPS discipline, the mean delay is reduced whenever a level is added by splitting an existing one. By numerical means we quantify the reduction on the mean delay after the addition of levels. We show that the mean delay of an MLPS discipline can get close to the minimum feasible delay (FB) with just a few levels. This supports the claim that in order to improve the flow-level performance in the Internet, a simple two-class classification (mice and elephants) might be sufficient.

Adam Wierman, Carnegie Mellon University
Classifying Scheduling Policies with Respect to Higher Moments of Conditional Response Time

We aim to understand predictability of response times under a range of scheduling policies. We study the conditional variance in response times as seen by jobs of different sizes. We define a metric and a criterion that distinguish between different behaviors of conditional variance, and use these to classify large groups of scheduling policies. Finally we find that cumulant moments offer an excellent metric for studying higher conditional moments of response time across different scheduling policies, due to their beautiful limiting properties.

This is joint work with Mor Harchol-Balter.

Alan Scheller-Wolf, Carnegie Mellon University
Simple Formula for Analysis of Alternating Load Queues

We consider a FIFO M/M/1 queue operating in a time-varying environment: The queue experiences Poisson arrivals and exponential service, at possibly different rates while in each of its two states, which we call “low” and “high”. The duration of low and high states are themselves exponentially distributed (with possibly different rates). Overall the queue is assumed to be stable, although transient overload (in the “high” state) is allowed.

This model can be analyzed via Matrix Analytic Methods or spectral expansion techniques. Unfortunately, neither these (nor any other) methods provide a simple, closed-form, intuitive expression for how mean system time changes with problem parameters. This is our goal: We obtain simple expressions relating the mean system time to a non-time varying M/M/1 queue operating at the average arrival and service rates, modified by a correction term. In general, our expressions involve system primitives, as well as the probabilities of finding zero jobs in system upon a switch to the high (or low) state. We derive effective bounds for these latter probabilities, ultimately achieving simple, yet accurate, closed-form expressions for the mean system time. (Work is ongoing for higher moments of system time.)

We find closed-form expressions for system time in terms of only the primitives for the special cases in which: (i) the arrival rate is zero in the low state (on/off model); (ii) the service rate is zero in one state (breakdown model); or (iii) the arrival rate in the high state tends to infinity while the duration of the high state tends to zero, yielding a finite mean number of arrivals in a high (BMAP model).

Tom van Woensel, Technische Universiteit Eindhoven
Variability in Dynamic Routing Problems

In routing problems, the variability on travel times can not be ignored in order to carry out a realistic optimization. The approach proposed introduces a travel time distribution based on queueing theory resulting in a stochastic dynamic routing problem. The approach allows for evaluating routes on the travel time risk involved. The models are validated using numerical results based on standard datasets.

This is joint work with Christophe Lecluyse (UA), Herbert Peremans (UA), and Nico Vandaele(UA).

Nicola Secomandi, Carnegie Mellon University
An Analysis of the Control Algorithm Re-solving Issue in Dynamic Resource Allocation Problems

Many operations management (OM) problems involve the dynamic allocation of multiple resources to satisfy the stochastic demand for a company's products or services and can be represented as Markov decision process (MDP) models. In most cases, the well-known dynamic-programming curse-of-dimensionality makes it computationally prohibitive to solve them exactly. An alternative solution approach, called here the control-algorithm approach, is to employ a math program (MP) to approximately represent the MDP and use its optimal solution to heuristically instantiate the parameters of the decision rules of a given class of control policies. As new information is observed over time, the control algorithm can incorporate it by re-solving the MP and updating the parameters of the decision rules with the newly obtained solution. The control-algorithm re-solving issue arises when one reflects on the consequences of this updating: Does the performance of the control algorithm really improve by revising its decision-rule instantiation with the solution of the re-solved MP, or should rather the prior solution be used? The paper develops a theory of control-algorithm re-solving for a class of finite-horizon dynamic resource allocation problems, that includes problems of production, distribution, and demand management, and applies it to control algorithms for problems of multiproduct make-to-order production, freight-railcar distribution, and network revenue management.

Continuation of Center Discussion and Wrap-Up