Bicriteria scheduling for contiguous and non-contiguous parallel tasks

Bicriteria scheduling for contiguous and non-contiguous parallel tasks

0.00 Avg rating0 Votes
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: , , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.