（电力电子与电力传动专业论文）机车检修中网络计划技术的优化研究.pdf

西南交通大学硕士研究生学位论文第1i 页 a b s tr a c t u n d e rt h eg u i d a n c eo ft h e l e a p i n gd e v e l o p m e n tt h e o r y , c h i n a sr a i l w a y m a n u f a c t u r i n gi n d u s t r yi sg o i n gt h r o u g hap r o f o u n dt r a n s f o r m a t i o n t h u s ，i tr a i s e d n e w e r & h i g h e rr e q u i r e m e n t so ft h em a i n t e n a n c es y s t e mo fl o c o m o t i v ed e p a r t m e n t s t h ec o n s t r u c t i o no fw h i c hi ss oc r i t i c a lf o r t h e l e a p i n gd e v e l o p m e n to ft h e l o c o m o t i v et e c h n i c a le q u i p m e n t m a n a g e m e n t a n di tw i l lp l a ya ni m p o r t a n tp a r t i ng u a r a n t e e i n gt h er a i l w a yt r a n s p o r t a t i o ns a f e t y , i m p r o v i n gt h eo v e r a l lr a i l w a y e c o n o m i cb e n e f i t s ，a n dp r o v i d i n gh i 曲q u a l i t ys e r v i c et ot h ec u s t o m e r h o w e v e r , m o s to ft h el o c o m o t i v em a i n t e n a n c em e t h o d sw e r er e l a t i v e l yb a c k w a r d s u c ha sl o w l e v e lo fc u r r e n ti n t e l l i g e n t & a u t o m a t i o no ft h e i n s p e c t i o n t e s te q u i p m e n t s u n s c i e n t i f i cm a n a g e m e n td u r i n gt h em a i n t e n a n c ep r o c e s s ，l i t t l e c o n t r o lo ft h e l o c o m o t i v e m a i n t e n a n c e q u a l i t y , a n dc o l l e c tp l e n t yo fl o c o m o t i v ei n f o r m a t i o n m a n u a l l ya n ds oo n b a s e do nt h ea b o v er e a s o n ，t h eo p e r a t i o na n dm a n a g e m e n to f c h i n a 引o c o m o t i v em a i n t e n a n c es y s t e mi sb e h i n dw o r l ds t a n d a r d i na d d i t i o n d u e t os p e c i a lt r a n s p o r t a t i o nm o d e & t r a f f i cv o l u m ei nc h i n a t h e r ei s r e l a t i v e l yl o w e r l e v e lo nm a n a g e m e n to fc h i n a s1 0 c o m o t i v em a i n t e n a n c es y s t e m a p p l i c a t i o no fn e t w o r kp l a n n i n gi nl o c o m o t i v em a i n t e n a n c es y s t e mw i l lb et h e b r e a k t h r o u g ht ou p g r a d et h ee n t e r p r i s e & d e v e l o pt h er a i l w a y a n di tw i l lh a v e i m p o r t a n t e f f e c t s i n i m p r o v i n gc o r p o r a t i o nm a n a g e m e n t ，t r a n s f o r m i n gt h e m a n a g e m e n t ss y s t e m ，r e d u c i n gc o s t & e n h a n c i n gm a r k e tc o m p e t i t i v e n e s se t c t h ep a p e rd i s c u s s e dt h eo p t i m i z a t i o nd e s i g no ft h em a i n t e n a n c es y s t e mb yt h e n e t w o r kp l a n n i n g ，e s p e c i a l l yi n a n a l y z i n g t h e r e q u i r e m e n to ft h el o c o m o t i v e m a i n t e n a n c es y s t e md e v e l o p m e n t ，g i v i n gad e t a i l d e s c r i p t i o no nt h em a n a g e m e n t s y s t e m & p r o c e s so p t i m i z a t i o n a n dd o i n gt h er e s e a r c ho nt h en cl o c o m o t i v e c a p a c l t ye x p a n s i o nr e v a m p i n ge n g i n e e r i n g t h es t u d ys h o w e dt h ea p p l i c a t i o no ft h e n e t w o r kp l a n n i n gt e c h n o l o g yw i l ls h o r t e nt h em a i n t e n a n c ep e r i o di na l a r g ee x t e n d ， i m p r o v et h em a i n t e n a n c ee f f e c t i v e n e s s ，s a v i n gt h er e s o u r c ei n v e s t m e n t ，a n db e i n g m o r ei n s t r u c t i v et od e s i g n k e yw o r d s ：l o c o m o t i v ed e p o t ；l o c o m o t i v em a i n t e n a n c e ：n e t w o r kp l a n n i n g t e c h n o l o g y ；c r i t i c a lp a t hm e t h o d 西南交通大学四南父通大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密b ，一使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名： 日期： 扬嘞 瑚7 口i t 吗 艚柳繇前训 日期：争新弓 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本文工作的创新点是：运用网络计划技术，对机务段的检修工作量进行研 究设计，此法不同于一般的检修工作量计算方法。在通过对机车走行公里和平 均走行速度、配属机车对数等因素计算后，再对检修工作台位进行网络计划优 化，创造性地对设计工作进行了研究，为具体工程项目实施提供依据，使其达 到最优利用资源的目的。本文还对最新的网络计划算法进行研究，使其融合到 设计工作中，达到理论和实际相结合的目的。 学位论文作者签名：功奶踢 日期： m 7 ，口“口 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景与意义 第1 章绪论 在“十五期间，铁道部制定的铁路科技发展“十五”计划明确指出 要实现铁路跨越式的发展，其中就包括了铁路信息化跨越式发展，目标是要实 现“铁路现代化、机车控制网络化、机车运用检修管理信息化 。 铁路信息化规划是从全面、系统的战略高度，抓住国内外信息时代发展变 化的脉络，跳出传统封闭的意识；规范、协调、综合、集成目前铁路各信息系 统的建设状况，指导未来铁路信息系统的发展，以达到有序规划建设、节省投 资、充分利用已有资源、用信息技术改造传统铁路运输产业和提高运输经济效 益的目的。 2 0 0 7 年，铁道部又制定了铁路信息化发展建设的总体目标( 远景目标) ： 形成具有国际水平的铁路信息化基础通信平台，实现各部门、系统间的信息数 据资源共享、互连互通；建成车、机、工、电、辆各部门调度控制、安全生产、 运输指挥的现代化保障体系。为铁路运输各部门提供所需要的各种管理信息资 源和强有力的决策支持；通过现代客货营销手段和电子商务等运用，带动铁路 运输经济发展，大幅度提高运输效益；建立与信息化相适应的健全的管理机制。 铁路机务部门主管着全路的机车、设备、人力等资源的调配，是运输生产 的重要保障。所以，机务信息化是实现铁路跨越式发展的重要举措之一。 随着铁路信息化建设的不断深入，对机务段的检修、整备及监控等各个环 节的工作也提出了更高的要求。目前铁路机务段面临三大突出问题，即网络化、 知识化和服务化，这也导致了对机务段的组织结构和功能的非线性、时变性、 突发性和不平衡，难以用传统的运行模式和控制策略来驾驭。机车检修、运用、 整备及监控信息的表征、存储、处理、传递和加工的深刻变化，使机务段由传 统的能量驱动型逐步转向为信息驱动型。随着网络化、信息化的飞速发展，数 字技术也在快速发展和广泛应用，新型机务段必将以数字化、网络化等为基本 特征。数字化机务段的提出是当代社会经济和科学技术发展的必然结果，是改 造传统机务段和提高高新技术产业品位的必由之路，肯定会成为未来机务段发 展的重要特征。 西南交通大学硕士研究生学位论文第2 页 目前，数字化机务段的概念才刚刚被提出，还没有形成有效的、系统的数 字化机务段体系，所以，铁道部统计中心、铁科所、铁路局、机车研究所以及 一些机车设备公司正在开展机务信息化系统的研究。 铁路机务检修工作是机务工作中的一项重要内容。在过去几年中，检修作 业由机务部门的一个车间负责，很少有人对检修作业进行深入研究。但近几年 来，随着基于“长交路、集中修”理念的机务布局的发展、机车微机控制的发 展以及新技术、新设备的使用，使得机务段管辖范围增大，机务检修规模逐渐 扩大，检修工作也面临着新的挑战。建立现代化的机车检修质量管理控制系统， 不仅可以适应新形势的发展，有效克服现行检修质量管理体系中的诸多弊端， 提高检修质量，压缩检修时间和成本，对检修作业过程、作业质量实行有效控 制，而且可以对物料消耗，甚至对管理者的管理行为、绩效进行有效控制和评 价。因此，如何将机车检修管理系统提高一个层次，是铁道设计院必须花时间 研究的一项新课题。 近年来，在跨越式发展的思想指导下，我国铁路正进行着深刻的变革，同 时，对机务检修部门也提出了更新、更高的要求，因此，机务检修部门的建设 是实现机务技术装备和管理水平跨越式发展的关键，它对保障铁路运输安全、 提高铁路整体效益、向铁路用户提供优质服务起到重要的作用。同时，它也是 带动企业升级和铁路发展各项工作创新的突破口，对于提高铁路企业管理水平、 转换经营机制、加快技术进步、有效降低成本、增强市场竞争力等方面都具有 重要的意义。 1 2 铁路机务及机务检修的特点 在铁路局的车、机、工、辆、电等部门中，铁路机务段处于十分重要的地 位。从组织机构来看，机务段一般由运用整备车间、检修车间、设备车间、材 料车间、救援车间以及人、财、计等机关科室组成，编制齐全；从工作性质来 看，机务段主要是提供铁路运输的牵引动力；从工作区域来看，机务段的牵引 管辖范围一般为几百公里以上，线长点多；从工作质量来看，机务段具有半军 事化特点，规章制度严格，技术要求高；从运输安全角度来看，机务段是保证 铁路运输安全最为重要的关键点之一，机务的乘务作业和机车的检修作业直接 关系到铁路运输生产的正常运行。 下面对机务段和派驻机车折返段进行简单介绍。 西南交通大学硕士研究生学位论文第3 页 1 2 1 机务段 机务段按其工作性质不同，可分为货机段、客机段及客货机混合段。根据 其检修任务的不同，又分为中修机务段和小修机务段。 机务段实行段长负责制、段内各级领导负责制、专职人员负责制及工人岗 位责任制。 机务段的机车管理工作，主要分属于机车运用和机车检修两大车间。机车 运用车间负责组织乘务员工作、机车的运用及机车整备作业，并根据计划安排 检修机车的扣车和组织机车中间技术检查作业或进行状态修各级检查作业等。 运用车间的地勤行修组也有少量的检修工人，以处理机车临修故障及对机车进 行日常维护工作。 为了及时处理行车事故，起复机车车辆，及时开通线路，恢复行车，在机 务段一般设有救援列车。沿线如果发生行车事故，救援列车可随时出发进行事 故处理，以便迅速恢复正常行车。 机务段内设置救援列车办公室，专门负责救援列车的维护使用及救援列车 人员的组织管理工作。 所以，铁路机务段具有以下特点： ( 1 ) 配属有一定数量的干线机车和调车机车。 ( 2 ) 有完整的机车运转整备设备和一定能力的机车检修设备。 ( 3 ) 担当指定区段内的列车牵引作业和编组站、区段站及沿线较大中间 站的调车作业。 ( 4 ) 负责机车的运转整备作业和日常保养工作，担当一定的机车检修任 务。 1 2 2 派驻机车折返段 派驻机车折返段的组织成员和业务工作均属机务段领导，派驻有一定数量 的机车担当机车交路和调车作业，根据需要设置全部或部分运转整备设施，可 设置机车中检及部分临修设备。机车的轮定修由机务段承担。 段所的规模和能力是根据其所承担的机车修程和检修工作量来确定的。所 以检修设备设计的好坏，在一定程度上会直接影响机车检修质量的高低、检修 停时的长短和基建投资的效果。因此在设计工作中一定要切实贯彻专业化、集 中化的方针，加强研究调查，务必使检修设备设计得切合实际，向着加速实现 检修设备现代化的方向努力。 西南交通大学硕士研究生学位论文第4 页 在进行机车检修设备设计时，应遵循以下原则： ( 1 ) 机务段设计年度分近期和远期，近期为正式交付运营后五年，远期为 正式交付运营后十年以上。那些随着生产发展的需要可逐步扩建和改建的建筑 物和设备应按近期设计，并考虑预留发展；而一次建成后不易扩建和改建的建 筑物和设备应按远期设计。 ( 2 ) 在统一规划的基础上，调整段修的生产方案，使分工合理，实现集中 修，提高专业化程度。组织专业化生产，是现代工业发展的必然趋势，在搞好 机车配件标准化、系列化、通用化的条件下推广大部件互换修工艺，以达到提 高修车质量和速度的目的。 ( 3 ) 在旧线电化或增建新线时，对改建、扩建的机务段，应当最大限度地 利用原有建筑物、设备和各种设施，减少不必要的废弃和拆迁工程，以节约投 资。 ( 4 ) 采用设计标准时，要分清主次，区别对待。对生产工艺、主要设备和 今后不容易增建和改建的主题工程，必须考虑今后的发展；对辅助生产工程， 要在保证发挥主体工程生产能力的前提下，力求节约。 ( 5 ) 检修设备的设计和选用，应以机务段修范围为标准。在不增加重大设 备或投资的情况下，可以适当提高对机车检修的能力。 ( 6 ) 设计中应积极而慎重地采用新技术、新工艺、新材料、新设备，在一 些有条件的车间有计划、有重点地提高生产过程的机械化和自动化水平，以利 于提高劳动生产率。 1 3 网络计划技术的国内外发展情况 1 3 1 国外发展情况 网络计划技术就是利用网络图表达计划任务的进度安排及其各项作业之间 的相互关系，进而对网络进行分析并计算网络时间值，确定关键工序和关键路 线，并运用一定的技术组织措施对项目进行优化的方案。其中关键路线是完成 各个工序所需时间最长的路线，关键路线法的目标是缩短作业时间，降低成本， 实现资源的优化配置。当前，世界上工业发达国家都非常重视现代管理科学， 网络计划技术己被许多国家公认为目前最行之有效的管理方法。国外多年的实 践证明，应用网络计划技术组织与管理生产一般能缩短工期2 0 左右，降低成 本1 0 左右。 美国是网络计划技术的发源地，美国的泰迪建筑公司在4 7 个建筑项目中应 西南交通大学硕士研究生学位论文第5 页 用此法，平均节省时间2 2 ，节约资金1 5 。美国政府于1 9 6 2 年规定，凡与政 府签订合同的企业，都必须采用网络计划技术，以保证工程进度和质量。1 9 7 4 年麻省理工学院调查指出：“绝大部分美国公司采用网络计划编制施工计划”。 目前，美国基本上实现了机画、计算、机编、机调，实现了计划工作自动化。 日本、原苏联、德国、英国也普遍在工程中应用了网络计划技术，并把这 一技术应用在建筑工程的全过程管理之中。t l 】 1 3 2 国内发展情况 我国从6 0 年代中期，在著名数学家华罗庚教授的指导下，开始在国民经济 各部门试点应用网络计划技术，当时为结合我国国情，并根据“统筹兼顾、全 面安排”的指导思想，曾将这种方法命名为“统筹方法”瞳1 。此后，在工农业 生产实践中有成效地推广起来。近几年，随着科技的发展和进步，网络计划技 术的应用也日趋得到工程管理人员的重视，且已取得可观的经济效益。如上海 宝钢炼铁厂1 号高炉土建工程施工中，应用网络计划技术，缩短工期2 1 ，降 低成本9 8 。广州白天鹅宾馆在建设中，运用网络计划技术，工期比与外商签 订的合同提前四个半月，仅投资利息就节约1 0 0 0 万港元。 3 0 多年来，网络计划技术作为一门现代管理技术已逐渐被各级领导和广大 科技人员所重视。在实践应用过程中，科研、教学和生产领域通力合作，在网 络计划技术理论研究、网络模式、实用方法以及计算机算法和绘制网络图上， 有了许多新的发现和创新。从5 0 年代的一般网络计划技术( c p m p e r t ) 扩展 到搭接网络计划技术、流水网络计划技术并增加到强制时限，较好地解决了工 序作业的搭接和工种作业的流水施工。后来又出现了能够反映有多种随机因素 并具备适用重复运行和其有反馈环节的随机网络计划技术( g e r t ) 以及风险 网络计划技术( v e l 玎) 和循环作业网络( c y c l o n r ) 。各种不同功能的网络 的出现，极大地丰富了网络计划技术的内涵。目前，各种牌号的网络计划方法 在国内外多达百种。在实践应用中针对标准设计应用了通用( 标准) 网络图， 在管理层次上使用了分级网络、群体网络、多目标网络，在企业计划管理中使 用了年、季、月度网络计划和旬作业网络。针对双代号易出现逻辑差错，提出 了断路法和前锋线等方法，在使用计算机上不仅研制出大批网络计划软件，还 较好地解决了不用绘图仪直接用点阵打印机输出网络图，计算上解决了自动布 点、各种网络逻辑关系自动转换，使网络计划实现了机编、机算、机画自动化。 一些高等院校也投入力量研制以知识库为基础的项目管理专家系统( k b e s ) 。 随着计算机软件市场的发展，对推动网络计划技术的计算机化起到了很大 西南交通大学硕士研究生学位论文第6 页 的作用。虽然我们在理论水平与应用方面同发达国家相比相差无几，但在应用 管理上，特别是计划执行中的监督、控制及跟踪调整方面，国外落在实处，而 我们基本停留在编制上，对执行中的管理抓得很不得力，缺少行之有效的办法 t 4 j 主要表现为： ( 1 ) 应用目的不明确。许多企业应用网络计划，或因招标文件所要求，或 为投标施工组织增加“技术含量，或为显示本企业管理水平而“装点门面”。 由此绘制出的网络图不是错误连篇，就是华而不实，根本谈不上如何应用这一 科学管理方法进行项目管理。 ( 2 ) 应用普及率不高。我国现有施工企业素质差别很大，发展也很不平衡。 据统计，央企或省级i 、i i 级施工企业，管理水平较高，每年应用网络计划组 织施工面达5 0 左右；地市级施工企业应用网络计划组织施工面在2 0 左右； 县级及其他技术管理水平较差者，应用网络计划组织施工面不到5 。 ( 3 ) 应用管理水平低。绝大部分施工企业网络计划技术的应用只停留在编 制计划或画几张网络图上，对计划执行中的监督与控制及计划调整缺少有效的 管理方法。 ( 4 ) 应用深度不够。在施工网络计划的编制中，只是确定各工作单元之间 的逻辑关系，而没有根据施工方法确定工作单元中各项工作之间的所有关系。 编制深度不够，更谈不上网络计划的优化与控制。 另外，美国、日本、德国等在应用网络计划技术上都使用电子计算机进行 管理，并建立了相应的管理系统，而我们则刚刚起步。 1 4 本文主要研究的内容及组织结构 本文主要研究应用网络计划技术对电力机车检修进行时间和资源优化，其 目的在于分析网络优化技术在机务段机务检修系统中的应用，对我们合理进行 机务工程设计进行指导。论文主要研究内容包括： 1 研究网络计划技术的应用和发展。 介绍了网络计划技术的基本知识，重点用十字链储存方式研究了网络图的 关键路径法，应用c + + b u i l d e r 语言编制网络图绘图软件，用关键路径法和广度 优先搜索法对网络图进行了优化。 2 研究机务段检修设施系统。 分析电力机车检修流程，建立检修设施系统模型，研究设施功能需求，推 动机务检修设施的智能化发展，同时也使得检修设施系统化、模型化。 西南交通大学硕士研究生学位论文第7 页 本论文的结构共分五章，主要内容如下： 第一章，介绍本课题的研究意义，通过对机务检修现状和网络计划技术的 发展进行分析，突出了网络计划在机务检修系统中的应用趋势。 第二章，研究网络计划技术的国内外发展情况，重点介绍网络计划技术的 功能及其优化理论。 第三章，研究现代化机务检修设施系统，建立检修设施系统模型，研究检 修工艺流程。 第四章，结合具体项目，运用网络计划技术对其进行优化分析，再利用建 立的系统模型进行机务工程设计。 最后，在总结了论文所做工作的同时，给出了下一步工作的方向及内容。 西南交通大学硕士研究生学位论文第8 页 第2 章网络计划技术基本理论 2 1 网络计划技术 网络计划技术是通过网络图的形式表达一项计划，以选择最优方案来组织、 协调和控制生产( 工作) 的进度和费用( 成本) ，使其达到预定目标的一种科学 管理方法。通俗地讲，其基本思想就是“统筹兼顾”、“求快、求好、求省”。基 本原则是：首先，将工程计划看做一个系统，用网络图形式来表达一项计划中 的各项工作( 工序) 的先后顺序和相互关系；其次，通过计算获得计划中的关 键工作和关键路线；接着，通过不断改善网络图以选择最优的工程计划方案， 并付之实施；然后，再在计划执行过程中进行有效的控制与监督，使此系统对 资源进行合理的安排，有效地加以利用，达到以最少的时间和资源投入来完成 整个系统的预定计划目标，取得最佳的经济效益。 2 1 1 网络计划技术的产生 ( 1 ) 产生条件：在计划工作中，人们曾广泛采用横道计划。这种横道计划， 对提高管理工作水平和促进生产的发展起到过重要作用。但是，随着生产的迅 速发展，工程规模越来越大，各个生产环节之间、各项工作之间的关系错综复 杂，影响生产技术过程的各项因素也日益增多。在这种情况下，横道计划越来 越难以反映这些复杂关系，更难以统筹安排众多的工程项目以及年、季、月计 划。所有这些，都需要有一种新型的编制计划的方法和计划表达方式。因而引 起了计划理论与方法中的变革。网络计划法就是在这种历史条件下产生的。许 多工业发达国家，为了适应现代化生产发展，为了组织生产和科学研究的需要， 进行了大量的调查研究工作，先后发明并采用了一些新的科学管理方法，其中 网络计划技术也得到了发展。它有许多种具体方法，其中关键路径法( c r i t i c a l p a t hm e t h o d 简称c p m ) 和计划评审技术( p r o g r a me v a l u a t i o na n dr e v i e w t e c h n i q u e ，简称p e r t ) ，是应用最广泛且最具有代表性的两种方法。 ( 2 ) c p m 的产生：1 9 5 6 年美国杜邦化学公司新化工厂在建设生产设备的 西南交通大学硕士研究生学位论文第9 页 维修工作中首次使用c p m ，使停工时间由原来的1 2 5 小时减少到7 8 小时，从 而在一年内节约了1 0 0 多万美元，它相当于研究发展c p m 所花费的5 倍多。 这种计划借助于网络表示各种工作及所需要的时间，表示出各种工作之间的相 互关系，从而找出编制与执行计划的关键路线，这种方法被称为关键路径法， 即c p m 。 ( 3 ) p e r t 的产生：p e r t 首次应用于1 9 5 8 年，当时美国海军特种计划局制 定了北极星导弹计划，这个工程由八家总承包公司、2 5 0 家分公司承担，涉及1 万多个企业，工作任务十分繁重复杂。采用p e r t 后，提高了工作效率，使整个 工期比预定计划提前约两年完成，成本控制方面也取得了显著的效果。不过它 注重于对各项任务安排的评价和审查，所以把这种方法称为计划评审方法，即 p e r t 。1 9 7 9 年，使用p e r t 组织“阿波罗 载人登月计划，获得了圆满成功。 从此以后，网络计划技术成为一种盛行的科学管理方法。 2 1 2 网络计划技术的功能和优点 网络计划技术的功能和优点如下所示： ( 1 ) 能够把方案规划中的工序，组成一个有机的整体，因而可以全面准确 地表达各种工序，尤其是紧邻工序之间的逻辑关系。 ( 2 ) 能够计算出各项工序的时间参数，从而可以提高管理的计划性与预见 性。 ( 3 ) 标明关键工序与关键路线。了解关键路线，对施工计划有着非常重要 的意义。指挥人员可以凭此“向关键路线要工期，向非关键路线要资源”。 ( 4 ) 计划的实施过程中，因某种因素使一些工序无法如期完成时，应用网 络计划法，通过每项工序的时差计算，可以为决策提供可靠的依据。 ( 5 ) 工序提前或推迟时，网络计划法能够充分描绘出对其紧后工序以及总 工期的影响程度。 ( 6 ) 能够为优化提供形象而简洁的数学模型，并可以从许多可行的方案中 选出最优方案。因而可以缩短工期，降低成本，提高经济效益。 ( 7 ) 可以利用计算机进行计算，为项目管理、全面计划管理提供必要的前 提。综上所述，网络计划技术，既是方案、规划、计划的科学表达方法，又是 一种有效地实施方案、有规划、有计划的控制和管理方法。编制和修订网络计 划的过程，也就是利用网络计划对工程进行模拟的过程，是进行动态的仿真与 预演的过程p j 。 西南交通大学硕士研究生学位论文第10 页 2 1 3 网络计划图的基本概念 网络计划图是通过网络图来表示一项工程或组成工程的各道工序及其相互 之间的关系。网络图( n e t w o r kg r a p h ) 是由圆圈和箭线组成的，代表一项工程 计划的图形又称为箭头图。箭线表示工作、工序、活动，圆圈即节点表示事项。 工作是组成整个任务的各个局部任务，需要一定的时间与资源，而事项则是表 示一个或若干个工作的开始或结束，与工作相比，它不需要时间或所需时间少 到可以忽略不计。用箭线表示工作，每个工作用其首尾两端事项表示的网络图 称为双代号网络图。与此相应，国际上还流行一种单代号网络图，它用节点表 示工作，用箭线表明工作之间的关系构成网络【7 】。 下面对网络计划图的一些基本概念进行解释： ( 1 ) 工程：一项施工任务、科研试制项目、生产及较复杂的工作任务，统 称为工程。 ( 2 ) 工序：即网络图中的箭线，它代表一项工程中的一道工艺过程或局部 工作，它既消耗时间也消耗资源。一般用大写字母a ，b ，c 表示，或用工序 首尾相连的两个节点表示。 紧后工序指的是某工序结束之后紧接着要进行的后继工序。紧前工序指的 是与某工序箭尾直接相连的工序，其紧前工序结束之后，该工序可以紧接着开 始。两工序之间无其他工序的紧前工序，同时又是它紧前工序的紧后工序。 ( 3 ) 节点：即网络图中的圆圈，它代表某工序可能的开始时间或可能的结 束时间，一般用o 表示。节点只是表示某事件的开始时间或结束时间，只代表 着某一个瞬间，因此节点既不消耗时间也不消耗资源。 开始节点是指代表某工序开始时间的节点；结束节点是指代表某工序结束 时间的节点。同一个节点，对不同的工序而言，既可以是开始节点，也可以是 结束节点。 两节点间无第三个节点称其为紧前紧后的关系；否则，称为前继后继的关 系。总开始的节点叫源点，总结束的节点叫汇点。 ( 4 ) 工序的工期：工序消耗的时间称为该工序的工期，用字母t 表示。 工期一般情况下写在箭线的下方。 ( 5 ) 虚工序：网络图中的虚箭线，既不消耗时间也不消耗资源。它代表虚 工序的紧前工序结束之后，虚工序的紧后工序才能开始。 ( 6 ) 路线、关键路线、关键工序：由源点开始顺着箭线方向一直到达汇点 西南交通大学硕士研究生学位论文第1 1 页 的一条通道，叫做一条路线。每条路线都要由很多工序组成。 路线上所有各工序的工期之和叫做该路线的路长，记为z ，。路长最长的路 线叫做关键路线。有时关键路线有一条，有时好几条，无论有几条都叫做关键 路线。在网络图中用红色表示。 关键路线上的所有工序都叫做关键工序。关键工序是工程的主要矛盾环节， 如果关键工序的工期推迟一天，则整个工程的总工期必定推迟一天，如果关键 工序的工期提前一天，则整个工程的总工期可能提前一天。 ( 7 ) 总工期：总工期等于关键路线的长。 2 1 4 网络计划图的绘制规则 为了避免出现逻辑上的矛盾，网络图中不允许出现回路。有效的解决方法 是在给节点编号时，使一个工序的开始节点的号码总是小于结束节点的号码 【1 1 1 o 节点编号时一般采取：先左后右，由上而下的顺序来编号。 ( 1 ) 紧前工序全部结束后，紧后工序才能开始。 ( 2 ) 箭线与工序之间一一对应。 ( 3 ) 相邻两个节点之间只允许有一道工序。 ( 4 ) 源点与汇点唯一。 2 1 5 网络计划图的时间参数 网络计划技术是系统工程的方法，它研究问题是从全局出发，从局部与周 围环境的联系中去把握事物。时间参数，正是一个局部的工序与周围的环境以 及与全局联系的一种具体描述，所以，研究时间参数就是研究局部与整体的关 系。网络计划技术的优越之处都是从时间参数而来的。因此，研究网络的时间 参数是网络的中心任务之一。 2 1 5 1 最早时间参数 最早时间参数主要反映一个工序与前继工序的关系，有三个时间参数：工 序的最早开始时间、工序的最早结束时间、节点的最早开始时间【1 2 】。 ( 1 ) 工序的最早开始时间：在网络计划中，工序最早可能开始的时间，记 为e s i j 或e s a 。 西南交通大学硕士研究生学位论文第12 页 ( 2 ) 工序的最早结束时间：在网络计划中，工序最早可能结束的时间，记 为e f i j 或e f a 。 工序最早开始时间加上该工序工期就得到该工序的最早结束时间，用公式 表示为 e f a = e s a + t a t a 代表a 工序的工期，是作网络图时给出的，可当作已知的。因此只要知 道工序的最早开始时间，可立即推知工序的最早结束时间。工序的最早开始时 间等于其紧前工序最早结束时间的最大值，即 e s i j = m a x e s k i j ，e s k 2 i ，e s k 。i 因( i ) ( i ) 与( i ) ( r ) 有相同的紧前工序，所以 e f o = m a x e f k l i ，e f k 2 i ，e f k n i 即e s i j = e s i r 也就是说，共开始节点的工序其最早开始时间相等。 ( 3 ) 节点的最早开始时间：某节点的任一紧后工序的最早开始时间，称为 该节点的最早开始时间，记为e s i 。显然，e s i = e s i i o 节点的最早开始时间等于 其紧前工序最早时间的最大值。 ( 4 ) 最早开始时间的特点：同一节点的所有紧后工序的最早开始时间都相 同，或者说共开始节点的工序其最早开始时间相同。 2 1 5 2 最迟时间参数 最迟时间参数主要反映工序与其后继工序之间的相互关系。它也有三个时 间参数：工序的最迟结束时间、工序的最迟开始时间、节点的( 最迟) 结束时 间。 ( 1 ) 工序的最迟结束时间：在不影响总工期的前提下，工序最迟可能结束 的时间，记为l f a 或l f i i 。工序实际结束时间比最迟结束时间推迟多少天，则 总工期也会被推迟多少天。 ( 2 ) 工序的最迟开始时间：在不影响总工期的前提下，工序最迟可能的开 始时间，记为l s a 或l s i i o 工序的最迟结束时间减去工期就等于工序最迟开始 时间，用公式表示为 l s a = l f a t a 工序的最迟结束时间应等于其紧后工序最迟开始时间的最小值，用公式表 示为 l f i j = m i n l s j k l ，l s j k 2 ，l s j k n ， 因( i ) ( i ) 与( i ) ( r ) 有相同的紧后工序，所以 l f i j = l f r j 西南交通大学硕士研究生学位论文第13 页 即共结束节点的工序其最迟结束时间都相等。 很显然，若实际开始时间比最迟开始时间推迟n 天，则总工期就会因此而 推迟n 天。 ( 3 ) 节点的最迟结束时间：节点的任一紧前工序的最迟结束时间称为该节 点的( 最迟) 结束时间。即 l f j = l f i j 节点的最迟结束时间等于紧后工序最迟开始时间的最小值。 ( 4 ) 最迟结束时间的特点：同一节点的所有紧前工序最迟结束时间都相等， 或者说共结束节点的工序其最迟结束时间都相等。 2 1 5 3 机动时间参数 机动时间参数反映了工序与其他工序联系的总和，也反映了该工序在整体 工程中的地位，因此它是一个综合性的指标。目前在国际上通用的有三种机动 时间参数：总时差、单时差、公用时差。 计算各项工作的最早开始与完成时间、最迟开始与完成时间，目的之一就 是要分析各项工作在实施的时间安排上是否合理。为了安排合理的工作计划， 需要计算时差。时差，是指在不影响按期完成任务的条件下，在工作中可以灵 活机动使用的一段时间。 ( 1 ) 工作总时差t f i j o 某一项工作的完工期，可以推迟一定时间而不至于 影响整个计划任务的总工期，这样的时间称为工作的总时差。计算公式为 t f i j = l s i j e s t i 式中，t f i i 工作总时差； l s i i 工作最迟开始时间； e s i i 工作最早开始时间。 ( 2 ) 工作单时差f f i o 单时差是指在不影响紧后工作最早开工时间的条件 下，工作完工期的机动时间，以f f i i 表示。计算公式为 f f i j = e s j k e f i j 式中，e s j k 紧后工作的最早开始时间； e f i i 本工作的最早完成时间。 西南交通大学硕士研究生学位论文第1 4 页 2 2 关键路径法 2 2 1 相关概念 在网络图中通常把需时最长的路径叫做关键路径。为了缩短工期，必须进 行人力、物力的调度和分配，这就要求我们必须找出影响工程进度的关键活动， 这也就是关键路径的求解问题。通常，求解关键路径是在拓扑排序的基础上进 行的。本文通过对关键路径问题的分析，在按广度优先搜索的基础上，采用一 种新的求解关键路径的算法。该算法采用图的十字链表结构形式，不需要进行 拓扑排序，算法的时间复杂度为0 ( n + e ) ，较传统的算法效率更高【l 引。 定义1 ：d 3 ，v ，e ，w 为n 阶有向带权图，满足：d 是简单图，d 中无 环。有一个顶点入度为0 ，称为发点，有一个顶点出度为o ，称为收点；边 带的权为c o i i 。在计划评审图中求关键路径就是求从发点到收点的一条最长 路径。 定义2 ：在一条路中，若出现的节点互不相同，称其为基本路。图的广 度优先搜索实际上是类似于数的按层遍历的过程。首先从图的某个顶点出发， 依次搜索其邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使 “先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到 结束。广度优先搜索的过程是以某点v 为起始点，由近至远，依次访问和v 有 路径相通且路径长度为1 ，2 的顶点。 定理l 在一个具有n 个节点的图中，任何基本路的秩均不大于n 一1 。 证明：因任何基本路中各节点互不相同且最多为n 个，因此其秩均不大于 n l 。 定理2 设l 为简单有向加权图g _ v ，e ，w 中顶点u 到v 的基本路。 证明：若l 不是基本路，则l 上至少存在一个重复出现的节点w ，于是经 过节点w 一定存在一个回路，与g 为简单有向加权图矛盾，所以l 一定是基 本回路。 定理3 给定简单有向加权图g = ，v 为发点，u 为收点，对于图 g 的任意节点w ，如果w 到v 的最长距离和w 到u 的最长距离之和等于关键路 径的长度，则w 一定在从v 到u 的某一条关键路径上。 接下来的算法就是基于这些定理的。 西南交通大学硕士研究生学位论文第15 页 2 2 2 算法 十字链表( o r t h o g o n a l l i s t ) 是有向图的一种链式存储结构。可以看成是将 有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向 图中每一条弧有一个节点，对应于每个顶点也有一个节点。这些节点的结构如 图2 1 所示。 弧节点 顶点节点 图2 - 1 节点的结构 在弧节点中有四个域( 若加上和弧相关的信息，则为五个域) ：其中尾域 ( t a i l v e x ) 头域( h e a d v e x ) 分别指示弧尾和弧头这两个顶点在图中的位置，链 域h l i n k 指向弧头相同的下一条弧，而链域t l i n k 指向弧尾相同的下一条弧。弧 头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。它们的头节点即为 顶点节点，它由三个域组成：其中d a t a 域存储和顶点相关的信息，如顶点的名 称等；f i r s t i n 和f i r s t o u t 为两个链域，分别指向以该顶点为弧头或弧尾的第一个 弧节点。 设简单加权有向图g - ，为了实现方便，不妨设v = o ，1 ， n 1 。在程序设计中，我把十字链表结构定义为： t y p e d e f s t r u c ta r c b o x i n t t a i l v e x ，h e a d v e x ； i n t w e i g h t ； s t r u c ta r c b o x h i n k , * f l i n k ； a r c b o x ； t y p e d e f s t r u e tv e x n o d e i n t d a t a ： a r c b o x 辜f i r s t i n , * f i r s t o u t ； v e x n o d e ； t y p e d e fs t r u c t ， 西南交通大学硕士研究生学位论文第16 页 v e x n o d e x l i s t m a x ； i n tv e x l l u m ，a r c n u m ； ) o l g r a p h ； 为了求出每个节点到发点和收点的最长距离，分别设置辅助数组d m a x 和 c m a x ，其中d k 存储发点到节点k 的最长距离，c k 存储节点k 到收点的最 长距离。为了判断图是否有环，设置辅助数组c o u n t m a x ，c o u n t k 存储从发 点到节点k 的路径的秩( 弧的数目) 。 对算法的描述如下： ( 1 ) 对数组d 、c 和c o u n t 进行初始化。 ( 2 ) 对图g 从发点开始进行广度优先搜索，求出发点到其余各项点的最长 距离d k ( k = 0 ，1 ，n 一1 ) k = 0 ，1 ，n 一1 。若在求解过程中某个c o u n t k 大于n - i ，则说明该图有