A dynamic programming algorithm for dynamic lot size models with piecewise linear costs
type: Item
instance of: scholarly article
title: A dynamic programming algorithm for dynamic lot size models with piecewise linear costs
zbMATH Open document ID: 0812.90038
DOI: 10.1007/BF01099265
author: Hsin-Der Chen
author: Donald W. Hearn
author: Chung-Yee Lee
published in: Journal of Global Optimization
publication date: 1995-05-15T00:00:00Z
review text: A single item dynamic lot size model with finite time horizon \(T\) is considered. The problem is formulated as the following optimization problem: \[ \min_{x_ 1,\dots, x_ T} \sum^ T_{i=1} (P_ t(x_ t)+ H_ t(X_ t)). \] The process \(X_ t\) is given by \(X_ 0= 0\), \(X_ T= D_ T\), \(X_ t= X_{t-1}+ x_ t\), \(t= 1,\dots, T\), \(X_ t\in {\mathbf R}_ t\), \(x_ t\in {\mathbf H}_ t\), where the costs \(P_ t(\cdot)\) and \(H_ t(\cdot)\) are described by piecewise linear functions. \(D_ t\) denotes the cumulative demand, \({\mathbf H}_ t\) a set of feasible production levels and \({\mathbf R}_ t\) a set of feasible cumulative production levels. The methods of dynamic programming are used. It is proved that the corresponding value functions are piecewise linear with finitely many pieces for any \(t\). Some numerical examples are presented.
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 590820
zbMATH Keywords: single item dynamic lot size model
zbMATH Keywords: finite time horizon
reviewed by: Ryszarda Rempała
MaRDI profile type: Publication
cites work: An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints
cites work: Computational Complexity of the Capacitated Lot Size Problem
cites work: Finite-production-rate inventory models with first-and second-shift setups
cites work: A new dynamic programming algorithm for the single item capacitated dynamic lot size model
cites work: An O(T2) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem
cites work: Q4427313
cites work: A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints
cites work: A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time
cites work: Deterministic Production Planning with Concave Costs and Capacity Constraints
cites work: Deterministic Production Planning: Algorithms and Complexity
cites work: An efficient algorithm for the capacitated single item dynamic lot size problem
cites work: Production planning with time-dependent capacity bounds
cites work: A capacity constrained singlefacility dynamic lot-size model
cites work: A Dynamic Lot-Size Model with Make-or-Buy Decisions
cites work: Optimal Inventory Policy with Multiple Set-Up Costs
cites work: Bounded Production and Inventory Models with Piecewise Concave Costs
cites work: Multiple Finite Production Rate Dynamic Lot Size Inventory Models
cites work: A Deterministic Multi-Period Production Planning Model with Piecewise Concave Production and Holding-Backorder Costs
cites work: Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
cites work: A Deterministic Multi-Period Production Scheduling Model with Backlogging
full work available at URL: https://doi.org/10.1007/bf01099265
OpenAlex ID: W2032730604
description: scientific article; zbMATH DE number 590820