350
eng
reportzib
0
1998-02-25
1998-02-25
--
Combinatorial Online Optimization in Practice
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.
SC-98-07
351
urn:nbn:de:0297-zib-3508
Appeared in: OPTIMA - Mathematical Programming Society Newsletter, Nr. 57, March 1998, pp. 1-6
Norbert Ascheuer
Martin Grötschel
Nicola Kamin
Jörg Rambau
ZIB-Report
SC-98-07
eng
uncontrolled
Online optimization
eng
uncontrolled
combinatorial optimization
eng
uncontrolled
real-world problems
Informatik, Informationswissenschaft, allgemeine Werke
Transportation, logistics
Case-oriented studies
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/350/SC-98-07.ps
https://opus4.kobv.de/opus4-zib/files/350/SC-98-07.pdf
3117
1998
1998
eng
1
6
57
article
0
--
--
--
Combinatorial online optimization in practice
OPTIMA
urn:nbn:de:0297-zib-3508
Norbert Ascheuer
Martin Grötschel
Nicola Kamin
Jörg Rambau
Mathematical Optimization
Grötschel, Martin
367
eng
reportzib
0
1998-09-22
1998-09-22
--
Combinatorial Online Optimization
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.
SC-98-24
368
urn:nbn:de:0297-zib-3674
Appeared in: Proceedings of the International Conference of Operations Research Zürich (OR'98), Springer, 1999, pp. 21-37
Norbert Ascheuer
Martin Grötschel
Sven Krumke
Jörg Rambau
ZIB-Report
SC-98-24
eng
uncontrolled
Online Optimization
eng
uncontrolled
competitiveness
eng
uncontrolled
combinatorial optimization
eng
uncontrolled
real-world problems
Informatik, Informationswissenschaft, allgemeine Werke
Transportation, logistics
Combinatorial optimization
Applications of mathematical programming
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/367/SC-98-24.ps
https://opus4.kobv.de/opus4-zib/files/367/SC-98-24.pdf
3123
1999
1999
eng
21
37
conferenceobject
Springer
0
--
--
--
Combinatorial Online Optimization
Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research Zurich, August 31 – September 3, 1998
urn:nbn:de:0297-zib-3674
Norbert Ascheuer
Peter Kall
Martin Grötschel
Hans-Jakob Lüthi
Sven Krumke
Jörg Rambau
Mathematical Optimization
Grötschel, Martin
377
eng
reportzib
0
1998-12-08
1998-12-08
--
The Online Transportation Problem: Competitive Scheduling of Elevators
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.
SC-98-34
378
urn:nbn:de:0297-zib-3779
Appeared as: Online Dial-a-Ride Problems: in: Minimizing the Completion Time. Proceeding of the 17th International Symposium on Theoretical Aspects of Computer Science, Vol 1770 of Lecture Notes in Computer Science, Springer 2000, 639-650
Norbert Ascheuer
Sven Krumke
Jörg Rambau
ZIB-Report
SC-98-34
eng
uncontrolled
online optimization
eng
uncontrolled
competitive analysis
eng
uncontrolled
elevator
Informatik, Informationswissenschaft, allgemeine Werke
Modes of Computation
Transportation, logistics
Combinatorial optimization
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/377/SC-98-34.ps
https://opus4.kobv.de/opus4-zib/files/377/SC-98-34.pdf
386
eng
reportzib
0
1999-01-27
1999-01-27
--
The Generalized Baues Problem for Cyclic Polytopes II
Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d < d' < n$.
SC-98-43
387
urn:nbn:de:0297-zib-3862
Appeared in: Publications de l'Institut Mathematique, Belgrade 66 (1999) 3-15
Christos A. Athanasiadis
Jörg Rambau
Francisco Santos
ZIB-Report
SC-98-43
eng
uncontrolled
Generalized Baues Problem
eng
uncontrolled
Polyhedral Subdivisions
eng
uncontrolled
Induced Subdivisions
eng
uncontrolled
Poset
eng
uncontrolled
Spherical
eng
uncontrolled
Cyclic Polytopes
eng
uncontrolled
Bistellar Operations
Informatik, Informationswissenschaft, allgemeine Werke
None of the above, but in this section
Tilings in n dimensions [See also 05B45, 51M20]
ZIB Allgemein
ZIB-PolSub
https://opus4.kobv.de/opus4-zib/files/386/SC-98-43.ps
https://opus4.kobv.de/opus4-zib/files/386/SC-98-43.pdf
837
eng
reportzib
0
2005-01-05
2005-01-05
--
Online-Optimization of Multi-Elevator Transport Systems with Reoptimization Algorithms based on Set-Partitioning Models
We develop and experimentally compare policies for the control of a system of $k$ elevators with capacity one in a transport environment with $\ell$ floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each req uest and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average sq uared waiting times can be implemented to run in real-time ($1\,s$) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used polic ies like multi-server variants of greedy and nearest neighbor.
05-03
837
urn:nbn:de:0297-zib-8373
Appeared in: Discrete Applied Mathematics 154 (2006) 1908-1931
Philipp Friese
Jörg Rambau
ZIB-Report
05-03
eng
uncontrolled
elevator group control
eng
uncontrolled
policy
eng
uncontrolled
reoptimization
eng
uncontrolled
online
eng
uncontrolled
real-time
eng
uncontrolled
simulation
Informatik, Informationswissenschaft, allgemeine Werke
Transportation, logistics
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/837/ZR-05-03.ps
https://opus4.kobv.de/opus4-zib/files/837/ZR-05-03.pdf
397
eng
reportzib
0
1999-03-12
1999-03-12
--
Simulation Studies for the Online-Dial-a-Ride Problem
In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.
SC-99-09
398
urn:nbn:de:0297-zib-3976
Martin Grötschel
Dietrich Hauptmeier
Sven Krumke
Jörg Rambau
ZIB-Report
SC-99-09
eng
uncontrolled
online optimization
eng
uncontrolled
competitive analysis
eng
uncontrolled
elevator
eng
uncontrolled
simulation studies
Informatik, Informationswissenschaft, allgemeine Werke
Modes of Computation
Transportation, logistics
Combinatorial optimization
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/397/SC-99-09.ps
https://opus4.kobv.de/opus4-zib/files/397/SC-99-09.pdf
643
eng
reportzib
0
2001-07-24
2001-07-24
--
Online Optimization of Complex Transportation Systems
This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.
01-17
644
urn:nbn:de:0297-zib-6438
Appeared in: Online Optimization of Large Scale Systems, Springer (2001)
Martin Grötschel
Sven Krumke
Jörg Rambau
ZIB-Report
01-17
Informatik, Informationswissenschaft, allgemeine Werke
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/643/ZR-01-17.ps
https://opus4.kobv.de/opus4-zib/files/643/ZR-01-17.pdf
417
deu
reportzib
0
1999-08-18
1999-08-18
--
Wo bleibt der Aufzug?
Dieser Artikel gibt eine allgemeinverständliche Einführung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung.
SC-99-29
418
urn:nbn:de:0297-zib-4175
Erschienen in: OR News Nr. 5, März 1999, ISSN 1437-2045, S. 11-13
Martin Grötschel
Sven Krumke
Jörg Rambau
ZIB-Report
SC-99-29
deu
uncontrolled
Aufzugsteuerung
deu
uncontrolled
Online-Optimierung
deu
uncontrolled
Echtzeit-Optimierung
deu
uncontrolled
kompetitive Analyse
Informatik, Informationswissenschaft, allgemeine Werke
Research exposition (monographs, survey articles)
Combinatorial optimization
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/417/SC-99-29.ps
https://opus4.kobv.de/opus4-zib/files/417/SC-99-29.pdf