  In this paper, we study the single-item economic lot-sizing problem with
production cost functions that are piecewise linear. The lot-sizing problem
stands as a foundational cornerstone within the domain of lot-sizing problems.
It is also applicable to a variety of important production planning problems
which are special cases to it according to \cite{ou}. The problem becomes
intractable when $m$, the number of different breakpoints of the
production-cost function is variable as the problem was proven NP-hard by
\cite{Florian1980}. For a fixed $m$ an $O(T^{2m+3})$ time algorithm was given
by \cite{Koca2014} which was subsequently improved to $O(T^{m+2}\log(T))$ time
by \cite{ou} where $T$ is the number of periods in the planning
horizon.\newline We introduce a more efficient $O(T^{m+2})$ time algorithm for
this problem which improves upon the previous state-of-the-art algorithm by Ou
and which is derived using several novel algorithmic techniques that may be of
independent interest.
