PROGRAM
Abstracts presentations phd students
DOBBER, MENNO
Faculty of Mathematics & Computer Science
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
amdobber@few.vu.nl
http://www.math.vu.nl/~amdobber
Supervisor
Koole
Title
Dynamic load balancing for a grid application
Abstract
Grids functionally combine globally distributed computers and
information systems for creating a universal source of computing power
and information. A key characteristic of grids is that resources (e.g.,
CPU cycles and network capacities) are shared among numerous
applications, and therefore, the amount of resources available to any
given application highly fluctuates over time. In this paper we analyze
the impact of the fluctuations in the processing speed on the
performance of grid applications. Extensive lab experiments show that
the burstiness in processing speeds has a dramatic impact on the
running times, which heightens the need for dynamic load balancing
schemes to realize good performance. Our results demonstrate that a
simple dynamic load balancing scheme based on forecasts via exponential
smoothing is highly effective in reacting to the burstiness in
processing speeds.
GOOSSENS, DRIES
Department of Applied Econometrics
Katholieke Universiteit Leuven
Naamsestraat 69
B-3000 Leuven
dries.goossens@econ.kuleuven.ac.be
Supervisor
Spieksma
Title
Exact algorithms for procurement problems under a total quantity
discount structure
Abstract
In this paper, we study the procurement problem faced by a buyer who
needs to purchase a variety of goods from suppliers applying a
so-called total quantity discount policy. This policy implies that
every supplier announces a number of volume intervals and that the
volume interval in which the total amount ordered lies determines the
discount. Moreover, the discounted prices apply to all goods
bought from the supplier, not only to those goods exceeding the volume
threshold. We refer to this cost-minimization problem as
the total quantity discount (TQD)
problem. We give a mathematical
formulation for this problem and argue that not only it is NP-hard, but
also that there exists no polynomial-time
approximation algorithm with a constant ratio (unless P=NP).
Apart from the basic form of the TQD
problem, we describe three
variants. In a first variant, the market share that one or more
suppliers can obtain is constrained. Another variant allows the buyer
to procure more goods than strictly needed, in order to
reach a lower total cost. In a third variant, the number of winning
suppliers is limited. We show that the TQD problem and its
variants can be solved by solving a series of min-cost flow problems.
Finally, we investigate the performance of three exact
algorithms (min-cost flow based branch-and-bound, linear programming
based branch-and-bound, and branch-and-cut) on
randomly generated instances involving 50 suppliers and 100 goods. It
turns out that even the large instances of the basic problem
are solved to optimality within a limited amount of time. However, we
find that different algorithms perform best in terms of
computation time for different variants.
HEUVEL, WILCO VAN DEN
Econometric Institute
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
wvandenheuvel@few.eur.nl
Supervisor
Wagelmans
Title
The economic lot-sizing problem with
remanufacturing options
Abstract
We consider an extension of the classical economic lot sizing (ELS)
problem. In the classical ELS problem a manufacturer has a know demand
for a fixed number of periods. This demand has to be satisfied such
that total costs are minimized. The costs consist of a fixed setup cost
for
manufacturing, unit manufacturing cost and unit holding cost. We
consider an extension of the ELS problem where there is also a
remanufacturing option. We call this the ELS problem with
remanufacturing options (ELSR). In this problem there is a known number
of returned items in each period. The returned items may be held in
stock or may be remanufactured to satisfy (future) demand. So demand
can
be satisfied by both manufacturing or remanufacturing. If returned
items are remanufactured, a setup cost and unit remanufacturing cost
are
incurred. We consider two versions of the ELSR problem: 1) there is a
joint setup cost for manufacturing and remanufacturing and 2) there is
a
separate setup cost for both manufacturing and remanufacturing. We will
show that the first problem can be solved in polynomial time. However,
the second problem will be shown to be NP-hard.
HUSSLAGE, BART
Department of Econometrics & Operations Research
Tilburg University
P.O. Box 90153
5000 LE Tilburg
b.g.m.husslage@uvt.nl
http://center.uvt.nl/phd_stud/husslage/
Supervisors
Aarts, Den Hertog and Van Dam
Title
Maximin Latin hypercube designs in two dimensions
Abstract
The problem of finding a maximin Latin hypercube design (LHD) in two
dimensions can be described as positioning n rooks on an nxn chessboard
such that the rooks do not attack each other, and such that the minimal
distance between pairs of rooks is maximized. Maximin LHDs are
important for the approximation and optimization of black box
functions. The LHD structure is used to avoid collapsingness. In this
talk general
formulas are derived for maximin LHDs for general n, and when the
distance measure is Linf or L1. Furthermore, for L2 we obtain maximin
LHDs for n upto 70 and
approximate maximin LHDs for other values of n. We show that the
reduction in the maximin distance caused by imposing the LHD structure
is little. This
justifies the use of maximin LHDs instead of unrestricted designs.
KAMPSTRA, PAUL
Department of Econometrics & Operations Research
Tilburg University
P.O. Box 90153
5000 LE Tilburg
kampstra@uvt.nl
http://center.uvt.nl/phd_stud/kampstra/main
Supervisor
Ashayeri
Title
Coping with uncertainties at distribution centers
Abstract
Shifts in distribution strategies show that distributors buy as little
stock as possible or even buy as they sell. While inventories are
reduced, at the same time supply chain response is increasingly
important. The combination is a challenging situation where the order
fulfillment process is under high pressure. It is necessary to
eliminate the uncertainties that are currently affecting the order
fulfillment process. We point out that uncertainty is created within
the organization, i.e. functional silos like sales, purchasing and
logistics, and outside the organization, i.e. customers or suppliers.
Demand uncertainty is characterized by limited advance knowledge on
orders, and incomplete order placement. Supply uncertainty features
unpredictability of arrival times, and unpredictability of products and
quantities available. We developed a conceptual planning and control
tool in cooperation with some flower exporters that experience high
degrees of uncertainty. Currently, we are gathering company data for
testing and simulation. The concept is simple: there are four decision
layers linked together: namely, resources planning, system supervision,
operational plan, and real-time response. What makes this decision
support system interesting is the interaction between real-time
information and the operational planning. As information is gathered in
real-time format, a set of heuristical procedures mixed with
forecasting techniques plans all distribution centre resources and
capacities for current and future periods.
LE DUC, THO
Rotterdam School of Management
Erasmus University Rotterdam
P.O. Box 1738
3062 PA Rotterdam
tleduc@fbk.eur.nl
Supervisor
de Koster
Title
Storage zone optimization for
class-based manual-pick warehouses
Abstract
Order picking has been considered as the most critical operation in
warehousing. Recent trends in logistics
demand faster but more reliable order picking systems. The efficiency
of an order picking process greatly depends on the storage policy used,
i.e. where products are located within the warehouse. In this study, we
deal with the most popular storage policy that is
class-based (or ABC) storage strategy. Particularly, we investigate the
problem of determining the optimal storage boundaries (zones) of
classes in each aisle for manually operated warehouses. We first
propose a probabilistic model that enables us to estimate the average
travel distance of a picking tour. We found that the differences
between results obtained from simulation and the model were slight.
Using the average travel distance as the objective function, we present
a mathematical formulation for the storage zone optimisation problem.
However, the exact approach can handle only small size warehouse
instances. To circumvent this obstacle, we propose a heuristic for the
problem. Numerical examples we conducted show that the heuristic
performs fairly well.
LOK, REINDER
Faculty of EW & B
Maastricht University
P.O. Box 616
6200 MD Maastricht
r.lok@ke.unimaas.nl
Supervisor
Romero Morales
Title
Parametric shortest path tree problem
Abstract
We consider a complete directed graph with a source node. The length of
an arc (i,j) is defined as the scalar product of an arc-dependent
vector c(i,j) and an unknown node-dependent vector x. The problem is to
choose the vectors x, within certain bounds, such that the weighted sum
of the shortest paths originating from the source node is maximized.
The parametric shortest path tree problem relates to the literature on
parametric flow problems. However, in these problems the parameter is a
scalar and is usually the same for all arcs allowing thus an easy
description of the optimal objective value of the problem as a function
of the parameter.
Once we fix the vectors x, the problem reduces to the well-known
shortest path tree model. A straightforward formulation of the problem
will have an objective function defined by shortest path lengths. In a
similar fashion as in Pallottino and Scutellà (1997), we provide
a linear programming formulation of the parametric shortest path tree
problem. We present a combinatorial primal-dual algorithm. In this
algorithm we iteratively fix the shortest path tree and search for the
best vectors xj. If the obtained solution is not optimal for the
original problem we will step into a new shortest path tree.
POT, AUKE
Faculty of Mathematics & Computer Science
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
sapot@few.vu.nl
Supervisor
Koole
Title
Approximating multi-skill blocking systems by hyperexponential
decomposition
Abstract
We consider multi-class blocking systems in which jobs require a
single processing step.
There are groups of servers that can each serve a different subset of
all job classes.
The assignment of jobs occurs according to some fixed overflow policy.
We are interested in the blocking probabilities of each class.
This model can be used for call centers, tele-communication and
computer networks.
An approximation method is presented that takes the burstiness of the
overflow processes into account.
This is achieved by assuming hyperexponential distributions of the
inter-overflow times.
The approximations are validated with simulation and we make a
comparison to existing approximation methods.
The overall blocking probability turns out to be approximated with high
accuracy by several methods.
However, the individual blocking probabilities per class are
significantly more accurate for the method that is introduced in this
paper.
QUANT, MARIEKE
Department of Econometrics & Operations Research
Tilburg University
P.O. Box 90153
5000 LE Tilburg
m.quant@uvt.nl
Supervisor
Borm
Title
Congestion network situations and related games
Abstract
Congestion situations arise in various economic situations in which a
group of agents uses facilities and the costs of these facilities
depend on the number of users. Situations particularly suitable for
studying congestion effects are operations research problems. We
introduce network problems with congestion effects and analyze them
from a cooperative game theoretic perspective. For convex cost
functions the corresponding congestion network game turn out to be
balanced. Furthermore an algorithm, based on a shortest path algorithm,
to compute optimal networks is provided. If cost functions are concave,
then the corresponding game does not necessarily have core elements,
but contrary to the convex congestion situation, there always exists
optimal tree networks.
ÖZEN, ULAS
Department of Technology Management
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
u.ozen@tm.tue.nl
Supervisors
Fransoo, Norde and Slikker
Title
Cooperation between multiple newsvendors with warehouses
Abstract
This study considers a supply chain that consists of n retailers, each
of them facing a newsvendor problem, m warehouses and a supplier. The
retailers are supplied with a single product via some warehouses. In
these warehouses, the ordered amounts of goods of these retailers
become available after some lead time. At the time that the goods
arrive at the warehouses, demand realizations are known by the
retailers. The retailers can increase their expected joint profits by
coordinating their orders and making allocations after demand
realization. For this setting, we consider an associated cooperative
game between the retailers. We show that this associated cooperative
game has a nonempty core. Finally, we study a variant of this game,
where the retailers are allowed to leave unsold goods at the
warehouses.
SCHAKEL, LOLKE
Faculty of Economics
Groningen University
P.O. Box 800
9700 AV Groningen
l.p.schakel@eco.rug.nl
Supervisors
Sierksma and Ghosh
Title
Optimal cabling of the LOFAR radio telescope
Abstract
LOFAR is a revolutionary radio telescope consisting of 76 sensor
stations to be located in a five-armed spiral structure in the
Netherlands. LOFAR (Low Frequency Array) is specifically designed to
operate at the lowest radio frequencies from the electromagnetic
spectrum. Its main purpose is to study celestial objects and to analyze
astronomical processes so that a better understanding can be obtained
from the origins of our universe.
We consider the combined network design and routing problem of the
LOFAR radio telescope. The 76 sensor stations are located in the
scenery and connected by means of fiber optic cables. The complexity of
the problem is due to the possibility of leasing or buying up cables
from telecom companies and cable providers. Since these existing cables
have a significant cost advantage, it is advisable to utilize the
existing infrastructure as much as possible.
The problem is formulated as an instance of the Steiner problem in
graphs, and heuristically solved by means of constructive heuristics
and local search techniques.
SELÇUK, BARIŞ
Department of Technology Management
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
b.selcuk@tm.tue.nl
Supervisors
de Kok and Fransoo
Title
The effect of updating lead times on the performance of hierarchical
planning systems
Abstract
In this study, our concern is to show the effect of updating lead times
on the performance of a two level hierarchical planning system. Lead
times are updated by taking periodic feedbacks of the most recent
information from the production environment and using this information
in estimating lead times for planning the future production orders. A
simulation model is used based on a multi stage production planning and
scheduling environment where the components are manufactured in a
general job shop, and final products are manufactured in a flow shop.
Our results demonstrate that under certain conditions frequent updates
of lead times will lead to uncontrolled production system with erratic
and very long lead times.
SIEM, ALEX
Department of Econometrics & Operations Research
Tilburg University
P.O. Box 90153
5000 LE Tilburg
a.y.d.siem@uvt.nl
Supervisors
Den Hertog and de Klerk
Title
Positive, increasing and convex
polynomials for meta-modelling
Abstract
Polynomials are widely used to model the input-output behaviour of
computer
simulations. Often, it is known beforehand, that the computer
simulations
have certain properties. It could be e.g. known that the output is
positive,
increasing or convex as a function of the input. However, commonly used
meta-models may not inherit these properties automatically. We present
some
methodology (using semidefinite optimization and robust optimization)
to
construct polynomials that conserve these properties.
SOOMER, MAARTEN
Faculty of Mathematics & Computer Science
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
mjsoomer@cs.vu.nl
Supervisor
Koole
Title
An optimisation model for airport taxi scheduling
Abstract
A mixed-integer programming formulation to represent the movement of
aircraft on the surface of the airport will be presented. In the
optimal
schedule delays due to taxi conflicts are minimised. Implementation
issues for solving this optimisation problem will be treated.
Numerical results with real data of Amsterdam Airport Schiphol
demonstrate that the algorithms lead to significant improvements of the
efficiency with reasonable computational effort.
Co-authors paper: J.W. Smeltink, P.R. de Waal and R.D. van der Mei.
TURKENSTEEN, MARCEL
Faculty of Economics
Groningen University
P.O. Box 800
9700 AV Groningen
m.turkensteen@eco.rug.nl
Supervisor
Sierksma
Title
Tolerances versus costs in Branch and Bound algorithms
Abstract
A combinatorial optimization problem (COP) is the problem of finding an
optimal combination from a set of elements. A large number of COPs is
NP-hard. The search for improvements in exact algorithms remains
important, since it allows us to solve larger and more difficult
instances to optimality. A common method for solving NP-hard problems
is Branch and Bound (B&B), which uses relaxations of the problem.
If a relaxation solution is infeasible for the original problem, then
B&B creates new subproblems by including or excluding elements,
called branching. This procedure is repeated until an optimal solution
is obtained. Currently, the selection of elements to be
included/excluded is done on the base of cost values.
We introduce branching rules and lower bounds based on upper tolerance
values of the relaxation solution. In spite of the fact that it
requires time to calculate tolerances, our computational experiments
show that in most situations tolerance-based algorithms outperform
cost-based algorithms. The solution time reductions are mainly caused
by the fact that the branching process becomes much more effective, so
that optimal solutions are found in earlier stages of the branching
process. The use of tolerances also reveals the rationale behind the
choice for branching on a smallest cycle in assignment solutions.
VLASIOU, MARIA
EURANDOM
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
vlasiou@eurandom.tue.nl
Supervisor
Adan
Title
An alternating service problem
Abstract
We consider a system consisting of a server alternating between two
service points. At both service points there is an infinite queue of
customers that have to undergo a preparation phase before being served.
We are interested in the waiting time of the server. The waiting time
of the server satisfies an equation very similar to Lindley's equation
for the waiting time in the $GI/G/1$ queue. We will analyse this
Lindley-type equation under the assumptions that the preparation phase
follows a phase type distribution while the service times have a
general distribution. If we relax the condition that the server
alternates between the service points, then the model turns out to be
the machine repair problem. Although the latter is a well-known
problem, the distribution of the waiting time of the server has not
been studied yet. We shall derive this distribution under the same
setting and we shall compare the two models numerically. As expected,
the waiting time of the server is on average smaller in the machine
repair problem than in the alternating service system, but they are not
stochastically ordered.
|
