IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i3p674-683.html

Charlemagne's Challenge: The Periodic Latency Problem

Author

Listed:
  • Sofie Coene

    (Operations Research Group, Katholieke Universiteit Leuven, B-3000 Leuven, Belgium)

  • Frits C. R. Spieksma

    (Operations Research Group, Katholieke Universiteit Leuven, B-3000 Leuven, Belgium)

  • Gerhard J. Woeginger

    (Department of Mathematics, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands)

Abstract

Latency problems are characterized by their focus on minimizing the waiting time for all clients. We study periodic latency problems, a nontrivial extension of standard latency problems. In a periodic latency problem each client has to be visited regularly: there is a server traveling at unit speed, and there is a set of n clients with given positions. The server must visit the clients over and over again, subject to the constraint that successive visits to client i are at most q i time units away from each other.We investigate two main problems. In problem PLPP the goal is to find a repeatable route for the server visiting as many clients as possible without violating their q i s. In problem PLP the goal is to minimize the number of servers needed to serve all clients. Depending on the topology of the underlying network, we derive polynomial-time algorithms or hardness results for these two problems. Our results draw sharp separation lines between easy and hard cases.

Suggested Citation

  • Sofie Coene & Frits C. R. Spieksma & Gerhard J. Woeginger, 2011. "Charlemagne's Challenge: The Periodic Latency Problem," Operations Research, INFORMS, vol. 59(3), pages 674-683, June.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:3:p:674-683
    DOI: 10.1287/opre.1110.0919
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0919
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0919?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. D. S. Johnson & K. A. Niemi, 1983. "On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees," Mathematics of Operations Research, INFORMS, vol. 8(1), pages 1-14, February.
    2. Jan Korst & Emile Aarts & Jan Karel Lenstra, 1997. "Scheduling Periodic Tasks with Slack," INFORMS Journal on Computing, INFORMS, vol. 9(4), pages 351-362, November.
    3. Y. Crama & V. Kats & J. van de Klundert & E. Levner, 2000. "Cyclic scheduling in robotic flowshops," Annals of Operations Research, Springer, vol. 96(1), pages 97-124, November.
    4. Yoshiyuki Karuno & Hiroshi Nagamochi & Toshihide Ibaraki, 1997. "Vehicle scheduling on a tree with release and handling times," Annals of Operations Research, Springer, vol. 69(0), pages 193-207, January.
    5. Campbell, Ann Melissa & Hardin, Jill R., 2005. "Vehicle minimization for periodic deliveries," European Journal of Operational Research, Elsevier, vol. 165(3), pages 668-684, September.
    6. Rommert Dekker & Ralph Wildeman & Frank Duyn Schouten, 1997. "A review of multi-component maintenance models with economic dependence," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(3), pages 411-435, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nourelfath, Mustapha & Châtelet, Eric, 2012. "Integrating production, inventory and maintenance planning for a parallel system with dependent components," Reliability Engineering and System Safety, Elsevier, vol. 101(C), pages 59-66.
    2. Liu, Gia-Shie, 2011. "Dynamic group instantaneous replacement policies for unreliable Markovian service systems," International Journal of Production Economics, Elsevier, vol. 130(2), pages 203-217, April.
    3. Bagchi, Tapan P. & Gupta, Jatinder N.D. & Sriskandarajah, Chelliah, 2006. "A review of TSP based approaches for flowshop scheduling," European Journal of Operational Research, Elsevier, vol. 169(3), pages 816-854, March.
    4. Kajji, Anass & Aouam, Tarik & El Mokrini, Asmae & Raa, Birger, 2025. "The cyclic inventory routing problem with environmental considerations: Model, solution procedure, and insights," International Journal of Production Economics, Elsevier, vol. 287(C).
    5. Hurink, Johann & Knust, Sigrid, 2005. "Tabu search algorithms for job-shop problems with a single transport robot," European Journal of Operational Research, Elsevier, vol. 162(1), pages 99-111, April.
    6. Liu, Gehui & Chen, Shaokuan & Jin, Hua & Liu, Shuang, 2021. "Optimum opportunistic maintenance schedule incorporating delay time theory with imperfect maintenance," Reliability Engineering and System Safety, Elsevier, vol. 213(C).
    7. Izquierdo, J. & Márquez, A. Crespo & Uribetxebarria, J. & Erguido, A., 2020. "On the importance of assessing the operational context impact on maintenance management for life cycle cost of wind energy projects," Renewable Energy, Elsevier, vol. 153(C), pages 1100-1110.
    8. Dao, Cuong D. & Zuo, Ming J. & Pandey, Mayank, 2014. "Selective maintenance for multi-state series–parallel systems under economic dependence," Reliability Engineering and System Safety, Elsevier, vol. 121(C), pages 240-249.
    9. Bruns, Peter, 2002. "Optimal maintenance strategies for systems with partial repair options and without assuming bounded costs," European Journal of Operational Research, Elsevier, vol. 139(1), pages 146-165, May.
    10. Olde Keizer, Minou C.A. & Teunter, Ruud H. & Veldman, Jasper, 2016. "Clustering condition-based maintenance for systems with redundancy and economic dependencies," European Journal of Operational Research, Elsevier, vol. 251(2), pages 531-540.
    11. Seyed Habib A. Rahmati & Abbas Ahmadi & Kannan Govindan, 2018. "A novel integrated condition-based maintenance and stochastic flexible job shop scheduling problem: simulation-based optimization approach," Annals of Operations Research, Springer, vol. 269(1), pages 583-621, October.
    12. Ayse Sena Eruguz & Tarkan Tan & Geert‐Jan van Houtum, 2017. "Optimizing usage and maintenance decisions for k‐out‐of‐n systems of moving assets," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(5), pages 418-434, August.
    13. Yuanxiao Wu & Xiwen Lu, 0. "Improved algorithms for single vehicle scheduling on tree/cycle networks," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-16.
    14. Weidong Lei & Liu Yang & Pengyu Yan & Chengbin Chu & Jie Yang, 2025. "Production coordination of local and cloud orders in shared manufacturing: a bi-objective pre-scheduling approach," Annals of Operations Research, Springer, vol. 345(1), pages 207-245, February.
    15. Drobouchevitch, Inna G. & Neil Geismar, H. & Sriskandarajah, Chelliah, 2010. "Throughput optimization in robotic cells with input and output machine buffers: A comparative study of two key models," European Journal of Operational Research, Elsevier, vol. 206(3), pages 623-633, November.
    16. Maquirriain, Javier & García-Villoria, Alberto & Pastor, Rafael, 2024. "Matheuristics for scheduling of maintenance service with linear operation cost and step function maintenance cost," European Journal of Operational Research, Elsevier, vol. 315(1), pages 73-87.
    17. Jong-Jang Lin & Yi-Kuei Lin & Louis Cheng-Lu Yeng & Ruey-Huei Yeh, 2025. "An outcome-based maintenance contracting model by considering multi-criteria and risk equilibrium," Annals of Operations Research, Springer, vol. 349(1), pages 47-66, June.
    18. J Ansell & T Archibald & J Dagpunar & L Thomas & P Abell & D Duncalf, 2003. "Analysing maintenance data to gain insight into systems performance," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(4), pages 343-349, April.
    19. Aslan, Ayse & Ursavas, Evrim & Romeijnders, Ward, 2023. "A Precedence Constrained Knapsack Problem with Uncertain Item Weights for Personalized Learning Systems," Omega, Elsevier, vol. 115(C).
    20. Verbert, K. & De Schutter, B. & Babuška, R., 2017. "Timely condition-based maintenance planning for multi-component systems," Reliability Engineering and System Safety, Elsevier, vol. 159(C), pages 310-321.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:59:y:2011:i:3:p:674-683. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.