This work proposes a non-delayed relax-and-cut algorithm, based on a Lagrangean relaxation of a time indexed formulation of the problem. A Lagrangean heuristic is also developed to obtain approximate solutions.
Using the proposed methods, it is possible to obtain optimal solutions within reasonable time for some instances with up to 180 jobs and six machines. For the solutions for which it is not possible to prove optimality, interesting gaps are obtained.