Bicriteria scheduling for contiguous and non contiguous parallel tasks |
| |
Authors: | Fabien Baille Evripidis Bampis Christian Laforest Christophe Rapine |
| |
Institution: | (1) LIAFA, Université Paris 7, CNRS UMR 7089, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France;(2) Laboratoire IBISC, Université d’évry Val d’Essonne, CNRS FRE 2873, Tour évry 2, 523 Place des Terrasses, 91000 évry, France;(3) Laboratoire GILCO, 46 avenue Félix Viallet, 38031 Grenoble Cedex 1, France |
| |
Abstract: | We study the problem of scheduling on k identical machines a set of parallel tasks with release dates and deadlines in order to maximize simultaneously two criteria,
namely the Size (number of scheduled tasks) and the Weight (sum of the weights of scheduled tasks). If no task requires more than half of the machines, we construct schedules that
are simultaneously approximations for the Size and the Weight by combining two approximate schedules, one for each parameter. We obtain existence results and polynomial time bicriteria
approximation algorithms in contiguous and non contiguous models. |
| |
Keywords: | Scheduling Parallel tasks Bicriteria approximation |
本文献已被 SpringerLink 等数据库收录! |
|