A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles

We consider a generalization of the resource-constrained project scheduling problem (RCPSP), namely the RCPSP with flexible resource profiles (FRCPSP) in discrete time periods. In the FRCPSP, for each activity the given resource requirement is allocated in a variable number of contiguous periods in which the activity is processed. As the resource allocation can be adjusted between time periods, the resulting resource profile of the activity becomes flexible. The FRCPSP consists of scheduling activities and determining for each activity a resource profile and, thus, a duration in order to minimize the makespan. We propose a Hybrid Metaheuristic for the FRCPSP. It contains the Flexible Resource Profile Parallel Schedule Generation Scheme which employs the concepts of delayed scheduling and non-greedy resource allocation, embedded in a genetic algorithm. The best-found schedules are further improved in a variable neighborhood search by transferring resource quantities between selected activities. The results of a computational study demonstrate that the proposed method yields significantly better solutions than three benchmark methods on problem instances with up to 200 activities.