1999 | OriginalPaper | Buchkapitel
Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis
verfasst von : Rainer Kolisch, Sönke Hartmann
Erschienen in: Project Scheduling
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The resource-constrained project scheduling problem (RCPSP) can be given as follows. A single project consists of a set J = {0,1,…, n, n +1} of activities which have to be processed. Fictitious activities 0 and n + 1 correspond to the “project start” and to the “project end”, respectively. The activities are interrelated by two kinds of constraints. First, precedence constraints force activity j not to be started before all its immediate predecessor activities comprised in the set P j have been finished. Second, performing the activities requires resources with limited capacities. We have k resource types, given by the set K = {1,…,K}. While being processed, activity j requires r j,k units of resource type k ∈ K during every period of its non-preemptable duration p j . Resource type k has a limited capacity of R k at any point in time. The parameters pj,r j,k , and R k are assumed to be deterministic; for the project start and end activities we have pj = 0 and r j,k = 0 for all k ∈ K. The objective of the RCPSP is to find precedence and resource feasible completion times for all activities such that the makespan of the project is minimized. Figure 7:1 gives an example of a project comprising n = 6 activities which have to be scheduled subject to K = 1 renewable resource type with a capacity of 4 units. A feasible schedule with an optimal makespan of 13 periods is represented in Figure 7:2.