A branch-and-bound algorithm for the unit-capacity resource constrained project scheduling problem with transfer times

DOI码：10.1016/j.cor.2022.106097

发表刊物：Computers & Operations Research

关键字：Project scheduling, Transfer times, Branch-and-bound, Exact algorithm, Dominance rules

摘要：本研究探讨涉及单位容量资源与转移时间的项目调度问题，并提出分支定界算法进行求解。该问题中每种资源具有唯一性，且活动间的资源转移时间不可忽略。目标在于找到包含活动开始时间向量和资源转移方案的可行解，以实现项目最大完工时间的最小化。我们设计的分支定界算法采用分支策略对每个节点所有可调度活动进行分支操作，并通过调度方法确定下一活动的最早可行开始时间（不早于已调度活动的最后开始时间）。基于分支策略与调度方法的结合，我们设计了五条有效支配规则以加速分支定界树的搜索过程。这些支配规则避免了不同节点产生相同解，并剪枝大量无效节点。在每个节点计算两个下界，同时采用基于优先级规则的启发式算法产生上界。通过在标准实例集上进行大量计算实验，结果表明：我们的精确算法性能显著优于使用CPLEX或CP Optimizer求解该问题现有数学模型的方法。

是否译文：否

发表时间：2023-03-01

收录刊物：SCI