A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles
A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles
复制标题
DOI：
10.1016/j.ejor.2017.03.006
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
M. Tritschler;A. Naber;R. Kolisch
中科院分区：
文献类型：
--
作者：
M. Tritschler;A. Naber;R. Kolisch
本文考虑了资源约束项目调度问题（RCPSP）的一种推广，即离散时间段内具有灵活资源配置的RCPSP问题（FRCPSP）。在FRCPSP中，对于每个活动，给定的资源需求是在处理活动的可变连续周期中分配的。由于资源分配可以在不同的时间段之间进行调整，因此活动的最终资源概要文件变得灵活。FRCPSP包括活动调度和确定每个活动的资源配置文件，从而确定持续时间，以最小化完工时间。我们提出了一个混合元启发式的FRCPSP。该方案将延迟调度和非贪婪资源分配的概念嵌入到遗传算法中。在可变邻域搜索中，通过在选定的活动之间转移资源量，进一步改进了最佳发现的调度。计算研究结果表明，在多达200个活动的问题实例上，所提出的方法产生的解明显优于三种基准方法。
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.