Scheduling is a key factor for manufacturing productivity due to the penalties of not delivering orders on time. Since manufacturing scheduling problems are NP-hard, there is a need of improving scheduling methodologies to get good solutions within low computation time. Lagrangian relaxation (LR) is known for handling large-scale separable problems because of the exploiting problem separability, however, the convergence can be slow and the final feasible solutions may not be good. Constraint programming (CP) is also effective in solving large problems, especially in the area of planning, however, it may not take advantage of the problem structure. In this paper, we combine LR and CP to establish a new methodology capable of obtaining better solutions than the current methodologies and with less computation time. Using the LR approach, the divide and conquer idea is applied through decomposition and coordination. The original NP-hard problem is decomposed into smaller non NP-hard subproblems by using Lagrange multipliers. These subproblems can be solved efficiently, and the multipliers are then iteratively adjusted to maximize the dual function. The convergence, however, may be slow. CP is used in certain iterations to obtain better step sizes to speed up convergence. When the iterative method stops, the result is an infeasible schedule for the original problem. Time windows around this solution are constructed and CP is used to find the best solution within them. Testing results show that the approach can generate good results with a low computation time