In this paper,we proposed a polynomial algorithm
based on semi-Markovian decision processes to solve
the dynamic lot sizing problem, in which the production and
the inventory costs of each period are concave, and the
unit production cost evolves according to a continuous time
Markov process over the planning horizon.