IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v302y2021i2d10.1007_s10479-020-03550-7.html
   My bibliography  Save this article

A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources

Author

Listed:
  • Matthias Horn

    (TU Wien)

  • Günther R. Raidl

    (TU Wien)

  • Elina Rönnberg

    (Linköping University)

Abstract

We consider a sequencing problem with time windows, in which a subset of a given set of jobs shall be scheduled. A scheduled job has to execute without preemption and during this time, the job needs both a common resource for a part of the execution as well as a secondary resource for the whole execution time. The common resource is shared by all jobs while a secondary resource is shared only by a subset of the jobs. Each job has one or more time windows and due to these, it is not possible to schedule all jobs. Instead, each job is associated with a prize and the task is to select a subset of jobs which yields a feasible schedule with a maximum sum of prizes. First, we argue that the problem is NP-hard. Then, we present an exact A* algorithm and derive different upper bounds for the total prize; these bounds are based on constraint and Lagrangian relaxations of a linear programming relaxation of a multidimensional knapsack problem. For comparison, a compact mixed integer programming (MIP) model and a constraint programming model are also presented. An extensive experimental evaluation on three types of problem instances shows that the A* algorithm outperforms the other approaches and is able to solve small to medium size instances with up to about 40 jobs to proven optimality. In cases where A* does not prove that an optimal solution is found, the obtained upper bounds are stronger than those of the MIP model.

Suggested Citation

  • Matthias Horn & Günther R. Raidl & Elina Rönnberg, 2021. "A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources," Annals of Operations Research, Springer, vol. 302(2), pages 477-505, July.
    • Handle: RePEc:spr:annopr:v:302:y:2021:i:2:d:10.1007_s10479-020-03550-7
    DOI: 10.1007/s10479-020-03550-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03550-7
    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/s10479-020-03550-7?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. 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.
    2. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    3. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Froger, Aurélien & Sadykov, Ruslan, 2023. "New exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources," European Journal of Operational Research, Elsevier, vol. 306(1), pages 65-82.

    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. Johannes Maschler & Günther R. Raidl, 2021. "Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources," Annals of Operations Research, Springer, vol. 302(2), pages 507-531, July.
    2. Estévez-Fernández, Arantza, 2012. "A game theoretical approach to sharing penalties and rewards in projects," European Journal of Operational Research, Elsevier, vol. 216(3), pages 647-657.
    3. Xiong, Jian & Leus, Roel & Yang, Zhenyu & Abbass, Hussein A., 2016. "Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project," European Journal of Operational Research, Elsevier, vol. 251(2), pages 662-675.
    4. Vega-Velázquez, Miguel Ángel & García-Nájera, Abel & Cervantes, Humberto, 2018. "A survey on the Software Project Scheduling Problem," International Journal of Production Economics, Elsevier, vol. 202(C), pages 145-161.
    5. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    6. Sciau, Jean-Baptiste & Goyon, Agathe & Sarazin, Alexandre & Bascans, Jérémy & Prud’homme, Charles & Lorca, Xavier, 2024. "Using constraint programming to address the operational aircraft line maintenance scheduling problem," Journal of Air Transport Management, Elsevier, vol. 115(C).
    7. Paraskevopoulos, Dimitris C. & Laporte, Gilbert & Repoussis, Panagiotis P. & Tarantilis, Christos D., 2017. "Resource constrained routing and scheduling: Review and research prospects," European Journal of Operational Research, Elsevier, vol. 263(3), pages 737-754.
    8. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2021. "Scheduling Human-Robot Teams in collaborative working cells," International Journal of Production Economics, Elsevier, vol. 235(C).
    9. Jeunet, Jully & Bou Orm, Mayassa, 2020. "Optimizing temporary work and overtime in the Time Cost Quality Trade-off Problem," European Journal of Operational Research, Elsevier, vol. 284(2), pages 743-761.
    10. Wolfgang Wörndl & Alexander Hefele & Daniel Herzog, 2017. "Recommending a sequence of interesting places for tourist trips," Information Technology & Tourism, Springer, vol. 17(1), pages 31-54, March.
    11. Majsa Ammouriova & Massimo Bertolini & Juliana Castaneda & Angel A. Juan & Mattia Neroni, 2022. "A Heuristic-Based Simulation for an Education Process to Learn about Optimization Applications in Logistics and Transportation," Mathematics, MDPI, vol. 10(5), pages 1-18, March.
    12. Korytkowski, Przemyslaw & Malachowski, Bartlomiej, 2019. "Competence-based estimation of activity duration in IT projects," European Journal of Operational Research, Elsevier, vol. 275(2), pages 708-720.
    13. Vaseghi, Forough & Martens, Annelies & Vanhoucke, Mario, 2024. "Analysis of the impact of corrective actions for stochastic project networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 503-518.
    14. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    15. Yang-Kuei Lin & Chin Soon Chong, 2017. "Fast GA-based project scheduling for computing resources allocation in a cloud manufacturing system," Journal of Intelligent Manufacturing, Springer, vol. 28(5), pages 1189-1201, June.
    16. Billaut, Jean-Charles & Della Croce, Federico & Grosso, Andrea, 2015. "A single machine scheduling problem with two-dimensional vector packing constraints," European Journal of Operational Research, Elsevier, vol. 243(1), pages 75-81.
    17. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    18. Benita, Francisco & López-Ramos, Francisco & Nasini, Stefano, 2019. "A bi-level programming approach for global investment strategies with financial intermediation," European Journal of Operational Research, Elsevier, vol. 274(1), pages 375-390.
    19. José Ruiz-Meza & Julio Brito & Jairo R. Montoya-Torres, 2021. "Multi-Objective Fuzzy Tourist Trip Design Problem with Heterogeneous Preferences and Sustainable Itineraries," Sustainability, MDPI, vol. 13(17), pages 1-22, August.
    20. Gonzalo Muñoz & Daniel Espinoza & Marcos Goycoolea & Eduardo Moreno & Maurice Queyranne & Orlando Rivera Letelier, 2018. "A study of the Bienstock–Zuckerberg algorithm: applications in mining and resource constrained project scheduling," Computational Optimization and Applications, Springer, vol. 69(2), pages 501-534, March.

    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:annopr:v:302:y:2021:i:2:d:10.1007_s10479-020-03550-7. 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.