Computational Complexity of the Capacitated Lot Size Problem

In this paper we study the computational complexity of the capacitated lot size problem with a particular cost structure that is likely to be used in practical settings. For the single item case new properties are introduced, classes of problems solvable by polynomial time algorithms are identified,...

Full description

Saved in:
Bibliographic Details
Published in:Management science 1982-10, Vol.28 (10), p.1174-1186
Main Authors: Bitran, Gabriel R, Yanasse, Horacio H
Format: Article
Language:English
Subjects:
Algorithms
Capital costs
Carrying costs
Computational complexity
Cost structure
Costs
inventory
Inventory control
inventory/production: capacitated lot sizing
Management science
Mathematical models
Objective functions
Optimal solutions
Order quantity
Polynomials
Production costs
Production planning
production: capacitated lot sizing
Recursion
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we study the computational complexity of the capacitated lot size problem with a particular cost structure that is likely to be used in practical settings. For the single item case new properties are introduced, classes of problems solvable by polynomial time algorithms are identified, and efficient solution procedures are given. We show that special classes are NP-hard, and that the problem with two items and independent setups is NP-hard under conditions similar to those where the single item problem is easy. Topics for further research are discussed in the last section.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.28.10.1174