Order and production scheduling rescheduling for flow shops

The authors present an integrated framework for order and production scheduling of a discrete-part, make-to-order flow shop. They first formulate the integrated problem and then decompose it by applying Lagrangian relaxation into subproblems of order scheduling, production scheduling, and overtime capacity allocation, which match the operational functions in a manufacturing organization, and form a dual problem to optimize the Lagrange multipliers for relaxation. which are interpreted as marginal costs. The solution algorithm has a structure that clearly captures the interrelationship among subproblems and provides a framework for integration. Exploiting such a framework. effective rescheduling algorithms for handling new order insertion and capacity loss are developed