Optimization-based scheduling: Algorithms and applications

Global competition is forcing corporations to confront the weaknesses of inflexible mass production lines to enhance their profitability. New technological solutions are now required to overcome the problems of manufacturing customized items, and competitiveness means quick response to new demand, short cycle times, and on-time delivery in the diverse manufacturing environments. Flow shops and job shops are typical manufacturing environments, and in many cases, a manufacturing facility is a hybrid shop with significant interactions between these two. To address the above important goals, the newly evolving manufacturing systems are likely to require sophisticated computer integrated production management, where production scheduling plays an extremely important role and significantly affects the manufacturer\u27s profitability.^ The dissertation is to advance scheduling theory and its applications with emphasizing on permutation flow shops, job shops with transfer lots, and integrated order and production scheduling. The common characteristics of these environments are their focus on manufacturing a high variety of products, while coping with variable demand for each product. The objective is to meet demand in a timely fashion with low work-in-process and finished goods inventory, subject to relevant constraints including resource capacity, operation precedence, and processing times.^ This dissertation presents novel separable integer programming formulations for permutation flow shops, job shops with transfer lots, and the integrated order and production scheduling. The problems are solved under the Lagrangian relaxation framework. Lagrange multipliers are used to relax coupling constraints, and the relaxed problems are decomposed into relevant subproblems which can be solved by using dynamic programming method, or directly. The multipliers are updated at the high level by using the recently developed Reduced Complexity Bundle Method. Numerical testing results show that the operation waiting times are substantially reduced by using lot splitting techniques, and the product deliveries and machine utilizations are significantly improved.