IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v308y2022i1d10.1007_s10479-021-04106-z.html
   My bibliography  Save this article

A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III

Author

Listed:
  • Wuliang Peng

    (Yantai University)

  • Jiali lin

    (Yantai University)

  • Jingwen Zhang

    (Northwestern Polytechnic University)

  • Liangwei Chen

    (Yantai University)

Abstract

In enterprise project management systems, a program at the tactical level coordinates and manages multiple projects at the operational level. There are close relationships between multiple projects in a program, which are typically manifested as shared resources and precedence relationships. Most research efforts have concentrated on the resource sharing by projects, while the precedence relationships between projects have yet to be comprehensively investigated. In this paper, a bi-objective hierarchical resource-constrained program scheduling problem proposed, where both resource sharing and precedence relationships between projects are considered in a distributed environment. The problem contains two different sub-problems at the operational level and the tactical level, and they are modeled in the same way as two bi-objective multi-mode scheduling problems. Shared resources are allocated from the tactical level to the operational level, and once they are allocated to a project, they can only be re-allocated to other projects once the current project is finished. Subsequently, a two-phase algorithm based on NSGA-III is developed. The algorithm runs at the operational level and the tactical level in turn. According to the Pareto fronts of projects that are submitted from the operational level, the bi-objective program planning at the tactical level is conducted under the constraints of precedence relationships and shared resources. The results of computational simulations demonstrate the satisfactory performance of the improved algorithm. By coordinating the local optimization of projects and the global optimization of the program in a hierarchical framework, the method proposed in this paper provides an effective integrated scheduling method for decision-makers at various levels of a program.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:308:y:2022:i:1:d:10.1007_s10479-021-04106-z
    DOI: 10.1007/s10479-021-04106-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-021-04106-z
    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-021-04106-z?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. 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.
    2. 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.
    3. Farnaz Torabi Yeganeh & Seyed Hessameddin Zegordi, 2020. "A multi-objective optimization approach to project scheduling with resiliency criteria under uncertain activity duration," Annals of Operations Research, Springer, vol. 285(1), pages 161-196, February.
    4. Mohanty, R. P. & Siddiq, M. K., 1989. "Multiple projects -- Multiple resources constrained scheduling: A multiobjective analysis," Engineering Costs and Production Economics, Elsevier, vol. 18(1), pages 83-92, October.
    5. Deckro, Richard F. & Winkofsky, E. P. & E. Hebert, John & Gagnon, Roger, 1991. "A decomposition approach to multi-project scheduling," European Journal of Operational Research, Elsevier, vol. 51(1), pages 110-118, March.
    6. Browning, Tyson R. & Yassine, Ali A., 2010. "Resource-constrained multi-project scheduling: Priority rule performance revisited," International Journal of Production Economics, Elsevier, vol. 126(2), pages 212-228, August.
    7. Huan Neng Chiu & Deng Maw Tsai, 2002. "An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows," Construction Management and Economics, Taylor & Francis Journals, vol. 20(1), pages 55-66.
    8. Lawrence, Stephen R. & Morton, Thomas E., 1993. "Resource-constrained multi-project scheduling with tardy costs: Comparing myopic, bottleneck, and resource pricing heuristics," European Journal of Operational Research, Elsevier, vol. 64(2), pages 168-187, January.
    9. Speranza, M. Grazia & Vercellis, Carlo, 1993. "Hierarchical models for multi-project planning and scheduling," European Journal of Operational Research, Elsevier, vol. 64(2), pages 312-325, January.
    10. 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.
    11. Elimam, A.A. & Dodin, B., 2013. "Project scheduling in optimizing integrated supply chain operations," European Journal of Operational Research, Elsevier, vol. 224(3), pages 530-541.
    12. 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.
    13. Sönke Hartmann, 2001. "Project Scheduling with Multiple Modes: A Genetic Algorithm," Annals of Operations Research, Springer, vol. 102(1), pages 111-135, February.
    14. Geiger, Martin Josef, 2017. "A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 729-741.
    15. Antonio Lova & Pilar Tormos, 2001. "Analysis of Scheduling Schemes and Heuristic Rules Performance in Resource-Constrained Multiproject Scheduling," Annals of Operations Research, Springer, vol. 102(1), pages 263-286, February.
    16. 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.
    17. Aidin Delgoshaei & Timon Rabczuk & Ahad Ali & Mohd Khairol Anuar Ariffin, 2017. "An applicable method for modifying over-allocated multi-mode resource constraint schedules in the presence of preemptive resources," Annals of Operations Research, Springer, vol. 259(1), pages 85-117, December.
    18. Beşikci, Umut & Bilge, Ümit & Ulusoy, Gündüz, 2015. "Multi-mode resource constrained multi-project scheduling and resource portfolio problem," European Journal of Operational Research, Elsevier, vol. 240(1), pages 22-31.
    19. Alessandro Agnetis & Cyril Briand & Sandra Ulrich Ngueveu & Přemysl Šůcha, 2020. "Price of anarchy and price of stability in multi-agent project scheduling," Annals of Operations Research, Springer, vol. 285(1), pages 97-119, February.
    20. Massimiliano Caramia, 2020. "Project management and scheduling," Annals of Operations Research, Springer, vol. 285(1), pages 1-8, February.
    21. Homberger, Jörg & Fink, Andreas, 2017. "Generic negotiation mechanisms with side payments – Design, analysis and application for decentralized resource-constrained multi-project scheduling problems," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1001-1012.
    22. 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.
    23. Giuseppe Confessore & Stefano Giordani & Silvia Rismondo, 2007. "A market-based multi-agent system model for decentralized multi-project scheduling," Annals of Operations Research, Springer, vol. 150(1), pages 115-135, March.
    24. Hans, E.W. & Herroelen, W. & Leus, R. & Wullink, G., 2007. "A hierarchical approach to multi-project planning under uncertainty," Omega, Elsevier, vol. 35(5), pages 563-577, October.
    25. Umut Beşikçi & Ümit Bilge & Gündüz Ulusoy, 2019. "Resource portfolio problem under relaxed resource dedication policy in multi-mode multi-project scheduling," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 14(4), pages 541-567.
    26. 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.
    27. 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. Hongbo Li & Linwen Zheng & Hanyu Zhu, 2023. "Resource leveling in projects with flexible structures," Annals of Operations Research, Springer, vol. 321(1), pages 311-342, February.

    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. 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.
    2. 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.
    3. 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.
    4. 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).
    5. He, Naihui & Zhang, David Z. & Yuce, Baris, 2022. "Integrated multi-project planning and scheduling - a multiagent approach," European Journal of Operational Research, Elsevier, vol. 302(2), pages 688-699.
    6. Yukang He & Tao Jia & Weibo Zheng, 2024. "Simulated annealing for centralised resource-constrained multiproject scheduling to minimise the maximal cash flow gap under different payment patterns," Annals of Operations Research, Springer, vol. 338(1), pages 115-149, July.
    7. Browning, Tyson R. & Yassine, Ali A., 2010. "Resource-constrained multi-project scheduling: Priority rule performance revisited," International Journal of Production Economics, Elsevier, vol. 126(2), pages 212-228, August.
    8. He, Yukang & Jia, Tao & Zheng, Weibo, 2023. "Tabu search for dedicated resource-constrained multiproject scheduling to minimise the maximal cash flow gap under uncertainty," European Journal of Operational Research, Elsevier, vol. 310(1), pages 34-52.
    9. Maryam Sadeghloo & Saeed Emami & Ali Divsalar, 2024. "A Benders decomposition algorithm for the multi-mode resource-constrained multi-project scheduling problem with uncertainty," Annals of Operations Research, Springer, vol. 339(3), pages 1637-1677, August.
    10. 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.
    11. 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.
    12. 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.
    13. Fink, Andreas & Gerhards, Patrick, 2021. "Negotiation mechanisms for the multi-agent multi-mode resource investment problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 261-274.
    14. 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.
    15. Van Eynde, Rob & Vanhoucke, Mario, 2022. "New summary measures and datasets for the multi-project scheduling problem," European Journal of Operational Research, Elsevier, vol. 299(3), pages 853-868.
    16. 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).
    17. 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.
    18. Ramírez Palencia, Alberto E. & Mejía Delgadillo, Gonzalo E., 2012. "A computer application for a bus body assembly line using Genetic Algorithms," International Journal of Production Economics, Elsevier, vol. 140(1), pages 431-438.
    19. Joosung Lee & Jaejun Kim, 2017. "BIM-Based 4D Simulation to Improve Module Manufacturing Productivity for Sustainable Building Projects," Sustainability, MDPI, vol. 9(3), pages 1-23, March.
    20. Feifei Li & Zhe Xu, 2018. "A multi-agent system for distributed multi-project scheduling with two-stage decomposition," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-24, October.

    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:308:y:2022:i:1:d:10.1007_s10479-021-04106-z. 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.