A tree search heuristic for the resource constrained project scheduling problem with transfer times

影响因子：1.3

DOI码：10.1016/j.ejor.2022.05.014

发表刊物：European Journal of Operational Research

关键字：Project scheduling, Transfer times, Schedule generation scheme, Lower bound, Tree search

摘要：在本研究中，我们探讨了带资源转移时间的资源受限项目调度问题，其中活动间的资源转移需要耗费特定时间。针对该问题，我们提出了改进的串行调度生成方案、新的下界计算方法以及树搜索启发式算法。该改进型串行调度生成方案通过迭代调度活动，采用打破现有资源流的方式，并高效确定最早开始时间。新下界方法由关键容量下界改进而来，额外考虑了资源转移时间因素。树搜索启发式算法利用改进的串行调度生成方案安排活动的最早开始时间，并采用新下界对搜索树中无潜力的节点进行剪枝。算法中引入了多种优先级规则，用于分支过程中选择下一个活动，同时也应用于贪婪算法中以计算节点评估的上界。在基准实例上的计算实验表明：相较于现有文献中的串行调度生成方案，改进方案平均减少91.30%的计算时间；新下界方法优于已知的改进型关键路径下界，平均提升幅度达7.95%；树搜索启发式算法的性能优于现有三种针对该问题的算法。

论文类型：SCI

是否译文：否

发表时间：2023-02-01

收录刊物：SCI