Scheduling flexible flow shops with no setup effects

The authors present an efficient, optimization model-based approach for scheduling the production of discrete-part, make-to-order type of flexible flow shops, where setup effects are negligible. A nominal scheduling algorithm based on Lagrangian relaxation and minimum cost linear network flow is developed for scheduling under nominal conditions. Fast rescheduling algorithms that exploit the economic interpretation of Lagrange multipliers and the network structure of production flows are proposed for timely adjustment of the nominal schedule to cope with disturbances. Numerical results on realistic examples demonstrated that the methodology was quite effective. It generated near-optimal schedules, provided relatively smooth adjustments and was computationally efficient