@incollection{GroetschelHillerTuchscherer2009, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Structuring a Dynamic Environment}, booktitle = {Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines}, editor = {Lucas, Klaus and Roosen, Peter}, publisher = {Springer}, doi = {10.1007/978-3-642-00870-2}, pages = {199 -- 214}, year = {2009}, language = {en} } @misc{GroetschelHillerTuchscherer2007, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Combinatorial Online Optimization: Elevators \& Yellow Angels}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10360}, number = {07-36}, year = {2007}, abstract = {In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon.}, language = {en} } @article{GroetschelHinrichsSchroeeretal.2006, author = {Gr{\"o}tschel, Martin and Hinrichs, Hinrich and Schr{\"o}er, Klaus and Tuchscherer, Andreas}, title = {Ein gemischt-ganzzahliges lineares Optimierungsmodell f{\"u}r ein Laserschweißproblem im Karosseriebau}, volume = {101}, journal = {Zeitschrift f{\"u}r wirtschaftlichen Fabrikbetrieb (ZWF) Karosseriebau}, number = {5}, pages = {260 -- 264}, year = {2006}, language = {en} } @phdthesis{Tuchscherer2010, author = {Tuchscherer, Andreas}, title = {Local Evaluation of Policies for Discounted Markov Decision Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11963}, school = {Freie Universit{\"a}t Berlin}, pages = {208}, year = {2010}, abstract = {Providing realistic performance indicators of online algorithms for a given online optimization problem is a difficult task in general. Due to significant drawbacks of other concepts like competitive analysis, Markov decision problems (MDPs) may yield an attractive alternative whenever reasonable stochastic information about future requests is available. However, the number of states in MDPs emerging from real applications is usually exponential in the original input parameters. Therefore, the standard methods for analyzing policies, i.e., online algorithms in our context, are infeasible. In this thesis we propose a new computational tool to evaluate the behavior of policies for discounted MDPs locally, i.e., depending on a particular initial state. The method is based on a column generation algorithm for approximating the total expected discounted cost of an unknown optimal policy, a concrete policy, or a single action (which assumes actions at other states to be made according to an optimal policy). The algorithm determines an \$\varepsilon\$-approximation by inspecting only relatively small local parts of the total state space. We prove that the number of states required for providing the approximation is independent of the total number of states, which underlines the practicability of the algorithm. The approximations obtained by our algorithm are typically much better than the theoretical bounds obtained by other approaches. We investigate the pricing problem and the structure of the linear programs encountered in the column generation. Moreover, we propose and analyze different extensions of the basic algorithm in order to achieve good approximations fast. The potential of our analysis tool is exemplified for discounted MDPs emerging from different online optimization problems, namely online bin coloring, online target date assignment, and online elevator control. The results of the experiments are quite encouraging: our method is mostly capable to provide performance indicators for online algorithms that much better reflect observations made in simulations than competitive analysis does. Moreover, the analysis allows to reveal weaknesses of the considered online algorithms. This way, we developed a new online algorithm for the online bin coloring problem that outperforms existing ones in our analyses and simulations.}, language = {en} } @article{HillerKlugTuchscherer2013, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups}, journal = {Flexible Services and Manufacturing Journal}, doi = {10.1007/s10696-013-9175-6}, pages = {1 -- 24}, year = {2013}, language = {en} } @inproceedings{HillerKlugTuchscherer2009, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improving the performance of elevator systems using exact reoptimization algorithms}, booktitle = {Proceedings of MAPSP}, pages = {224 -- 226}, year = {2009}, language = {en} } @inproceedings{HillerKlugTuchscherer2010, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improved destination call elevator control algorithms for up peak traffic}, booktitle = {Operations Research Proceedings 2010}, publisher = {Springer}, year = {2010}, language = {en} } @inproceedings{HeinzKrumkeMegowetal.2006, author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, volume = {3879}, booktitle = {Proc. 3rd Workshop on Approximation and Online Algorithms}, editor = {Erlebach, Thomas and Persiano, Giuseppe}, publisher = {Springer}, pages = {230 -- 243}, year = {2006}, language = {en} } @inproceedings{HillerTuchscherer2008, author = {Hiller, Benjamin and Tuchscherer, Andreas}, title = {Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers}, booktitle = {Operations Research Proceedings}, editor = {Kalcsics, J{\"o}rg and Nickel, Stefan}, publisher = {Springer}, pages = {357 -- 362}, year = {2008}, language = {en} } @inproceedings{HillerKrumkeSalibaetal.2009, author = {Hiller, Benjamin and Krumke, Sven and Saliba, Sleman and Tuchscherer, Andreas}, title = {Randomized Online Algorithms for Dynamic Multi-Period Routing Problems}, booktitle = {Proceedings of MAPSP}, pages = {71 -- 73}, year = {2009}, language = {en} }