论文部分内容阅读
资源受限项目调度问题(Resource-constrained Project Scheduling Problem,简称RCPSP)是项目管理实践的核心内容,其具有很强的工程应用背景,广泛存在于生产制造、工程管理、科学服务等领域,关于该问题的研究一直是学术界和工业界的研究热点。RCPSP要求在满足时序约束和资源约束的条件下,合理安排任务、分配资源,以达到工期最短、成本最小、资源均衡等优化目标。然而考虑到资源特征的复杂性,经典RCPSP模型并不适用于所有情况,因此,多技能资源受限项目调度问题(Multi-skill Resource-constrained Project Scheduling Problem,简称MS-RCPSP)被提出。在MS-RCPSP中,每个资源掌握几项不同的技能且对各技能的掌握程度不同,当被分配的资源满足任务所需的技能和熟练度时,该任务才能被完成。MS-RCPSP除经典RCPSP存在的大规模、强约束和多目标等复杂性之外,还需考虑技能和熟练度等问题。因此MS-RCPSP求解难度更高,更具挑战性。超启发式算法是新近提出的一类解决复杂优化问题的概念模型。该模型主要通过一种高层次启发式策略(High-level Heuristic,简称HLH)管理和操纵一系列低层次启发式(Low-level Heuristics,简称LLH)方法以实现在解空间中的寻优。作为一种有效的搜索方法,超启发式算法可以自动选择、组合或生成多个简单的LLH方法以解决复杂优化问题。本文以MS-RCPSP为研究目标,结合超启发式算法框架,从单目标和多目标两个角度对该问题进行优化。本文主要研究内容如下:(1)针对单目标MS-RCPSP,本文提出了一种遗传规划超启发式算法(Genetic Programming Hyper-heuristic,简称GP-HH)。该算法采用遗传规划(Genetic Programming,简称GP)算法作为HLH策略,灵活地管理启发式域上的LLH方法。此外,本文设计了包含十种启发式规则的LLH方法集合;不同于常规的双列编码方式,GP-HH采用单列任务向量对个体进行编码,并提出了与之对应的基于修复的左移解码策略以生成可行调度。为验证参数设置对算法性能的影响,本文采用实验设计法(Design-of-experiment,简称DOE)对参数进行分析,提出针对不同规模实例的参数组合。最后,采用智能多目标项目调度环境(intelligent Multi-objective Project Scheduling Environment,简称iMOPSE)数据集进行仿真实验以验证算法性能。实验结果表明,GP-HH在处理单目标MS-RCPSP时表现出较好的有效性和鲁棒性。(2)针对多目标MS-RCPSP,本文提出了一种基于分解的遗传规划超启发式算法(Decomposition Based Genetic Programming Hyper-heuristic,简称GP-HH/D)。该算法采用基于分解的思想将多目标MS-RCPSP分解为多个子问题以进行求解。为设计高效的参数组合,算法采用部分GP-HH参数以及与对比算法相同的种群规模和最大迭代次数。为验证算法性能,本依旧采用iMOPSE数据集进行仿真实验。结果表明,相比较现有算法,GP-HH/D在处理多目标MS-RCPSP时具有更好的寻优性能。本文采用超启发式算法来处理MS-RCPSP,该算法在问题模型的单目标及多目标优化过程中均表现出良好的性能。本文的创新点可归纳如下:(1)作为一种新近提出且高效的智能优化方法,超启发式算法已受到广泛关注,然而对于该算法框架的研究尚处于起步阶段,还没有学者将其应用于解决MS-RCPSP。本文针对MS-RCPSP,基于单目标和多目标优化视角,在超启发式算法框架下,从HLH策略和LLH方法两方面研究算法性能的提升思路,构建了高效超启发式算法模型,实现了针对MS-RCPSP的优化求解。这进一步拓展了超启发式算法的应用领域。(2)设计高效和通用的超启发式算法框架,还需对目标问题特征做更深入的研究,这方面的研究对于理解和设计高效超启发式算法框架具有重要意义。本文结合MS-RCPSP特征,一方面通过引入和设计高效启发式规则,构建新的LLH方法集合,提升算法领域搜索能力;另一方面采用GP作为HLH策略,动态地管理和组织一系列LLH方法。在此基础上,构建了GP-HH和GP-HH/D等超启发式算法,这进一步丰富了超启发式算法的理论方法。(3)目前有关超启发式算法的研究主要针对单目标优化问题,还没有扩展到多目标调度优化领域。本文将超启发式算法与基于分解的多目标优化思想结合,提出了一种GP-HH/D算法模型。该模型构建了包含十种启发式规则的LLH方法集合以及一种基于修复的左移解码策略。仿真实验结果表明,相比较其它典型优化算法,GP-HH/D在处理多目标MS-RCPSP时表现出更好的寻优性能。