This paper presents an optimization methodology based on lagrangean relaxation to solve the problem of scheduling jobs with due date. Each job consists of a distinct number of operations to be processed in a specified order. We obtain an efficient near-optimal algorithm with guaranteed bounds for the non-preemptive job shop scheduling problem. The method is investigated for scheduling jobs on possibly different sets of identical parallel machines for different operations of a job. By relaxing the coupling capacity constraints with nonnegative Lagrange multipliers and forming the lagrangean, we decompose the problem according to jobs, which may be solved independently. The multipliers are adjusted at each step by a subgradient procedure. A list-scheduling heuristic then derives a feasible schedule from this solution.
