【作者】 邓林义；

【导师】 林焰； 陈明；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2008， 博士

【摘要】 资源受限的项目调度问题(Resource-Constrained Project Scheduling Problem,RCPSP)是运筹学领域的一个重要分支,它要求在满足项目时序约束和资源约束的条件下,安排所有任务的开始时间和结束时间,以达到工期最短、资源均衡、代价最小等目标。本文针对RCPSP的三个分支(经典的项目调度问题、任务可拆分项目调度问题以及多项目调度问题)进行了研究,取得了较好的结果。针对经典的资源受限的项目调度问题,本文提出了一种根据粒子适应值的变化动态调整惯性权重的粒子群算法,对标准粒子群算法(Particle Swarm Optimization,PSO)的惯性权重的调整策略进行改进。在此基础上给出了基于优先数编码的粒子群算法(PrirorityValue Based Particle Swarm Optimization,PVPSO)与基于优先规则编码的粒子群算法(Prirority Rule Based Particle Swarm Optimization,PRPSO)。其中PVPSO算法采用了一种启发式信息与随机信息相结合的初始化方法,比全部采用随机信息的初始化方法所选取的初始种群效果更好。PRPSO以粒子群算法为基础,搜索求解RCPSP问题最优优先规则组合。本文还提出了一种基于任务列表的混合粒子群算法(Permuation Based ParticleSwarm Optimization,PEPSO),该算法将遗传算法中的单点交叉引入到粒子的更新过程中,通过增加粒子的局部搜索技术帮助粒子跳出局部最优解。在PSPLIB测试集上的实验表明,与其他启发式算法相比,本文给出的算法PVPSO、PRPSO与PEPSO与本问题国内外其它同类算法相比,最短工期的平均偏差率均较低。针对允许通过任务拆分以缩短工期的资源受限的项目调度问题,本文采用PEPSO算法对Patterson问题集进行了测试,结果表明PEPSO算法能有效地缩短项目的偏差率。为进一步解决经典的任务不可拆分的项目调度问题,本文提出了一种基于虚拟任务拆分预测的PWiest方法,与优先规则、粒子群算法和蚁群算法等智能优化方法相结合,有效改进了算法的性能,PSPLIB集上的测试结果表明新算法能够进一步降低算法的偏差率。针对无耦合任务的多项目调度问题,本文提出了基于迭代的拓扑优化方法,根据项目网络结构的特点进行任务调度,在任务的调度过程中综合考虑任务的各种信息,如项目资源的影响,后续任务影响、关键路径任务优先以及最小空闲时间等优先规则。通过实例测试结果表明,该方法与其它启发式方法相比能得到更短的工期。对含有耦合任务的多项目调度问题,本文采用设计结构矩阵(Design Structure Matrix,DSM)表示含有耦合信息的任务之间的关系,给出了基于信息量对DSM中的耦合集进行解耦的方法。针对实际设计任务调度的特点,结合耦合信息的割裂方法和迭代拓扑优化方法,提出了求解含有耦合关系的多项目调度问题的拓扑优化方法。并将该方法应用到船舶设计任务调度系统中。更多还原

【Abstract】 Within the classical resource-constrained project scheduling problem(RCPSP),the activities of a project have to be scheduled such that the makespan(cost,etc.) of the project is minimized.RCPSP continues to be an active area of research attracting in recent years increasing interest from researchers and practitioners in the search for better solution procedures.The purpose of this paper is to introduce some new optimization algorithms to solve three kinds of RCPSP:classical RCPSP,preemptive RCPSP and resource-constrained multi-project scheduling problem(RCMPSP).To solve the classical RCPSP,we introduce a particle swarm optimization(PSO) with dynamic inertia weight to adjust the inertia weight with the fitness of particles.Three PSO procedures based on different solution representations are propsed—Priority Value Based Particle Swarm Optimization(PVPSO),Priority Rule Based Particle Swarm Optimization (PRPSO),and Permutation Based Particle Swarm Optimization(PEPSO).PVPSO employs a new initialization method in which the heuristic information is added to the classical randomized method to improve the performance of the algorithm.PRPSO searches the optimal combination of priority rules based on PSO.PEPSO adopts the one-point crossover technique into the updating of particles,and makes use of a local search to help the particle escape the local optimum.Numerical results obtained from the PSPLIB show that these PSOs yields better results than several heuristic procedures presented in the literatureThis paper provides the PSOs for the preemptive RCPSP.The experiments on Patterson show that the acitivity splitting can short the makespan of project.This paper develops a new wiest’s justification in which the activity splitting is applied to predict whether the schedule could be improved.The new Wiest’s justification with prediction(PWiest) was applied to improve the performance of algorithms,such as priority-rule heuristic method,particle swarm optimization and ant colony system and so on,for classic RCPSP,and the algorithms are approved with these experiments on PSPLIB.Finally,the paper studies resource-constrained multi-project scheduling problem (RCMPSP) in which each project has a priority.For RCMPSP without coupling sets,we propose a topological travel optimization algorithm in which various influence factors are considered(such as resources constraints,successors,critical-path-activity-first,etc.).For RCMPSP with coupling sets,we present an uncouple method to deal with the coupling sets in DSM,which is used to represent the coupling relations between activities.The algorithms have been applied to the development of the Ship Design Plan Management System of Dalian Heavy Industry Ship Yard.更多还原