TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenAbstracts COGA-Seminar

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

Abstracts for COGA-Seminar WS2013/14

Tobias Klein: Smith's rule im deterministischen und stochastischen Scheduling

In dieser Arbeit wird das Problem betrachtet, die gewichtete Summe der Fertigstellungszeiten in einem unterbrechungsfreien Schedule auf identischen parallelen Maschinen zu minimieren. Dabei analysieren wir für deterministische und stochastische Varianten des Problems die Güte von Smith’s rule, einer Heuristik, welche die Jobs nach ihrem Verhältnis von Gewicht zu (erwarteter) Bearbeitungsdauer zunächst absteigend sortiert und den Maschinen dann in dieser Reihenfolge zuweist.

Für den deterministischen Fall geben Kawaguchi und Kyan 1986 eine Gütegarantie von (1+sqrt(2))/2 ~ 1,207 und zeigen anhand einer Instanz, dass diese Schranke scharf ist – wir betrachten hier den 2011 von Schwiegelshohn vorgestellten Beweis dieser Gütegarantie. Für den stochastischen Fall zeigen Jagtenberg, Schwiegelshohn und Uetz 2011 durch eine Stochastifizierung der deterministischen Variante, dass die Gütegarantie nicht besser ist als 1, 243 sein kann – auch dieser Beweis wird umfassend vorgestellt.

Rebecca Maier: Koordinationsmechanismen bei eigennütziger Planung in Scheduling-Spielen

Es wird das Maschinenbelegungsproblem betrachtet, bei denen eine gegebene Menge von Jobs auf einer Menge von parallel arbeitenden Maschinen bearbeitet werden müssen. Dabei wird jedem Job eine Bearbeitungszeit auf jeder Maschine zugeordnet und von genau einer Maschine ohne Unterbrechung bearbeitet. Die Kosten eines Jobs entspricht gerade der Fertigstellungszeit auf seiner Maschine. Wird dieses Problem spieltheoretisch aufgefasst, handelt es sich bei den Spielern um die Jobs, die sich eine Maschine so wählen, dass ihre Kosten minimiert werden (entspricht also privaten Zielfunktion). Die konkurrierende globale Zielfunktion will den maximalen Makespan der Maschinen minimieren.

Unter diesen Annahmen werden verschiedene Bearbeitungsreihenfolgemechanismen auf den Maschinen untersucht und betrachtet, inwiefern dies zu einem Nashgleichgewicht führt bzw. wie dieses Nashgleichgewicht eine optimale soziale Verteilung approximiert. Ich werde Approximationsschranken aufzeigen, die von Immorlica, Mirrokni und Schulz gefunden wurden.

Lilli Bergner: Integrality Gap of Bin Packing

Bin packing is a problem from the field of combinatorial optimization in which a set of items with given sizes smaller than 1 is to be assigned to a minimum number of subsets, each of sum at most 1. It is an important open question to determine whether the integrality gap of the Gilmore-Gomory LP formulation of bin packing can be bounded by a small constant such as 2. A $O(\log^2 n)$ upper bound has been proven 30 years ago, however, numerous experiments suggest that even finding instances with gap equal to or slightly larger than 1 is very difficult.

The presentation will focus on the algorithmic complexity of the problem of finding instances with large integrality gap. I show that this problem can be formulated as a bilevel integer linear program, thus conjecturing its $\Sigma_2$-hardness. Finally, I will present a heuristic approach to solving this problem.

Salih Becirovic: Effiziente Koordinationsmechanismen für Unrelated Machine Scheduling Probleme

Bei Unrelated Machine Scheduling Problemen ist eine Menge von Jobs und Maschinen gegeben. Ein Job kann unterschiedliche Bearbeitungszeiten auf den Maschinen haben und die Aufgabe besteht darin, eine optimale Zuordnung der Jobs zu den Maschinen zu finden. Je nachdem, wie die Zielfunktion aussieht, können verschieden Zuordnungen optimal sein. Als Zielfunktion betrachten wir die Minimierung der maximalen Fertigstellungszeit.

Man wählt nun einen spieltheoretischen Ansatz um Unrelated Maschine Scheduling Probleme effizient zu lösen, indem man die Jobs als Spieler betrachtet und die Wahl einer Maschine ist eine mögliche Strategie. Koordinationsmechanismen sollen eine möglichst gute Zuordnung finden. Es werden für Unrelated Machine Scheduling Probleme drei effiziente Koordinationsmechanismen vorgestellt und analysiert. Die Zuordnungen, die wir durch die Koordinationsmechanismen erhalten sind Nash-Gleichgewichte. Es wird ein Vergleich dieser Koordinationsmechanismen bezüglich dem Price of Anarchy und der Existenz von Nash-Gleichgewichten durchgeführt. Abschließend wird für einen der Mechanismen eine mögliche Implementierung vorgestellt und es werden Instanzen gesucht, bei denen ein Nash-Gleichgewicht erst nach vielen Runden erreicht wird. 

Thilo Grimm: Scheduling Probleme mit dedizierten Maschinen und eine Anwendung auf Telekommunikationsprobleme

Diese Arbeit behandelt ein Scheduling Problem mit dedizierten Maschinen. Jobs müssen ohne Unterbrechung ausgeführt werden und das Ziel ist es den Makespan zu minimieren. Das Problem stammt aus der Telekommunikation.

Im Verlauf der Arbeit wird das Problem in einen mathematischen Zusammenhang gebracht und die Komplexität analysiert. Es findet ein Übertrag von einem graphentheoretischen auf das gezeigt Problem statt. Des Weiteren werden Algorithmen gezeigt, die das Problem in geringer Laufzeit lösen und gemischt ganzzahlige Programme die optimale Lösungen des Problems erzeugen. Letztendlich werden die Ergebnisse verglichen und eine Empfehlung ausgesprochen wie das Problem in der Praxis behandelt werden sollte.

Sebastian Kamprath: Paralleles Sortieren in Stapelnetzwerken mit linearer Substruktur

In Stahlwerken sind Zwischenlager oftmals logistischer Engpass der Produktionskette. Stahlbrammen aus der Herstellung müssen dort auf Stapeln abgelegt werden und stehen ggf. nicht sofort für die Weiterverarbeitung zur Verfügung. Um Rohlinge zum Lagerausgang zu liefern, muss Zeit und Arbeit in das Sortieren und Transportieren investiert werden. Mit dem Ziel die Arbeitszeit zu verkürzen, werden diese Aufgaben von mehreren, auf den gleichen Schienen gelagerten, Kränen bewerkstelligt. Folglich kommt es dabei zu Kollisionen. Unter der Bedingung die Lagereingaben zu verstauen, gilt es die Zeit für die Bedienung des Lagerausgangs zu minimieren.

Im kollisionsfreien Fall haben König et al. dieses Problem in der Entscheidungsversion als PSPACE-vollständig identifiziert. Zur Lösung von Instanzen diente ein Greedy-Algorithmus im Lagerzustandsraum mit einer problemangepassten, heuristischen Zielfunktion. Ein MIP berechnet instanzabhängige untere Schranken für den Makespan. Felsner und Pergel untersuchten die minimale und maximale Anzahl an benötigten Umsortierungen einer Permutation in einem vollständigen Netzwerk von k Stacks.

Ziel meiner Arbeit ist es, auf Basis obiger Grundlagen, untere und obere Schranken für den Fall mehrerer Kräne anzugeben und zu klären wann eine solche Sortierung überhaupt möglich ist. Ebenso sollen heuristische Lösungsansätze in Implementierungen untersucht werden.

Daniel Schmand: Pure Nash equilibria in the atomic selfish routing game

The "atomic selfish routing game" is a game with independent players, who try to find a cheapest path for themselves in a network. It is given a source-sink pair for each player and the amount of traffic every player sends from its source to its sink. In addition to that every player knows the previously given load-dependent cost function for every edge.

We will consider a possibility to share the occurring costs on each edge "fairly" between the players such that we can guarantee the existence of a so called Nash-equilibrium, that is a situation in the network such that no player can reduce its costs by only changing its own path. This Shapley-based cost sharing method was first introduced by Tim Roughgarden and induces a potential function. We will use this potential function to show the existence and to analyze the quality of these Nash-equilibria.

Julia Kern: Ein 2-Approximationsalgorithmus für das Prize-Collecting Steiner-Baum Problem

Für das Prize-Collecting Steiner-Baum Problem wird ein ungerichteter Graph mit nicht-negativen Knoten- und Kantenpreisen sowie einem ausgezeichneten Knoten als Wurzel gegeben. Ziel ist es nun eine Teilmenge der Knoten und Kanten zu finden, die die Wurzel enthält und den Profit maximiert. Dabei tragen ausgewählte Knoten positiv und ausgewählte Kanten negativ zum Profit bei. Für jeden ausgewählten Knoten muss es einen Weg von der Wurzel geben. Das Prize-Collecting Steiner-Baum Problem ist eine Verallgemeinerung des Steiner-Baum Problems mit Terminalen und damit auch NP-vollständig.

Im Vortrag wird ein primal-dualer 2-Approximationsalgorithmus mit den wesentlichen Beweisideen der Approximationsschranke gezeigt.

Im Rahmen der Bachelorarbeit wurde der Approximationsalgorithmus leicht verändert und implementiert. Parallel wurde ein exakter Algorithmus mit CPLEX umgesetzt. Die beiden Algorithmen und Ergebnisse der durchgeführten Implementationen werden vorgestellt.

Valentin Dauth: Network Design Games on Undirected Graphs with Fair Cost Allocation

In network design games self-interested players each attempt to connect an own set of designated notes, terminals, in a graph, here undirected, evenly distributing the cost of used edges between using players. Each player will change its connection if that decreases the player's overall cost. If no player can decrease its cost like that the game is in a Nash equilibrium. The game is in a social optimum if its combination of connections yields the minimum total cost of edges used.

Anshelevich et al. (2008) demonstrated the price of stability, i.e. the ratio of cost of cheapest Nash equilibrium over social optimum cost, is bound up by H(k), i.e. the k-th harmonic number where k is the number of players. Anshelevich et al. (2008) also showed that in games with two players both with two terminals and a single source, i.e. one terminal shared between players, the price of stability is tightly bound by 4/3<3/2=H(2).

This thesis aspires to tightly bound three-player, single-source games by use of optimization models. Disser et al. (2013) bounded up games with two terminals per player strictly below H(k). We will aim at generalizing their methods to multiterminals, i.e. players may have two or more terminals.

Jessica Raffaelli: Models and Methods for Management

This presentation will concern models and methods for management. In particular, when scarce resources must be considered. In this context, models and optimization algorithms need to include a set of constraints according to different resources.

Norman Vincent Backhaus: Paarweise Gleichgewichte in minimalen Aufwandsspielen

Ein Aufwandsspiel wird in einem (sozialen) Netzwerk gespielt, in dem die Spieler durch die Knoten repräsentiert sind. Jeder Spieler kann einen Teil eines gewissen Gutes (Geld, Zeit etc.) in die Beziehungen zu den an ihn angrenzenden Spieler investieren. Der Nutzen eines Spielers hängt von den Einsätzen der Spieler auf den adjazenten Kanten ab. Wir zeigen, dass in Spielen, in denen der Ertrag einer Kante lediglich vom Minimum der Einsätze der adjazenten Spieler abhängt, stets ein paarweises Gleichgewicht existiert. Paarweise Gleichgewichte sind eine Verschärfung reiner Nash-Gleichgewichte, die sogar robust gegenüber der gleichzeitigen Abweichung zweier Spieler sind.

Wir präsentieren Algorithmen, die ein paarweises Gleichgewicht berechnen und werden durch Angabe einer konkreten Instanz zeigen, dass der Preis der Stabilität unbeschränkt ist.

János Höner: Optimale Tutorienvergabe

Die Tutorienvergabe an der TU Berlin ist ein Anwendungsbeispiel für das Post-Enrollment-Course-Timetabling Problem. Dabei geht es im Allgemeinen um die Verteilung von Veranstaltungen und Teilnehmern auf Räume und Zeiten unter Berücksichtigung diverser Rahmenbedingungen. Im Vortrag wird ein neues IP-Modell zur Lösung dieses Problems an der TU Berlin vorgestellt. Dazu wird zunächst das Problem selbst und die aktuell verwendete Modellierung vorgestellt, um dann eine Reihe von Erweiterungen einzuführen, für die im Rahmen der Bachelorarbeit eine neue Formulierung gefunden wurde. Für beide Modellierungen soll eine graphentheoretische Interpretation als kostenminimaler Fluss mit Nebenbedingungen geliefert werden.

Die neue Modellierung wurde implementiert und der Vergleich mit alten Lösungen aus dem Wintersemester 12/13 zeigt eine deutliche Verbesserung.

Antje Lehmann: Über Variationen des Standortentscheidungsproblems

Das Standortentscheidungsproblem ist ein Problem aus der kombinatorischen Optimierung, bei dem aus einer gegebenen Menge von Standorten eine Teilmenge ausgesucht und eine gegebene Menge von Kunden vollständig an die eröffneten Standorte angebunden wird. Ziel ist, die Summe aus Eröffnungs- und Anbindungskosten zu minimieren. Es ist im Allgemeinen NP-schwer. Eine Variation ist das beschränkte Standortproblem, bei welchem an jedem Standort nur höchstens eine bestimmte Anzahl von Kunden angebunden werden kann. Hier wurde u.A. für den Spezialfall mit konstanten Standorteröffnungskosten eine 5-Approximation von Levi et al. gegeben.

Wir betrachten den Fall, dass an jeden Standort entweder keine oder exakt eine vorher gegebene Anzahl an Kunden angebunden wird und untersuchen Komplexität und Approximationsalgorithmen.

Lin Chen: On the optimality of the approximation schemes for the classical scheduling problem

We consider the classical scheduling problem on parallel identical machines to minimize the makespan, and achieve the following results under the Exponential Time Hypothesis (ETH).

1. The scheduling problem on a constant number $m$ of identical machines, denoted as Pm||C_{max}, is known to admit an FPTAS of running time $O(n) + (1/\epsilon)^{O(m)}$. We prove it is essentially the best possible in the sense that a $(1/\epsilon)^{O(m^{1-d}) }+n^{O(1)}$ time FPTAS for any d>0 implies that ETH fails.

2. The scheduling problem on an arbitrary number of identical machines, denoted as P||C_{max}, is known to admit a PTAS of running time $2^{O(1/\epsilon^2\log^3(1/\epsilon))}+n^{O(1)}$. We prove it is nearly optimal in the sense that a $2^{O((1/\epsilon)^{1-d})}+n^{O(1)}$ time PTAS for any d>0 implies that ETH fails.

We also obain lower bounds of exact algorithms for the scheduling problem that almost matches upper bounds.

Benjamin Labonté: A Simulation-System for Stochastic Scheduling Problems and Empirical Studies on the Approximation Ratio of Policies

I will give an abstract of my Master's thesis "A Simulation-System for Stochastic Scheduling Problems and Empirical Studies on the Approximation Ratio of Policies" ("Ein Simulationssystem für stochastische Scheduling-Probleme und empirische Untersuchung zur Approximationsgüte von Politiken"). The stochastic scheduling-problem I focused on is P||E(\sum{w_j C_j}). The results that will be presented concern the following topics:

1) Use of preemption for exponential distributed processing times. (In the context of the non-idleness-problem.)

2) Lower bounds for the WSEPT-approximation algorithm.

3) A lower bound for the MinIncrease-approximation algorithm on exponential processing times.

Felix Seibert: On the VPN design problem

This talk will be about the Virtual Private Network design (VPN) problem. We are given an undirected graph with costs per unit on the links and a subset of the nodes, called terminals. We want to find an assignment of capacities to the links such that every possible traffic pattern between the terminals is routable, that means the capacities are sufficient to support the traffic. In this context, "possible" basically means that the traffic pattern respects the capacity thresholds of every terminal. It has been conjectured and shown that an optimal solution always exists in the form of a tree. I will explain some of the basic mechanisms of VPN design as well as why a very simple approach fails to prove optimality of tree routing.

Maximilian Werk: Über die Planbarkeit von periodischen Tasks mit Deadlines

Die Analyse der Planbarkeit eines Tasksystems ist ein Problem im Bereich Scheduling. Es soll für Tasks fester Periode, Deadline und Bearbeitungszeit beantwortet werden, ob diese auf einem bzw. mehreren Prozessoren planbar sind. Das heißt, eine "Ja" Antwort muss garantieren, dass alle Deadlines für beliebigen Zeithorizont eingehalten werden. Dies ist schon auf einer Maschine NP-schwer.

Bei m Maschinen ist bekannt, dass ein Erhöhen der Prozessorgeschwindigkeit das Problem vereinfacht. Ziel ist es, zu untersuchen, ob der gleiche Effekt mit k m Prozessoren erreicht werden kann.

Svenia Vedder: Local-Effect Spiele – Existenz von reinen Nash-Gleichgewichten

Local-Effect Spiele bieten als Erweiterung der Congestion Spiele neue Möglichkeiten bekannte Fragestellungen und Probleme spieltheoretisch darzustellen. Dabei werden klassische Congestion Spiele um die Option erweitert, dass Spieler ihre Kosten nicht nur durch die Wahl der gleichen Strategie, sondern auch benachbarter Strategien, gegenseitig beeinflussen. Auch asymmetrische Effekte können so modelliert werden. In Local-Effect Spielen existieren im Gegensatz zu Congestion Spielen nicht immer reine Nash-Gleichgewichte. Allerdings kann die Klasse aller Local-Effect Spiele mit Potentialfunktion definiert werden und auch für Spiele ohne Potentialfunktion können Anforderungen identifiziert werden, die die Existenz eines reinen Nash- Gleichgewichts garantieren. Des Weiteren kann mit der myopic best responds dynamic in vielen Spielen, die nicht von den positiven theoretischen Erkenntnissen betroffen sind, ein Nash-Gleichgewicht berechnet werden.

Daniel Schmand: The efficiency of Shapley cost sharing

We consider a generalization of congestion games in which the cost of each resource depends on the set rather than the number of users. Our goal is to share the joint costs of the resources among its users so as to guarantee the existence of pure Nash equilibria. We give tight bounds on the inefficiency of the Shapley cost sharing protocol for submodular, supermodular or arbitrary increasing cost functions, respectively, and show that Shapley cost sharing is (asymptotically) optimal among all uniform protocols, i.e., protocols that use only local information.

Mario Meißner: Praxisorientierte Untersuchungen von Sortierregeln im online-Scheduling zur Vermeidung exzessiver Wartezeiten

Ein Berliner Bremsenhersteller besitzt eine Messstation zur Vermessung verschiedener Produktionsteile. Dabei kommt es immer wieder zu mehr Aufträgen für die Station, als diese auf einmal bewältigen kann. Die Firma möchte nun wissen in welcher Reihenfolge wartende Teile gemessen werden sollten, sodass keine unverhältnismäßig große Wartezeit auftritt.

In meiner Masterarbeit wird diese Aufgabe als Schedulingproblem auf parallelen identischen Maschinen modelliert. Ich konzentriere mich auf die Lösung dieses Problems mit der gewichteten quadratischen Verspätung als die zu minimierende Zielfunktion. Es wurden Dominanzregeln für Jobs angegeben und drei verschiedene Sortierregeln aufgestellt, um Jobreihenfolgen zu erstellen, die per Listscheduling eine Maschinenbelegung liefern.

Im praktischen Teil der Arbeit wurden diese Regeln implementiert und an geeigneten Instanzen getestet. Am Ende wird eine Empfehlung gegeben, wie das Praxisproblem schnell zu lösen ist.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe