论文标题
资源约束项目调度问题具有净现值目标的近似算法
Approximation algorithm for resource-constrained project scheduling problems with net present value objective
论文作者
论文摘要
资源受限的项目调度问题（RCPSP）是许多应用程序中许多生产计划问题的核心。尽管自1960年代初以来就已经研究了这个问题，但大多数开发和测试实例仅限于少于300个工作的问题，这与现实生活中的成千上万的工作相去甚远。此外，在许多这些设置中，具有折扣成本（DC）的RCPSP至关重要，这些设置要求决策者评估完成任务的净现值，但是非线性成本功能使问题更难解决或分析。 在这项工作中，我们为RCPSP-DC提出了一种新颖的近似算法。我们的主要贡献是，通过使用几何增加的间隔，我们可以构建近似算法，跟踪优先限制，使用多个资源和时间要求。据我们所知，这是此问题的第一个近似算法。最后，通过对实际实例的实验分析，我们报告了方法的经验性能，这表明我们的技术使我们能够在合理的时间范围内解决相当大的地下采矿问题，并且差距比理论上计算的问题要小得多。
Resource-constrained project scheduling problems (RCPSP) are at the heart of many production planning problems across a plethora of applications. Although the problem has been studied since the early 1960s, most developments and test instances are limited to problems with less than 300 jobs, far from the thousands present in real-life scenarios. Furthermore, the RCPSP with discounted cost (DC) is critical in many of these settings, which require decision makers to evaluate the net present value of the finished tasks, but the non-linear cost function makes the problem harder to solve or analyze. In this work, we propose a novel approximation algorithm for the RCPSP-DC. Our main contribution is that, through the use of geometrically increasing intervals, we can construct an approximation algorithm, keeping track of precedence constraints, usage of multiple resources, and time requirements. To our knowledge, this is the first approximation algorithm for this problem. Finally, through experimental analysis over real instances, we report the empirical performance of our approach, showing that our technique allows us to solve sizeable underground mining problems within reasonable time frames and gaps much smaller than the theoretically computed ones.
