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
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
Ö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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |
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
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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |
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.
| Back to home page | Program | Parallel sessions |