|
|
Abstracts presentations phd studentsBIJVANK, MARCO Department of Mathematics
Supervisor
Heuristics for Car Stock Management Abstract In this presentation we focus on the repair kit problem, which is a special case of a multi-item inventory system. High customer service is becoming an important strategy to increase the competitiveness of a firm. Since customers perceive a good quality of service when all the items they demand are on stock, it becomes more realistic to model customer satisfaction with an order-based service level. A well known problem from literature is the repair kit problem, which has an after sales service setting. In this problem technicians visit customers to repair machine failures and extra costs are incurred whenever the repairer has to come back to complete a repair if not all the required parts were available at the first visit. Therefore, technicians have to take along some spare parts, taking into account the holding costs (and other limitations like space or budget). Most (practical) models implement a cost minimization objective, while a service requirement is neglected. We have improved the most general heuristic for cost minimization models as well as for service agreement models, such that we achieve near-optimal solutions which indicate which spares to take and in which quantity.
CORBACIOGLU, UMUT Rotterdam School of Management Supervisor
Title
The Net Present Value (NPV) approach is considered to be the right approach to study inventory systems since it accounts for the cash flows as is. The average cost (AC) approach is more widely used in both practice and theory. However, the opportunity cost interpretation of AC framework is not that straightforward in systems with joint manufacturing and remanufacturing. In such systems, in the end-product (serviceable) stock, manufactured and remanufactured items are present. Due to this convergent structure, the valuation of serviceable inventory is ambiguous. Also, in the analysis another stock point for returned items (remanufacturables) is considered. Returned products are acquired for less investment, but they have a potential of being added to serviceable inventory with less expenditure than manufacturing. Moreover, remanufacturing can be used to convert returns into different products. This divergent structure which is a natural result of designs that allow disassembly and reuse adds another layer of ambiguity on opportunity cost interpretation. In this paper we analyse a two-product system with manufacturing and remanufacturing operations in a deterministic setting. For this system, by considering two different models under a net present value (NPV) approach and an average cost (AC) approach, we determine holding cost rates such that the two approaches are approximately equivalent. Then we demonstrate the effect of traditional valuation methodology on the remanufacturing operation dynamics by comparing that approach to the theoretical results of our analysis.
DIEPEN, GUIDO Institute of Information & Computing Sciences Supervisors
Title
In this paper we look at the problem where we have to schedule n jobs with release dates, due dates, weights, and equal processing times on a single machine. The objective is to minimize the sum of weighted tardiness (1 | rj, pj = p | ∑wjTj in the three-field notation scheme). We formulate the problem as a time indexed ILP after which we solve the LP-relaxation. We show that for certain special cases (namely when either all due dates, all weights, or all release dates are equal, or when all due dates and release dates are equally ordered), the solution for the LP-relaxation is either integral or can be rewritten in polynomial time into an integral one. For the general case we present a branching rule that performs well. Furthermore we show that the same approach holds for the m parallel machines variant of the problem. Finally we show that with a minor modification the same approach also holds for the single-machine problems of minimizing the sum of weighted late jobs (1 | rj, pj = p | ∑wjUj) and the sum of weighted late work (1 | rj, pj = p | ∑wjVj) as well as their respective m parallel machines variants.
DOBBER, MENNO Department of Mathematics
Supervisor
An Effective Prediction Method for Running Times of Jobs on Shared Processors Abstract Grid computing is an emerging technology by which huge numbers of processors over the world create a global source of processing power. Their collaboration makes it possible to perform computations that are too extensive to perform on a single processor. On a grid processors may connect and disconnect at any time, and the load on the computers can be highly bursty. Those characteristics raise the need for the development of techniques that make grid applications robust against the dynamics of the grid environment. In particular, applications that use significant amounts of processor power for running jobs need effective predictions of the expected computation times of those jobs on remote hosts. Currently, there are no e_ective prediction methods available that cope with the ever-changing running times of jobs on a grid environment. Motivated by this, we develop the Dynamic Exponential Smoothing (DES) method to predict running times in a grid environment. We have performed extensive experiments in a real global-scale grid enviroment to compare the e_ectiveness of DES. The results demonstrate that DES strongly and consistently outperforms existing prediction methods.
EGOROVA, REGINA CWI
Supervisors
Sojourn Time Tails in the M/D/1 Processor Sharing Queue Abstract We consider the sojourn time V in the M/D/1 processor sharing (PS) queue, and show that P(V > x) is of the form Ce -γx as x becomes large. The proof involves a geometric random sum representation of V, and a connection with Yule processes, which also enables us to simplify Ott's (1984) derivation of the Laplace transform of V. Numerical experiments show that the approximation P(V > x) ≈ Ce-γx is excellent even for moderate values of x. In addition, we present some results on tail behavior of the conditional sojourn time in PS queue with exponential service.
ELABWABI, GAMAL Delft University of Technology Supervisor Nonnegative bilinear functions on the cartesian product of Lorentz cones Abstract
GVOZDENOVIC, NEBOJSA CWI
Supervisor
Approximating the Chromatic Number of a Graph by Semidefinite Programming Abstract The Lovász theta number of a graph is a well studied graph parameter that can be computed efficiently to an arbitrary precision in polynomial time by using semidefinite programming. It is known to be "sandwiched" between two "NP-hard" parameters, i.e. the stability number of a graph and the chromatic number of a graph complement. Recently, several hierarchies of semidefinite bounds, starting either from the Lovász theta or one of its strengthenings were proposed in order to approximate the stability number of a graph. It turned out that some bounds in these hierarchies that can be computed efficiently give better approximations for the stability number than the Lovász theta number for certain graph classes. We show how these hierarchies can be adapted for approximating the fractional chromatic number, and the chromatic number of a graph. We prove that our new bounds are at least as good as the best known semidefinite lower bounds on the chromatic number of a graph. In addition, we give some computational results that show that in some cases our bounds are better.
HAIJEMA, RENÉ Department of Quantitative Economics
Supervisor
Blood Platelet Production: Optimization by Dynamic Programming and Simulation Abstract Blood banks produce and store blood products in order to fulfill the uncertain demand at hospitals. Platelet pools are the most expensive and most perishable blood product having a shelf life of only four to six days. The demand may be categorized into two groups: demand for ‘young’ platelet pools (at most three days old) and demand that can be met by pools of any age up to the maximal lifetime. Production volumes need to be chosen carefully in order to reduce outdating while keeping the occurrence of shortages low. In current (national and foreign) practice about 15 to 20% of pools are not used because of outdating. We show that by applying a simple rule outdating can be reduced to less than 1%. We investigate the structure of the optimal production policy by solving a down sized periodic Markov Decision Problem (MDP). Down sizing is required to overcome the curse of dimensionality in the state space. An innovative frequency table, obtained via simulation, depicts the structure of the optimal MDP strategy. The optimal production volumes appear to depend on the number of pools on stock and their ages. A simple rule can be derived, with two parameters for each working day. By a simulation based search algorithm we find optimal values for the parameters in realistic sized cases. Via an extensive simulation study (for one of the four Dutch blood banks) we show that the simple rule performs quite well (nearly optimal) even if one acknowledges: - the distinction of multiple and limited compatible blood groups; - the uncertainty in the supply by donors; - that 70% of the demand prefers ‘young’ platelets.
Econometric Institute Supervisor
Title
The economic lot-sizing problem is described as follows. Given the (deterministic) demand for a discrete and finite planning horizon, find the production schedule that satisfies the demand and minimizes the total costs. Costs include setup cost for each time period production takes place and holding cost for each item carried over from a period to the next period. Although the problem can be solved to optimality in polynomial time, heuristics are often applied when the problem has to be solved in a rolling horizon environment. A certain class of heuristics possesses the so-called insulation property, i.e., previous set production periods cannot alter while constructing the overall production schedule. In other words, given the production quantities scheduled up to period t, only the production quantity in the last production period may change when considering period t+1. It is shown in the literature that there exist heuristics satisfying the insulation property that have a worst case ratio of 2. In this talk we try to find bounds on the worst case ratio for all heuristics satisfying the insulation property. We consider the problem as a kind of online scheduling problem and derive a methodology to find lower bounds on the worst case ratio for a fixed number of periods T. The first results show that for large T we can find lower bounds close to 1.5. That means, for each heuristic satisfying the insulation property, there exist problem instances for which the heuristic constructs solutions with a worst case ratio close to 1.5.
HEYDENREICH, BIRGIT Department of Quantitative Economics
Supervisors
Mechanisms for Decentralized Online Scheduling Abstract We study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time - P | rj | ∑ wjcj in the notation of Graham et al. [1] - from a new perspective: We assume a strategic setting, where the data of each job, namely its release date rj, its processing time pj and its weight wj is only known to the job itself, but not to the system. Furthermore, we assume a restricted communication paradigm, referred to as decentralizationP = NP. In addition, in the strategic setting, selfish agents trying to maximize their own benefit can do so by reporting strategically about their private information, thus manipulating the resulting outcome. We present a polynomial time mechanism for this setting building upon the MinIncrease-algorithm from [3]. As usual in mechanism design, the mechanism defines payments that have to be made by the jobs for being processed. We show that there does not exist a payment scheme that extends the MinIncrease-algorithm to a mechanism in a way that makes truthful revealing of private information an ex-post dominant strategy for every job. The payments we introduce make truthful reporting of private information a dominant strategy at least for myopic rational jobs. Those payments result in a balanced budget and can be computed online. We show that those payments enable us to decentralize the mechanism according to the restricted communication paradigm. The resulting mechanism is 3.281-competitive which coincides with the bound that is known for the non-strategic setting. An earlier version of the paper is available as a Meteor Research Memorandum [2]. References [1] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5: 287-326, 1979. [2] B. Heydenreich, R. MMüller and M. Uetz. Mechanisms for Decentralized Online Scheduling, Meteor Research Memorandum, Maastricht University, 2005. [3] N. Megow, M. Uetz and T. Vredeveld. Stochastic Online Scheduling on Parallel Machines. In G. Persiano and R. Solis-Oba, editors, Proc. Second International Workshop on Approximation and Online Algorithms, volume 3351 of Lecture Notes in Computer Science, pages 167-180. 2005.
LIESHOUT, PASCAL CWI Supervisor
Title
Abstract
LOON, JOYCE VAN Department of Quantitative Economics
Supervisors
How to Sell a Graph: Some Guidelines for the Graph Retailer Abstract We consider a profit maximization problem when pricing a set of m items which can be represented as the edges of an undirected graph G. There is a set of n customers, each of which is interested in purchasing a path in the graph. The path is also called a customer's bundle, and each customer has a known budget for her respective bundle. Customers are single minded, so they are only interested in that particular bundle. The objective is to find a pricing and a feasible assignment of items to customers in order to maximize total profit. We give an overview of recent results on the tractability of that class of profit maximization problems. While recent papers mainly address the case of unlimited availability of the items [1,3,5,6], we particularly focus on the problem with limited availability of items. Our results are as follows. When the graph G is a path, we derive a fully polynomial time approximation scheme, complementing previous approximation schemes, and matching a recent NP-hardness proof [2,3]. If the graph G is a tree, and all items are unique, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the graph G is a grid, and items are unique, we show that it is even NP-complete to approximate the problem within n1-ε. This talk is based on joint work with Alexander Grigoriev, Marc Uetz and René Sitters [4]. Keywords: Pricing problems, tollbooth problem, computational complexity, dynamic programming, fully polynomial time approximation scheme. References [1] M.F. Balcan and A. Blum, Approximation algorithms for item pricing, Working paper, 2005. [2] H. Bodlaender and E. Penninkx, An elegant NP-completeness proof for profit maximization on paths, May 2005. [3] P. Briest and P. Krysta, Single-minded unlimited supply pricing on sparse instances, Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, 2006, to appear. [4] A. Grigoriev, J. van Loon, R. Sitters, and M. Uetz, How to sell a graph: Some guidelines for the graph retailer, Working paper, 2005. [5] V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry, On pro¯t-maximizing envy-free pricing, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, 2005, pp. 1164-1173. [6] J. D. Hartline and V. Koltun, Near-optimal pricing in near-linear time, Algorithms and Data Structures (F. K. H. A. Dehne, A. López-Ortiz, and J.-R. Sack, eds.), vol. 3608, Springer, 2005, pp. 422-431.
MANSOURI, HOSSEIN Delft University of Technology Supervisor A simplified O(nL) infeasible interior-point algorithm for linear optimization using full Newton steps Abstract
MES, MARTIJN Department of Operational Methods for Production and
Logistics Supervisor
Title
In this talk we consider a real-time, dynamic pickup and delivery problem with time-windows where orders should be assigned to one of a set of competing transportation companies. This assignment is made in a sequential second-price auction marketplace. Our approach decomposes the problem into a multi-agent structure where vehicle agents are responsible for the pricing, routing and scheduling decisions. Therefore the system performance will be heavily dependent on the pricing strategy of the vehicle agents. We propose a pricing strategy which not only takes the direct cost of a job insertion into account, but also the so-called opportunity costs. These opportunity costs are used to capture the loss in expected future revenue of a vehicle schedule due the insertion of a new job. In order to calculate expected future revenue we have to look at all possible future scenario's that can take place given a certain schedule. These possible scenarios are described by a Markov Decision Process (MDP). Simulation is used to evaluate the benefit of pricing opportunities compared to simple pricing strategies in different market settings. Numerical results show that the proposed approach provides high quality solutions, in terms of profits, capacity utilization and delivery reliability. We explained these results from the following behavior of the vehicle agents. First, they tend to schedule unattractive jobs later increasing the probability of combining this job with another job. Second, they tend to create gaps before unattractive jobs, possibly reducing empty moves. Third, they tend to pick out only the most profitable jobs.
MINCSOVICS, GERGELY Eindhoven University of Technology
Supervisor
Title
The development of job intermediation and the increasing use of Internet allow companies to carry out quicker and quicker capacity changes. In many cases capacity adaptation can be driven according to the present workload. We introduce a set of Markov chain models to represent workload-dependent capacity control policies. In our analysis we assume exponential interarrival and service times, although the model permits extension to phase-type distributions. We present two analytical approaches to stationary analysis in order to evaluate the policies due-date performance. One provides an explicit expression of throughput time distribution, the other is a smart vector iteration method that calculates the moments of the throughput time. Eventually, we compare due-date performances, capacity costs, costs of changing capacity, lost sales and select optimal policies. Our results and tools can be used by manufacturing and service industries when declaring a static policy for a dynamic, workload-dependent capacity planning.
TENNEKES, MARTIJN Department of Mathematics
Supervisor
Variations on network formation games Abstract Network structures play an important role in many fields, e.g. in sociology and economics. Individuals are able to share information via the links of these networks. In line with Jackson and Wolinksy [2] and Bala and Goyal [1] (among others) we focus on the formation of these networks. We model the network formation as a non-cooperative game, which is a generalization of a game described by Bala and Goyal [1]. Consider a set of players where each player has some information value on his own. Furthermore, a player has access to another player's information value if they are connected, directly or indirectly. The underlying graph is directed. The links have certain costs. In a move, a player chooses with whom he contruct links. Players move sequentially in random order. The pay-off of a player is defined by the total information value that he gains minus the total costs of the links he constructs. Our goal is to find the Nash equilibria of this game. Furthermore, we want to know if these equilibria can be reached through a succession of moves and what the corresponding convergence rates are. Our first result is that we have found examples for which no Nash equilibria exist. References [1] V. Bala and S. Goyal, A non-cooperative model of network formation, Econometrica 68 (2000) 1181-1229. [2] M. O. Jackson and A. Wolinsky, A Strategic Model of Social and Economic Networks, Journal of Economic Theory 71 (1996) 44-74.
VERHEIJEN, BAS Rotterdam School of Management Supervisors
Title
This presentation deals with transportation costs for products which that are sharing a capacitated transport resource , such as a trucks (LTL transport) on a single link. The aim is to understand and explain transport costs as a function of order quantity. Although actual transportation tariffs in the market have been described and studied before, few studies explain the functional form of transport costs and its dependencies on the environment. A thorough understanding of the costs for transport enables better judgement on potential benefits and use of third party logistics providers and gives insight in cost savings that could potentially be achieved when advanced supplier vendor arrangements such as Vendor Managed Inventories or Factory Gate Pricing are used. Requests for transport services arrive as orders. The time between order arrivals is stochastic and the size of each order is a stochastic discrete value. At certain constant intervals, all orders that have accumulated are dispatched to the customer. The orders are packed into trucks in an efficient manner and transported, in such a way that the least number of trucks are used and that orders are not split unnecessarily. We assume that ultimately, the cost per truck that is used is constant. These costs consist of a.o. fuel, wear and tear and wages. As observed in practice, transport costs depend on the order-quantities. The transport costs for individual orders are derived by allocating the total costs of transport for a dispatch to individual orders. Three different allocation methods are studied: the Shapley value, a semi-proportional allocation and calculation of the expected additional costs. The arrival, accumulation and dispatch of orders is simulated using a discrete event simulation model. The transport costs are subsequently determined according to the allocation methods. The intensity of order arrivals and the order-size distribution are varied in the simulation experiments. The resulting transport cost curves are strictly increasing in order-size. However, contrary to literature on transport tariffs, the curves are not concave.
VIEIRA, MANUEL Delft University of Technology Supervisor Interior Point Methods for symmetric optimization based on kernel functions Abstract
VLASIOU, MARIA EURANDOM Supervisor Exact solution to a Lindley-type equation on a bounded support Abstract
WEIJ, WEMKE VAN DER CWI
Supervisor
Stability and Throughput in a Two-Node Queueing Network with a Shared Resource Abstract We study stability and throughput in a two-layered queueing network consisting of two multi-server nodes, where at any time the busy servers share a common underlying resource in a processor-sharing fashion. We consider a two-node network with general stationary arrival processes, general service-time distributions at both queues, arbitrary numbers of servers at both queues, and multiple customer classes, each with a class-specific arrival rate and visit order. For this model we derive a full characterization of the per-queue stability and the per-class throughput, in a general parameter setting. The results reveal that the per-queue stability strongly and throughput depend on the βi/ci ratios of both queues, where βi is the mean service time and ci is the number of servers at queue i. Moreover, we obtain several interesting and seemingly counter-intuitive results, and provide explanations for these observations. As such the results provide new intuition and fundamental insights into the behavior of queueing networks with this multi-layered structure.
|
