Bicriteria Parallel task scheduling

International audienceIn this paper, we study the problem of scheduling on $k$ identical machines a set of parallel tasks with release dates and deadlines in order to optimize simultaneously two conflicting criteria, namely the \emphSize (number of scheduled tasks) and the \emphWeight (sum of the weight of scheduled tasks). We distinguish two variants of the problem: In the first one, tasks have to be scheduled in a contiguous subset of machines, whereas in the second one, they can be scheduled on any subset of machines. In both variants, we show that if the maximal number of required machines is greater than $\frack2$ then there is no $(a ,b )$-approximate schedule for any two constants $a$ and $b$. Nevertheless, if the number of required machines is no more than $\frack2$ then we propose a $(3\alpha, 3\beta)$-approximation algorithm for the contiguous case and a $(6\alpha, 6\beta)$-approximation for the non-contiguous case, where $\alpha$ (resp. $\beta$) denotes the approximation ratio of a monocriterion algorithm maximizing the \emphSize (resp. the \emphWeight)