An O(T 2 ) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem

Chia-Shin Chung and Chien-Hua Mike Lin
Additional contact information
Chia-Shin Chung: Department of Quantitative Business Analysis, Cleveland State University, Cleveland, Ohio 44115
Chien-Hua Mike Lin: Department of Computer and Information Science, Cleveland State University, Cleveland, Ohio 44115

Management Science, 1988, vol. 34, issue 3, 420-426

Abstract: In this paper, we study a class of the capacitated dynamic lot size problem, where, over time, the setup costs are nonincreasing, the unit holding costs have arbitrary pattern, the unit production costs are nonincreasing and the capacities are nondecreasing. We investigate the properties of the optimal solution for the problem and develop the concept of candidate subplan. It is proven that only the candidate subplans need to be examined in searching for an optimal solution. A dynamic programming algorithm, incorporating the concept of candidate subplan, is then devised which has run time complexity of O(T 2 ).

Keywords: lot sizing; dynamic programming (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.3.420 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:3:p:420-426

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().