Approximation algorithms and hardness results for the joint replenishment Problepm with constant demands

Andreas S. Schulz*, Claudio Telha

*Autor correspondiente de este trabajo

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

9 Citas (Scopus)

Resumen

In the Joint Replenishment Problem (JRP), the goal is to coordinate the replenishments of a collection of goods over time so that continuous demands are satisfied with minimum overall ordering and holding costs. We consider the case when demand rates are constant. Our main contribution is the first hardness result for any variant of JRP with constant demands. When replenishments per commodity are required to be periodic and the time horizon is infinite (which corresponds to the so-called general integer model with correction factor), we show that finding an optimal replenishment policy is at least as hard as integer factorization. This result provides the first theoretical evidence that the JRP with constant demands may have no polynomial-time algorithm and that relaxations and heuristics are called for. We then show that a simple modification of an algorithm by Wildeman et al. (1997) for the JRP gives a fully polynomial-time approximation scheme for the general integer model (without correction factor). We also extend their algorithm to the finite horizon case, achieving an approximation guarantee asymptotically equal to √9/8.

Idioma originalInglés
Título de la publicación alojadaAlgorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
Páginas628-639
Número de páginas12
DOI
EstadoPublicada - 2011
Evento19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Alemania
Duración: 5 sept. 20119 sept. 2011

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen6942 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia19th Annual European Symposium on Algorithms, ESA 2011
País/TerritorioAlemania
CiudadSaarbrucken
Período5/09/119/09/11

Huella

Profundice en los temas de investigación de 'Approximation algorithms and hardness results for the joint replenishment Problepm with constant demands'. En conjunto forman una huella única.

Citar esto