【作者】 贾艳；

【导师】 李世其；

【作者基本信息】 华中科技大学 ， 机械设计及理论， 2012， 博士

【摘要】 资源受限项目调度问题(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来构造在第一步给定活动执行模式下的调度规则,并结合仿真方法将其转换为具体的调度方案,最终获得使项目周期最短的活动模式组合及活动顺序。本文针对多种类型的资源受限项目调度问题,以大型激光装置项目的安装过程和实验过程为应用对象,通过调度过程建模与仿真优化,能够对项目调度过程进行直观地描述,对各种调度方案进行评估和比较并提供最优方案,对激光装置的安装流程以及实验流程起到指导和优化的作用,提高项目管理效率与质量。更多还原

【Abstract】 Resource-constrained project scheduling problem (RCPSP) is an NP-hard problem and concerned with production, construction and science projects, where scarce resources have to be allocated to dependent activities over time. The aim of RCPSP is to minimize the project duration with the precedence constraints and resource constraints. It is very important for the prediction of project duration and the arrangement of project activities. In this dissertation, the research content is as follows:(1) The uncertainty characteristic of the project lends itself very well to simulation applications, therefore a method of discrete-event simulation (DES) for resource-constrained project scheduling is proposed. The simulation model of RCPSP is composed of resource management model and project scheduling model, where the resource management model is used to manage and model diverse kinds of resources in the project, and the project scheduling model is built using an extended-directed-graph (EDG) which is an extension of activity-on-node (AON) network by adding the definition of resource so as to describe the precedence constraints and resource constraints of project. An improved simulation strategy based on the three-phase scanning is applied on the simulation model to generate scheduling alternatives which are satisfied with the precedence constraints and resource constraints.(2) The goal of simulation for project scheduling model is to choose the best alternative from among a set of competing alternatives. When stochastic behaviors such as random activity durations are considered in the simulation model, the corresponding output performances contain random variances. So, special statistical method is required to evaluate and compare the output performances of different scheduling alternatives. A multiple-comparison procedure called Procedure CY based on common random numbers is exploited to compare the random output performances obtained from the stochastic simulation model so as to select the scheduling alternative with minimal average project duration.(3) Simulation is a technique of experimental analysis and cannot generate optimal solutions automatically. Therefore, simulation-based optimization method integrated optimization algorithms with simulation is rapidly becoming an effective tool for many real-world problems. Gene expression programming (GEP) is proposed to automatically construct effective scheduling rule for RCPSP, which is the algebraic combination of project status and attributes of activity and is also a new representation form of solution compared with other optimal algorithms for RCPSP. In the simulation optimation method, GEP is used to search the optimal scheduling rules which can lead to the minimal project duration, and simulation is adopted to transform the scheduling rules into explicit scheduling alternatives for the evaluation of chromosomes.(4) In practice, some activities may be performed in one of several execution modes, and each mode is characterized by a known duration and given resource requirements. This type RCPSP with multiple activity modes is categorized as multi-mode resource-constrained project scheduling problem (MMRCPSP). A new hybrid meta-heuristic algorithm is proposed to solve the MMRCPSP in view of minimizing the project duration. The new algorithm splits the problem into a mode assignment step and a single mode project scheduling step. The mode assignment step is solved by particle swarm optimization (PSO) and returns a feasible mode combination to the project scheduling step, then the project scheduling step is solved using GEP to discover effective scheduling rules which are transformed into explicit scheduling alternatives using simulation, and the mode combination and scheduling rule that leads to the minimal project duration is the optimal solution.Aiming at several kinds of RCPSP, the assembly process and experiment process of a lager laser device are used as the applications. According to the modeling, simulation and optimization, the project scheduling model can be described intuitively, and the multiple scheduling alternatives can be evaluated and compared so as to provide the best alternative. The proposed method guides and optimizes the assembly process and experiment process of the laser system, and improves the efficiency and quality of project management.更多还原