AN OPTIMIZATION-BASED ALGORITHM FOR JOB-SHOP SCHEDULING

Scheduling is a key factor for manufacturing productivity. Effective s cheduling can improve on-time delivery, reduce inventory, cut lead tim es, and improve the utilization of bottleneck resources. Because of th e combinatorial nature of scheduling problems, it is often difficult t o find optimal schedules, especially within a limited amount of comput ation time. Production schedules therefore are usually generated by us ing heuristics in practice. However, it is very difficult to evaluate the quality of these schedules, and the consistency of performance may also be an issue. In this paper, near-optimal solution methodologies for job shop scheduling are examined. The problem is formulated as int eger optimization with a ''separable'' structure. The requirement of o n-time delivery and low work-in-process inventory is modelled as a goa l to minimize a weighted part tardiness and earliness penalty function . Lagrangian relaxation is used to decompose the problem into individu al part subproblems with intuitive appeal. By iteratively solving thes e subproblems and updating the Lagrangian multipliers at the high leve l, near-optimal schedules are obtained with a lower bound provided as a byproduct. This paper reviews a few selected methods for solving sub problems and for updating multipliers. Based on the insights obtained, a new algorithm is presented that combines backward dynamic programmi ng for solving low level subproblems and interleaved conjugate gradien t method for solving the high level problem. The new method significan tly improves algorithm convergence and solution quality. Numerical tes ting shows that the method is practical for job shop scheduling in ind ustries.