Basis Paths and a Polynomial Algorithm for the Multistage Production-Capacitated Lot-Sizing Problem

Hark-Chin Hwang (), Hyun-Soo Ahn () and Philip Kaminsky ()
Additional contact information
Hark-Chin Hwang: School of Management, Kyung Hee University, Seoul 130-701, Republic of Korea
Hyun-Soo Ahn: Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109
Philip Kaminsky: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720

Operations Research, 2013, vol. 61, issue 2, 469-482

Abstract: We consider the multilevel lot-sizing problem with production capacities (MLSP-PC), in which production and transportation decisions are made for a serial supply chain with capacitated production and concave cost functions. Existing approaches to the multistage version of this problem are limited to nonspeculative cost functions---up to now, no algorithm for the multistage version of this model with general concave cost functions has been developed. In this paper, we develop the first polynomial algorithm for the MLSP-PC with general concave costs at all of the stages, and we introduce a novel approach to overcome the limitations of previous approaches. In contrast to traditional approaches to lot-sizing problems, in which the problem is decomposed by time periods and is analyzed unidirectionally in time, we solve the problem by introducing the concept of a basis path, which is characterized by time and stage. Our dynamic programming algorithm proceeds both forward and backward in time along this basis path, enabling us to solve the problem in polynomial time.

Keywords: lot-sizing; production capacity; inventory and logistics; algorithms (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1141 (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:oropre:v:61:y:2013:i:2:p:469-482

Access Statistics for this article

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