A PRACTICAL APPROACH TO JOB-SHOP SCHEDULING PROBLEMS

Scheduling is one of the most important issues in the planning and operation of manufacturing systems, but the generation of consistently good schedules has proven to be extremely difficult. The problem is that optimal scheduling solutions involve costly and impractical enumeration procedures, while the performance of most heuristic techniques is difficult to estimate and varies considerably from one problem to the next. Recently, scheduling methodologies based on Lagrangian relaxation have proven to be computationally efficient and have provided near-optimal solutions to identical, parallel machine scheduling problems. In this paper, we explore the use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraints, and simple routing considerations. Using an augmented Lagrangian formulation, the scheduling problem is decomposed into operation-level subproblems for the selection of operation beginning times and machine types, with given multipliers and penalty coefficients. The multipliers and penalty coefficients are then updated at the high level. The solution forms the basis of a list-scheduling algorithm that generates a feasible schedule. A procedure is also developed to evaluate the quality of this feasible schedule by generating a lower bound on the optimal cost. Numerical examples are taken from a representative industrial job shop. High-quality schedules are efficiently generated every other day over a three-week period, with costs generally within 4% of their respective lower bounds. The methodology compares favorably with a knowledge-based scheduling method used in the shop at the time of the numerical tests.