| DOI | Trouver le DOI : https://doi.org/10.1007/s13042-011-0014-3 |
|---|
| Auteur | Rechercher : Zhu, J.; Rechercher : Li, X.; Rechercher : Shen, W.1 |
|---|
| Affiliation | - Conseil national de recherches du Canada. Institut de recherche en construction du CNRC
|
|---|
| Format | Texte, Article |
|---|
| Sujet | 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 |
|---|
| Résumé | 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. |
|---|
| Date de publication | 2011 |
|---|
| Dans | |
|---|
| Langue | anglais |
|---|
| Publications évaluées par des pairs | Oui |
|---|
| Numéro NPARC | 21271447 |
|---|
| Exporter la notice | Exporter en format RIS |
|---|
| Signaler une correction | Signaler une correction (s'ouvre dans un nouvel onglet) |
|---|
| Identificateur de l’enregistrement | 7fec4d6f-f1b1-4a22-8725-88884f1cbf59 |
|---|
| Enregistrement créé | 2014-03-24 |
|---|
| Enregistrement modifié | 2020-04-21 |
|---|
