Search

The focus of this thesis is on algorithmic questions that are directly linked to practica! problems from diverse applications like manufacturing, train scheduling or telecommunications. We present four problem settings together with combinatorial problems (or mathematical modeis)that are at the core of the practical applications. From this we derive both interesting theoretical and relevant practical results, which we back up by experiments. In detail, the topics of this thesis are as follows. Sequential Vector Packing We study a novel variant of the well known d-dimensional bin (or vector) packing problem that is motivated by an application from the manufacturing industry. Given a sequence of non-negative d-dimensional vectors, the goal is to pack these into as few bins as possible. In the classical problem the bin size vector is given and the sequence can be partitioned arbitrarily. We study a variation where the vectors have to be packed in the order in which they arrive. The bin size vector can be chosen once in the beginning, under the constraint that the coordinate-wise bounds sum up to at most a given total bin size. We give both theoretical results and practical algorithms that we test on the original data. Optimization of a Freight Train System We consider the optimization of a Swiss freight train service that is operated as a (multi-) hub spoke system. This can be seen as a more complicated version of classical vehicle routing problems. We derive several mathematical modeis, consider some theoretical questions linked to the operations at the hub, and test our modeis on Üie real-world instance. For the mathematical mode is we use linear programming based optimization techniques like branch and cut and column generation. OVSF Code Assignment Orthogonal Variable Spreading Factor (OVSF-) codes are used in UMTS to share the radio spectrum among several conneetions of possibly different bandwidth requirements. The combinatorial core of the OVSF code assignment problem is to assign some nodes of a complete binary tree of height /; (the code tree) to n simultaneous conneetions, such that no two assigned nodes (codes) are on the same root-to-leaf path. A connection that uses a 2~d fraction of the total band width requires some code at depth d in the tree, but this code assignmentis allowed to change over time. We consider the one-step code assignment problem: Given an assignment, move the minimum number of codes to serve a new request. Minn and Siu propose the so called DCA-algorithm to solve the problem optimally. In contrast, we show that DCA döes'not always return an optimal solution, and that the problem is NP-hard. We present results on exact, approximation, online, and fixed parameter tractable algorithms. Joint Base Station Scheduling Consider a scenario where base stations need to send data to users with wireless devices. Time is discrete and slotted into synchronous rounds. Transmitting a data item from a base station to a user takes one round. A user can receive the daLa item from any of the base stations. The positions of the base stations and users are modeled as points in the Euclidean plane. If base Station 6 transmits to user u in a certain round, no other user within distance at most \\b u\\ Im Mittelpunkt dieser Arbeit stehen algorithmische Fragen, die durch praktische Probleme aus verschiedenen Gebieten wie Fertigung,Zug-Optimierung oder Telekommunikation motiviert sind. Wir stellen vier Anwendungen vor und dazujeweils ein kombinatorisches Problem (oder ein mathematisches Modell), das den Kern dieser Anwendung ausmacht. Daraus entwickeln wir sowohl theoretisch interessante als auch praktisch relevante Resultate, die wir noch durch Experimente untermauern. Im Detail betrachten wir die folgenden Themen. Sequentielles Vector Packing Wir untersuchen eine neuartige Variante des bekannten d-dimensionalen Bin (oder auch Vector) Packing Problems, welche durch eine Anwendung aus der Fertigung motiviert ist. Gegeben sei eine Sequenz von nicht-negativend-dimensionalen Vektoren. Die Aufgabe bestehtdarin, diese in so wenig Bins („Kisten") wie möglieh zu packen. Beim klassischen Bin Packingist der Bin-Grösscnvektor gegeben und die Sequenz kann beliebig angeordnet werden. Wir untersuchen eine Variation, bei der die Vektoren in der durch die Sequenz gegebenen Reihenfolge in die Bins gepackt werden müssen. Die Bin-Grössekann anfangs gewählt werden, mit der Einschränkung, dass ihre koordinatenweise Summe eine vorgegebene Grössenicht überschreiten darf. Wir präsentieren sowohl theoretische Resultate als auch praktische Algorithmen, die wir auf den realen Daten testen. Optimierung eines Frachtbahnsystems Wir betrachten die Optimierungeines Schweizer Frachtbahnsystems, das als (Multi-)Nabe-Speiche System operiert. Das Problem kann als kompliziertere Variante klassischer Vehicle RoutingProbleme gesehen werden. Wir entwickeln eine Sequenz von mathematischen Modellen für das Problem, betrachten einige theoretische Fragestellungen bezüglich des Ablaufs an der Nabe und testen unsere Modelle auf der realen Instanz. Für die mathematischen Modelle benutzen wir Optimierungstechniken, die auf linearer Programmierung beruhen wie branchand cut oder column generation. OVSF Code Zuweisung OrthogonalVariable SpreadingFactor (OVSF-) Codes werden in UMTS Netzwerken benutzt, um es den verschiedenen Benutzern innerhalb einer Funkzelle (mit potentiell verschiedenen Bandbreitenanforderungen) zu ermöglichen, gleichzeitig auf die vorhandene Bandbreite zuzugreifen. Der kombinatorische Kern des OVSF Code-Zuweisungsproblems besteht darin, Knoten eines vollständigen binären Baumes (der Code-Baum)der Höhe h einer Menge von n aktiven Verbindungen zuzuweisen, so dass keine zwei zugewiesenenKnoten (Codes) auf dem selben Wurzel-Blatt Pfad sind. Eine Verbindung, die einen Anteil von 2~d an der gesamten Bandbreite benötigt, muss einen Code der Tiefe d im Code-Baum zugewiesen bekommen. Diese Zuweisung ist nicht fix, sondern kann sich mit der Zeit ändern. Wir betrachten das Ein-Schritt Code-Zuweisungsproblem: Gegeben eineCode-Zuweisung,bewegedie minimale Anzahl von Codes, um eine neue Anfrage zu bedienen. Minn und Siu haben den so genannten DCA-Algorithmus vorgestellt, um das Problem optimal zu lösen. Demgegenüber zeigen wir, dass DCA nicht immer die optimale Lösung liefert und dass das Problem NP-hartist. Wir geben Resultate zu exakten, approximations-, online- und fixed-parameter Algorithmen. koordiniertes Funkmast Scheduling Wir betrachten ein Szenario, in dem Funkmasten Daten an Benutzermit Mobilgerätensenden. In unserem Modell betrachten wir die Zeit als diskretisiert und in Runden segmentiert. Die Übertragungeines Datenpakets von einem Funkmasten zu einem Benutzer benötigt eine Runde. Ein Benutzer kann Daten von jedem Funkmasten empfangen. Die Positionen der Funkmasten und Benutzerwerden als Punktein der Euklidischen Ebene betrachtet. Wenn in einerRunde Funkmast b an Benutzer u sendet, kann kein anderer Benutzer innerhalb einer Distanz von ||6 u\\2 von b ein Daten paket empfangen, weil das Senden an u zu Interferenz in diesem Bereich führt. Das Ziel besteht darin, für eine gegebene Konfiguration von Benutzernund Funkmasten das Senden von Daten so zu koordinieren, dass eine minimale Anzahl von Runden benötigt wird, um alle Benutzerzu bedienen. Wir nennen dieses Problem koordiniertes Funkmast Scheduling (JBS) und betrachten es auf einer Geraden (1D-.TBS) und in der Ebene (2D-JBS). Wir untersuchen die Komplexität von 2D-. TBS sowie Approximations algorithmen für beide Varianten. Darüber hinaus analysieren wir die Graphklasseder arrow graphs, die sich als Konfliktgraph in der eindimensionalen Variante ergibt.