PROGRAM
Abstracts presentations phd students
DRAGUT, ANDREEA
Department of Operations Planning and Control
Faculty of Technology Management
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
a.b.dragut@tm.tue.nl
http://www.tm.tue.nl/vakgr/lbs/dragut.htm
Supervisors
Bertrand/Zijm
Title
Optimal Design Task Allocation with Workload Constraints
Abstract
In the industry today, more and more interest is placed in the organization of the product development process, and the use of advanced operational
research techniques to achieve quality and time optimality. This process is often structured hierarchically, with management teams and an
engineering team. One of the models on which emphasis has been placed in the last
years by numerous researchers is the radical/experiential model, where technologically new products have to be designed and put to
manufacturing lines, in short time and with high quality. In this work we deal with the detailed planning level of such a
hierarchy. The problem at this level is the optimal allocation of a given set of
design tasks, with stochastic solving times, and with no precedence constraints.
They should be performed by the engineers, during a time interval called short-time planning horizon. This is an allocation problem involving
people, and, through stochastic parameters, we model some of their characteristics
(as workload). We also model the design task by assigning them a value and viewing them as collections of activities, which are the unit of work.
In its generality, the problem requires the allocation of each task to either a unique engineer or to none, in order to maximize the value of the
allocated ones minus the utility of the left out ones, subject to workload constraints
for each engineer, and with no precedence constraints between the tasks.
In some sense, the design task allocation problem we focus on is also linked to multiple choice knapsack problems. However, for our problem, the
stochasticity and the fact that to each engineer we can assign more than one design task changes the setting quite substantially. The first feature
of the problem does not allow a mixed-integer formulation of the problem, while the second one changes dramatically the structure of partial solutions
to be eliminated. Under the condition that to each engineer we can assign one and
only one design task, the concepts of IP or DP infeasibility and dominance allow the development of more efficient algorithms. Here we solve this
optimization problem through recursive best first search proving that we find an optimal feasible allocation whenever there exists one. We also
discuss its efficiency, and present experimental results.
HUISMAN, DENNIS
Econometric Institute
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
huisman@few.eur.nl
http://www.few.eur.nl/few/people/huisman
Supervisors
Dekker/Wagelmans
Title
A dynamic approach to vehicle scheduling
Abstract
This paper presents a dynamic approach to the vehicle scheduling
problem. The vehicle scheduling problem (VSP) is one of the main scheduling
problems of a public transport company. It can be defined as follows: given a
set of trips, find a minimum cost schedule for the vehicles such that all trips
are assigned to exactly one vehicle and every vehicle schedule is a feasible
sequence of trips, while starting and ending in its own depot.
In this paper, we discuss the potential benefit of our dynamic approach
compared to the traditional one, where the vehicle scheduling problem is solved
only once for a whole period and the travel times are assumed to be fixed. In
our approach, we solve a sequence of optimization problems, where we take into
account different scenarios for future travel times. Because in the
multiple-depot case we cannot solve the problem exactly within reasonable
computation time, we use a ''cluster-reschedule'' heuristic where we first
assign trips to depots by solving the static problem and then solve dynamic
single-depot problems. We use new mathematical formulations of these problems
that allow a fast solution by standard optimization software. We report on the
results of a computational study with real life data, in which we compare
different variants of our approach and perform a sensitivity analysis with
respect to deviations of the actual travel times from the estimated ones.
IVANESCU, VIRGINIA CRISTINA
Department of Operations Planning and Control
Faculty of Technology Management
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
c.v.ivanescu@tm.tue.nl
Supervisors
Bertrand/Fransoo
Title
Makespan estimation in batch process industries when processing times are
uncertain.
Abstract
Batch process industries are characterized by complex precedence relationship between operations which renders the estimation of an
acceptable workload very difficult. We propose a regression based model to estimate the makespan of a set of jobs in a batch process shop. We
extend earlier work which has been based on deterministic processing times by considering
Erlang-distributed processing times in our model. This regression-based model is further used to support aggregate decision
making such as customer order acceptance. Three order acceptance policies are compared in this paper: a scheduling
policy, a workload policy and a regression based policy. The performances of these order acceptance policies are compared by means of simulation
experiments. The results indicate that the differences in performance between the regression based policy and the scheduling policy are not
very large in situations with high variety in the job mix and high uncertainty in
the processing times.
KUIJPERS, BART
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
b.kuijpers@berfin.unimaas.nl
Supervisors
Kolen/Schotman
Title
Branch-and-Bound type method for lattice based mortgage valuation with partial prepayments.
Abstract
We discuss a solution method for European mortgage valuation problems using a lattice approach. A lattice is a recombining tree describing scenario paths, which only contains t+1 states of the world in period t, opposed to a non-recombining tree
containing 2t states at time t. In case of European mortgages optimal prepayment behaviour is constrained as only a prepayment of a fixed
percentage of the initial loan is allowed every calendar year. Because of this constraint the mortgage value does not only depend on the state of the world,
but also on the scenario path followed to reach that particular state. Therefore the standard solution method would be a non-recombining tree
approach. We transformed such approach to a more efficient lattice approach, which enables us to handle considerably larger problems. We apply a
branch-and-bound type method to represent the prepayment decisions and to construct smaller valuation problems given that some decisions have already
occurred.
LOUVEAUX, QUENTIN
UCL - Louvain-la-Neuve
Voie de Roman Pays 34
1348 Louvain-la-Neuve
Belgium
Visiting Eindhoven University of Technology (Stougie) and Utrecht University (Aardal)
qlouveau@win.tue.nl
Supervisor
Wolsey
Title
Combining problem structure and basis reduction to solve a class of hard integer programs
Abstract
Recently Aardal, Hurkens and Lenstra have succesfully solved some small difficult equality constrained integer programs by using basis reduction to reformulate the problem as inequality constrained integer programs in a different space. In this talk, we adapt their method to solve larger programs that have special structure. More formally, we look at problems of the form XA=C, BX=C. The main topic of the talk is the study of the homogeneous version, i. e. the study of the lattice L = {XA=0 BX=0}. It is shown that an integer basis of L can be obtained by taking the
Kronecker product of vectors from integer bases of two smaller lattices. Furthermore the resulting basis is a reduced basis if the integer bases of the two small lattices are reduced bases and a suitable ordering is chosen.
MAINEGRA HING, MARISELA
Department of Operations Methods and System Theory
Faculty of Technology and Management
University of Twente
P.O. Box 217
7500 AE Enschede
m.mainegrahing@sms.utwente.nl
Supervisor
Van Harten
Title
Order Acceptance under uncertainty with AI techniques
Abstract
Order Acceptance (OA) is one of the main functions in a business control framework. Basically, OA involves for each order a 0/1 (i.e., reject / accept) decision. Traditionally this problem is solved as follows: always accept an order if
sufficient capacity is available. However, always accepting an order when capacity is available could unable the system to accept more convenient orders in the future. Another important aspect is the availability of information to the
decision-maker. Generally in the literature information regarding negotiation with the customer (e.g., estimate of the work content of an order, a norm for the necessary processing time, the price and the due date) and a model of the production
process are assumed to be known or estimated. However sometimes it is difficult to obtain such information.
We use a stochastic modeling approach using Markov decision theory and learning methods from Artificial Intelligence techniques in order to deal with uncertainty and long-term decisions in OA. Reinforcement Learning (RL) is
a quite new approach that already combines this idea of modeling and solution method. There are some aspects that make RL appealing to our problem. The idea of learning without the necessity of complete model information and the
possibility of learning even from delayed rewards allows us to consider different degrees of uncertainty and to take into account the opportunity cost problem in a natural way. Here we report on solutions for some OA models.
MEERTENS, MARC
Department of Mathematics
Catholic University Nijmegen
Toernooiveld 1
6525 ED Nijmegen
meertens@sci.kun.nl
Supervisors
Potters/Tijs
Title
Envy-free and Pareto efficient allocations in economies with indivisible goods and
money.
Abstract
We consider the problem of allocating an inheritance of one ore more indivisible goods among a fixed number of agents, when
monetary compensations are allowed. Each agent has an appreciation for the goods and the amount of
money. We assume the preferences of the agents to be continuous, strictly monotonic in money and to
satisfy the so called `Archimedian property'. The main question is: `How should the goods be divided and
how much money do the agents have to pay or receive such that the inheritance is fairly divided?' Our first
normative concept is `no-envy'. Under an allocation is no envy if no agent strictly prefers the bundle,
consisting of a number of goods and an amount of money, of anyone else to his own. Later on we
consider a second normative concept: `Pareto efficiency and no-envy'. An allocation is Pareto efficient if
no agent can improve himself without disadvantaging the other agents. We will prove the existence of
envy-free allocations, but we will give an example in which the set of envy-free allocations and the set of
Pareto efficient allocations are disjoint. Furthermore we will give two conditions, each sufficient for the
existence of envy-free and Pareto efficient allocations.
VAN NORDEN, LINDA
Department of Decision and Information Sciences
Rotterdam School of Management
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
l.norden@fac.fbk.eur.nl
Supervisors
Van Nunen/Van de Velde
Title
Minimizing total completion time in a two-machine flowshop
Abstract
We
analyze the NP-hard problem of minimizing total completion time in the
two-machine flow shop. This problem looks deceivingly simple, but state-of-the
art algorithms cannot even solve all randomly generated instances with 30 jobs.
This poor performance is due to the lack of strong lower bounds. The best lower
bounds thus far, which require O(n3) time, show an average relative
gap of about 1.8% between optimal solution value and lower bound, where n is the
number of jobs.
Our goal is to compute as strong as possible lower bounds in polynomial time. We
present a new integer linear programming formulation for the problem, of which
the linear programming relaxation gives very strong lower bounds. The linear
program has O(n2) variables and O(n) constraints and shows an average
relative gap of only 0.8%. We design an effective branch-and-bound algorithm
that makes selective use of the lower bounds and insights developed in this
paper.
SITTERS, RENÉ
Department Mathematics and Computer Science
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
r.a.sitters@tue.nl
http://www.win.tue.nl/~sitters
Supervisors
Stougie/Lenstra
Title
The complexity of the traveling repairman problem
Abstract
In the traveling repairman problem we are given a finite set of points and a
travel time between any two of them and we wish to find a tour through them
which minimizes the sum of the arrival times in the points. This routing
problem is well known in operations research but has lately also been
studied for its applications in computer networks. Imagine for example that
some agent moves through a network searching for information that is equally
likely to be in any of the points. Then the problem of finding a tour that
minimizes the expected search time is exactly the traveling repairman
problem. The problem has a reputation for being much harder than the
traveling salesman problem and its currently best approximation ratio for
general metric spaces is 7.11. We prove that even for edges-weighted trees
the problem is NP-hard. Notice that the traveling salesman problem is
trivial in this case.
ZERGUINI, LOUCIF
Department of Computer Science
Faculty of Mathematics and Computer Science
Eindhoven University of Technology
P.O. Box 513
5600 MB Eindhoven
l.zerguini@tue.nl
Supervisors
Van der Aalst/Van Hee
Title
Computation of response time distribution in workflows
Abstract
Because a process definition is the blueprint of a Business process, it is vitally important that it contains no grave errors. The process should be designed in such a way that the
response time is kept as small as possible. A severe limitation to Petri net modeling is the very large size of resulting nets, especially when dealing with real
systems at a detailed level. In a practical setting there are workflows consisting of more than 100 tasks with a very complex interaction structure.
For the designer of such workflows the complexity is overwhelming and communication with end-users using huge diagrams is difficult. Hence, it is
only natural to look into model reduction and modular design. In most cases hierarchical decomposition is used to tackle this problem. In this paper, we will exploit the peculiarities
of the topology of the network specifying any workflow in order to implement an efficient algorithm based on successive reductions of a Petri net to determine
the response time distribution. We discuss besides the use of Non-Markovian stochastic Petri nets in the context of performance analysis of a workflow.
Stochastic Petri nets are an established tool for modeling and analyzing processes. This type of estimate can assist designers of workflow management
system in delivering efficient support to business processes.
|
