A Novel exact algorithm for economic lot-sizing with piecewise linear production costs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913289277014016 |
|---|---|
| author | Papadopoulos, Kleitos |
| author_facet | Papadopoulos, Kleitos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16314 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Novel exact algorithm for economic lot-sizing with piecewise linear production costs Papadopoulos, Kleitos Data Structures and Algorithms 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. |
| title | A Novel exact algorithm for economic lot-sizing with piecewise linear production costs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.16314 |