On-line Bicriteria Interval Scheduling

International audienceWe consider the problem of scheduling a sequence of intervals revealed on-line one by one in the order of their release dates on a set of k identical machines. Each interval i is associated with a processing time p i and a pair of arbitrary weights ( w i A, w i B) and may be scheduled on one of the k identical machines or rejected. The objective is to determine a valid schedule maximizing the sum of the weights of the scheduled intervals for each coordinate. We first propose a generic on-line algorithm based on the combination of two monocriteria on-line algorithms and we prove that it gives rise to a pair of competitive ratios that are function of the competitive ratios of the monocriteria algorithms in the input. We apply this technique to the special case where w i A=1 and w i B= p i for every interval and as a corollary we obtain a pair of constant competitive ratios