A Forward Algorithm for the Capacitated Lot Size Model with Stockouts.
Abstract
This paper considers the lot size model for the production and storage of a single commodity with limitations on production capacity and the possibility of not meeting demand, i.e., stockouts, at a penalty. The stockout option means that horizons can exist and permits the use of horizons to develop a forward algorithm for solving the problem. The forward algorithm is shown in the worst case to be asymptotically linear in computational requirements, in contrast to the case for the classical lot size model which has exponential computing requirements. Two versions of the model are considered: the first in which the upper bound on production is the same for every time period; and the second, in which the upper bound on production is permitted to vary each time period. In the first case the worst case computational difficulty increases in a cubic fashion initially, and then becomes linear. In the second case the initial increase is exponential before becoming linear. Besides the forward algorithm, a number of necessary conditions are derived which reduce the computational burden of solving the integer programming problem posed by the model.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 15, 1987
- Accession Number
- ADA181660
Entities
People
- Gerald L. Thompson
- Richard A. Sandbothe
Organizations
- Carnegie Mellon University