Efficient approximation algorithms for the economic lot-sizing in continuous time

Claudio Telha () and Matthieu van Vyve ()
Additional contact information
Claudio Telha: Université catholique de Louvain, CORE, Belgium
Matthieu van Vyve: Université catholique de Louvain, CORE, Belgium

No 2014016, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We consider a continuous-time variant of the classical Economic Lot-Sizing (ELS) problem. In this model, the setup cost is a continuous function with lower bound $K_min > 0$, the demand and holding costs are integrable functions of time and the replenishment decisions are not restricted to be multiples of a base period. Starting from the assumption that certain operations involving the setup and holding cost functions can be carried out efficiently, we argue that this variant admits a simple approximation scheme based on dynamic programming: if the optimal cost of an instance is OPT, we can find a solution with cost at most $(1 + ε)OPT$ using no more than $O ({1\over ε^2} {OPT \over K_min} log {OPT \over K_min}$ of these operations. We argue, however, that this algorithm could be improved on instances where the setup costs are “generally” very large compared with $K_min$. This leads us to introduce a notion of input-size σ that is significantly smaller than $OPT/K_min$ on instances of this type, and then to define an approximation scheme that executes $O({1\over ε^2}σ^2 ({OPT \over K_min}))$ operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems.

Keywords: game theory; equilibrium refinements; strategic stability; stochastic games (search for similar items in EconPapers)
JEL-codes: A23 C72 (search for similar items in EconPapers)
Date: 2014-06-11
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2014.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2014016

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().