On dynamic lot sizing with bounded inventory for a perishable product

Jie Fan and Jinwen Ou

Omega, 2023, vol. 119, issue C

Abstract: It is well-known in the single-item dynamic lot-sizing (DLS) literature that the DLS problem for a perishable product (DLS-P) can be solved in polynomial time (see, e.g., Hsu [1]), and that the DLS problem with bounded inventory (DLS-BI) is also polynomially solvable (see, e.g., Love [2]). However, the computational complexity of the DLS problem with bounded inventory for a perishable product (DLS-BI-P) remains to be open. In this note, we answer this open problem and show that DLS-BI-P is NP-hard. Recently, Jing and Mu [20] presented an exact algorithm for an important extension of DLS-BI-P and claimed that the proposed algorithm is polynomial, while Jing and Chao [19] also developed an exact algorithm for another important extension of DLS-BI-P. In this note, we also point out that both of these two exact algorithms are exponential, and that the algorithm by Jing and Chao [19] may not generate an optimal solution in general.

Keywords: Dynamic lot sizing; NP-hardness; Perishable product; Bounded inventory (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048323000592
Full text for ScienceDirect subscribers only

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:eee:jomega:v:119:y:2023:i:c:s0305048323000592

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2023.102895

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().