A Decomposition-Based Hybrid Algorithm for Large-Scale Project Portfolio Selection and Scheduling With Reaction to Changing Environments
提出一种结合进化算法全局搜索和精确求解器局部搜索的混合算法，用于解决大规模项目组合选择与调度问题，并能在环境变化时快速重新优化，相比精确求解器节省高达57%的计算时间。
The project portfolio selection and scheduling problem (PPSSP) aims to select and schedule a set of projects, known as a portfolio, to maximize their benefits while adhering to various constraints. However, addressing PPSSP in a reasonable time becomes increasingly challenging with a growing number of projects, especially in changing environments. This paper proposes a decomposition-based hybrid algorithm with evolutionary algorithm-based global search and exact solverbased local search to optimize large-scale PPSSP, and integrates a reactive approach to re-optimize PPSSP when unexpected changes occur. Specifically, a heuristic solution repair method is designed to accelerate the evolutionary global search, which is then expanded to repair the baseline schedule when dealing with changes. A problem-specific grouping method and a constrained sub-problem construction approach are developed for conducting the cooperative local search using the exact solver. Besides, a reactive approach is crafted to deal with changing circumstances by updating the problem structure, repairing the pre-scheduled solution, and re-optimizing the solutions. Experiments conducted on 28 large-scale PPSSPs and 28 changed PPSSPs have validated the superiority of the proposed hybrid algorithm in achieving competitive results in a shorter time, saving up to 57% computational time to achieve high-quality solutions when compared to the exact solver Gurobi.