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

Autor:	Chien-Hua Mike Lin, Chia-Shin Chung
Rok vydání:	1988
Předmět:	Dynamic programming Mathematical optimization Strategy and Management Holding cost Production (economics) Management Science and Operations Research Algorithm Time complexity lot sizing dynamic programming Mathematics
Zdroj:	Management Science. 34:420-426
ISSN:	1526-5501 0025-1909
DOI:	10.1287/mnsc.34.3.420
Popis:	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(T2).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fd3b188927231be8c35ee161e892cd00 https://doi.org/10.1287/mnsc.34.3.420 Zobrazit plný text záznamu Plný text ve formátu PDF