This paper discusses scheduling problems that combine tails and deadlines o
r, equivalently, due dates and deadlines. This approach is illustrated to b
e of practical interest to strengthen some lower bounds in shop scheduling
problems. We show that both deadlines and tails can efficiently be modelled
via a nondecreasing cost function of the completion time so that we can us
e the O(n(2)) algorithm due to Baker, Lawler, Lenstra and Rinnooy Kan for t
he 1 \pmtn,prec,r(j), \f(max) problem to solve 1 \pmtn,prec,r(j),d(j),q(j)\
C-max. For this problem, we present an algorithm with improved complexity
of O(e + n log n) where e is the number of precedence constraints and we pr
esent some extensions of this algorithm to solve two parallel machine probl
ems with unit execution time operations. Copyright (C) 2001 John Wiley & So
ns, Ltd.