TY - CHAP A1 - Tesch, Alexander T1 - Improved Compact Models for the Resource-Constrained Project Scheduling Problem T2 - Operations Research Proceedings 2016 N2 - In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments. Y1 - 2017 SP - 25 EP - 30 ER - TY - GEN A1 - Tesch, Alexander T1 - Exact Energetic Reasoning in O(n^2 log^2 n) N2 - In this paper, we address the Energetic Reasoning propagation rule for the Cumulative Scheduling Problem (CuSP). An energetic reasoning propagation algorithm is called exact, if it computes the maximum possible energetic reasoning propagation for all the jobs. The currently best known exact energetic reasoning algorithm has complexity O(n^3). In this paper, we present a new exact energetic reasoning propagation algorithm with improved complexity of O(n^2 \log^2 n). T3 - ZIB-Report - 16-46 KW - Cumulative Scheduling KW - Energetic Reasoning KW - Sweep Line KW - Constraint Programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60367 SN - 1438-0064 N1 - Preprint Version ER - TY - THES A1 - Tesch, Alexander T1 - Compact MIP Models for the Resource-Constrained Project Scheduling Problem N2 - In the Resource-Constrained Project Scheduling Problem (RCPSP) a set of jobs is planned subject to resource- and precedence constraints. The objective is to minimize the makespan, that is the time when all jobs have been completed. There exist several Mixed-Integer-Programming (MIP) models in order to solve the problem. Most common models are based on time-discretization. In this case, the scheduling horizon is split into unit size intervals and each job gets assigned a unique starting interval. The drawback of time-discrete models is the computational intractability for large scheduling horizons or fine discretizations. In this connection, this thesis deals with compact MIP models where the model size is independent of the scheduling horizon. In addition to two compact models from the literature, we present two new compact models. We investigate their induced polyhedra and deduce an inclusion hierarchy via linear transformations. Moreover, we give a combinatorial interpretation of these transformations. Furthermore, we study a class of valid cutting planes for the compact models, which are known as cover inequalities. In order to strengthen these cutting planes we introduce a lifting algorithm that is independent of the model size. Subsequently, we examine lower bounds for the RCPSP from linear programming. Based on a linear transformation, we reveal a connection between two approaches from the literature. For one model we generate strong cutting planes that are obtained from a primal-dual relation between the models. Two cutting plane algorithms are derived. Likewise, we show that similar cutting planes can be transferred to the compact MIP models. Our models have been implemented, tested and evaluated on the instances of the PSPLIB problem library. KW - Resource-Constrained Project Scheduling KW - Compact MIP Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60208 ER - TY - CHAP A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots T2 - Proceedings of the IAROR conference RailLille N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem 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 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 present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. Y1 - 2017 ER - TY - GEN A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem 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 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 present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. T3 - ZIB-Report - 17-23 KW - Depot Planning KW - Railway Track Assignment Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63843 SN - 1438-0064 ER - TY - THES A1 - Tesch, Alexander T1 - Optimization of Large-Scale Conference Schedules N2 - Scientific conferences play an important role in almost all areas of today’s science and research. They offer a wide platform for international researchers and developers for communication and scientific exchange of current problems, experiences and knowledge in nearly all fields of research. Such conferences usually consist of talks about different topics that are given by authorized speakers. The planning process of a conference includes the creation of a scientific program schedule, that means a local and temporal allocation of all available talks. As the number of talks can grow into thousands for large-scale conferences, the conference scheduling becomes a complex challenge. Furthermore there exist a great bandwidth on various and individual requirements on the allocation of the talks. In this thesis we discuss the major problems that occur during the development of a conference schedule and provide a framework how proper conference schedules can be generated computationally. For that, we use Mixed-Integer-Programming techniques to find sched- ules that respect the difficult range of additional constraints. The basis of this thesis was the development of an optimized conference schedule of the International Symposium on Mathematical Programming 2012 (ISMP 2012) in Berlin, Germany. The ISMP is one of the largest conferences in the field of applied mathematics and mathematical optimization and constitutes a great attraction for in- ternational mathematicians and researchers. We will present our results based on the problem instance that we used for the ISMP 2012. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-49506 ER - 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 - Tesch, Alexander T1 - A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) T2 - Principles and Practice of Constraint Programming (CP 2016) N2 - In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-44953-1_32 VL - 22 SP - 493 EP - 519 ER - TY - JOUR A1 - Tesch, Alexander T1 - Kompakte MIP Modelle für das Ressourcenbeschränkte Projektplanungsproblem JF - OR News Y1 - 2016 VL - 58 SP - 19 EP - 21 ER - TY - GEN A1 - Tesch, Alexander T1 - Improved Compact Models for the Resource-Constrained Project Scheduling Problem N2 - In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments. T3 - ZIB-Report - 16-76 KW - Scheduling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62891 SN - 1438-0064 ER -