论文部分内容阅读
资源受限项目调度问题(Resource-Constrained Project Scheduling Problem, RCPSP)属于NP-hard问题,广泛地存在于制造业、建筑工程和科学工程等项目中,它要求在满足项目时序约束和资源约束的条件下,合理地分配资源、安排活动,以达到某种优化目标如工期最短等,这对预测项目周期、指导项目进展都具有重要意义。因此研究RCPSP具有重要的理论和现实意义,本文主要研究内容如下:(1)实际项目的复杂性和随机性使其非常适用于仿真方法,于是本文首先提出了一种面向资源受限项目调度问题的离散事件仿真(Discrete-Event Simulation, DES)方法。该方法采用资源池管理项目中不同类型和数量的资源,同时对节点式活动网络图(Activity-on-Node, AON)进行扩展,通过加入资源定义形成扩展有向图(Extended-Directed Graph, EDG)来全面描述项目调度问题中的时序约束和资源约束。接着针对基于扩展有向图的项目调度模型,采用改进的三段扫描法对其进行仿真,生成满足时序和资源约束的项目调度方案。(2)项目调度仿真的目的是对多个可选调度方案进行实验并从中选出最优的方案,同时当仿真模型中的项目活动持续时间为随机数时,由仿真所产生的调度结果也是随机的,因此需要采用统计的方法对仿真结果进行分析与比较。本文采用基于公共随机数的多方案比较程序Procedure CY对仿真结果进行分析研究,并从多个调度方案的评估和比较中选出使项目期望完工时间最小的调度方案。(3)由于仿真实质上是一种试验分析方法,无法给出问题最优或近优解。因此将仿真技术和优化方法相结合为解决实际问题提供了有效的手段。本文基于基因表达式编程(Gene Expression Programming, GEP)算法针对具体问题构造新的调度规则,该调度规则由项目状态、活动属性及数学符号等元素编码而成,与求解RCPSP的其他优化算法相比,这是一种新的编码方式与求解方法。在仿真优化方法求解RCPSP中,GEP用来寻找使项目周期最短的调度规则,而仿真方法用来将GEP染色体所表示的调度规则解码为具体的项目调度方案,以用于染色体性能评估。(4)在实际项目中,同一活动可能存在多种执行模式,在每种执行模式下,活动都有相应的持续时间和资源需求,称为多模式资源受限项目调度问题(Multi-Mode Resource-Constrained Project Scheduling Problem, MMRCPSP)。本文采用一种混合元启发式算法求解MMRCPSP并使项目完工时间最短。该混合算法将MMRCPSP分为模式选择和单模式项目调度两步进行求解。其中在第一步中采用粒子群优化算法(Particle Swarm Optimization, PSO)来搜寻可行的活动模式组合,在第二步中采用GEP来构造在第一步给定活动执行模式下的调度规则,并结合仿真方法将其转换为具体的调度方案,最终获得使项目周期最短的活动模式组合及活动顺序。本文针对多种类型的资源受限项目调度问题,以大型激光装置项目的安装过程和实验过程为应用对象,通过调度过程建模与仿真优化,能够对项目调度过程进行直观地描述,对各种调度方案进行评估和比较并提供最优方案,对激光装置的安装流程以及实验流程起到指导和优化的作用,提高项目管理效率与质量。