Capacitated scheduling in multistage production systems

This dissertation develops a procedure for deriving an optimal material requirements plan. The procedure minimizes inventory holding cost subject to work center capacity constraints.

The problem is formulated as a large, but highly structured linear program.

A Dantzig-Wolfe decomposition algorithm is developed to solve the model. The capacity constraints of the model are used to define the master problem and the flow balance constraints are used to define one or more subproblems.

The constraint matrix for each subproblem is highly structured and similar to the node-arc incidence matrix for a network. This similarity to a network is exploited in a a special network-like algorithm for the subproblems.

In this algorithm the concept of an arc and the concept of a network are generalized. The algorithm is similar to the network simplex algorithm in that the basis is not explicitly stored or inverted.

A computer code is developed to perform the algorithm for the subproblem. Computational results are reported.