项目组合选择调度问题及其算法优化

一方面，企业往往同时开展多个项目，而这些项目之间又共享部分资源；另一方面，企业需要考虑选择合适的项目（Liu et al.，2019；Mahdavi et al.，2019），选择合适的项目伙伴和项目资源（寿涌毅、宋淳江，2014），从而在符合企业战略的前提下充分利用有限资源，有效地并行开展多个项目，从而实现企业战略目标。但是，项目组合选择是一个复杂的决策问题，面临着项目评估不恰当、组合搭配不合理等诸多风险。设计科学有效的方法来选择最佳项目组合，并对这些项目进行合理的调度与资源分配，成为项目决策者迫切需要解决的问题。

作为典型的组合优化问题，项目组合选择问题已被证明是NP-hard问题（Doerner et al.，2006）。项目组合选择问题就是在有限的资源或其他约束条件下，从一组有限的备选项目中选择一个项目子集作为一个组合，使得该组合在满足约束条件的情况下获得最大的收益（Ghasemzadeh and Archer，2000；寿涌毅、姚伟建，2009）。近20年来，项目组合选择问题得到了广泛关注，学者们不断引入新的决策情境。Schmid（t1993）讨论了项目之间存在的三类交互作用，即收益交互、资源交互及产出交互。Stummer和Heidenberger（2003）进一步扩展了具有交互作用的项目数量。刘亚旭、汪应洛（2007）则分析了项目之间的不对称交互风险。赵静等（2011）分析了项目的组合风险。Gabriel等（2006）考虑了项目成本的不确定性。Yu等（2012）在项目组合选择过程中纳入了决策者偏好。针对项目组合选择问题，现有文献也提出了各种求解方法，既有定性的评价指标体系（杨敏等，2006），也有定量的优化算法，如模拟退火（杨颖等，2011）、邻域搜索（Gutjahr and Froeschl，2013）、蚁群优化（Doerner et al.，2004；Doerner et al.，2006）、遗传算法（Yu et al.，2012；杜先进等，2008；赵静等，2011）、演化算法（Medaglia et al.，2007）。

在项目组合选择研究中，通常会割裂项目选择与项目调度之间的内在联系。传统的项目组合选择问题通常假定项目的进度计划是固定不变的，而只考虑项目组合选择对最终收益的影响。然而，项目调度能够调整任务的起止时间，往往会对项目组合选择的可行域与目标函数值造成影响（Coffin and Taylor，1996）。尤其是在资源受限的情况下，决策者可以通过重新调度项目任务实现资源的有效配置从而优化项目组合收益（Shou et al.，2014）。(www.xing528.com)

然而，项目调度本身就是一个NP-hard问题，将项目调度引入项目组合选择问题将显著增加问题的复杂度和求解难度。因此，这类问题适合采用启发式或元启发式等非精确方法进行求解（Chen and Askin，2009；Gutjahr et al.，2008）。Liu和Wang（2011）考虑了项目选择过程中的调度问题，但是其调度单元是单个项目，而非项目中的各个任务。任嵘嵘、祝丹梅（2009）将每个项目分为三个阶段，然后对中选项目的各个阶段进行调度优化。少数文献则已经将调度单元深入到项目任务层面。例如，Gutjahr等（2008）将项目任务调度、人员分配作为子问题与项目组合选择一起求解，采用贪婪算法处理项目调度和人员分配，采用蚁群优化算法处理项目组合选择。针对项目组合选择及调度问题所开发的隐枚举法（Chen and Askin，2009）和多单位组合拍卖算法（Shou and Huang，2010）都有效提高了项目组合选择及调度问题的求解效率。徐汉川等（2010）在对企业项目伙伴选择模型进行研究时，综合考虑了项目优先关系、子任务加工时间和工期等关键约束，并将项目调度算法嵌入到禁忌搜索方案中对模型进行求解，优化求解速度和最优率。