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

《基于网络图技术的排产算法评价及系统开发》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈尔滨工业大学工学硕士学位论文第1章绪论1.1课题来源及研究目的和意义1.1.1课题来源本文研究内容是哈尔滨电机厂集团有限公司项目“面向大设备平衡的生产计划技术与系统开发”的组成部分。1.1.2课题研究的目的和意义网络计划的作用是协调工程中各环节的关系，保证工程顺利进行，其核心是提供一种描述计划任务中各项活动之间（工艺或组织）逻辑关系的图解模型――网络图。与传统横道图（甘特图）计划方法相比，网络计划利用图解模型和相关算法，可把握项目计划的全局，分析其规律，以便揭示方要矛盾，抓住关键，并采用科学的方法动态

2、地调整计划安排，找出最优的计划方案。在网[1~6]络图自动绘制方面，虽取得丰硕成果PP，但仍然存在网络图逻辑不清、信息不丰富等不足。复杂性科学（ScienceofComplexity）是一种新兴的边缘、交叉[7~11]学科PP。由于所评价系统的异构性和复杂性，目前在复杂性度量方面还没有[12,13]一种通用方法，只能针对具体系统提出具体测度手段PP。在基于资源受限网络图的排产方面，目前主流的方法是启发式排产调度算法，而在启发式排产调度算法的选择方面还没有一种有效的方法。针对上述问题，本文针对网络图自动生

3、成技术、网络图复杂性度量、排产调度算法等网络计划制定中的关键技术进行深入的研究，并结合哈电机的工程实例，实现网络图布点算法、网络图复杂性度量方法和网络图排产调度算法合理性选择的应用验证。可见，本文的研究对企业网络计划的制定有一定的技术价值和实际应用价值。1.2国内外研究现状及分析1.2.1网络图自动生成技术发展综述在网络计划技术中，网络图的绘制是十分重要的一环，网络计划通过网络-1-哈尔滨工业大学工学硕士学位论文图才能直观地表现出来。经过长期发展，绘制网络图已经达到了自动化水平。目前，在双代号网络图自动

4、生成算法上主要有两种趋势：一种趋势是以毕义明[14]提出的深度优先自动绘图算法PP类：该算法的核心思想是按路线来画结点，将其分为不同的层，再绘路径。算法先画出所有关键路径，确定关键节点的坐标，然后对未确定坐标的节点，寻找由关键结点出发再回到关键节点的最短路径，并将该路径上所有的节点设置到同一层，按不同的路线分类不同的层次进行绘制，直到所有节点均确定坐标。但是，该算法在布图时进行了节点编号重[15]排，容易使操作者混淆。另一种趋势是以张彩庆为代表的广度优先算法PP类：其特点是先找出无紧前工序的工序并将其开

5、始节点赋1，其后面节点赋2、3…记下最大的节点编号（IP），遍历紧后表，将其紧后工序开始节点赋开始工序结束节点号，任取M工序，若其开始节点已赋值，找出紧后工序X（可能不止一个紧后工序），若X开始结点已赋值，则将其赋给M的结束结点，若X工序开始节点未赋值，则M结束节点和X工序开始节点同时赋值IP+1，直到所有节点均赋值。此算法采用了邻接矩阵，算法相对简洁，然而布图时关键路径不清楚，关键工序不能明确表达。在自动布图系统方面，比较典型的代表是美国的P3系统，西北工业大学[16]的JFWF-1系统PP。但P3系

6、统在网络图绘制好后，节点是按顺序排列而不是节点之间的逻辑关系，使用户不能一目了然；西北工业大学的JFWF-1系统在绘图上采用分层布点，并将每个节点分布在不同的列上，节点虽然分级，但每个节点占一列，不能很好地理顺节点之间的逻辑关系。上述算法和系统都基于双代号网络图，其算法都十分复杂，而且目前比较多的做法是人工输入单代号网络图信息，再由计算机自动转化为双代号网络图，其过程复杂且转化前后网络图形式相差很大，容易使操作者混淆工序关系。而在自动生成单代号网络图上，人们却很少研究，单代号网络图以节点代表工序，表达直

7、观，而且与输入信息表达相差不大，不容易使操作者混淆，并且网络数据生成简单，绘图迅速，人工干预少，免去了向双代号网络图转化的过程，节省人力和计算机资源。1.2.2网络图复杂性度量发展综述网络计划中网络图的复杂性是通过紧前、紧后关系所表现出来的约束复杂程度，它是反映网络图特征的一个重要指标。关于网络图约束的复杂性度量方法在有关的进度计划研究文献中已经提出,但是仍然存在着网络计划约束的复杂性能否精确地量化的争论。在网络图结构复杂性度量方面，国内外已有大量学者进行了长期研究，Pascoe于1966年提出了（Co

8、efficientofNetworkComplexity—CNC）的概念，-2-哈尔滨工业大学工学硕士学位论文[17]并提出了具体计算模型PP，Davis于1975年改进了CNC模型并使用于单代号网[18]络图的评价中PP，比较典型的成果有Badiru.A.B提出的一个综合性的复杂性指标并用它来衡量网络图的复杂性，但是用一个指标反映网络约束的复杂程度和网络资源约束的复杂关系难以应用到工程实现中。西北工业大学白思俊提出[19]了网络复杂性系数