TY  - THES
A1  - Kämmerer, Lutz
T1  - Mathematische Modellierung und Behandlung von Stapelproblemen
T1  - Mathematical Models of Pileproblems
N2  - Stapelprobleme treten in der Praxis in vielfältiger Form auf. So finden sich Stapelprobleme in einer großen Fülle von Variationen im Logistikbereich, aber auch im Bauwesen. Zunächst wird das klassische Turm von Hanoi Problem kurz vorgestellt. Dieses Problem wird als Stapelproblem formuliert. Weiterhin werden verzweigte Stapelproblem untersucht: Ein gegebener Stapel -- bestehend aus den Elementen v der Menge V -- soll an anderer Stelle in einer vorgeschriebenen, veränderten Struktur wieder aufgebaut werden. Dazu stehen Hilfsstapelplätze zur Verfügung. Die Optimierung dieses Problems hinsichtlich der Anzahl der benötigten Hilfsstapelplätze ist NP-vollständig. Es werden Erfahrungen mit einem Branch-and-Bound Algorithmus zur Lösung des Problems vorgestellt sowie ein heuristischer Algorithmus diskutiert. Schließlich werden verzweigte Stapelprobleme betrachtet, bei denen keine eineindeutige Zuordnung mehr von Elementen des Ausgangsstapels zu verfügbaren Positionen im Zielstapel existiert. Hier ist schon die Bestimmung einer günstigsten Zuordnung in bezug auf die Anzahl benötigter Hilfsstapelplätze NP-schwer.
N2  - Pileproblems are discrete optimization problems. In practice they occur in various ways, especially in logistics and civil engineering. First we consider the well-known Tower of Hanoi Problem as a pileproblem. Furthermore pileproblems with a branched structure are investigated: A given pile, consisting of elements v of a set V, has to be piled up in a well-defined structure on another place. Auxiliary piles are allowed to use. Computing the minimal number of necessary auxiliary piles turns out to be NP-complete. We discuss a branch-and-bound algorithm, as well as a heuristic approach to solve the problem. Finally we consider pileproblems with no unique mapping between the elements and the positions of the piles. Finding the best mapping in the sense of minimizing the number of necessary auxiliary piles is also NP-hard.
KW  - Stapelproblem
KW  - Graphentheorie
KW  - Turm von Hanoi
KW  - Sortierung von Permutationen
KW  - heuristische Lösungsverfahren
KW  - pile problem
KW  - Tower of Hanoi
KW  - permutations
KW  - heuristic solutions
Y1  - 1998
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:gbv:wim2-20040216-298
ER  - 
TY  - THES
A1  - Hommel, Angela
T1  - Fundamentallösungen partieller Differenzenoperatoren und die Lösung diskreter Randwertprobleme mit Hilfe von Differenzenpotentialen
T1  - Fundamental Solutions for Partial Difference Operators and the Solution of Discrete Boundary Value Problems by the Help of Difference Potentials
N2  - Im Mittelpunkt der Dissertation steht die Theorie der Differenzenpotentiale, die eng mit der klassischen Potentialtheorie verbunden ist. Vorgestellt wird eine Methode zur Lösung von Randwertproblemen, die nicht auf der Diskretisierung einer Randintegralgleichung beruht, sondern von der Übertragung des Problems in ein Differenzenrandwertproblem ausgeht. Das diskrete Randwertproblem wird mit Hilfe einer Randreduktionsmethode auf eine Randoperatorgleichung transformiert, die detaillierter zu untersuchen ist. Voraussetzung für den Aufbau der Theorie ist die Existenz diskreter Fundamentallösungen. Die Definition der Differenzenpotentiale wird von Ryabenkij übernommen. Seine Herangehensweise führt jedoch zu überbestimmten linearen Gleichungssystemen auf dem Rand. Durch die Aufspaltung des Randpotentials in ein diskretes Einfach- und Doppelschichtpotential wird diese Schwierigkeit in der Dissertation überwunden. Bewiesen werden Eindeutigkeits- und Lösbarkeitsaussagen für Differenzenrandwertprobleme. Das onvergenzverhalten der diskreten Potentiale wird im Kapitel 3 untersucht. Im Kapitel 4 werden numerische Resultate vorgestellt.
N2  - The theses are based on the theory of difference potentials, which are closely related to the classical potential theory. A method for solving boundary value problems is presented, that does not start from the discretization of a boundary integral equation. In the first step the original problem is replaced by a discrete boundary value problem. By the help of a boundary reduction method the discrete problem is transformed into a boundary operator equation, which is to study in more detail. An important assumption for the theory of difference potentials is the existence of discrete fundamental solutions. The definition of the difference potentials is taken from Ryabenkij. His approach leads to overdetermined linear equation systems on the boundary. By splitting the boundary potential into a discrete single-layer and double-layer potential these problems are solved in the theses. Uniqueness and existence theorems are proved for discrete boundary value problems. The convergence of the discrete potentials is investigated in chapter 3. In chapter 4 numerical results are presented.
KW  - Diskrete Fourier-Transformation
KW  - Randwertproblem
KW  - Greensche Matrix
KW  - diskrete Fundamentallösung
KW  - Lösung innerer und äußerer Randwertprobleme
KW  - Differenzenpotentiale
KW  - diskretes Einfach- und Doppelschichtpotential
KW  - discrete Fourier transform
KW  - discrete fundamental solution
KW  - solution of inner and outer boundary value problems
KW  - difference potentials
Y1  - 1998
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:gbv:wim2-20040216-303
ER  -