Abstracts presentations phd students

BRITO, MARISA DE
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
debrito@few.eur.nl

Supervisor
R. Dekker

Title
Product returns in inventory control: an emperical study

Abstract
Already for a long time, companies take back products as part of their marketing strategy, where products in good condition go back to inventory. Furthermore, environmental consciousness, legal and economic forces have brought more attention to systems with reverse flows, and to its control. From a modelling perspective, one of the consequences of reverse flows is the loss of monotonicity of inventory levels between replenishments of new products. That is, the inventory level does not only decrease because of demand but it also may increase in case of returns. Since this makes the analysis much more difficult than traditional inventory control, authors use simplifying assumptions regarding the return process. These assumptions typically are 1) the demand is a homogeneous Poisson process; 2) the return flow is similarly a homogeneous Poisson process, and 3) the return process is independent of the demand process. However, there is nearly no (scientific) literature on empirical analysis of data with reverse flows. Thus, we present a methodology to check empirically the common assumptions on the inventory modelling literature concerning the demand and return processes. Moreover, we apply it to real data and we discuss practical implications of our findings, for instance relatively to information management on inventory systems with returns. The data to be used concerns inventory transactions, both purchases and returns, in the warehouse of the European Organization for Nuclear Research (CERN).
 

BUMB, ADRIANA
Department of Discrete Mathematics, Operations Research and Statistics
Faculty of Applied Mathematics
University of Twente
P.O. Box 217
7500 AE Enschede
a.f.bumb@math.utwente.nl
http://www.math.utwente.nl/dos/bumb.htm

Supervisors
U. Faigle and W. Kern

Title
An approximation algorithm for the 2-level uncapacitated facility location problem

Abstract
We present an approximation algorithm for the maximization version of the two level uncapacitated facility location problem.The problem can be described as follows.There are two types of facilities to be built:one type of depots and one type of transit stations.Each unit of demand must be shipped from a depot through a transit station to the demand points.The goal is to decide simultaneously which facilities to open and how to assign the clients to the open facilities, such that the total profit is maximized. The main idea of the algorithm is to reduce the problem to a special case of MAX SAT, for which an approximation algorithm based on randomized rounding is presented.
 

GRIGORIEV, ALEXANDER
Operations Research Group
Department of Quantitative Economics
Faculty of Economics abd Business Administration
University of Maastricht
P.O. Box 616
6200 MD Maastricht
a.grigoriev@ke.unimaas.nl

Supervisors
A.W.J. Kolen/Y. Crama/J. van de Klundert

Title
Throughput Rate Optimization in High Multiplicity Sequencing Problems

Abstract
In mixed model assembly systems products or parts of different types are being assembled in certain ratios. A minimal part set is a smallest possible set of product type quantities, to be called the multiplicities, in which the numbers of assembled products of the various types are in the desired ratios. It is common practice to repeatedly input the minimal part set into the assembly system, where the products of each of the minimal part set are fed into the system in a same sequence. Such a sequencing strategy is expected to yield a good line balance and low inventories. Very little is known however regarding the resulting throughput rate, in particular in comparison to the throughput rates attainable by other input strategies. In general, other strategies can be described by considering the same problem with modified multiplicities yielding the same ratios, as they can be obtained by multiplying the multiplicities by a same number. In this work, we investigate the relationship between throughput rates and the multiplicities for two basic sequencing problems, namely, the traveling salesman problem and the no-wait flowshop scheduling problem. We will investigate and answer questions such as: What is the possible loss of throughput that results from inputing minimal part sets? What are the smallest multiplicities for which the minimal  throughput rate is the lowest possible? What are the smallest multiplicities for which an optimal input sequence has the same structure as the overall optimal, but possibly infinitely long, input sequence? Our analysis uses well known concepts from scheduling theory and combinatorial optimization.
 
 

HUITZING, HIDDO
Faculty of Psychological, Pedagogical and Sociological Sciences
Groningen University
Grote Rozenstraat 15
9712 TG Groningen
h.a.huitzing@ppsw.rug.nl
http://www2.ppsw.rug.n/~beukema/persoon/hiddo.html

Supervisors
W.K. Klein Haneveld/Timminga

Title
Detecting, Pinpointing and Analyzing of Infeasibility of Linear Programming Test Assembly Models using Data Sampling and Set Covering

Abstract
In this paper it shown how Set Covering (SC) methods can be used in the pre-analysis of linear programming (LP) models for test assembly (LPTA) models. The focus will be on the LPTA models. Use of SC and data sampling to analyze infeasibility was first suggested by Feng (personal communication, 2000). While SC can in a first  step help to detect feasibility or infeasibility, its power lies in pinpointing causes of infeasibility such as Irreducible Infeasible Sets of constraints (IIS), Maximal Feasible Subsets of constraints (MFS) and Minimal Cardinality IIS Set Covers (MCISC) of the original infeasible LPTA model. Timminga & Adema (1996), Timminga (1998), van der Linden (1998) and Huitzing (2000), among others, have presented means to detect infeasibility in LPTA models and described methods to resolve infeasibility, actually adjusting the model constraints minimizing “loss”, where "loss" is to be defined beforehand. First, a short introduction to the theory and its possible applications to LPTA models is given. Second, a simulation study, using data sampling, of the power of SC in detecting, pinpointing and analysis of infeasibility in LPTA models is presented. Third, the practical advantages and shortcomings of SC are explored.
 

KOVALEVA, SOFIA
Department of Mathematics
Maastricht University
P.O. Box 616
6200 MD Maastricht
s.kovaleva@math.unimaas.nl

Supervisor
F. Spieksma

Title
Approximation algorithms for an interval packing and covering problem

Abstract
Consider a grid consisting of rows and columns. Intervals are placed at arbitrary positions on each row, each interval having a nonnegative integral weight and integral length. A nonnegative integral capacity is  associated to each row and to each column. The packing problem is to specify a multiplicity for each interval maximizing total weight while the sum of multiplicities of intervals that share each column or row does not exceed the given capacity. The covering problem is to specify a multiplicity for
each column and row minimizing total weight while the sum of the multiplicities that stab each interval is not below its weight. These MAX-SNP-hard problems arise in project scheduling, admission control and DNA sequencing. Their linear relaxations  constitute a primal-dual pair of problems.  We  prove an approximative min-max result for the case of unit weights and that of unit capacities. We get a 1/2-approximation algorithm for the packing problem and 2-approximation algorithm for the covering
problem.
 
 

LISTES, OVIDIU
Econometric Institute
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
listes@few.eur.nl
http://www.few.eur.nl/few/people/listes

Supervisor
R. Dekker

Title
Stochastic solutions vs. scenario analysis for product recovery network design

Abstract
For product recovery network design under uncertainty a strategic location model is presented. We use data from a real case on recycling sand from demolition waste in The Netherlands. The model is extended using stochastic programming techniques to account for the uncertainties in demand and supply. Computational results for two-stage and three-stage variants are presented. The interpretation of the results is meant to give more insight into decision-making under uncertainty for reverse logistics.
 
 

LITVAK, NELLY
EURANDOM
Eindhoven University of Technology
Building LG
P.O. Box 513
5600 MB Eindhoven
n.litvak@tue.nl

Supervisor
J.Wessels

Title
Order picking in carousel systems operating under the Nearest Item heuristic

Abstract
A carousel (or paternoster) is an automated warehousing system consisting of a large number of drawers rotating in a closed loop in either direction. Such systems are mostly used for storage and retrieval of small and medium sized goods, which are requested moderately often. The picker has a fixed position in front of the carousel, which rotates the required items to the picker.
An important performance characteristic is the travel time needed to pick a list of items. In this presentation we study the travel time under the Nearest Item (NI) heuristic, where the next item to be picked is always the nearest one. This simple algorithm is frequently used in real warehouses. We first give a tight upper bound for the travel time under the NI heuristic. Then we present an exhaustive analysis of the travel time assuming that the required items are uniformly distributed on the carousel.
 
 

PEETERS, LEON
Rotterdam School of Management
Room F1-2
Erasmus University Rotterdam
P.O. Box 1738
3000 DR Rotterdam
lpeeters@fbk.eur.nl

Supervisors
J.A.E.E. van Nunen/L. Kroon

Title
Optimization for Cyclic Railway Timetabling

Abstract
Many European railway companies operate a cyclic timetable in which trains leave every hour at the same time from a certain station for a certain direction. In the Netherlands, NS Reizigers and Railned are currently using a constraint-propagation algorithm called to search for feasible railway timetables. We present an optimization model for cyclic railway timetabling that provides an extension of this feasibility model, which is based on Periodic Event Scheduling. The optimization model enables one to (i) search for a timetable that is optimal, and (ii) to gain insight into the necessary changes to an infeasible instance, by allowing a penalized violation of the constraints. We use a mixed integer programming formulation for the problem, where the integer variables correspond to cycles in the graph induced by the constraints. A heuristic for constructing a good cycle basis is presented. Furthermore we propose preprocessing procedures that considerably reduce the size of problem instances. The usefulness of both the formulation and the preprocessing procedures is illustrated by the application of the model to the Dutch Intercity train network for several objective functions, e.g. minimizing travelers' waiting time, maximizing timetable robustness, and minimizing the number of trains needed to operate the timetable.
 
 

POP, PETRICA
Department of Discrete Mathematics, Operations Research and Statistics
Faculty of Applied Mathematics
University of Twente
P.O. Box 217
7500 AE Enschede
ppop@math.utwente.nl

Supervisor
U. Faigle

Title
Relaxation Methods for the Generalized Minimum Spanning Tree Problem

Abstract
We consider the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose nodes are partitioned into clusters, the GMSTP is then to find a minimum-cost tree which includes exactly one node from each cluster. It is known that the GMSTP is an NP-hard problem and even finding a near optimal solution is also an NP-hard problem. We introduce several mixed integer programming formulations of the problem and examine the polyhedra defined by the linear programming relaxations of these formulations. Based  on a new formulation of the GMST problem we give a heuristic solution, a lower bound procedure, an upper bound procedure and discuss the advantages of our approach in comparizon with an earlier method.
 
 

POPOV, NICOLAI
Department of Mathematics
University of Leiden
P.O. Box 9512
2300 RA Leiden
popov@math.leidenuniv.nl

Supervisors
A. Hordijk/F.M.Spieksma

Title
Large deviation principle for a transient deflected two-dimensional random walk on the nonnegative integers

Abstract
Click here  for the postscript file.
 
 

SLEPTCHENKO, ANDREI
Faculty of Technology & Management
Operation Methods and System Theory
University of Twente
P.O. Box 217
7500 AE Enschede
a.sleptchenko@sms.utwente.nl

Supervisor
A. van Harten

Title
On multi-class multi-server queueing and spare parts management

Abstract
Multi-class multi-server queuing problems are a generalization of the well-known M/M/k situation to arrival processes with clients of N types that require exponentially distributed service with different averaged service time. Problems of this sort arise naturally in various applications, such as spare parts management, for example. Here we are going to present a procedure to construct exact solutions of the stationary state equations, and to illustrate it with numerical results."
 
 

SMITS, SANNE
Faculty of Technology Management
Eindhoven University of Technology
Paviljoen E6
P.O. Box 513
5600 MB Eindhoven
s.r.smits@tm.tue.nl

Supervisor
A.G. de Kok

Title
Approximations for the waiting time in (s,nQ)-inventory models for different type of consolidation policies

Abstract
 The coordination of the inventory managemment and the transportation management is crucial for an efficient management of the supply chain.Transportation management includes the application of different types of shipment consolidation policies. The consolidation policy coordinates the shipment processes of different ccustomer orders for the same (intermediate) destination at the warehouse, and this can lead to a reduction in the transport costs.
Shipment consolidation implies that two or more customer orders are combined such that a larger quantity can be dispachted on the same vehicle. We distinguish between two types of consolidation policy. The "quantity" policy, which dispatches the orders when a given quantity is consolidated. The "time" policy, which dispatches the orders when the shipping date is expired.
In this paper we assume that customer orders originate from customer warehouses.
Each customer warehouse control multiple product inventories according to (s,nQ)-policies. I.e. whenever the inventory level drops below the reorder level s, a quantity nQ is ordered such that the inventory position is raised to a level between s and s+Q.
The focus of the paper is on the determination of the customer order lead time behaviour. The waiting time due to c
In the inventory control the lead times play an important role. The waiting time due to the consolidation of the shipment is included in the lead time. A change in the shipping date for the "time" policy or a change in the shipped quantity for the "quantity" policy leads to a change in the lead times and hence this leads to a re-evaluation of variables in the inventory control to keep the same service degree.
In this paper, we will derive approximations for the lead time behaviour in a multi- echelon (s,nQ)-inventory models when the products are shipped according to different types of consolidation policies. The derived approximations are tested through extensive computer simulation.
A further step in this research will be to find close to optimal values for the batchsizes and the shipping date in the "time" policy and close to optimal values for the batchsizes and the shipped quantity in the "quantity" policy.
 
 

UITERT, MIRANDA VAN
CWI - Center for Mathematics and Computer Science
Department PNA 2
P.O. Box 94079
1090 GB Amsterdam
e-mail  : miranda@cwi.nl

Supervisor
S.C. Borst

Title
Generalized Processor Sharing Queues with Heterogeneous Traffic Classes

Abstract
We consider a queue fed by a mixture of light-tailed and heavy-tailed traffic. The two traffic flows are served in accordance with the Generalized Processor Sharing (GPS) discipline. GPS-based scheduling algorithms, such as Weighted Fair Queueing (WFQ), have emerged as an important mechanism for achieving service differentiation in integrated networks.
We analyze the asymptotic behavior of the workload distribution of the light-tailed traffic flow under the assumption that its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload of the light-tailed flow is bounded above by that in an isolated system, which consists of the light-tailed flow served in isolation at a constant rate equal to its GPS weight.
We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the presence of the heavy-tailed flow. The pre-factor represents the probability that the heavy-tailed flow is backlogged long enough for the light-tailed flow to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.