基于多目标遗传算法的项目调度及其仿真研究

发布时间：2017-06-26 04:18

  本文关键词：基于多目标遗传算法的项目调度及其仿真研究，由笔耕文化传播整理发布。

【摘要】：项目管理至少可以追溯到4500年以前埃及金字塔以及1800年以前南美玛雅墓的建成，它们依靠的是最简单最原始的工具。后来慢慢发展到始于美国杜邦公司的CPM技术、始于美国海军开发“北极星导弹计划”的PERT技术。时至今日，大量关于项目管理的研究如雨后春笋般涌现：从原理、算法到系统（包括相关的软件），从简单到复杂，以充分帮助管理人员对各种项目进行计划、安排、监督和控制。 项目调度问题，是项目管理的一个重要研究领域，自20世纪60年代被提出之后，就引起了各行各界专家和学者们的广泛关注。随着现代化技术广泛应用于生产，具有较高自动化水平的生产系统，在使生产过程更加合理、高效运行的同时，也使得项目调度问题变得更加困难，其复杂性往往超出人脑的决策能力。 大多数项目调度问题是一类组合优化问题，计算复杂性理论已经证明大多数组合优化问题是NP-hard问题。传统的运筹学求解方法往往无法在多项式时间范围内寻求到这些NP-hard问题的最优解，随之人们开始尝试在多项式时间范围内求解的近似算法即启发式方法。 目前对复杂的项目调度问题的求解算法主要集中在对元启发式方法即智能优化方法的研究。智能优化算法是模拟某一自然现象或过程而建立起来的具有高度并行、自组织、自学习与自适应特征的适于复杂的高度非线性问题求解的算法。这类算法包括模拟煺火、禁忌搜索、粒子群算法、蚁群算法和进化计算等等。 理论和算法是为应用服务的，，建筑行业，作为项目管理应用的主要应用行业之一，也针对项目管理提出更多更高的要求。为了帮助建筑行业的施工单位更好的控制施工过程，增强项目的可预见性，避免不必要的损失，虚拟施工技术因此而产生。 鉴于以上的考虑，本文以多模式资源约束的项目调度及其应用研究为对象，以多目标遗传算法为手段展开研究。目前主要存在如下的问题： （1）尽管智能优化算法能同时处理一组解，以及很好的逼近非凸或不连续的最优前端面，然而对设计的参数进行动态调整和自适应改变依然是值得探讨的方向。 （2）多目标遗传算法的求解质量和求解效率还有待于提高。基于Pareto的多目标遗传算法在每一次迭代时都要构造Pareto最优解集，有必要寻找构造Pareto最优解集的最少时间复杂度。 （3）项目时间成本质量历来是项目管理的三大控制点，决定着项目的成败。然而更多的研究却集中在时间费用的优化，而缺少对质量因素的考虑。或者即使考虑了质量，而往往限定其中的一个或两个因素作为常量来考虑。因此建立合理的项目时间成本质量的多目标优化模型并加以解决是当务之急。 （4）在实际的项目调度过程中更多的存在着不确定性因素，这些不确定因素使得项目调度在本质上成为一个动态的过程。对不确定性因素的研究更加贴近实际，如何针对考虑不确定性因素的问题建立随机或者模糊网络模型并采用合适的机制去解决也是我们亟待思考的问题。 因此，本文结合这些问题，具体做了如下方面的研究工作： （1）在探讨组合优化问题、计算复杂性等相关原理的基础上，总结和比较了各种优化算法的优缺点，指出元启发式方法即智能优化算法是目前研究的趋势。在与实际应用相关的难解组合优化问题方面，智能优化方法使得在合理的时间范围内明显提高了找到高质量解的能力，尤其对于大型的或了解甚少的问题而言，智能优化算法的作用更加显著。 （2）结合组合优化理论，介绍了资源约束的项目调度的一般模型、规范分类以及基于不同求解方法的已有文献，指明多模式资源约束的项目调度是可行的研究方向。 （3）研究了多目标遗传算法及其基本概念：非支配集构造、种群保留机制以及遗传操作等等。对多目标遗传算法作了合理的改进，对分布系数采用多项式逼近获得交叉系数的概率分布，找出了交叉系数合适的改进方案，同时证明了种群大小的下限。 （4）分别以时间、成本和质量进行建模分析，指出了各个因素之间的相互关系及其研究思路，同时形成时间-成本-质量的多目标权衡数学模型。并用多目标遗传算法加以求解及其仿真实现，最后比较了不同方法的优劣，从收敛性和分布性方面证明了改进的方法的有效性。同时给出了基于不同偏好的建筑项目调度问题的决策者决策过程。 （5）对项目调度中涉及到的随机变量的分布、数字特征进行分析，指出了PERT网络分析法往往低估了项目完成时间，给项目的完成带来不必要的损失。研究了随机多目标决策问题的数学模型及其等价问题的处理，提出了随机条件下多目标多模式资源约束的项目调度建模、算法分析，并给出了仿真结果。 （6）基于虚拟建筑机理的分析，对虚拟原型（CVP）系统涉及的集成平台、开发环境、设计步骤等方面进行研究，说明项目调度及其优化理论在虚拟建筑中的应用，并以一个实例进行应用分析。 论文的主要创新点： （1）修正了NSGA-Ⅱ算法中原有的固定交叉系数，使得该交叉系数能够动态调整和自适应改变，并给出算法中种群大小的下限值并加以证明。 （2）将多目标遗传算法应用到考虑时间成本质量权衡问题的多目标多模式资源约束的项目调度问题中，给出了优化机制分析，并从收敛性和分布性方面证明方法的有效性。 （3）基于活动时间的随机变化引起活动成本和质量的动态改变，结合机会约束规划设计了概率转换机制和随机数模拟，以提高多目标遗传算法求解多目标多模式资源约束的随机项目调度问题的能力。 总体来说，就算法而言，本文以多目标遗传算法的NSGA-Ⅱ算法为着眼点，提出了两种修改策略，并通过实验证明了算法的有效性，充实了多目标优化算法理论。就项目调度而言，对项目的绩效评估综合考虑了质量因素，丰富了常规的时间费用分析理论；对项目调度的研究考虑了随机因素，弥补了不确定性网络分析理论。
【关键词】：项目调度 多目标 遗传算法 随机网络 机会约束编程 虚拟建筑
【学位授予单位】：上海交通大学
【学位级别】：博士
【学位授予年份】：2010
【分类号】：C93;F224
【目录】：

• 摘要5-8
• Abstract8-13
• 目录13-16
• 图目录16-19
• 表目录19-20
• 第一章 绪论20-27
• 1.1 研究背景及其意义20-23
• 1.1.1 研究背景20-22
• 1.1.2 研究意义22-23
• 1.2 研究内容和文章结构23-25
• 1.3 主要创新点25-27
• 第二章 资源约束的项目调度问题的算法基础27-45
• 2.1 组合优化问题27-28
• 2.2 计算复杂性28-31
• 2.3 启发式方法31-43
• 2.3.1 模拟煺火32-35
• 2.3.2 禁忌搜索35-37
• 2.3.3 蚁群算法37-39
• 2.3.4 进化计算39-43
• 2.4 其它43-45
• 第三章 资源约束的项目调度相关问题综述45-60
• 3.1 资源约束的项目调度问题描述45-48
• 3.2 资源约束的项目调度问题分类48-50
• 3.3 资源约束的项目调度相关文献50-59
• 3.3.1 基于确定性方法的资源约束的项目调度51-55
• 3.3.2 基于启发式算法的资源约束的项目调度55-59
• 3.4 本章小结59-60
• 第四章 多目标遗传算法研究60-77
• 4.1 多目标优化问题60-61
• 4.2 多目标遗传算法61-68
• 4.2.1 非支配集构造62-64
• 4.2.2 种群保留机制64-66
• 4.2.3 遗传操作66-67
• 4.2.4 NSGA-Ⅱ算法67-68
• 4.3 NSGA-Ⅱ算法的更新68-76
• 4.3.1 交叉系数的自适应改变68-73
• 4.3.2 种群规模的自适应改变73-76
• 4.4 本章小结76-77
• 第五章 多目标多模式资源约束的项目调度问题研究77-98
• 5.1 现有文献的不足77-78
• 5.2 多目标多模式资源约束的项目调度建模分析78-84
• 5.2.1 项目工期优化78-80
• 5.2.2 项目成本优化80-82
• 5.2.3 项目质量优化82-83
• 5.2.4 多目标优化模型的建立83-84
• 5.3 实例分析一84-92
• 5.3.1 算法设计与仿真结果85-89
• 5.3.2 算法的性能分析89-92
• 5.4 实例分析二92-97
• 5.5 本章小结97-98
• 第六章 多模式资源约束的随机项目调度问题研究98-119
• 6.1 随机活动持续时间98-105
• 6.1.1 β分布的广义性98-101
• 6.1.2 PRET网络分析法机理101-102
• 6.1.3 PRET网络分析法缺陷102-104
• 6.1.4 其它分布的随机活动时间104-105
• 6.2 随机变量的生成105-107
• 6.3 多模式资源约束的随机项目调度问题107-118
• 6.3.1 一般意义下的随机多目标模型分析107-108
• 6.3.2 现有文献的不足108-109
• 6.3.3 多模式资源约束的随机多目标项目调度数学模型109-111
• 6.3.4 实例分析111-118
• 6.4 本章小结118-119
• 第七章 项目调度-虚拟原型系统设计119-130
• 7.1 虚拟施工简介119-120
• 7.2 CVP系统设计120-126
• 7.2.1 集成平台120-121
• 7.2.2 开发环境121-122
• 7.2.3 设计步骤122-126
• 7.3 应用实例126-128
• 7.4 本章小结128-130
• 第八章 总结与展望130-133
• 8.1 论文的主要工作和结论130-131
• 8.2 存在的问题和进一步研究的展望131-133
• 参考文献133-150
• 附录一150-153
• 附录二153-154
• 附录三154-156
• 附录四156-158
• 附录五158-166
• 附录六166-168
• 博士期间发表论文和科研情况168-171
• 致谢171-172

【引证文献】

中国期刊全文数据库 前1条

1 邹汪平;;遗传算法在计算机加密解密技术中的应用[J];池州学院学报;2013年06期

  本文关键词：基于多目标遗传算法的项目调度及其仿真研究，由笔耕文化传播整理发布。

本文编号：484791