The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays

We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be $$\mathcal {NP}$$NP-complete; many studies were devoted to the determination of polynomial time algorithms for some special subcases, most of them based on a particular list schedule. The Garey---Johnson and Leung---Palem---Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifying them using necessary conditions until a fixed point is reached. The present paper shows that these two algorithms are different implementations of the same generic one. The main consequence is that all the results valid for GJ algorithm are also for LPP and vice versa.