IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i3p674-683.html
   My bibliography  Save this article

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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. 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.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Zhicheng Zhu & Yisha Xiang & Bo Zeng, 2021. "Multicomponent Maintenance Optimization: A Stochastic Programming Approach," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 898-914, July.
    7. Paul, Henrik J. & Bierwirth, Christian & Kopfer, Herbert, 2007. "A heuristic scheduling procedure for multi-item hoist production lines," International Journal of Production Economics, Elsevier, vol. 105(1), pages 54-69, January.
    8. Liu, Xinbao & Yang, Tianji & Pei, Jun & Liao, Haitao & Pohl, Edward A., 2019. "Replacement and inventory control for a multi-customer product service system with decreasing replacement costs," European Journal of Operational Research, Elsevier, vol. 273(2), pages 561-574.
    9. Briš, Radim & Byczanski, Petr & Goňo, Radomír & Rusek, Stanislav, 2017. "Discrete maintenance optimization of complex multi-component systems," Reliability Engineering and System Safety, Elsevier, vol. 168(C), pages 80-89.
    10. Zhu, Mixin & Zhou, Xiaojun, 2024. "Maintenance modeling of serial-parallel multi-station manufacturing system with failure-induced damage and assembly parts," Reliability Engineering and System Safety, Elsevier, vol. 249(C).
    11. Doostparast, Mohammad & Kolahan, Farhad & Doostparast, Mahdi, 2014. "A reliability-based approach to optimize preventive maintenance scheduling for coherent systems," Reliability Engineering and System Safety, Elsevier, vol. 126(C), pages 98-106.
    12. Kats, Vladimir & Lei, Lei & Levner, Eugene, 2008. "Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence, setups, and time-window constraints," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1196-1211, June.
    13. N. Samphaiboon & Y. Yamada, 2000. "Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem," Journal of Optimization Theory and Applications, Springer, vol. 105(3), pages 659-676, June.
    14. Jyrki Savolainen & Michele Urbani, 2021. "Maintenance optimization for a multi-unit system with digital twin simulation," Journal of Intelligent Manufacturing, Springer, vol. 32(7), pages 1953-1973, October.
    15. Maaroufi, Ghofrane & Chelbi, Anis & Rezg, Nidhal, 2013. "Optimal selective renewal policy for systems subject to propagated failures with global effect and failure isolation phenomena," Reliability Engineering and System Safety, Elsevier, vol. 114(C), pages 61-70.
    16. Xia, Tangbin & Xi, Lifeng & Zhou, Xiaojun & Lee, Jay, 2012. "Dynamic maintenance decision-making for series–parallel manufacturing system based on MAM–MTW methodology," European Journal of Operational Research, Elsevier, vol. 221(1), pages 231-240.
    17. Nguyen, Kim-Anh & Do, Phuc & Grall, Antoine, 2017. "Joint predictive maintenance and inventory strategy for multi-component systems using Birnbaum’s structural importance," Reliability Engineering and System Safety, Elsevier, vol. 168(C), pages 249-261.
    18. Olde Keizer, Minou & Teunter, Ruud, 2014. "Opportunistic condition-based maintenance and aperiodic inspections for a two-unit series system," Research Report 14033-OPERA, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    19. Torgny Almgren & Niclas Andréasson & Michael Patriksson & Ann-Brith Strömberg & Adam Wojciechowski & Magnus Önnheim, 2012. "The opportunistic replacement problem: theoretical analyses and numerical tests," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(3), pages 289-319, December.
    20. Bouvard, K. & Artus, S. & Bérenguer, C. & Cocquempot, V., 2011. "Condition-based dynamic maintenance operations planning & grouping. Application to commercial heavy vehicles," Reliability Engineering and System Safety, Elsevier, vol. 96(6), pages 601-610.

    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.