Abstract: In this paper, an approach based on Lagrangian Relaxation and dynamic programming is used to schedule job-shops with limited waiting times. A heuristic method based on beam search is proposed to get a good feasible solution from the dual problem. Computational results are given to demonstrate the efficiency and effectiveness of the approach.