TY - THES A1 - Ascheuer, Norbert T1 - Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems N2 - In this thesis we describe a practical problem that we encountered in the on--line optimization of a complex Flexible Manufacturing System. In the considered system a stacker crane has to fulfill all transportation tasks (jobs) in a single aisled automatic storage system. The jobs have to be sequenced in such a way, that the time needed for the unloaded moves is minimized. The modelling of this question leads to the so--called on--line Hamiltonian path problem. We computationally compare several on--line heuristics and derive lower bounds on the value obtained by an optimal on--line strategy by analyzing two off--line Combinatorial Optimization problems: the asymmetric Hamiltonian path problem with precedence constraints, also called sequential ordering problem (SOP), and the asymmetric Hamiltonian path problem with time windows (AHPPTW). We study the SOP and AHPPTW from a polyhedral point of view and derive several new classes of valid inequalities. Based on the polyhedral investigations we develop branch&cut algorithms for both problems and can achieve encouraging results on solving problem instances from real--world examples of the practical application. T3 - ZIB-Report - TR-96-03 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5328 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - Solving the Asymmetric Travelling Salesman Problem with Time Windows by Branch-and-Cut N2 - Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions. T3 - ZIB-Report - SC-99-31 KW - Asymmetric Travelling Salesman Problem KW - Time Windows KW - Integer Programs KW - Branch&Cut-Algorithm KW - Heuristics KW - Control of Stacker Cranes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4191 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Combinatorial Online Optimization N2 - In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material. T3 - ZIB-Report - SC-98-24 KW - Online Optimization KW - competitiveness KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3674 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - A polyhedral study of the asymmetric travelling salesman problem with time windows N2 - The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances. T3 - ZIB-Report - SC-97-11 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2807 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Schorer, Herbert T1 - Simulation und Optimierung einer PC-Fertigung unter Echtzeitbedingungen N2 - Die Business Unit PC in Augsburg ist die zentrale Produktionsstätte der Siemens--Nixdorf Informationssysteme (SNI) AG für Personal Computer sowie für einige Periphärgeräte. Das Werk, entworfen nach modernen CIM/CAI--Konzepten (Computer Integrated Manufacturing/ Computer Aided Industry), wurde 1987 errichtet. Bald zeigte sich jedoch, daß es für ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engpässe im Produktionsbetrieb darstellen. Das Management suchte nach Möglichkeiten, den Produktionsfluß zu verbessern, ohne teure technische Änderungen am System vornehmen zu müssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums für Informationstechnik (die ehemals an der Universität Augsburg ansässig war) analysierte, unterstützt von einigen Studenten und Ingenieuren der SNI, den Produktionsfluß und lokalisierte Schwachstellen. Basierend auf diesen Erkenntnissen wurden mathematische Fragestellungen erarbeitet und auf mathematischen Optimierungsverfahren basierende Softwarepakete entwickelt, die jetzt teilweise bei SNI im Einsatz sind. Im folgenden werden einige dieser Fragestellungen, deren Modellierung und mathematische Behandlung beschrieben. Einige der Ansätze, die hier dargestellt werden sollen, sind teilweise schon in Grötschel [Grö92] angesprochen worden. T3 - ZIB-Report - SC-95-04 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1700 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin T1 - Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs N2 - We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems. T3 - ZIB-Report - SC-98-08 KW - Traveling Salesman Problem KW - Online-Algorithm KW - Automatic Storage System Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3519 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints N2 - In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time. T3 - ZIB-Report - SC-97-70 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3391 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Kamin, Nicola A1 - Rambau, Jörg T1 - Combinatorial Online Optimization in Practice N2 - This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems. T3 - ZIB-Report - SC-98-07 KW - Online optimization KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3508 ER - TY - CHAP A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Schorer, Herbert ED - Bachem, Achim ED - Jünger, Michael ED - Schrader, Rainer T1 - Simulation und Optimierung einer PC-Fertigung unter Echtzeitbedingungen T2 - Mathematik in der Praxis. Fallstudien aus Industrie, Wirtschaft, Naturwissenschaften und Medizin Y1 - 1995 SP - 261 EP - 277 PB - Springer ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Kamin, Nicola A1 - Rambau, Jörg T1 - Combinatorial online optimization in practice JF - OPTIMA Y1 - 1998 VL - 57 SP - 1 EP - 6 ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - A Polyhedral Study of the Asymmetric Traveling Salesman Problem with Time Windows JF - Networks Y1 - 2000 VL - 36 IS - 2 SP - 69 EP - 79 ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut JF - Mathematical Programming, Series A Y1 - 2001 VL - 90 IS - 3 SP - 475 EP - 506 PB - Springer ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Abdel-Hamid, Atef Abdel-Aziz T1 - Order picking in an automatic warehouse JF - Mathematical Methods of Operations Research Y1 - 1999 VL - 49 IS - 3 SP - 501 EP - 515 ER - TY - CHAP A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg ED - Kall, Peter ED - Lüthi, Hans-Jakob T1 - Combinatorial Online Optimization T2 - Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research Zurich, August 31 – September 3, 1998 Y1 - 1999 SP - 21 EP - 37 PB - Springer ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Escudero, Laureano A1 - Grötschel, Martin A1 - Stoer, Mechthild T1 - A Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing) JF - SIAM Journal on Optimization Y1 - 1993 VL - 3 IS - 1 SP - 25 EP - 42 ER - TY - CHAP A1 - Ascheuer, Norbert A1 - Escudero, Laureano A1 - Grötschel, Martin A1 - Stoer, Mechthild ED - Kannan, Ravi ED - Pulleyblank, William T1 - On Identifying in Polynomial Time Violated Subtour Elimination and Precedence Forcing Constraints for the Sequential Ordering Problem T2 - Integer Programming and Combinatorial Optimization, Proceeedings of a Conference held at the University of Waterloo, May 28-30, 1990 Y1 - 1990 SP - 19 EP - 28 PB - University of Waterloo Press ER - TY - GEN A1 - Ascheuer, Norbert A1 - Krumke, Sven A1 - Rambau, Jörg T1 - The Online Transportation Problem: Competitive Scheduling of Elevators N2 - In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service. T3 - ZIB-Report - SC-98-34 KW - online optimization KW - competitive analysis KW - elevator Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3779 ER -