|
|
Abstracts presentations phd studentsBOMHOFF, MATTHIJS Dept. of Applied Mathematics Supervisor Space-efficient recognition of perfect elimination bipartite graphs Abstract When applying Gaussian elimination to a sparse matrix, it is desirable to avoid turning zeros into non-zeros to preserve the sparsity. The class of perfect elimination bipartite graphs is closely related to square matrices that Gaussian elimination can be applied to without turning any zero into a non-zero in the process. Existing literature on the recognition of this class of graphs and matrices (and finding a suitable set of corresponding pivots) mainly focusses on the time complexity of this problem. However, when viewed from a practical perspective, the space complexity also deserves our attention: it may not be worthwhile to look for a suitable set of pivots for a sparse matrix if this requires a `dense' amount of space. This talk will focus on a new, more space-efficient algorithm for this problem.
BUYUKKARAMIKLI, CAGDAS Eindhoven University of Technology Dept. of Technology Management PO Box 513 5600 MB Eindhoven n.c.buyukkaramikli@tue.nl Supervisors Periodic capacity management under a lead-time performance constraint Abstract In this paper, we study a production system that operates under a lead time performance constraint which guarantees the completion of a job order before a pre-determined lead time (e.g. 1 week) with a certain (e.g. 95%) probability. The demand arrival times and the service requirement of the job orders are random. In order to reduce the capacity related operational costs, the production system under study decides to use flexible capacity policies. Most of the flexible capacity practices in real life are inherently periodic due to several reasons. Motivated by this observation, we focus on periodic capacity policies and model the production system as a queuing system. For the sake of practicality as well as convenience, we assume two levels of capacity available: permanent and the contingent capacity levels. The permanent capacity is always employed in the system, whereas the use of the contingent capacity in a period is decided based on the number of job orders in the system at the start of each period. The external supplier has to be on alert and ready to supply the required amount of contingent capacity at the start of each period, however the actual use of the contingent capacity is uncertain due to the periodic capacity policy of the production system. Uncertainty on the use of the contingent capacity creates an opportunity cost for the external supplier, as the contingent capacity could be deployed somewhere else if it was not reserved for the production system. This opportunity cost makes the per time unit cost for contingent capacity more expensive, particularly for shorter period lengths. For a given lead time performance constraint and a permanent/contingent capacity cost structure, we develop a procedure to create a set for candidate period lengths and permanent/contingent capacity levels. Afterwards we propose a search algorithm that finds the threshold point that minimizes the capacity related costs for a given period length. Due to the cost structure of the permanent and contingent capacity levels, the behavior of the operational costs changes drastically under different period lengths. In our computational study, we observe that the periodic capacity management reduces the operational costs significantly. The percentage savings are higher for more ambitious lead time performance constraints.
CANER, SERRA Department of Economics &
Business
Supervisor Competition in remanufacturing Abstract We study remanufacturing competition between an original equipment manufacturer (OEM) and an independent operator (IO). Different from the existing literature, the OEM and IO compete for returned products (cores) with their acquisition prices. We consider a 2-period model with manufacturing by the OEM in the first period, and manufacturing as well as remanufacturing in the second period. We determine the optimal policies for both players by establishing a Nash Equilibrium in the second period. A sensitivity analysis leads to a number of managerial insights. One interesting result is that the acquisition price of the OEM only depends on its own cost structure, and not on the acquisition price of the IO. Further insights are obtained from a numerical investigation. Contrary to intuition we find that if there is more demand in the second period, manufacturing in the first period is reduced and hence fewer cores are available in the second period. In this way, the OEM protects its total market share.
DOLLEVOET, TWAN Econometric Institute Supervisors Delay management with passenger re-routing Abstract Every regular train passenger will recognize the frustration of missing a transfer to a connecting train or bus due to a small delay of the incoming train. When a connection is missed, the passengers' travel time may easily be enlarged by half an hour. Delay management is the field in railway operations that deals with connections between trains. When one train has a small delay, it might be beneficial for the transferring passengers to delay another train slightly as well, to allow the passengers to transfer to the second train. However, by delaying the connecting train, the travel time for the passengers already in that train will be enlarged. Furthermore, there might be connections from that train to others at subsequent stations that have to be considered. This makes delay management a complex problem, especially in dense railway networks such as in the Netherlands. The first approaches to model the delay management problem assume that the delay for a passenger who misses a connection equals the cycle time of the timetable: if a connection is dropped, passengers have to wait for the same train that departs an hour later. In practice, there are more trains between two stations, and therefore passenger will have a smaller delay. To model the behavior of the passengers more realistically, an extended model for delay management is proposed that takes the routes of the passengers into account explicitly. In particular, the model allows the passengers to adjust their route in case of delays.
FIRAT, MURAT Eindhoven University of Technology Dept. of Mathematics and Computer Science PO Box 513 5600 MB Eindhoven m.firat@tue.nl Supervisor Detecting, measuring and repairing instabilties in schedules of tasks with skill requirements Abstract The problem we consider in this study is the complex scheduling problem that has been defined by France Telecom in Challenge ROADEF 2007. The day-to-day schedules are merely the assignments of tasks to teams of technicians under certain skill requirements. The feasibility of a schedule is satisfied when each teams has enough skills to perform the assigned tasks. The task sequences that are assigned to teams are called workloads of the teams, shortly teamloads. Skills are categorized in several domains and the expertness of technicians is specified by levels in skill domains. The skill requirements of teamloads are specified as the number of technicians at certain levels of several specialization fields. By definition tasks have deterministic durations and they are grouped into several priority classes that represent their urgency. The quality of a schedule is determined by the weighted sum of completion times of these priority classes. In this work we assume that we are given day-to-day schedules of good quality that are constructed by the combinatorial algorithm that we introduced. Our goal is to analyse the stability of those schedules by defining a notion of blocking pairs and measuring the degree of instability if some of schedules fail to be stable. Finally we propose a reassignment procedure to decrease the instabilities of schedules.
GABALI, OLLA Eindhoven University of Technology Dept. of Technology Management PO Box 513 5600 MB Eindhoven o.gabali@tue.nl Supervisor Analysis of travel times and CO2 emissions in time-dependent vehicle routing Abstract Due to the growing concern over environmental issues, regardless of whether companies are going to voluntarily incorporate green policies in practice, or will be forced to do so in the context of new legislation, change is foreseen in the future of transportation management. Assigning and scheduling vehicles to service a predetermined set of clients is a common distribution problem. Considering time-dependent travel times between the links, we address the vehicle routing problem from two extreme standpoints; one seeks to optimize exclusively on total travel time; the other does so on total CO2 emissions. We also present a cost-based model that optimizes on a weighted average of travel time, emission and fuel costs. As the generated amount of CO2 emissions is correlated with vehicle speed, the emissions-based optimization is done by limiting vehicle speed. The emissions per kilometer as a function of speed, is a function with a unique minimum optimal speed v*. However, we show that limiting vehicle speed to this v* might be sub-optimal, in terms of total emissions. Obviously, during congestion vehicles are constrained by lower speeds and produce much higher emissions. Consequently, for emissions, it might be worthwhile to travel at speeds higher than v*, where possible, in order to avoid congestion. Furthermore, we construct bounds on the total amount of emissions that may be saved by making use of distance based VRP solutions. We experiment with standard sets from the literature. Solutions are obtained via an iterative tabu search procedure.
HAENSEL, ALWIN VU University Amsterdam Supervisor Estimating unconstrained demand rate functions using customer choice sets Abstract A good demand forecast should be at the heart of every Revenue Management model. Yet most demand models focus on product demand and do not incorporate customer choice behavior under offered alternatives. We are using the ideas of customer choice sets to model the customer’s buying behavior. A customer choice set is a set of product classes representing the buying preferences and choice decisions of a certain customer group. A demand estimation method for these choice sets is presented. The procedure is based on the maximum likelihood method and to overcome the problem of incomplete data or information we additionally apply the expectation maximization (EM) method. Using this demand information per choice sets, the revenue manager obtains a clear view of the underlying demand. In doing so, the sales consequences from different booking control actions can be compared and the over all revenue be maximized.
HOORN, JELKE VAN VU University Amsterdam FEWEB De Boelelaan 1105 1081 HV Amsterdam jhoorn@feweb.vu.nl Supervisors Exponentially better than brute force: solving the job-shop problem by dynamic programming Abstract Scheduling problems received substantial attention during the last decennia. The job-shop problem is a very important scheduling problem, which is NP-hard in the strong sense and with well-known benchmark instances of relatively small size which attest the practical difficulty in solving it. The literature on job-shop scheduling problem includes several approximation and optimal algorithms. So far, no algorithm is known which solves the job-shop scheduling problem optimally with a lower complexity than the exhaustive enumeration of all feasible solutions. We propose such an algorithm, based on the well-known Bellman equation designed by Held and Karp to find optimal sequences and which offers the best complexity to solve the Traveling Salesman Problem known to this date. For the TSP this means O(n^2 2^n) which is exponentially better than O(n!) required to evaluate all feasible solutions. We reach similar results by first recovering the principle of optimality, which is not obtained for free in the case of the job-shop scheduling problem, and by performing a complexity analysis of the resulting algorithm. Our analysis is conservative but nevertheless exponentially better than brute force. We also show very promising results obtained from our implementation of this algorithm, which seem to indicate two things: firstly that there is room for improvement in the complexity analysis (we observe the generation of a number of solutions per state for the benchmark instances considered which is orders of magnitude lower than the bound we could devise) and secondly that the potential practical implications of this approach are at least as exciting as the theoretical ones, since we manage to solve some celebrated benchmark instances in processing times ranging from seconds to minutes.
JAARSVELD, WILLEM VAN Econometric Institute Supervisor Optimization of demand rationing for inventory control with multiple demand classes Abstract We examine the (S,S-1) lost sales inventory model with multiple demand classes. We examine simple procedures to find good policies for this problem: local searches in the rationing levels. Our main result is that we establish guaranteed optimality for two of these heuristics. As a corollary, we provide an alternative proof for the optimality of rationing policies among the class of all policies.
JANSEN, MICHIEL Eindhoven University of Technology Supervisor The effect of workload constraints in periodic order release models Abstract We study periodic capacitated models for Supply Chain Operations Planning (SCOP) within a hierarchical planning concept. The SCOP problem is one of timing the release of orders to production units. Production units are predefined parts of the production process that transform a set of input materials into a set of (different) output materials, and are decoupled by stock points. Too late release of orders to these production units leads to short supply in subsequent stages of the supply chain and eventually to tardy customer deliveries. Too early release leads to piling up of "dead" inventory. The time between release of an order to a production unit and the time that the order is available for use in next stage production or for delivery to the customer, is the flow time. The time between release and the planned availability is the planned lead time. Flow time and planned lead time are generally not equal. If the flow time is less than the planned lead time, this results in inventories higher than planned for a short period of time. In the opposite direction the effect is much more severe. If the flow time exceeds the planned lead time, downstream production is delayed. This may lead to unplanned capacity requirements in the subsequent period, piling up of inventory of other components, and a potential delay of customer deliveries. There are essentially two approaches to the dilemma in the previous paragraph. In one approach, a planned lead time is selected such that flow times never exceed it. In the other approach, the planned lead time is made conditional on some capacity constraint. (Some may argue that there also is an approach where lead time is made endogenous to the planning problem but in effect, in periodic release models, this approach can be seen as the special case with a planned lead time of a single period). Often, particularly in multi-level lot sizing models, this capacity constraint is a deterministic one. Practice is different. Production processes are subject to all sorts of uncertainty and the capacity parameters in the planning model are set to some average or below the average if a higher level of reliability is desired. The choice of the planned lead time and capacity parameters heavily influences how efficient resources can be utilized. In this research we consider a single production unit that is represented by a single server with generic service times. We found that there is a simple, intuitive relation between the planned lead time, capacity constraints, and the maximum utilization of a production unit. We explore this relation further using a generating function approach. We also develop accurate approximations for mean and variance of workload and flow times. Finally, we show for a simple case, how these results can be applied to find the efficient combinations of planned lead time and the capacity constraint.
KILIC, ONER Department of Economics &
Business
Supervisors A simple heuristic for non-stationary (s,S) policies Abstract In this paper, we consider the finite-horizon non-stationary periodic review inventory problem with replenishment set-up costs. The problem has already been addressed in the literature. It is well-known that the (s,S) policy is optimal for the problem under very mild assumptions. It has also been shown that the optimal (s,S) parameters can be established by a dynamic program. However, the procedure is very complex and computationally expensive which rules out any chance of successful implementation. In this study, we propose a simple heuristic to compute near-optimal (s,S) parameters. The heuristic is based on analyzing expected replenishment cycles and corresponding newsvendor problems. My means of a numerical study we compare our heuristic with an earlier one and the optimal dynamic program. We show that our heuristic significantly outperforms the earlier heuristic and provides near-optimal results for a large variety of demand patterns and cost parameters.
KLEPPE, JOHN Tilburg University Supervisor Per capita nucleolus Abstract One of the most important and studied one-point solution concepts for coopera- tive games is the nucleolus and the related prenucleolus. The (pre-)nucleolus is the unique element in the (pre-)imputation set for which the maximal coalitional objection to it is minimised. Related to these concepts is the per capita (pre-) nucleolus. The per capita (pre-)nucleolus is the unique element in the (pre-) imputation set for which the maximal objection per player of a coalition to it is minimised. Although the per capita (pre-)nucleolus is mentioned in many papers over the years it was never extensively studied. In this presentation we discuss the per capita (pre-)nucleolus and the related concept of the per capita (pre-)kernel, and study many of their properties. Let us discuss the per capita prenucleolus here in somewhat more detail. An important result is that the per capita prenucleolus can be characterised balanced collections. Furthermore, the per capita nucleolus satisfies, among other properties: efficiency, single-valuedness, anonymity, covariance, reasonableness from above, weak coalitional monotonicity and strong aggregate monotonicity. We also introduce a reduced game and show that the per capita prenucleolus satisfies the corresponding reduced game property. Moreover, we characterise the per capita prenucleolus by single-valuedness, covariance, anonymity and this reduced game property. For the per capita prekernel, the per capita nucleolus and the per capita kernel we show a similar type of results. Furthermore, we characterise the core of a TU-game by the use of the reduced game game property as well.
KOSINSKI, KAMIL EURANDOM Eindhoven University of Technology PO Box 513 5600 MB Eindhoven kosinski@eurandomtue.nl Supervisors Onno Boxma and Michel Mandjes Title Polling models with Levy input Abstract In this talk we consider a ring of N>=1 queues served by the same server in a cyclic order. After having served a queue (according to a discipline that may vary from queue to queue), there is a switchover period and then the server proceeds to the next queue and so forth. This model is known in the literature as a polling model. Each of the queues is fed by a non-decreasing Levy process, which can be different during each of the subsequent periods within the server's cycle. The N-dimensional Levy processes obtained in this fashion are described by their Laplace exponents allowing for non-independent input streams. For such a system we derive the steady-state distribution of the joint workload at embedded epochs, i.e. polling and switching instants. Using a multidimensional version of the Kella-Whitt martingale we also derive the steady-state distribution at an arbitrary epoch. Finally we make a link between this model and the classical (Poisson arrivals) polling systems considered in Resing (Queueing Syst. 13, 409--426), by showing that the interpretation of polling systems as multitype branching processes presented therein, can be generalized to fluid (Levy input) polling systems and multitype Jirina processes (continuous-state discrete-time branching processes). This is done by defining properly the notion of the branching property for a discipline, which can be traced back to Fuhrmann. This definition is broad enough to contain the most important disciplines (e.g., the exhaustive and gated discipline).
KRUSHANSKY, DMITRY Department of Economics &
Business
Supervisor An efficient model for multiobjective cell formation in group technology Abstract In the last several decades, group technology (GT) has emerged as an important scientific principle in involving the productivity of batch-type manufacturing systems having many different types of products with relatively low lot sizes. Its basic idea is to decompose a production process into a set of subsystems for the sake of better control by exploiting the similarities of product design and manufacturing process. As the number of possible subsystems grows extremely fast with increase in the size of the manufacturing system, the problem becomes computationally intractable. This fact forced researchers in the field to turn to heuristics that are fast but provide no worst-case guarantee on the quality of solutions. Another peculiarity is that most of the available papers consider functional approach to cell formation when machines are grouped based on similarity of the products that they process. However, the current trend is to incorporate additional objectives and\or constraints, reflecting available workforce, sequences of operations, etc. In this paper we consider a mathematical model for the optimal cell formation that is based on a well-known p-Median Problem (PMP). Though, the PMP is NP-hard in general, we present a new pseudo-Boolean formulation that allows substantial problem size reductions, thus making it possible to solve even large-size instances with standard ILP software.
LANGESTRAAT, ROMEO Tilburg University Supervisor Introducing CO2 allowances: Higher prices for all consumers, higher revenues for who? Abstract Introducing a ceiling on total CO2 emissions and allowing polluting industries to buy and sell permits to meet it (aka a cap-and-trade system) affects investment strategies, generation quantities, and prices in electricity markets. In this paper we analyze these effects under the assumption of perfect competition and make a comparison with another potential way of reducing CO2 emissions, namely a fixed carbon tax charged per unit emission. We deal with an energy only market and model it as a two stage Nash game where capacities are installed in the first stage and production takes place in the future spot market. For a stylized version of this model (with no network effects and deterministic demand), we show that at the equilibrium a mixture of two technologies is used. This mixture consists of a relatively clean and a relatively dirty technology. In the absence of a ceiling on total emissions, marginal operating costs of different technologies form a fixed merit order; that is, the marginal costs are ordered in an ascending fashion. Based on the observed demand, this fixed merit order is used to determine the total number of technologies used so that all demand is satisfied. We show that, as long as there is enough capacity in the system, when a fixed maximum allowance level is introduced, different demand levels impose different prices for a unit of emission allowance, and consequently there is no fixed merit order on the technologies. Therefore, for different levels of observed demand one can find a different optimal mixture. We develop an algorithm for finding the induced optimal mixture in a systematic way. Next, we show that the price of electricity and the price of allowances increase as the maximum allowance level decreases, as expected. When, in comparison, a fixed tax is charged for the emissions, the merit order is fixed and the first technology in the merit order is the only generating unit. We also consider a more general version of the model with stochastic demand. We illustrate how to solve the two-stage stochastic game as a two-stage stochastic program or a complementarity problem under uncertainty, using sampling. In our numerical study, we observe that broader mixtures of technologies are used to satisfy the uncertain demand. Furthermore, we show that if there is shortage of transmission capacity in the system, only introducing financial incentives and instruments (such as taxation or a cap-and-trade system) is neither sufficient to curb CO2 levels nor necessarily induces investment in cleaner technologies, respectively.
LOHMANN, EDWIN Tilburg University Supervisor Preparation sequencing situations Abstract In this paper we discuss preparation sequencing situations, a new class of one-machine sequencing situations. In preparation sequencing situations, a job is called to the factory as soon as the previous job has finished. However, the machine requires preparation before it can process the new job. We assume this preparation only depends on the direct predecessor. In particular, the time the job spends in the system depends not only on his processing time but also on the preparation time of the machine. We provide an algorithm for the optimal order of jobs and analyze the related cost allocation problem. In both cases, we prove balancedness of the corresponding cooperative games and provide a characterization of the core and the nucleolus.
MARBAN, SEBASTIAN Dept of Quantitative Economics
Supervisor Dynamic pricing problems with elastic demand Abstract We study a dynamic pricing problem for a company that either has monopolistic market power or operates within a market with imperfect competition. The company sells a single product to a group of customers over a fixed time horizon. It is assumed that these customers are price sensitive and that the price of today influences the group of customers of tomorrow. The objective is to set the prices so as to maximize revenue. We consider a deterministic and stochastic demand setting. For several variants of these two settings, we develop algorithms that run in polynomial time.
MEUFFELS, INEKE Tilburg University Supervisor Enriching the tactical network design of express service carrriers with fleet scheduling characteristic Abstract Express service carriers provide time-guaranteed deliveries of parcels via a network consisting of nodes and hubs. In this, nodes take care of the collection and delivery of parcels, and hubs have the function to consolidate parcels in between the nodes. The tactical network design problem assigns nodes to hubs, determines arcs between hubs, and routes parcels through the network. Afterwards, fleet scheduling creates a schedule for vehicles operated in the network. The strong relation between flow routing and fleet scheduling makes it difficult to optimise the network cost. Due to this complexity, fleet scheduling and network design are usually decoupled. We propose a new tactical network design model that is able to include fleet scheduling characteristics (like vehicle capacities, vehicle balancing, and drivers’ legislations) in the network design. The model is tested on benchmark data based on instances from an express provider, resulting in significant cost reductions.
OUT, PAULIEN VU University Amsterdam Supervisor Optimal outpatient scheduling with emergency arrivals Abstract We present an efficient method for scheduling outpatient appointments to a facility with emergency arrivals. A weighted sum of the waiting times, idle times and tardiness is minimised. No-shows are allowed. We assume Poisson arrivals for emergency patients and general iid service times.We will present numerical examples.
POURAKBAR, MORTEZA ERIM Supervisor End-of-life inventory decisions for consumer electronics service parts Abstract We consider consumer electronics (CE) manufacturer problem of controlling the inventory of spare parts in the final phase of the service life cycle. The final phase starts upon termination of the production of the part and goes on till the last service contract or warranty period expires. Placing final orders for service parts are considered as a popular tactic to satisfy demand during this period and mitigate the effect of part obsolescence at the end of the service life cycle. To satisfy demand for service, previous works on final order quantity consider just repair of defective products by replacing the defective part of the product with a properly functioning spare one. However, for consumer electronic products there is remarkable price erosion while repair costs may stay steady over time. As a consequence, it brings up this idea that there might be a point in time where from that point on unit price of the product is less than repair associated costs. Therefore, it would be more cost effective to meet demand for service by means of an alternative policy such as offering customer a replacement of the defective product with a new one or offering a discount on the next generation of the product rather than repairing the defective one. Bearing this idea of an alternative policy in mind, we will explore the cost trade-offs of implementing those policies and develop an exact formulation for the expected total cost function. Based on the developed cost function we propose policies trying to find simultaneously the optimal final order quantity and time to switch from repair to an alternative replacement policy. Numerical analysis of a real world case study sheds light over the effectiveness and advantage of these policies in terms of cost reduction and also yields insights into the quantitative importance of the various cost parameters.
RETEL HELMRICH, MATHIJN Econometric Institute Supervisor Efficient reformulations of the economic lot-sizing problem with remanufacturing Abstract In light of reverse logistics, the classic economic lot-sizing problem has been extended with a remanufacturing option. In this extended problem, a known quantity of used products is returned from customers in each period. These returned products can be remanufactured, so that they are as good as new. Customer demand can then be fulfilled from both newly produced and remanufactured items. We are to determine in which periods to set-up a production process to remanufacture returned products an in which to set-up another production process to manufacture new items. A “natural” MIP formulation of this problem contains big M type constraints. These big M constraints often lead to an untight LP-relaxation. Therefore, we propose several alternative formulations of the lot-sizing problem with remanufacturing, all inspired by reformulations of the classic (single item) lot-sizing problem. The first reformulation is based on the shortest path reformulation as proposed by Eppen and Martin (1987). The second one uses a partial shortest path reformulation as proposed by Van Vyve and Wolsey (2006). The last reformulation is based on the (l, S, WW)-inequalities for the classic lot-sizing problem with Wagner-Whitin costs. Computational tests have been carried out to compare the performances of these different formulations.
RUTTEN, CYRIEL Faculty of Economics & BA Supervisors Local search performance guarantees for restricted related parallel machine scheduling Abstract We consider the problem of minimizing the makespan on restricted related parallel machines. In restricted machine scheduling each job is only allowed to be scheduled on a subset of machines. We study the worst-case behavior of local search algorithms. The following neighborhoods are considered: the jump, swap, push and lexicographical jump neighborhood. For each of these neighborhoods we analyze the quality by establishing worst-case performance guarantees for the restricted identical parallel machines, restricted related parallel machines with identical jobs and restricted related parallel machines problems. Furthermore, we provide examples to show that these performance guarantees are tight or almost tight. Keywords: Local search, performance guarantee, restricted machines, eligibility constraints.
SPLIET, REMY Erasmus University Supervisor Robust optimization in distribution networks: The vehicle rescheduling problem Abstract The capacitated vehicle routing problem is to find a routing schedule describing the order in which geographically dispersed customers are visited to satisfy demand by supplying goods stored at the depot, such that the traveling costs are minimized. In many practical applications, a long term routing schedule has to be made for operational purposes, often based on average demand estimates. When demand substantially differs, constructing a new schedule is beneficial. The vehicle rescheduling problem is to find a new schedule that not only minimizes the total traveling costs but also minimizes the costs of deviating from the original schedule. In our research project, we aim to find a robust long term schedule. The vehicle rescheduling problem is an intrinsic part of this research. In this presentation a mathematical programming formulations of the rescheduling problem is presented as well as two heuristic methods, a two-phase heuristic and a modified savings heuristic. Computational and analytical results show that for sufficiently high deviation costs, the two-phase heuristic generates a schedule that is on average close to optimal or even guaranteed optimal, for all considered problem instances. The modified savings heuristic generates schedules of constant quality, however the two-phase heuristic produces schedules that are on average closer to the optimum.
USOTSKAYA, NATALYA Dept of Quantitative Economics
Supervisor The time-optimal helicopter path is a circle segment Abstract We consider the problem of determining the fastest helicopter trajectory between two points without any obstacles. The absolute value of the helicopter speed decreases linearly in altitude, i.e., v(h) = max{v* - qh; 0}, where v* is the speed at the ground level and q is the speed loss per one meter altitude. Although intuitively one might think that the optimal path is a straight line, it is not the case in general. We show that the only time-optimal trajectory is, in fact, a circle segment.
VANBERKEL, PETER University of Twente Supervisor An exact approach for relating recovering surgical patient workload to the master surgical schedule Abstract No other department influences the workload of a hospital more than the Department of Surgery and in particular, the activities in the operating room. These activities are governed by the master surgical schedule (MSS), which states which patient types receive surgery on which day. In this paper we describe an analytical approach to project the workload for downstream departments based on this MSS. Specifically the ward occupancy distributions, patient admission/discharge distributions, and the distributions for ongoing interventions/treatments is computed. Recovering after surgery requires the support of multiple departments, such as nursing, physiotherapy, rehabilitation and long term care. With our model, managers from these departments can determine their workload by aggregating tasks associated with recovering surgical patients. The model, which supported the development of a new MSS at the Netherlands Cancer Institute-Antoni van Leeuwenhoek Hospital, provides the foundation for a decision support tool to relate downstream hospital departments to the operating room.
VEELENTURF, LUUK RSM Erasmus University PO Box 1738 3000 DR Rotterdam lveelenturf@rsm.nl
Railway crew rescheduling with retiming Abstract Railway operations are disrupted frequently. For example, the Dutch railway network experiences about three large disruptions per day on average. In such a disrupted situation part of the network or resources can not be used by the railway operators, which makes the timetable, the rolling stock schedule and the crew schedule infeasible. Then the railway operators need to quickly adjust their resource schedules. In practice, the timetable, the rolling stock schedule and the crew schedule are recovered in a sequential way. In our research however, we model and solve the crew rescheduling problem with retiming: we use the possibility of delaying the departure of some trains within the crew rescheduling problem. In this way we partially integrate timetable adjustment and crew rescheduling. For our model, we assume that the inevitable timetable changes have been taken into account already and that the rolling stock has been rescheduled according to this modified timetable. We use the retiming to prevent additional cancellations of trains next to the inevitable cancellations. The algorithm we use to solve the problem is based on column generation techniques combined with Lagrangian heuristics. In order to keep the computational times low, retiming is allowed only for those trains where it seems promising. Computational experiments with real-life disruption data show that, compared to the approach without retiming, it is possible to find better solutions by using crew rescheduling with retiming. In our experiments the computation times are less than 5 minutes, and they can be reduced by allowing parallel computations. This should make our approach applicable within a decision support system for disruption management.
WIJK, SANDRA VAN Eindhoven University of Technology Supervisors Optimal lateral transshipment policy for a two location inventory problem Abstract We consider an inventory model for spare parts with two stockpoints, providing repairable parts for a critical component of advanced technical systems. As downtime costs for these systems are huge, ready-for-use spare parts are kept on stock, to be able to quickly respond to a breakdown of a system because of the failure of a critical component. We allow for lateral transshipments of parts between the stockpoints upon a demand arrival. We are interested in the optimal lateral transshipment policy. Using dynamic programming, we completely characterize and prove the structure of the optimal lateral transshipment policy, that is, the policy for satisfying demands, minimizing the long-run average costs of the system. Demands are satisfied from own stock, via a lateral transshipment, or via an emergency procedure. This optimal policy is a threshold type policy. In addition, we derive conditions under which certain simple policies are optimal, such as the so-called complete pooling policy, a straightforward strategy often assumed in the literature.
ZONDERLAND, MAARTJE Dept. of Applied Mathematics Supervisor Planning and scheduling of semi-urgent surgeries Abstract Semi-urgent surgeries, that have to be performed within the regular operating room (OR) schedule shortly but not necessarily today, pose an uncertain demand on available hospital resources, and interfere with the planning of elective patients. For a highly utilized OR, reservation of a fraction of OR time for semi-urgent surgeries avoids excessive cancellation of elective surgeries, but may also result in unused OR time, since arrivals of semi-urgent patients are unpredictable. We consider the trade-off between cancellation of elective surgeries and unused OR time. First, using a queuing theory framework, we evaluate the OR capacity needed to accommodate every incoming semi-urgent surgery. Second, we introduce another queuing model that enables a trade-off between the cancelation rate of elective surgeries and unused OR time. Third, based on Markov decision theory, we develop a decision support tool that assists the scheduling process of elective and semi-urgent surgeries. We demonstrate our results with actual data obtained from a department of neurosurgery.
|
