Coauthors: Aurélien Carlier and Claire Hanen

This talk deals with the classical scheduling of a dependent typed task system (including parallel and dedicated processors) of unit durations with release and due dates. The existence of a feasible scheduling problem is NP-Hard and can be, for some special subcases, polynomially or approximatively solved using Garey/Jonson (GJ in short) or Leung/Palem/Pnueli (LPP in short) algorithms. These two algorithms rely both on an iterative process that modifies the due dates until either a fixed point is reached (due dates are then said to be consistent), or a contradiction is observed. These modified due dates are then used as priorities to build a feasible schedule using a list scheduling algorithm. The motivation of our talk is to analyze the relationships between these two iterative process. We proved that although GJ and LPP algorithms are different, they rely on the same notion of consistency, (i.e. the modified due dates produced by one of the algorithm are consistent with respect to the other algorithm) and they converge to the same fixed point if it exists. The consequence is that all the results obtained in the literature for one of these algorithm are also valid for the other one.