Back to Search
Start Over
Approximation algorithms for replenishment problems with fixed turnover times
- Source :
- LATIN 2018: Theoretical Informatics ISBN: 9783319774039, LATIN, LATIN 2018-13th Latin American Symposium on Theoretical Informatics, LATIN 2018-13th Latin American Symposium on Theoretical Informatics, Apr 2018, Buenos Aires, Argentina. pp.217-230, Algorithmica, Algorithmica, 2022, 84 (9), pp.2597-2621. ⟨10.1007/s00453-022-00974-4⟩, Bosman, T, van Ee, M, Jiao, Y, Marchetti-Spaccamela, A, Ravi, R & Stougie, L 2018, Approximation algorithms for replenishment problems with fixed turnover times . in M A Bender, M Farach-Colton & M A Mosteiro (eds), LATIN 2018: Theoretical Informatics : 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10807 LNCS, Springer/Verlag, pp. 217-230, 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018, Buenos Aires, Argentina, 16/04/18 . https://doi.org/10.1007/978-3-319-77404-6_17, Algorithmica, 84, 2597-2621, Bosman, T, van Ee, M, Jiao, Y, Marchetti-Spaccamela, A, Ravi, R & Stougie, L 2022, ' Approximation Algorithms for Replenishment Problems with Fixed Turnover Times ', Algorithmica, vol. 84, no. 9, pp. 2597-2621 . https://doi.org/10.1007/s00453-022-00974-4, LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, 217-230, STARTPAGE=217;ENDPAGE=230;TITLE=LATIN 2018: Theoretical Informatics, Algorithmica, 84(9), 2597-2621. Springer New York
- Publication Year :
- 2022
-
Abstract
- We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
- Subjects :
- FOS: Computer and information sciences
Schedule
Mathematical optimization
Optimization problem
Computational complexity theory
General Computer Science
Computer science
0211 other engineering and technologies
Time horizon
G.2.2
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Traveling salesman
Computer Science - Data Structures and Algorithms
Inventory routing
Data Structures and Algorithms (cs.DS)
[INFO]Computer Science [cs]
Approximation algorithms
F.2.2
021103 operations research
Applied Mathematics
Approximation algorithm
SDG 8 - Decent Work and Economic Growth
Pinwheel scheduling
Computer Science Applications
Periodic maintenance
010201 computation theory & mathematics
Replenishment problem
Node (circuits)
Routing (electronic design automation)
Constant (mathematics)
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-319-77403-9
- ISSN :
- 01784617 and 14320541
- ISBNs :
- 9783319774039
- Volume :
- 84
- Database :
- OpenAIRE
- Journal :
- Algorithmica
- Accession number :
- edsair.doi.dedup.....1dd82bda4b740a1a38f88b91094880c1