How good are SPT schedules for fair optimality criteria |
| |
Authors: | Eric Angel Evripidis Bampis Fanny Pascual |
| |
Institution: | (1) IBISC, Université d’évry Val d’Essonne, 523 Place des Terrasses, 91000 Evry, France;(2) LIP6, Université Pierre et Marie Curie (Paris 6), 104 avenue du Président Kennedy, 75016 Paris, France |
| |
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. |
| |
Keywords: | Multiprocessor scheduling SPT Fairness measures Approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|