Real-world extensions to a production scheduling algorithm based on Lagrangian relaxation

Develops three extensions to a production scheduling algorithm based on Lagrangian relaxation (Luh, Hoitomt, and Pattipati, 1990). These extensions handle the following real-world features: stochastic availability of raw material; reworking and scrapping of parts; and incorporating set-up costs and set-up times in the scheduling of multiclass manufacturing systems. The first two extensions yield on-line algorithms which are illustrated using a 89-job scheduling problem. The third extension uses an algorithmic procedure to insert switchovers to obtain a good schedule and is illustrated for a two-class, 89-job scheduling problem