IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v20y2020i2d10.1007_s12351-017-0358-x.html
   My bibliography  Save this article

A lagrangian relaxation algorithm for facility location of resource-constrained decentralized multi-project scheduling problems

Author

Listed:
  • Mohammad Rostami

    (University of Science and Technology (IUST))

  • Morteza Bagherpour

    (University of Science and Technology (IUST))

Abstract

Recent literature on multi-project scheduling problems has been focused on the transfer of available resources between project activities, especially in decentralized projects. Determining the right location for storage facilities where resources are moved between activities is major topics in decentralized multi-projects scheduling problems. This paper introduces a new decentralized resource-constrained multi-project scheduling problem. Its purpose is to simultaneously minimize the cost of the project completion time and the cost of facilities location. A mixed integer linear programming model is first presented to solve small-size problems by using conventional solvers. Then, three heuristic/meta-heuristic methods are proposed to solve larger-size problems. To this end, a fast constructive heuristic algorithm based on priority rules is introduced. Then, using the heuristic method structure, a combinatorial genetic algorithm is developed to solve large-size problems in reasonable CPU running time. Finally, the lagrangian relaxation technique and branch-and-bound algorithm are applied to generate an effective lower bound. According to the computational results obtained and managerial insights, total costs can be significantly reduced by selecting an optimal location of resources. By the use of a scenario-based TOPSIS approach, the heuristic methods are ranked based on changes in the importance of metrics. Friedman’s test result of TOPSIS shows that there is no significant difference among the heuristic methods.

Suggested Citation

  • Mohammad Rostami & Morteza Bagherpour, 2020. "A lagrangian relaxation algorithm for facility location of resource-constrained decentralized multi-project scheduling problems," Operational Research, Springer, vol. 20(2), pages 857-897, June.
    • Handle: RePEc:spr:operea:v:20:y:2020:i:2:d:10.1007_s12351-017-0358-x
    DOI: 10.1007/s12351-017-0358-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-017-0358-x
    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/s12351-017-0358-x?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. Monique Guignard, 2003. "Lagrangean relaxation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 11(2), pages 151-200, December.
    2. Gonçalves, J.F. & Mendes, J.J.M. & Resende, M.G.C., 2008. "A genetic algorithm for the resource constrained multi-project scheduling problem," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1171-1190, September.
    3. Krüger, Doreen & Scholl, Armin, 2009. "A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times," European Journal of Operational Research, Elsevier, vol. 197(2), pages 492-508, September.
    4. Messelis, Tommy & De Causmaecker, Patrick, 2014. "An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 233(3), pages 511-528.
    5. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    6. Al-Fawzan, M. A. & Haouari, Mohamed, 2005. "A bi-objective model for robust resource-constrained project scheduling," International Journal of Production Economics, Elsevier, vol. 96(2), pages 175-187, May.
    7. Anıl Can & Gündüz Ulusoy, 2014. "Multi-project scheduling with two-stage decomposition," Annals of Operations Research, Springer, vol. 217(1), pages 95-116, June.
    8. Nicky J. Welton & Howard H. Z. Thom, 2015. "Value of Information," Medical Decision Making, , vol. 35(5), pages 564-566, July.
    9. Belarmino Adenso-Díaz & Manuel Laguna, 2006. "Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search," Operations Research, INFORMS, vol. 54(1), pages 99-114, February.
    10. Adhau, Sunil & Mittal, M.L. & Mittal, Abhinav, 2013. "A multi-agent system for decentralized multi-project scheduling with resource transfers," International Journal of Production Economics, Elsevier, vol. 146(2), pages 646-661.
    11. Zamani, Reza, 2013. "A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 552-559.
    12. Gutjahr, Walter J., 2015. "Bi-Objective Multi-Mode Project Scheduling Under Risk Aversion," European Journal of Operational Research, Elsevier, vol. 246(2), pages 421-434.
    13. 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.
    14. Marshall L. Fisher, 1985. "An Applications Oriented Guide to Lagrangian Relaxation," Interfaces, INFORMS, vol. 15(2), pages 10-21, April.
    15. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.
    16. N.R. Achuthan & A. Hardjawidjaja, 2001. "Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm," Annals of Operations Research, Springer, vol. 108(1), pages 55-74, November.
    17. Andreas Fink & Jörg Homberger, 2015. "Decentralized Multi-Project Scheduling," International Handbooks on Information Systems, in: Christoph Schwindt & Jürgen Zimmermann (ed.), Handbook on Project Management and Scheduling Vol. 2, edition 127, chapter 0, pages 685-706, Springer.
    18. Salewski, Frank & Schirmer, Andreas & Drexl, Andreas, 1997. "Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application," European Journal of Operational Research, Elsevier, vol. 102(1), pages 88-110, October.
    19. Vijay S. Bilolikar & Karuna Jain & Mahesh Sharma, 2016. "An adaptive crossover genetic algorithm with simulated annealing for multi mode resource constrained project scheduling with discounted cash flows," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 25(1), pages 28-46.
    20. Kolisch, Rainer & Sprecher, Arno, 1997. "PSPLIB - A project scheduling problem library : OR Software - ORSEP Operations Research Software Exchange Program," European Journal of Operational Research, Elsevier, vol. 96(1), pages 205-216, January.
    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. Jun Wu & Xin Liu & Yuanyuan Li & Liping Yang & Wenyan Yuan & Yile Ba, 2022. "A Two-Stage Model with an Improved Clustering Algorithm for a Distribution Center Location Problem under Uncertainty," Mathematics, MDPI, vol. 10(14), pages 1-17, July.
    2. Gómez Sánchez, Mariam & Lalla-Ruiz, Eduardo & Fernández Gil, Alejandro & Castro, Carlos & Voß, Stefan, 2023. "Resource-constrained multi-project scheduling problem: A survey," European Journal of Operational Research, Elsevier, vol. 309(3), pages 958-976.
    3. Wuliang Peng & Jiali lin & Jingwen Zhang & Liangwei Chen, 2022. "A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III," Annals of Operations Research, Springer, vol. 308(1), pages 389-414, January.

    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. Ben Issa, Samer & Patterson, Raymond A. & Tu, Yiliu, 2021. "Solving resource-constrained multi-project environment under different activity assumptions," International Journal of Production Economics, Elsevier, vol. 232(C).
    2. Kellenbrink, Carolin & Helber, Stefan, 2015. "Scheduling resource-constrained projects with a flexible project structure," European Journal of Operational Research, Elsevier, vol. 246(2), pages 379-391.
    3. Wuliang Peng & Jiali lin & Jingwen Zhang & Liangwei Chen, 2022. "A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III," Annals of Operations Research, Springer, vol. 308(1), pages 389-414, January.
    4. Rob Eynde & Mario Vanhoucke, 2020. "Resource-constrained multi-project scheduling: benchmark datasets and decoupled scheduling," Journal of Scheduling, Springer, vol. 23(3), pages 301-325, June.
    5. Gómez Sánchez, Mariam & Lalla-Ruiz, Eduardo & Fernández Gil, Alejandro & Castro, Carlos & Voß, Stefan, 2023. "Resource-constrained multi-project scheduling problem: A survey," European Journal of Operational Research, Elsevier, vol. 309(3), pages 958-976.
    6. Hartmann, Sönke & Briskorn, Dirk, 2022. "An updated survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 1-14.
    7. Bredael, Dries & Vanhoucke, Mario, 2023. "Multi-project scheduling: A benchmark analysis of metaheuristic algorithms on various optimisation criteria and due dates," European Journal of Operational Research, Elsevier, vol. 308(1), pages 54-75.
    8. Liu, Ying & Zhou, Jing & Lim, Andrew & Hu, Qian, 2023. "A tree search heuristic for the resource constrained project scheduling problem with transfer times," European Journal of Operational Research, Elsevier, vol. 304(3), pages 939-951.
    9. Alireza Etminaniesfahani & Hanyu Gu & Leila Moslemi Naeni & Amir Salehipour, 2024. "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 41-68, July.
    10. 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.
    11. Alfredo S. Ramos & Pablo A. Miranda-Gonzalez & Samuel Nucamendi-Guillén & Elias Olivares-Benitez, 2023. "A Formulation for the Stochastic Multi-Mode Resource-Constrained Project Scheduling Problem Solved with a Multi-Start Iterated Local Search Metaheuristic," Mathematics, MDPI, vol. 11(2), pages 1-25, January.
    12. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    13. Arda Turkgenci & Huseyin Guden & Mehmet Gülşen, 2021. "Decomposition based extended project scheduling for make-to-order production," Operational Research, Springer, vol. 21(2), pages 801-825, June.
    14. 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.
    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. Nadia Chaudry & Ingunn Vermedal & Kjetil Fagerholt & Maria Fleischer Fauske & Magnus Stålhane, 2020. "A decomposition solution approach to the troops-to-tasks assignment in military peacekeeping operations," The Journal of Defense Modeling and Simulation, , vol. 17(4), pages 357-371, October.
    17. Rahman Torba & Stéphane Dauzère-Pérès & Claude Yugma & Cédric Gallais & Juliette Pouzet, 2024. "Solving a real-life multi-skill resource-constrained multi-project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 69-114, July.
    18. Xabier A. Martin & Rosa Herrero & Angel A. Juan & Javier Panadero, 2024. "An Agile Adaptive Biased-Randomized Discrete-Event Heuristic for the Resource-Constrained Project Scheduling Problem," Mathematics, MDPI, vol. 12(12), pages 1-21, June.
    19. Zsolt T. Kosztyán & Eszter Bogdány & István Szalkai & Marcell T. Kurbucz, 2022. "Impacts of synergies on software project scheduling," Annals of Operations Research, Springer, vol. 312(2), pages 883-908, May.
    20. Chen, Chung-Yang & Liu, Heng-An & Song, Je-Yi, 2013. "Integrated projects planning in IS departments: A multi-period multi-project selection and assignment approach with a computerized implementation," European Journal of Operational Research, Elsevier, vol. 229(3), pages 683-694.

    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:operea:v:20:y:2020:i:2:d:10.1007_s12351-017-0358-x. 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.