This ongoing research effort on job shop scheduling explores three generic problems in the manufacturing industry. The first problem is to schedule products with bills of materials to improve on-time deliveries of products. The second problem pertains to the scheduling of facilities capable of batch processing several jobs concurrently, such as an oven or a plating facility. Since these facilities are often expensive and have long processing times, they constitute bottlenecks in many manufacturing systems. The scheduling of a flexible manufacturing cell (FMC) is the third problem for study. The purpose of this research is to obtain an efficient, effective and consistent solution methodology for scheduling general job shops. Through extensive collaboration, an optimization-based scheduling methodology using the Lagrangian relaxation technique has been developed. The method has many positive features, and has been tested at the Development Operations shop of a major aerospace manufacturer. The abilities to handle bills of materials, batch facilities, and FMC's, however, are of crucial importance for the method to be truly effective for general job shops. This research will thus advance the state of the art and practice of scheduling methodology, and enhance the profit-making ability of many manufacturing companies.
