Optimization-based manufacturing scheduling: Algorithms and applications

Scheduling is a key factor for productivity and competitiveness of corporations. Effective scheduling can improve on-time delivery, reduce inventory, cut lead time, and improve resource utilization. Production scheduling, however, has been widely recognized to be extremely difficult because of its combinatorial nature. In this dissertation, optimization-based solution methodologies are developed for the scheduling of job shops with batch machines, machine setup requirements, and machining centers.^ Job shop is a typical environment for manufacturing low-volume and high-variety parts. In a job shop, parts with various due dates and priorities are to be processed on diverse types of machines. Unlike most machines that can process one part at a time, a batch machine can simultaneously process multiple parts with the same processing requirement in a "batch." For some machines, significant setup time is required in-between the processing of two different types of parts, and parts of the same type can be processed back-to-back with negligible adjustment time in-between. Trade-off among efficiency and due date performance is often the difficulty encountered in industries. A machining center is an advanced NC machine that can continuously perform a variety of operations on a part by automatically changing the cutting tools. It has several pallets to hold fixtures which in turn clamp parts for processing, and a tool magazine to store the cutting tools needed. Machine setups, lot split, tool loading, and coordination of multiple resources are the key issues addressed.^ The scheduling problems are modeled as integer programs with a "separable" structure that is critical for efficiently solving the problems. Lagrangian relaxation is used to decompose the problems into smaller and easier subproblems with intuitive appeal. A new algorithm is presented that combines dynamic programming for solving low level subproblems and interleaved conjugate gradient method for high level problem. The new method significantly has improved convergence and computation efficiency, and provides high quality solutions for the scheduling of job shops with batch and setup machines, and in the scheduling of a machining center. ^