| DOI | Resolve DOI: https://doi.org/10.1007/s13042-011-0014-3 |
|---|
| Author | Search for: Zhu, J.; Search for: Li, X.; Search for: Shen, W.1 |
|---|
| Affiliation | - National Research Council of Canada. NRC Institute for Research in Construction
|
|---|
| Format | Text, Article |
|---|
| Subject | 0-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 |
|---|
| 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. © 2011 Springer-Verlag. |
|---|
| Publication date | 2011 |
|---|
| In | |
|---|
| Language | English |
|---|
| Peer reviewed | Yes |
|---|
| NPARC number | 21271447 |
|---|
| Export citation | Export as RIS |
|---|
| Report a correction | Report a correction (opens in a new tab) |
|---|
| Record identifier | 7fec4d6f-f1b1-4a22-8725-88884f1cbf59 |
|---|
| Record created | 2014-03-24 |
|---|
| Record modified | 2020-04-21 |
|---|
