Number of the records: 1
Online scheduling of jobs with fixed start times on related machines
- 1.
SYSNO ASEP 0457321 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Online scheduling of jobs with fixed start times on related machines Author(s) Epstein, L. (IL)
Jeż, Łukasz (MU-W) RID, SAI, ORCID
Sgall, J. (CZ)
van Stee, R. (GB)Source Title Algorithmica. - : Springer - ISSN 0178-4617
Roč. 74, č. 1 (2016), s. 156-176Number of pages 21 s. Language eng - English Country US - United States Keywords online scheduling ; online algorithms ; related machines Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support MU-W - RVO:67985840 UT WOS 000367622200006 EID SCOPUS 84953283240 DOI 10.1007/s00453-014-9940-2 Annotation We consider online preemptive scheduling of jobs with fixed starting times revealed at those times on m uniformly related machines, with the goal of maximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contribute their weights to the profit of the algorithm. In the most general setting, no algorithm has bounded competitive ratio, and we consider a number of standard variants. We give a full classification of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2016
Number of the records: 1