Network Programming Models for Production Scheduling in Multi-Stage, Multi-Item Capacitated Systems

This paper investigates a multi-item, multi-level production scheduling problem with linear costs and production and inventory constraints at one key facility. Two multi-item problems—one in which the constraint was on shipping capability and one in which there was a final stage bottleneck machine—motivated the paper. A multi-item facilities-in-series problem is formulated, in standard fashion, as a linear program. Then we show that in certain important cases the 3-period problem is a network problem. This 3-period result is used as the basis for a rolling heuristic for T-period problems. The conditions under which this heuristic fails to find optimal solutions are discussed and computational comparisons to standard linear programming are given. Finally, we discuss ways of dealing with two constrained facilities and with setup costs.