SummaryWe consider the problem of scheduling jobs on a single machine subject to given release dates and precedence constraints, in order to minimize maximum lateness. The algorithms of Bakerand Su(Naval Res. Logist. Quart.21(1974) 171–176) and of McMahonand Florian(Operations Res.23(1975) 475–482) for the problem without precedence constraints are extended to the general case. An extensive computational comparison establishes the superiority of the latter algorithm. We describe applications to the theory of job‐shop scheduling and to a practical scheduling situ