How good are SPT schedules for fair optimality criteria

Eric Angel (), Evripidis Bampis () and Fanny Pascual ()

Annals of Operations Research, 2008, vol. 159, issue 1, 53-64

Abstract: We consider the following scheduling setting: a set of n tasks have to be executed on a set of m identical machines. It is well known that shortest processing time (SPT) schedules are optimal for the problem of minimizing the total sum of completion times of the tasks. In this paper, we measure the quality of SPT schedules, from an approximation point of view, with respect to the following optimality criteria: sum of completion times per machine, global fairness, and individual fairness. Copyright Springer Science+Business Media, LLC 2008

Keywords: Multiprocessor scheduling; SPT; Fairness measures; Approximation algorithms (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-007-0267-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:159:y:2008:i:1:p:53-64:10.1007/s10479-007-0267-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-007-0267-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().