Lagrangian relaxation has recently emerged as an important method for solving complex scheduling problems. The technique has succeesfully been used to obtain near-optimal solutions for one machine scheduling problems and parallel machine scheduling problems. The approach consists of relaxing the capacity constraints on machines by using Lagrangian multipliers. The relaxed problem can be decomposed into independent job level subproblems. Peter B. Luh and his colleagues extended the technique to general job shop scheduling problems by introducing more Lagrangian multipliers to relax the precedence constraints among operations. Such that each job level relaxed subproblem can be further decomposed into a set of operation level subproblems which can easily be solved by enumeration. Unfortunately, the operation level subproblems exhibit solution oscillation from iteration to iteration and, in many cases, prevent convergence of the algorithm. Although they have proposed several method to prevent solution from oscillation, none of the methods is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to relaxed job level subproblems. We show that by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints is un-necessary, and thus the oscillation problem vanishes. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Furthermore, this algorithm makes it possible to optimize "min-max" criteria by Lagrangian relaxation. These criteria have been neglected in Lagrangian relaxation litterature for sake of indecomposability. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.