|
|
Online Algorithms for Packet Scheduling
Veselý, Pavel ; Sgall, Jiří (advisor) ; Stein, Clifford (referee) ; Englert, Matthias (referee)
We study online scheduling policies for buffer management models, in which packets are arriving over time to a buffer of a network switch to be sent through its single output port. However, the bandwidth of the port is limited and some packets need to be dropped, based on their weights. The goal of the scheduler is to maximize the weighted throughput, that is, the total weight of packets transmitted. Due to the natural lack of information about future, an optimal performance cannot be achieved, we thus pursue competitive analysis and its refinements to analyze online algorithms on worst-case inputs. Specifically, in the first part of the thesis, we focus on a simple online scheduling model with unit-size packets and deadlines, called Bounded-Delay Packet Scheduling. We design an optimal φ-competitive deterministic algo- rithm for the problem, where φ ≈ 1.618 is the golden ratio. It is based on a detailed understanding of an optimal schedule of pending packets, called the plan, which may be of independent interest. We also propose a semi-online setting with lookahead that allows the algorithm to see a little bit of future, namely, packets arriving in the next few steps. We provide an algorithm with lookahead for instances in which each packet can be scheduled in at most two consecutive slots and prove lower...
|
|
| |
|
| |
|
|
Online rozvrhování úloh stejné délky
Chrobak, M. ; Jawor, W. ; Sgall, Jiří ; Tichý, Tomáš
We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule of these jobs that maximizes the number of completed jobs. In the online version, each job arrives at its release time.
|
guest ::
