|
Multiprocessor Randomized On-line Scheduling
Tichý, Tomáš
This paper studies randomized on-line non-preemptive scheduling in multiprocessor systems. In this problem each task is specified by its processing time andscheduled on any of $m$ identical processors. The objective is to minimize theexpected mekespan. We prove lemmas and theorems describing $sigma_m$-competitive randomized algorithms on $m$ processors. The main result is an........
|
|
Online competitive algorithms for maximizing weighzed throughput of unit jobs. ITI Series 2003-172
Bartal, Y. ; Chin, F. Y. L. ; Chrobak, M. ; Fung, S. P. Y. ; Jawor, W. ; Lavi, R. ; Sgall, Jiří ; Tichý, Tomáš
We study an online buffer management problem for networks supporting Quality-of-Service (QoS) applications, equivalently as an online scheduling problem forunit-length jobs, where each job is specified by its release time, deadline, and a nonnegative weight (QoS value). The goal is to maximize the emph{weighted throughput}, that is the total weight of scheduled jobs.
|
| |
| |
| |
| |
| |
|
Dolní odhad pro omezené pravděpodobnostní online algoritmy pro rozvrhování
Tichý, Tomáš
This paper studies a restricted class of randomized on-line non-preemptive algorithms for scheduling in multiprocessor systems. In this class each task is specified by its processing time and scheduled to a processor with the smallest or $h$th biggest load for a fixed $h$. The competitive ratio is the maximum of the ratios of the expected makespan and the optimal makespan over all.
|