Bicriteria Scheduling For Contiguous and Non Contiguous Parallel Tasks

International audienceWe 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 \emphSize (number of scheduled tasks) and the \emphWeight (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 \emphSize and the \emphWeight 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