National Technical University of Athens (NTUA)
Προσεγγιστικοί αλγόριθμοι για δρομολόγηση πακέτων μηνυμάτων σε δίκτυα με κόστος επανεκκίνησης
Abstract
dc:descriptionThe problem tackled throughout this thesis is referred to and encountered in various forms in international bibliography and has many applications as far as Optical Networks, TDMA (Time Division Multiple Access) and parallel message or data transmission are concerned. For the purposes of this manuscript the graph theoretic model of the problem is used. Researchers are referring to the problem at hand as PREEMPTIVE BIPARTITE SCHEDULING (PBS). In its various forms it has been studied extensively by many researchers and scholars. It is described as follows:Given a set of transmission stations (a set of vertices V, |V|=n), a set of receivers U (a set of vertices U, |U|=m) and a set of messages to be transmitted from V to U (a set of edges E), we are required to produce an efficient schedule such that the total time duration from beginning of the first transmission to the conclusion of the last will be minimized. Each of the messages to be transmitted has some specific duration (edges weight: w). To achieve our goal we are allowed to interrupt (preempt) message packages. Unfortunately, preemption comes with a cost (delay=d) in order to reconfigure the system and/or prepare for the next transmission. Each time we decide to preempt, a reconfiguration delay add to the total transmission time. Therefor in order to produce an optimal schedule one has to take into account two different parameters simultaneously.Previous research resulted mainly in designing 2-approximation algorithms (100% deviation from the cost of the optimal solution).Briefly, the contributions of this thesis to tackling PBS are the following:1.Polynomial time algorithms to provide an optimal solution in the following cases:-In the case of unvarying graphs -In case we wish to minimize the number of preemptions-In case we need to minimize only the transmission time (d=0).To design the two later we prove that any PBS input might be transformed to an Open Shop input and vice versa.2.The best so far polynomial time approximation algorithm with guaranteed approximation ratio less than two. In fact, we designed a family of algorithms which we named A-PBS(a). Among those algorithms A-PBS(d+1) (a=d+1) stands out, as it produces the lowest approximation ratio. Proof of the algorithm’s approximation ratio as well as tightness were done using derivative methods to identify a minimum value. The approximation ratio of A-PBS(d+1) is 2-1/(d+1), resulting in down to just 50% deviation from eth optimal in the case of d=1. The same algorithm for d=0 will yield an optimal schedule for PBS.3.Fast heuristic algorithms to mitigate disadvantages and make improvements on preexisting research.4.Design not only of the fastest but also the best in terms of deviation from the cost of the optimal solution algorithm. Efficiency of this algorithm has been tested through experiments against the most efficient algorithms proposed for PBS by other researchers in the past.5.A combination of all previous results and methodologies to produce a final hybrid algorithm, the efficiency of which we tested not only for the usual uniform distribution data but also in cases the data may follow a normal or an exponential distribution.All of the above were studied in terms of computational complexity as well and were tested through experiments to verify how well they perform in practice.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Aslanidis, Timotheos
- Ασλανίδης, Τιμόθεος
Subjects
dc:subject × 6Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/45003