SpringerLink
Log in

Effective genetic algorithm for resource-constrained project scheduling with limited preemptions

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

In this paper, a specific preemptive resource-constrained project scheduling problem (PRCPSP) with makespan minimization is considered of which each activity could be interrupted at most M times. According to activity requirements and resource availability, resources are allocated to activities in different intervals. A resource-fragment chain is constructed to keep resource states dynamically. The resource allocation problem is transferred to the well-known 0–1 knapsack problem and solved by dynamic programming in pseudo-polynomial time complexity. The schedule enhancement method is developed to further improve the quality of obtained schedules by removing and rescheduling each activity in the activity list. By integrating the resource allocation and the schedule enhancement method, a genetic algorithm is proposed for the considered problem with the objective to minimize makespan. Computational experiments on the standard J30 and J120 sets show that the proposed algorithm is amongst the most competitive algorithms in literature for the pre-emptive cases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Ballestin F, Valls V, Quintanilla S (2008) Pre-emption in resource-constrained project scheduling. Eur J Oper Res 189:1136–1152

    Article  MATH  Google Scholar 

  2. Ballestin F, Valls V, Quintanilla S (2009) Scheduling projects with limited number of preemptions. Comput Oper Res 36(11):2913–2925

    Article  MATH  Google Scholar 

  3. Blazewicz J, Lenstra J, Kan AR (1983) Scheduling projects to resource constraints: classification and complexity. Discret Appl Math 5:11–24

    Article  MATH  Google Scholar 

  4. Buddhakulsomsiri J, Kim DS (2006) Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur J Oper Res 175:279–295

    Article  MATH  Google Scholar 

  5. Demeulemeester E, Herroelen W (1996) An efficient optimal procedure for the preemptive resource-constrained project scheduling problem. Eur J Oper Res 90:334–348

    Article  MATH  Google Scholar 

  6. Herroelen W, De Reyck B, Demeulmeester E (1998) Resource-constrained project scheduling: a survey of recent development. Comput Oper Res 25(4):279–302

    Article  MathSciNet  MATH  Google Scholar 

  7. Kolisch R, Sprecher A, Drexl A (1995) Characterization and generation of a general class of resource-constrained project scheduling problems. Manage Sci 41:1693–1703

    Article  MATH  Google Scholar 

  8. Mendes JJM, Goncalves JF, Resende MGC (2009) A random key based genetic algorithm for the resource constrained project scheduling problem. Comput Oper Res 36:92–109

    Article  MathSciNet  MATH  Google Scholar 

  9. Mika M, Waligora G, Weglarz J (2005) Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. Eur J Oper Res 164:639–668

    Article  MathSciNet  MATH  Google Scholar 

  10. Mika M, Waligora G, Weglarz J (2008) Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur J Oper Res 187:1238–1250

    Article  MATH  Google Scholar 

  11. Moumene K, Ferland JA (2009) Activity list representation for a generalization of the resource-constrained project scheduling problem. Eur J Oper Res 199(1):46–54

    Article  MathSciNet  MATH  Google Scholar 

  12. Patterson JH (1984) A comparison of exact procedures for solving the multiple constrained resource project scheduling problem. Manage Sci 30(7):854–867

    Article  Google Scholar 

  13. Peteghem VV, Vanhoucke M (2010) A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. Eur J Oper Res 201:409–418

    Article  MATH  Google Scholar 

  14. Weglarz J (1999) Project scheduling: recent models, algorithms and applications. Kluwer, Norwell

Download references

Acknowledgment

This work is supported by the National Natural Science Foundation of China (Nos. 60973073 and 60873236), the National 863 Project (No. 2008AA04Z103), and the Scientific Research Foundation of Graduate School of Southeast University (No. YBJJ0931).

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Southeast University, Nan**g, China

    Jie Zhu & ** Li

  2. Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, Nan**g, China

    Jie Zhu & ** Li

  3. Centre for Computer-Assisted Construction Technologies, National Research Council, London, ON, Canada

    Weiming Shen

Authors
  1. Jie Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. ** Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Weiming Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jie Zhu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhu, J., Li, X. & Shen, W. Effective genetic algorithm for resource-constrained project scheduling with limited preemptions. Int. J. Mach. Learn. & Cyber. 2, 55–65 (2011). https://doi.org/10.1007/s13042-011-0014-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-011-0014-3

Keywords

Search

Navigation