TY - JOUR A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Senan A1 - Tesch, Alexander T1 - Conflict-free railway track assignment at depots JF - Journal of Rail Transport Planning & Management N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. One aspect of managing rolling stock is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with a fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we show that the TAP is NP-hard and present two integer programming models for solving the TAP. We compare both models on a theoretical level. Moreover, to our knowledge, we consider the first approach that integrates track lengths along with the three most common types of parking tracks FIFO, LIFO and FREE tracks in a common model. Furthermore, to optimize against uncertainty in the arrival times of the trains we extend our models by stochastic and robust modeling techniques. We conclude by giving computational results for both models, observing that they perform well on real timetables. Y1 - 2018 U6 - https://doi.org/10.1016/j.jrtpm.2017.12.004 ER - TY - CHAP A1 - Sagnol, Guillaume A1 - Schmidt genannt Waldschmidt, Daniel A1 - Tesch, Alexander T1 - The Price of Fixed Assignments in Stochastic Extensible Bin Packing T2 - WAOA 2018: Approximation and Online Algorithms N2 - We consider the stochastic extensible bin packing problem (SEBP) in which n items of stochastic size are packed into m bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of 2. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of (1+eāˆ’1)ā‰ˆ1.368 under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-030-04693-4_20 VL - 11312 SP - 327 EP - 347 ER - TY - CHAP A1 - Tesch, Alexander T1 - Improving Energetic Propagations for Cumulative Scheduling T2 - Principles and Practice of Constraint Programming (CP 2018) N2 - We consider the Cumulative Scheduling Problem (CuSP) in which a set of $n$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69321 ER -