报告题目：Assessing the Robustness of Projects via Longest-Path Network Interdiction with Failure Groups

报告所属学科：管理科学与工程

报告人：吴菲（比利时鲁汶大学）

报告时间：2024年11月8日 15:00-16:30

报告地点：bat365中文官方网站702室

报告摘要：

本报告主题为阻断环境下具有失败组的项目调度问题。每个失败组内活动之间的相关干扰被建模为一个给定的不确定性集合。同时，问题构建过程整合了延迟活动组合选择决策，以避免过于保守的估计。研究了具有失败组的项目调度阻断问题（PSIP-FG）的各种特殊情况及其计算复杂性。对于连续阻断决策，我们证明了在每组仅包含一个活动且拦截成本不同的情况下，该问题具有NP难解性，这也暗示了具有多面体不确定性集的PSIP-FG问题具有NP难解性。我们还确定了具有多面体不确定性集的PSIP-FG问题的可处理情况。一个有趣的特殊情况是，每组中延迟的活动数量受到一个数字的限制，并且任何活动的替代处理时间是固定的，我们称之为预算不确定性。通过利用子集覆盖问题和3-SAT问题的归约，我们证明了即使失败组中的所有活动都可以延迟或每组只允许一个活动延迟，PSIP-FG问题也具有NP难解性。我们进一步研究了通用PSIP-FG问题的近似性，并获得了不可近似性界限。对于预算不确定性，我们开发了一种具有k近似保证的贪婪启发式算法。此外，我们还提出了两种局部搜索启发式算法，并提供了与精确解进行比较的实验结果。我们的结果表明，所提出的局部搜索启发式算法在计算上是有效的，特别是对于大型问题实例而言。

报告人简介：

吴菲，比利时鲁汶大学运筹学研究中心博士，研究方向包括组合优化、算法设计与分析、鲁棒优化，以及在调度中的应用。博士研究主题是 ”Policy Evaluation and Optimization for Scheduling under Uncertainty”。参与课题多项，如比利时弗兰德研究基金会（FWO）资助的课题“Optimization and analytics for stochastic and robust project scheduling”等。曾受邀参加波恩大学Hausdorff数学研究所举办的离散优化短期项目。