|
|
Abstracts presentations phd studentsBIJVANK, MARCO Department of Mathematics
Supervisors Equilibrium probabilities of lost sales inventory systems Abstract Equilibrium probabilities of lost sales inventory systems Abstract: The equilibrium distribution of the inventory on hand enables us to calculate all kinds of performance measures (e.g., service levels, cost objectives). These measures can be used again to find properties of the inventory system or optimal parameter values. During this presentation, we discuss a new technique that can be used to approximate such equilibrium probabilities for lost sales inventory models. We test the technique for different replenishment policies and different demand distributions.
COENE, SOFIE Katholieke Universiteit Leuven
Supervisor Profit-based Latency Problems on the Line Abstract Consider the following problem. Given are a set of n clients located in some metric space and profits pi associated with each client i, i = 1,2,...,n. In addition, a single server is given, positioned at the origin at time t = 0. The server travels at unit speed. If the server serves client i at time t, the revenue collected by the server equals pi - t. The goal is to select clients and to find a route for the server serving the selected clients, such that total collected revenue is maximal. We refer to this problem as the traveling repairman problem with profits, or TRPP for short. The TRPP is a generalization of the well-known traveling repairman problem (TRP), also known as the minimum latency problem (MLT). In the TRP, no profits are given and the goal is to serve all clients with minimal total latency. We show: (i) how a dynamic program solves the TRPP on the line in polynomial time, (ii) how this result can be generalized to the problem with multiple identical servers (referred to as MTRPP on the line), (iii) that the problem with multiple non-identical servers and release dates for each client, is NP-hard. In the proof of the latter result we settle the complexity of an open problem described in literature.
ES-SAGHOUANI, ABDELGHAFOUR University of Amsterdam Supervisor On the correlation structure of a Lévy-driven queue Abstract Clich here for pdf file of the abstract
HAAN, ROLAND DE University of Twente Supervisor A polling model with an autonomous server Abstract Polling models are used as an analytical performance tool in several application areas. In these models, the focus often is on controlling the operation of the server as to optimize some performance measure. For some applications, controlling the server is not an issue as the server moves independently through the system. We present the analysis for such a polling model with a so-called autonomous server. In this model, the server always remains for an exponential time at a queue, which implies that service is preemptive. Another implication, which contrasts with most of the previous research on polling models, is that the server does not immediately switch to a next queue when the current queue becomes empty. The analysis is based on considering imbedded Markov chains at specific instants. A system of equations for the queue-length distributions at these instants is given and solved for. Besides, we study to which extent the queues in the polling model are independent and identify parameter settings for which this is indeed approximately the case. These results may be used to approximate performance measures for complex multi-queue models by analyzing a simple single-queue vacation model. Finally, we show that tandem models with a single autonomous server can be analyzed using the same techniques.
IERSEL, LEO VAN Eindhoven University of Technology Supervisors Level-k phylogenetic networks: uniqueness and complexity Abstract A central problem in biology is to reconstruct plausible evolutionary histories. This area of research is called phylogenetics and provides fascinating challenges for both biologists and mathematicians. Throughout most of the history of phylogenetics researchers have concentrated on constructing phylogenetic trees. In recent years however, more and more attention is devoted to phylogenetic networks. From a biological point of view, networks are able to explain and visualise more complex evolutionary scenarios, since they take into account biological phenomena that cannot be displayed in a tree. These phenomena are so-called reticulate evolutionary events such as hybridisation, recombination and horizontal gene transfer. From a mathematical point of view however, phylogenetic networks pose formidable challenges. In this talk I consider the construction of level-k phylogenetic networks from triplets, i.e. phylogenetic trees with three leaves. The level k of the networks determines how non-treelike the evolution is allowed to be, with level-0 networks being trees. I give, for each k, a level-k network that is uniquely defined by its triplets. I demonstrate the applicability of this result in two proofs that show the computational intractability of constructing level-k phylogenetic networks from triplets, for all k.
LEAHU, HARALAMBIE Vrije Universiteit Amsterdam
Supervisor Strong bounds on perturbations using weak derivatives Abstract Clich here for pdf file of the abstract
MNICH, MATTHIAS Eindhoven University of Technology Supervisor Exact construction of galled phylogenetic networks from triplets Abstract Galled phylogenetic networks provide a way to describe and visualise evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridisation or horizontal gene transfer. In galled phylogenetic networks the undirected cycles of recombination are disjoint. We study the problem of constructing galled phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). It is NP-hard to construct a galled network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability we give an exponential time exact algorithm for constructing galled networks consistent with a maximum number of input triplets. This is joint work with Leo van Iersel (TU/e) and Steven Kelk (CWI).
ROOIJ, JOHAN VAN Utrecht University Supervisor Design by measure and conquer: A faster exact algorithm for Dominating Set Abstract Clich here for pdf file of the abstract
ROUBOS, DENNIS Faculty of Sciences
Supervisor Average-cost approximate dynamic programming for the control of birth-death processes Abstract Dynamic programming is an attractive method for solving decision problems in stochastic systems. However, due to the large scale and complex nature of many decision problems, dynamic programming suffers from the curse of dimensionality. Therefore, standard solutions techniques, such as value iteration and policy iteration, cannot be applied directly. Consequently, much research effort has been put into approximate dynamic programming to alleviate this problem. Approximate dynamic programming when applied to average-cost decision problems with a countably infinite state space suffers from several computational issues. In particular, the algorithm may converge to non-stable solutions and requires knowledge on the average cost in advance. We address these issues by providing a theoretical basis for the approximation structure such that the unique stable solution will be attained. We illustrate this for the broad class of birth-death processes.
VERLOOP, MAAIKE CWI Supervisors Scheduling in bandwidth-sharing networks Abstract Bandwidth-sharing networks as considered by Massoulie & Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. We focus on some simple linear bandwidth-sharing networks which provide a useful model for flows that traverse several links and experience bandwidth contention from independent cross-traffic. First we show that size-based scheduling strategies such as Shortest Remaining Processing Time first (SRPT) and Least Attained Service first (LAS), which are known to improve the mean-delay performance in a single server system, may cause instability effects in a linear network and will therefore not yield optimal delay performance. Then we characterize policies that minimize the mean delay or equivalently the mean number of users. For some particular cases, priority policies will stochastically minimize the number of users. In general, the optimal policy can be described by so-called switching curves. However, no exact characterization exists. By analyzing a related fluid model, we find that linear switching curves accurately approximate the optimal strategy. When two nodes on the flow path are equally loaded, however, the fluid scaling is not appropriate, and it may be shown that the switching curve has a square-root shape. Finally, we compare the performance of the optimal policy with that of various alpha-fair policies, which are representations of common distributed allocation schemes, and find that alpha-fair policies perform quite well.
VLIEGEN, INGRID Eindhoven University of Technology Supervisors Bounds on the order fill rates for an inventory system of service tools Abstract In this talk, we deal with the analysis of a single-location, multi-item inventory model for service tools. Multiple service tools are kept, with different stock levels, at the warehouse. Independent Poisson demand streams arrive at the warehouse requesting different sets of tools. Those tools from the requested set that are in stock are then released; they are “in use” for an exponential amount of time, after which they are returned together. (Requested tools that are not on stock are delivered via an emergency channel; for the warehouse they may be considered as lost sales.) Thus our model features coupled demands and coupled returns - sets of tools are released and returned together. We are interested in the order fill rates, i.e., the percentage of demands for which all requested tools are delivered from stock. As the Markov chain describing the original system is of extremely high dimension, we introduce two, more tractable, approximate models. By combining Markov reward theory and aggregation we prove that the order fill rates of these approximate models lead to a lower and an upper bound on the order fill rate in the original model.
WANG, XINHUI University of Twente Supervisor Recent results of the exact algorithm for Steiner tree problem Abstract Clich here for pdf file of the abstract
|
