The NP-hard problem addressed in this paper is well known in the scheduling literature as R|C_max. We introduce lower bounds based on Lagrangian relaxations and additive techniques. These are used to obtain exact and approximation algorithms. Computational experiments show that they outperform the most effective algorithms from the literature.