@misc{Tesch2016, author = {Tesch, Alexander}, title = {A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n)}, issn = {1438-0064}, doi = {10.1007/978-3-319-44953-1_32}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59332}, year = {2016}, abstract = {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.}, language = {en} } @misc{Tesch2016, author = {Tesch, Alexander}, title = {Exact Energetic Reasoning in O(n^2 log^2 n)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60367}, year = {2016}, abstract = {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).}, language = {en} } @misc{Tesch2016, author = {Tesch, Alexander}, title = {Improved Compact Models for the Resource-Constrained Project Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62891}, year = {2016}, abstract = {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.}, language = {en} } @inproceedings{Tesch2016, author = {Tesch, Alexander}, title = {A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n)}, volume = {22}, booktitle = {Principles and Practice of Constraint Programming (CP 2016)}, doi = {10.1007/978-3-319-44953-1_32}, pages = {493 -- 519}, year = {2016}, abstract = {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.}, language = {en} } @article{PeitzGraelerHenkeetal.2016, author = {Peitz, Sebastian and Gr{\"a}ler, Manuel and Henke, Christian and Hessel-von Molo, Mirko and Dellnitz, Michael and Tr{\"a}chtler, Ansgar}, title = {Multiobjective Model Predictive Control of an Industrial Laundry}, journal = {Procedia Technology}, number = {26}, pages = {483 -- 490}, year = {2016}, abstract = {In a wide range of applications, it is desirable to optimally control a system with respect to concurrent, potentially competing goals. This gives rise to a multiobjective optimal control problem where, instead of computing a single optimal solution, the set of optimal compromises, the so-called Pareto set, has to be approximated. When it is not possible to compute the entire control trajectory in advance, for instance due to uncertainties or unforeseeable events, model predictive control methods can be applied to control the system during operation in real time. In this article, we present an algorithm for the solution of multiobjective model predictive control problems. In an offline scenario, it can be used to compute the entire set of optimal compromises whereas in a real time scenario, one optimal compromise is computed according to an operator's preference. The results are illustrated using the example of an industrial laundry. A logistics model of the laundry is developed and then utilized in the optimization routine. Results are presented for an offline as well as an online scenario}, language = {en} } @misc{SagnolBarnerBorndoerferetal.2016, author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia and Wernecke, Klaus}, title = {Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations}, issn = {1438-0064}, doi = {10.1016/j.ejor.2018.05.022}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58502}, year = {2016}, abstract = {The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations.}, language = {en} }