Article ID: | iaor2009943 |
Country: | Netherlands |
Volume: | 159 |
Issue: | 1 |
Start Page Number: | 97 |
End Page Number: | 106 |
Publication Date: | Mar 2008 |
Journal: | Annals of Operations Research |
Authors: | Bampis Evripidis, Laforest Christian, Rapine Christophe, Baille Fabien |
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.