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

  1. Get@NRC: Effective genetic algorithm for resource-constrained project scheduling with limited preemptions (Opens in a new window)
DOIResolve DOI: http://doi.org/10.1007/s13042-011-0014-3
AuthorSearch for: ; Search for: ; Search for:
Journal titleInternational Journal of Machine Learning and Cybernetics
Pages5565; # of pages: 11
Subject0-1 knapsack problem; Activity list; Competitive algorithms; Computational experiment; Makespan; Makespan minimization; Pre-emption; Pseudo-polynomial time complexity; Resource allocation problem; Resource availability; Resource constrained project scheduling; Resource-constrained project scheduling problem; Dynamic programming; Integer programming; Polynomial approximation; Resource allocation; Scheduling algorithms; Genetic algorithms
AbstractIn 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. © 2011 Springer-Verlag.
Publication date
AffiliationNational Research Council Canada (NRC-CNRC); Construction (CONST-CONST)
Peer reviewedYes
NPARC number21271447
Export citationExport as RIS
Report a correctionReport a correction
Record identifier7fec4d6f-f1b1-4a22-8725-88884f1cbf59
Record created2014-03-24
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)