Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959841 | European Journal of Operational Research | 2017 | 14 Pages |
Abstract
For the online version of the basic problem, we provide a (2tâ1)-competitive deterministic online algorithm and a matching lower bound. Moreover, we provide several (sometimes tight) upper and lower bounds on the competitive ratios of online algorithms for several generalizations of the basic problem involving different weights, arbitrary release dates and deadlines, different processing times of tasks, and several identical machines per stage.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Michael Hopf, Clemens Thielen, Oliver Wendt,