Resource-constrained material requirements planning using parallel linear programming

This dissertation focuses on the design and implementation of algorithms for the scheduling of production in resource-constrained multistage assembly systems. We exploit both macro- and microstructure in a block-angular linear programming model of this problem. Using specialized algorithms and parallel computation, we demonstrate that one can solve large-scale instances of this problem that were heretofore beyond the capability of commercial-quality simplex codes.

We adopt a distributed decomposition approach to solve this linear program. A part of our work involved the design and implementation of a decomposition shell program (based on the Dantzig-Wolfe principle) on a 64-node distributed memory multiprocessor. This shell is capable of solving structured linear programs with up to about 30,000 rows, 120,000 columns and 3.6 million nonzeros. We have also designed and tested a specialized module for the nodal subproblems in this distributed approach. This module features a logical map for representing the basis and storage-efficient data structures for the problem data. It represents a substantial saving in terms of core memory requirements and data handling time. We report on our computational experience and provide a framework for developing a scheduling support system for multistage assembly based on these algorithms.