基于网络图技术的排产算法评价及系统开发

论文摘要

网络计划的作用是协调工程中各细节的关系,保证工程顺利进行,其核心是提供一种描述计划任务中各项活动之间(工艺或组织)逻辑关系的图解模型——网络图。目前,在网络图自动绘制方面,仍然存在网络图逻辑不清、信息不丰富等不足。在网络图的复杂性度量方面,由于系统的异构性和复杂性,还没有一种通用的评价方法,只能针对特定系统提出具体的测度手段。由于计划排产用到的启发式算法的排产效果因网络进度问题特征不同而不同,评价常用启发式算法的排产效果也成了亟待解决的问题。针对上述问题,本文提出了一种新的单代号网络图布图算法。该算法将深度优先与广度优先算法相结合,实现了二维平面上任务节点和箭线的拓扑结构初步确定,采用逻辑分类法进行网络图整体调整,最终实现逻辑清晰,少交叉网络图的自动生成,并通过工程实例进行了验证。在考虑了网络图节点数量、源点到汇点的实际路径条数等因素的前提下,提出了综合结构复杂度(TSC)的概念,用于反映网络图拓扑结构的复杂性,在此基础上,考虑网络计划中提供的设备种类、数量、节点工作时间等约束因素,提出了包含可选设备的网络图复杂度(ICECN)计算模型,较好地反映了实际工程中网络图的复杂性。在基于资源受限网络图排产方面,目前已经积累了大量的排产算法,包括理论上的最优化算法和实际应用中的大量启发式排产调度算法。使用启发式排产调度算法能得到在一定程度上满足实际问题的生产计划,并且其计算简单,可操作性强,目前已被广泛应用。但由于资源约束网络计划问题的复杂性,不同启发式排产调度算法处理同一网络计划问题的效果和同一启发式排产调度算法处理不同网络计划问题的效果却相差很大。因此,评价和分析这些启发式排产调度算法就成了网络计划排产的前提。本文基于前人成果和已建立的复杂性度量模型基础上,建立了排产调度算法的评价指标,并通过评价多种排产调度算法对资源受限网络图排产的效果和规律,实现排产调度算法的合理选择。论文最后用哈电机2006年戈兰滩5号水轮发电机组网络计划数据对系统功能进行了测试,测试结果表明了算法和系统的正确性和实用性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题来源及研究目的和意义
• 1.1.1 课题来源
• 1.1.2 课题研究的目的和意义
• 1.2 国内外研究现状及分析
• 1.2.1 网络图自动生成技术发展综述
• 1.2.2 网络图复杂性度量发展综述
• 1.2.3 启发式算法评价综述
• 1.3 本文主要研究内容
• 第2章 网络图自动生成技术与系统研究
• 2.1 引言
• 2.2 网络图布图算法
• 2.2.1 算法数据结构
• 2.2.2 布点算法步骤
• 2.3 实例
• 2.4 本章小结
• 第3章 网络计划中网络图的复杂性度量
• 3.1 引言
• 3.2 复杂度建模
• 3.2.1 基本概念
• 3.2.2 拓扑结构网络图复杂度（TSC）
• 3.2.3 设备约束网络图复杂度（ICECN）
• 3.2.4 TSC和ICECN度量性能实验
• 3.3 网络图随机生成器（RGSLN）
• 3.3.1 网络图随机生成器工作过程
• 3.3.2 网络图随机生成器测试
• 3.4 本章小结
• 第4章 启发式排产调度算法的评价
• 4.1 引言
• 4.2 启发式算法评价指标的建立
• 4.3 启发式算法回归方程的建立
• 4.3.1 网络计划模型
• 4.3.2 实验样本建立
• 4.3.3 回归分析过程
• 4.4 启发式算法分析与评价实例
• 4.5 本章小结
• 第5章 系统的实现与应用
• 5.1 系统的体系结构与功能模块
• 5.1.1 网络图自动生成模块
• 5.1.2 网络图复杂性度量和工期预测模块
• 5.1.3 基于启发式算法的网络计划排产
• 5.2 应用案例
• 5.2.1 网络图的建立
• 5.2.2 网络图自动生成
• 5.2.3 网络图复杂性度量与工期预测
• 5.2.4 基于网络图的排产实例
• 5.3 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢