IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v24y2021i3d10.1007_s10951-021-00684-9.html
   My bibliography  Save this article

Scheduling for multi-robot routing with blocking and enabling constraints

Author

Listed:
  • Jayanth Krishna Mogali

    (The Robotics Institute, Carnegie Mellon University)

  • Joris Kinable

    (Eindhoven University of Technology)

  • Stephen F. Smith

    (The Robotics Institute, Carnegie Mellon University)

  • Zachary B. Rubinstein

    (The Robotics Institute, Carnegie Mellon University)

Abstract

This paper considers the problem of servicing a set of locations by a fleet of robots so as to minimize overall makespan. Although motivated by a specific real-world, multi-robot drilling and fastening application, the problem also arises in a range of other multi-robot domains where service start times are subject to precedence constraints and robots must be routed in space and time to avoid collisions. We formalize this general problem and analyze its complexity. We develop a heuristic local search procedure for solving it and analyze its performance on a set of synthetically generated problem instances, some of which capture the specific structure of the motivating drilling and fastening application, and others that generalize to other application settings. We provide a differential analysis of our local search procedure and a comparison to other approaches to demonstrate the efficacy of the proposed heuristic.

Suggested Citation

  • Jayanth Krishna Mogali & Joris Kinable & Stephen F. Smith & Zachary B. Rubinstein, 2021. "Scheduling for multi-robot routing with blocking and enabling constraints," Journal of Scheduling, Springer, vol. 24(3), pages 291-318, June.
    • Handle: RePEc:spr:jsched:v:24:y:2021:i:3:d:10.1007_s10951-021-00684-9
    DOI: 10.1007/s10951-021-00684-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-021-00684-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-021-00684-9?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. J. A. John & N. R. Draper, 1980. "An Alternative Family of Transformations," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 29(2), pages 190-197, June.
    2. Julia Lange & Frank Werner, 2018. "Approaches to modeling train scheduling problems as job-shop problems with blocking constraints," Journal of Scheduling, Springer, vol. 21(2), pages 191-207, April.
    3. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    4. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    5. Mogali, Jayanth Krishna & Barbulescu, Laura & Smith, Stephen F., 2021. "Efficient primal heuristic updates for the blocking job shop problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 82-101.
    6. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    7. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    8. Kim, Kap Hwan & Park, Young-Man, 2004. "A crane scheduling method for port container terminals," European Journal of Operational Research, Elsevier, vol. 156(3), pages 752-768, August.
    9. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    10. E. Balas, 1999. "New classes of efficiently solvable generalized Traveling Salesman Problems," Annals of Operations Research, Springer, vol. 86(0), pages 529-558, January.
    11. Luigi Moccia & Jean‐François Cordeau & Manlio Gaudioso & Gilbert Laporte, 2006. "A branch‐and‐cut algorithm for the quay crane scheduling problem in a container terminal," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 45-59, February.
    12. Burke, Edmund K. & Bykov, Yuri, 2017. "The late acceptance Hill-Climbing heuristic," European Journal of Operational Research, Elsevier, vol. 258(1), pages 70-78.
    13. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    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. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    2. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.
    3. Mina Aliakbari & Joseph Geunes, 2022. "Multiple Train Repositioning Operations in a Railyard Network," SN Operations Research Forum, Springer, vol. 3(4), pages 1-31, December.
    4. Mogali, Jayanth Krishna & Barbulescu, Laura & Smith, Stephen F., 2021. "Efficient primal heuristic updates for the blocking job shop problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 82-101.
    5. Frank Meisel & Christian Bierwirth, 2013. "A Framework for Integrated Berth Allocation and Crane Operations Planning in Seaport Container Terminals," Transportation Science, INFORMS, vol. 47(2), pages 131-147, May.
    6. T. R. Lalita & G. S. R. Murthy, 2022. "Compact ILP formulations for a class of solutions to berth allocation and quay crane scheduling problems," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 413-439, March.
    7. Qin, Tianbao & Du, Yuquan & Chen, Jiang Hang & Sha, Mei, 2020. "Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel," European Journal of Operational Research, Elsevier, vol. 285(3), pages 884-901.
    8. Shucheng Yu & Shuaian Wang & Lu Zhen, 2017. "Quay crane scheduling problem with considering tidal impact and fuel consumption," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 345-368, December.
    9. Samà, Marcella & D’Ariano, Andrea & D’Ariano, Paolo & Pacciarelli, Dario, 2017. "Scheduling models for optimal aircraft traffic control at busy airports: Tardiness, priorities, equity and violations considerations," Omega, Elsevier, vol. 67(C), pages 81-98.
    10. Abdellah Salhi & Ghazwan Alsoufi & Xinan Yang, 2019. "An evolutionary approach to a combined mixed integer programming model of seaside operations as arise in container ports," Annals of Operations Research, Springer, vol. 272(1), pages 69-98, January.
    11. Shoufeng Ma & Hongming Li & Ning Zhu & Chenyi Fu, 2021. "Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty," Journal of Scheduling, Springer, vol. 24(2), pages 137-174, April.
    12. Corman, Francesco & D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2010. "A tabu search algorithm for rerouting trains during rail operations," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 175-192, January.
    13. Sun, Defeng & Tang, Lixin & Baldacci, Roberto, 2019. "A Benders decomposition-based framework for solving quay crane scheduling problems," European Journal of Operational Research, Elsevier, vol. 273(2), pages 504-515.
    14. Defeng Sun & Lixin Tang & Roberto Baldacci & Zihan Chen, 2024. "A Decomposition Method for the Group-Based Quay Crane Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 543-570, March.
    15. Frank Meisel, 2011. "The quay crane scheduling problem with time windows," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(7), pages 619-636, October.
    16. Guvenc Dik & Erhan Kozan, 2017. "A flexible crane scheduling methodology for container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 29(1), pages 64-96, March.
    17. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    18. Yuan, Shuai & Skinner, Bradley & Huang, Shoudong & Liu, Dikai, 2013. "A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 228(1), pages 72-82.
    19. Zhen, Lu & Lee, Loo Hay & Chew, Ek Peng, 2011. "A decision model for berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 212(1), pages 54-68, July.
    20. Andrea D'Ariano & Francesco Corman & Dario Pacciarelli & Marco Pranzo, 2008. "Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time," Transportation Science, INFORMS, vol. 42(4), pages 405-419, November.

    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:spr:jsched:v:24:y:2021:i:3:d:10.1007_s10951-021-00684-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.