
Abstracts 
Saturday, 2 July 2005
Sunday, 3 July 2005 
8:30 am 
Continental Breakfast / Discussion

9:30 am 
Erik
Winands, Technische Universiteit
Eindhoven
A TwoQueue Model with Alternating
Limited Service and StateDependent Setups
We consider a twoqueue model with statedependent setups,
i.e., a setup is incurred for a queue only when it is nonempty,
in which the single server serves the highpriority queue
exhaustively and the lowpriority queue according
to the klimited service strategy. Under this klimited
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 twofold. The first
one is applicationoriented. In particular, in many stochastic
multiproduct singlecapacity maketostock production systems
considerable setup times are incurred, i.e., the socalled
stochastic economic lot scheduling problem (SELSP).
A second motivation for the present work is the fact that,
so far, hardly any exact results for multiqueue systems
with the klimited service policy have been obtained.
For general k, an exact evaluation is only available
for very few special twoqueue 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 twoitem
singlecapacity production system.
This is joint work with I.J.B.F. Adan and
G.J. van Houtum.

10:00 am 
Maria
Vlasiou, Technische Universiteit
Eindhoven
On a nonincreasing Lindleytype
equation
We shall talk about an alternating service model that is
described by the Lindleytype equation $W=\max\{0, B  A
 W\}.$ The most striking characteristic or this equation
is that it is a nonincreasing monotone function in its
main argument $W.$ Our main goal is to derive a closedform
expression of the steadystate 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.

10:30 am 
Break / Discussion 
11:30 am 
Bram Kranenburg, Technische Universiteit Eindhoven
Cost optimization in the (S1,S) lost sales inventory model with priority demand classes
We consider a singleitem singlelocation 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 onebyone.
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 GeertJan van Houtum.

12:00 pm 
Paul
Enders, Technische Universiteit
Eindhoven
A Mixed LostSales 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 endusers. 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 machinedown 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.

12:30 pm 
Lunch 
2:00 pm 
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 herdinglike effect.
This is joint work with Christine Parlour
and Uday Rajan.

2:30 pm 
GeertJan 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 multiitem 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 LotSizing Problem, and he has just started a
project with BASF where they have this problem in their practice.

3:00 pm  5:00 pm 
Carnegie Mellon / Eindhoven Collaborative Center Discussion


Sunday, 3 July 2005 Saturday, 2 July 2005 
8:30 am 
Continental Breakfast / Discussion

9:30 am 
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 delaydifferential equation. We analyze this equation in detail;
in particular we show convergence to a simple fixedpoint 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).

10:00 am 
Urtzi
Ayesta, Centrum voor Wiskunde en
Informatica
Mean Delay Analysis of Multilevel
Processor Sharing
Multilevel ProcessorSharing (MLPS) scheduling disciplines
permit to model a wide variety of nonanticipating 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 flowlevel
performance in the Internet, a simple twoclass classification
(mice and elephants) might be sufficient.

10:30 am 
Break / Discussion 
11:30 am 
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 HarcholBalter.

12:00 pm 
Alan
SchellerWolf, Carnegie Mellon University
Simple Formula for Analysis of Alternating
Load Queues
We consider a FIFO M/M/1 queue operating in a timevarying 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, closedform, 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 nontime 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, closedform expressions for the mean system time. (Work is ongoing for higher moments of system time.)
We find closedform 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).

12:30 pm 
Lunch 
3:00 pm 
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).

3:30 pm 
Nicola Secomandi, Carnegie Mellon University
An Analysis of the Control Algorithm Resolving 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 wellknown dynamicprogramming
curseofdimensionality makes it computationally prohibitive to solve
them exactly. An alternative solution approach, called here the
controlalgorithm 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 resolving the MP and
updating the parameters of the decision rules with the newly obtained
solution. The controlalgorithm resolving issue arises when one
reflects on the consequences of this updating: Does the performance of
the control algorithm really improve by revising its decisionrule
instantiation with the solution of the resolved MP, or should rather
the prior solution be used? The paper develops a theory of
controlalgorithm resolving for a class of finitehorizon dynamic
resource allocation problems, that includes problems of production,
distribution, and demand management, and applies it to control
algorithms for problems of multiproduct maketoorder production,
freightrailcar distribution, and network revenue management.

4:00 pm  5:00 pm 
Continuation of Center Discussion and WrapUp

Back to Carnegie Mellon / Technische Universiteit Eindhoven Collaborative Workshop
