Preemptive scheduling in overloaded systems

0175332 - MU-W 20030084 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GA201/01/1195; GA MŠMT ME 476; GA AV ČR IAA1019901; GA MŠMT LN00A056
Výzkumný záměr: CEZ:AV0Z1019905; CEZ:AV0Z1019905
Klíčová slova: scheduling * online algorithms * benefit
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.795, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0072316