Preemptive scheduling in overloaded systems

0175332 - MU-W 20030084 RIV US eng J - Journal Article
Chrobak, M. - Epstein, L. - Noga, J. - Sgall, Jiří - van Stee, R. - Tichý, Tomáš - Vakhania, N.
Preemptive scheduling in overloaded systems.
Journal of Computer and System Sciences. Roč. 67, č. 1 (2003), s. 183-197. ISSN 0022-0000. E-ISSN 1090-2724
R&D Projects: GA ČR GA201/01/1195; GA MŠMT ME 476; GA AV ČR IAA1019901; GA MŠMT LN00A056
Institutional research plan: CEZ:AV0Z1019905; CEZ:AV0Z1019905
Keywords : scheduling * online algorithms * benefit
Subject RIV: BA - General Mathematics
Impact factor: 0.795, year: 2003

We are given a set of tasks with release times, deadlines, and profit rates. In the metered model, a task brings profit proportional to the execution time even if not completed. We present an efficient offline algorithm and improve both the lower and upper bounds on the competitive ratio of online algorithms.
Permanent Link: http://hdl.handle.net/11104/0072316