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 - JOUR A1 - Tesch, Alexander T1 - A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem JF - Journal of Scheduling N2 - We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997). Y1 - 2020 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Tesch, Alexander A1 - Sagnol, Guillaume T1 - Algorithmen unterstützen OP-Planung T2 - Management & Krankenhaus N2 - Mathematische Algorithmen können durch Vorhersage von Unsicherheiten optimierte OP-Pläne berechnen, sodass mehrere Zielkriterien wie Überstunden, Wartezeit und Ausfälle im OP minimiert werden. Y1 - 2019 IS - 12 SP - 20 PB - Wiley 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 - GEN A1 - Tesch, Alexander T1 - A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem N2 - We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997). T3 - ZIB-Report - 17-79 KW - Scheduling KW - Mixed-Integer Programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68485 SN - 1438-0064waoa ER - TY - GEN A1 - Sagnol, Guillaume A1 - Schmidt genannt Waldschmidt, Daniel A1 - Tesch, Alexander T1 - The Price of Fixed Assignments in Stochastic Extensible Bin Packing 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, bins 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+1/e \approx 1.368$ under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, 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. T3 - ZIB-Report - 18-19 KW - Approximation Algorithms KW - Stochastic Scheduling KW - Extensible Bin Packing Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68415 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) 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. T3 - ZIB-Report - 16-25 KW - Cumulative Scheduling KW - Energetic Reasoning KW - Sweep Line Algorithm Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59332 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - Improving Energetic Propagations for Cumulative Scheduling 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. T3 - ZIB-Report - 18-29 KW - Cumulative Scheduling KW - Constraint Programming KW - Propagation Algorithm Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69331 SN - 1438-0064 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 - 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 -