Optimization-based manufacturing scheduling: From multi-cell factory to job shop

Today\u27s time-based competition requires quick response to increasingly diverse and customized product designs, short cycle times, and on-time delivery. To obtain competitive edges, manufacturers are optimizing production processes from component manufacturing in job shops, product assembly on a mixed-model assembly lines, to coordination across multiple cells of a factory. Production scheduling is critical for on-time product delivery, high productivity and low inventory. Effective scheduling has been recognized to be extremely difficult because of all kinds of factors in different manufacturing levels, and the combinatorial nature of the problems. ^ In this study, scheduling algorithms are developed for the manufacturing from factory level to job shop level. The methods build on previous works on job shop scheduling and focus on the scheduling of factories with multiple cells, mixed-model assembly lines, and job shops with complicate process plan. The objectives are to meet customer demand in a timely fashion with low work-in-process and finished goods inventory. Because of the intrinsic difficulty for finding optimal schedules, near-optimal scheduling methodology will be developed by using the “Lagrangian relaxation” techniques. The critical factor for Lagrangian relaxation is to have “separable” problem formulations in that the objective function and “coupling constraints” should be additive in terms of basic decision variables. Additionally, fast convergence and short computation time are also the key for practical problems. In this study, several generic defects of LR leading to slow algorithm convergence are identified based on geometrical insights, and are overcome by perturbing/changing problem parameters. Various techniques are developed as well to speed up the computation. ^ The algorithms are implemented using object-oriented language C++, and tested on both UNIX and PC. Numerical results show that the methods can generate near-optimal schedules for practical problems with tens of thousands of activities within reasonable amount of computation time. The systems are currently under deployment at Toshiba Corporation. This collaborative effort of parties from different cultures and half globe away also provides invaluable experiences in the implementation and deployment of Lagrangian relaxation technique based scheduling methodology.