IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v265y2018i2p454-462.html
   My bibliography  Save this article

An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case

Author

Listed:
  • Kadri, Roubila Lilia
  • Boctor, Fayez F.

Abstract

In this article, we address the resource-constrained project scheduling problem with transfer times (RCPSPTT). We assume that pre-emption is not allowed, and precedence relations are zero-lag finish-to-start relations. We also assume that the durations and resource transfer times of activities are known and deterministic. The objective is to choose a start time for each activity of the project so that the project duration is minimized, while satisfying precedence relations, resource availabilities, and resource-transfer time constraints. We propose a new genetic algorithm using a two-point crossover operator. The experiment, conducted on a large number of instances, shows that the proposed algorithm performs better than several solution methods previously published.

Suggested Citation

  • Kadri, Roubila Lilia & Boctor, Fayez F., 2018. "An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case," European Journal of Operational Research, Elsevier, vol. 265(2), pages 454-462.
    • Handle: RePEc:eee:ejores:v:265:y:2018:i:2:p:454-462
    DOI: 10.1016/j.ejor.2017.07.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717306549
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.07.027?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. Patterson, James H. & Brian Talbot, F. & Slowinski, Roman & Weglarz, Jan, 1990. "Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems," European Journal of Operational Research, Elsevier, vol. 49(1), pages 68-79, November.
    2. Lova, Antonio & Tormos, Pilar & Cervantes, Mariamar & Barber, Federico, 2009. "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes," International Journal of Production Economics, Elsevier, vol. 117(2), pages 302-316, February.
    3. Sönke Hartmann, 2001. "Project Scheduling with Multiple Modes: A Genetic Algorithm," Annals of Operations Research, Springer, vol. 102(1), pages 111-135, February.
    4. Demeulemeester, Erik L. & Herroelen, Willy S., 1996. "An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 90(2), pages 334-348, April.
    5. 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.
    6. Bouleimen, K. & Lecocq, H., 2003. "A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version," European Journal of Operational Research, Elsevier, vol. 149(2), pages 268-281, September.
    7. Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
    8. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    9. J Alcaraz & C Maroto & R Ruiz, 2003. "Solving the Multi-Mode Resource-Constrained Project Scheduling Problem with genetic algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(6), pages 614-626, June.
    10. Vicente Valls & Francisco Ballestín & Sacramento Quintanilla, 2004. "A Population-Based Approach to the Resource-Constrained Project Scheduling Problem," Annals of Operations Research, Springer, vol. 131(1), pages 305-324, October.
    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. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    13. Jens Poppenborg & Sigrid Knust, 2016. "A flow-based tabu search algorithm for the RCPSP with transfer times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 305-334, March.
    14. Boctor, Fayer F., 1990. "Some efficient multi-heuristic procedures for resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 49(1), pages 3-13, 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. 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.
    2. 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.
    3. Patoghi, Amirhosein & Mousavi, Seyed Meysam, 2021. "A new approach for material ordering and multi-mode resource constraint project scheduling problem in a multi-site context under interval-valued fuzzy uncertainty," Technological Forecasting and Social Change, Elsevier, vol. 173(C).
    4. Wenzhu Liao & Tong Wang, 2019. "A Novel Collaborative Optimization Model for Job Shop Production–Delivery Considering Time Window and Carbon Emission," Sustainability, MDPI, vol. 11(10), pages 1-27, May.
    5. Urooj Asgher & Muhammad Babar Rasheed & Ameena Saad Al-Sumaiti & Atiq Ur-Rahman & Ihsan Ali & Amer Alzaidi & Abdullah Alamri, 2018. "Smart Energy Optimization Using Heuristic Algorithm in Smart Grid with Integration of Solar Energy Sources," Energies, MDPI, vol. 11(12), pages 1-26, December.
    6. Yanfen Zhang & Jinyao Ma & Haibin Zhang & Bin Yue, 2023. "Platform Resource Scheduling Method Based on Branch-and-Bound and Genetic Algorithm," Annals of Data Science, Springer, vol. 10(5), pages 1421-1445, October.
    7. Peng, Rui & Xiao, Hui & Guo, Jianjun & Lin, Chen, 2020. "Optimal defense of a distributed data storage system against hackers’ attacks," Reliability Engineering and System Safety, Elsevier, vol. 197(C).

    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. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    2. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    3. 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.
    4. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    5. Elloumi, Sonda & Fortemps, Philippe, 2010. "A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 31-41, August.
    6. Buddhakulsomsiri, Jirachai & Kim, David S., 2007. "Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting," European Journal of Operational Research, Elsevier, vol. 178(2), pages 374-390, April.
    7. 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.
    8. 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.
    9. Buddhakulsomsiri, Jirachai & Kim, David S., 2006. "Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting," European Journal of Operational Research, Elsevier, vol. 175(1), pages 279-295, November.
    10. T Wauters & K Verbeeck & G Vanden Berghe & P De Causmaecker, 2011. "Learning agents for the multi-mode project scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 281-290, February.
    11. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    12. Luis F. Machado-Domínguez & Carlos D. Paternina-Arboleda & Jorge I. Vélez & Agustin Barrios-Sarmiento, 2021. "A memetic algorithm to address the multi-node resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 24(4), pages 413-429, August.
    13. V. Van Peteghem & M. Vanhoucke, 2009. "Using Resource Scarceness Characteristics to Solve the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 09/595, Ghent University, Faculty of Economics and Business Administration.
    14. V. Van Peteghem & M. Vanhoucke, 2008. "A Genetic Algorithm for the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 08/494, Ghent University, Faculty of Economics and Business Administration.
    15. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    16. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    17. 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.
    18. 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.
    19. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    20. Drexl, Andreas & Nikulin, Yuri, 2005. "Multicriteria time window-constrained project scheduling with applications to airport gate assignment. Part I: Methodology," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 595, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    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:eee:ejores:v:265:y:2018:i:2:p:454-462. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.