基于PERT与CPM的船舶分段建造计划协调与优化

张 光 发， 刘 玉 君， 纪 卓 尚， 杨 海 天

（1.大连理工大学 船舶工程学院，辽宁 大连 116024；2.大连海洋大学 海洋工程学院，辽宁 大连 116023）

0 引 言

现代船舶制造模式是按照“以中间产品为导向”的原则进行组织的，每个分段都可以看作是一个中间产品，每个分段产品的生产制造都可以看成一项具体的任务，船舶生产企业均以分段产品为单位组织生产和制定生产计划.壳舾涂一体化的船舶分段建造计划是船厂建造计划的核心部分，它以船厂分段场地、起重能力、劳动力等资源为约束，以交船日和船厂年度（或三年）滚动生产计划为基准和依据，平衡协调生产资源及其成本，优化生产周期，提高各制造平台的利用率和生产量.由于分段产品及其生产过程复杂，且涉及各部门间的协调合作，船舶分段建造计划的制定非常困难.

一般的项目进度计划常采用Excel表格进行任务分解和工作量估计以后，利用甘特图安排日程，虽然简单明了，形象直观，但甘特图在反映各项工作之间的逻辑关系时比较困难，因而难以确定某项工作推迟对完成工期的影响，不适合船舶生产制造这样的大型和复杂工程项目（其任务可能多达几万项）.另外，如果需要根据条件计算每项任务的开始时间和结束时间，则需要在OFFICE－PROJECT日程计划基础上利用VBA进行二次开发，以实现其协调优化算法，并在已有计划的基础上进行计划与进度的偏差调整.

国内外学者利用各种技术，对船舶建造计划的制定和优化进行了研究.Lee等[1]在研究船厂资源及其计划组织方式的基础上，开发了能力需求计划 CRP（capacity requirement planning）系统.Neumann[2]基于 MAR II利用调度网络混合的方法，对船舶建造计划及其日程表的制定和管理进行了研究.Park等[3]对船厂分段制造日程计划进行了研究，考虑分段的生产日程及其空间布局，提出了部分枚举和分解调度的算法，设计了启发式搜索程序.刘建峰等[4]根据国内船厂的生产实际，构造船舶生产排序函数以及分段进出场地的规则，对船舶分段制造日程计划进行了模拟与优化.姜礼玲[5]利用模拟与仿真技术，对船舶建造过程及其计划进行了分析和优化.

上述方法，有的计算复杂，需要编制特殊的程序和软件，有的输入数据和信息比较繁琐，对使用者和决策者在技术方面要求比较高，都不太适合于或者实用于船厂计划部门在船舶建造初期的计划制定.

网络计划技术可以有效解决这些问题.目前，网络计划技术主要包括两种计划方法：关键路径法（critical path method，简称CPM）和计划评审技术（program evaluation and review technique，简称PERT）.这两种方法利用网络图分析制定计划以及对计划予以评价.PERT网络图能描绘出项目所包含的各种活动和任务的先后次序，标明每项活动的时间或相关的成本.在PERT的基础上，结合CPM的分析方法，可以方便地比较不同行动方案在进度和成本方面的效果，能协调整个计划的各道工序，合理安排人力、物力、时间、资金，加速计划的完成.在现代计划的编制和分析手段上，PERT被广泛使用，是现代化管理的重要手段和方法.

本文在详细分析船舶分段产品制造流程的基础上，利用网络计划技术，结合CPM和PERT，自动生成船舶分段产品制造计划，在工期和成本方面对制造计划进行协调与优化；并基于 MSProject软件，用VBA编制实用程序，以大连某船厂建造的某油船建造计划为实例进行计算和分析.

1 船舶分段建造流程及其生产计划

现代造船模式是壳舾涂一体化的区域造船作业模式，该模式将造船工艺过程分解为船体分道制造、区域舾装与区域涂装三大工艺流程，在设计和建造过程中对船舶舾装与涂装进行统筹安排.船厂将造船作业分解为一定粒度的生产流程，以船舶分段产品为单位，组织生产计划.船舶建造流程一般情况如图1所示[5]，主要生产流程如下.

（1）船体作业流程，其主要节点包括：零部件加工、部件制作、构件装配、分段合拢、船体大合拢.

（2）舾装作业流程，其主要节点包括：材料设备采购、单元组装、分段预舾装、船上安装、设备系统运转及试验.

（3）涂装作业流程，其主要节点包括：钢材预处理、管材涂装、分段涂装、单元涂装、跟踪补涂、完工涂装.

图1 船舶分段建造流程Fig.1 Block construction process of shipbuilding

按照上述船舶制造流程，一般采取倒排计划和逐级分解的方法制定船舶分段建造计划.先根据交船日期制定建造计划总线表，再根据分段/总段划分情况和建造方针，初步确立船舶大节点计划.船台（或船坞）属于船厂紧缺资源，要先根据分段划分图，结合船厂设备及其他资源制定船台（或船坞）施工计划（即船台搭载网络图），再以此为基础，倒排各分段的建造日程计划和其他计划，正排下水后的码头作业计划、船台（或船坞）内的舾装计划和密性试验计划等.

制定船舶分段建造计划时，要遵循如下原则和要求：单件分段合拢完成的时间满足船体大合拢的进度，以避免在船体铺龙骨前储备大量的分段而浪费场地资源，从而节约大量堆放分段的场地和转运分段的成本.

2 PERT与CPM网络分析方法的基本思想

CPM和PERT是独立发展起来的网络计划技术.CPM是以经验数据为基础来确定各项工作的时间，而PERT则把各项工作的时间作为随机变量来处理.前者往往被称为确定性网络计划技术，其以缩短时间、提高投资效益为目的；而后者往往被称为不确定性网络计划技术，其能指出缩短时间、节约费用的关键所在.在实际使用过程中，如果将两者有机结合，可获得更显著的效果.

（1）PERT

PERT以网络计划技术为基础，将工程项目中各个工序任务的工作时间看作不确定的待定值.通常情况，针对各任务先估计一个初始的工期时间，其延误率为未知，在实际实施的过程中处于一种被动变化的状态.由于组成网络计划的各项工作可变因素多，其工期统计资料不足，不能确定出一个肯定的工期.在PERT中引入概率计算方法对项目的各项任务进行估计，假设各项任务的工期服从β分布，近似地用三时估计法估算出3个工期值，即最长、最短和最可能工期，再加权平均算出期望值作为任务的工期，把三时估计变为单一时间估计，将非确定型转化为确定型，其计算公式为

式中：ti为任务i的平均工期，ai为其最短工期（亦称乐观估计时间），bi为其最长工期（亦称悲观估计时间），ci为其正常工期.ai和bi两种工期一般由统计方法进行估算，而ci可由施工定额（历史资料）估算.项目的总工期为项目某条路径上所有任务的工期和，即D＝∑ti，同时，利用任务i方差σ2i及其标准差σi对总工期的偏差进行估算和分析：

项目总体估计标准差

另外，PERT把风险因素引入到项目计划中，考虑按网络计划在指定的工期下，完成项目任务的可能性有多大，即计划的成功概率，或称可靠度，并基于此对工程计划进行风险估计.

项目在T时间内完工的概率可通过式（4）和查正态分布函数表求得.

（2）CPM

CPM体现在项目关键路径计算以及基于此的项目计划的优化上.在项目网络计划图中，项目的总工期决定于项目最长的路径，即关键路径.计算关键路径并对关键路径上的任务进行工期和资源优化，在此基础上，再对其他路径上的任务进行调整，即可达到对项目总体计划优化的目的.

3 结合PERT与CPM协调和优化船舶分段建造计划

对船舶分段建造流程和工序进行分析，结合工厂定额数据，利用PERT对各工序进行工作量估计，构造船舶分段建造流程PERT网络图，在此基础上，利用CPM计算关键路径，分配和优化工期、资源与成本.将PERT与CPM相结合，协调和优化船舶分段建造计划，其基本步骤如下：

（1）根据船舶分段建造的特点，分解、定义各分段的建造流程和各工序任务之间的逻辑关系，表1分析和总结了详细的船舶制造流程及其相应的施工场所，并对其进行了编号，以方便编程处理.

（2）根据分段信息，利用PERT详细估计各分段工序的工作量和工期（如表2所示）.

（3）根据船厂历史资料和生产实际，分析和计算各分段工序的应急（最短）工期及其相应的应急成本，并为其分配资源，编制成工作任务表（如表3～5），表中所列的工期为根据大连某船厂的生产实际对某油船估算的结果，基本符合当前该厂的实际情况，用来作为实际算例的基本数据.

（4）根据工序间的逻辑关系以及工期估计的数据，绘制（构造）PERT网络图（如图2所示）.

（5）计算PERT网络图的关键路径、完工期及其概率.完工概率按式（4）计算.式中计算的路径为关键路径，各工序也为关键路径上的工序，T为关键路径总时间.

（6）工期－成本（资源）优化.CPM 是解决工期－成本优化的一种较科学的方法.它包含两方面的内容：一是在满足成本最低的要求下，寻求最佳工期；二是根据计划规定的期限，规划最低成本.工期－成本优化的内容主要是对关键路径中的单位时间成本最小的任务进行压缩和平衡，其具体步骤和算法如下所述.

表1 船舶分段建造流程节点Tab.1 Nodes of ship block construction flow

表2 PERT工作量估算Tab.2 Workload estimation with PERT

表3 分段制造工序任务（部分）Tab.3 Procedure tasks of block construction（partial）

表4 总段制造工序任务（部分）Tab.4 Procedure tasks of assembly construction（partial）

表5 船体大合拢工序任务（部分）Tab.5 Procedure tasks of hull erection（partial）

图2 PERT网络示意图Fig.2 PERT network chart

步骤1 求项目的关键路径.

步骤2 计算每项任务的单位时间成本，计算公式为其中tn、Cn为正常时间、成本，te、Ce为应急时间、成本.

步骤3 对关键路径中单位时间成本最小（即总成本增加最少）并且可以压缩的分段工序进行工期压缩.

步骤4 计算项目总成本，输出压缩方案（项目工期及其成本）.

步骤5 扫描所有工序节点，检验是否还可压缩.如果还有可压缩的节点，则进行步骤1，再进行下一轮压缩.

步骤6 对所有输出的方案，根据输出的工期及其成本进行决策，得到最优计划.

以如图3所示的网络图为例，其中，tn、Cn为各工序的正常时间、成本，te、Ce为各工序的应急时间、成本.比较正常工期和应急工期两种情况下的关键路径和成本，可得出：

①在正常工期的情况下，关键路径为R3—R4，总工期18 d，总成本20.0万元（路径R1—R2的工期16 d，成本13万元；路径R3—R4的工期18 d，成本7万元）.

②当全部工序均在它们各自的应急时间内完成，关键路径为R3—R4，项目总工期15 d，总成本25.9万元（路径R1—R2的工期11 d，成本17.2万元；路径R3—R4的工期15 d，成本8.7万元）.

③利用工期 －成本平衡法对那些使总成本增加最少的工序的工期进行压缩，以确定项目最短完成时间.在压缩过程中，由于项目的总工期由关键路径的工期决定，优先压缩关键路径；从关键路径上具有最低的单位成本的工序开始压缩.

第一次压缩，对关键路径R3—R4进行优化.计算单位时间成本，k4＝0.6，k3＝0.5，k2＝1.0，k1＝0.6.k3最小，将工序R3的工期压缩1 d后项目周期变为17 d，总成本20.5万元.

第二次压缩，再次找出关键路径，两个路径的工期分别为16、17 d，关键路径是R3—R4，再次压缩路径R3—R4.由于此时工序R3已达到其应急工期9 d，只能加速工序R4的进程，将工序R4的工期压缩1 d，于是项目工期变为16 d，总成本21.1万元.

第三次压缩，计算可得R1—R2和R3—R4均为关键路径.将每个路径都加速1 d.压缩路径R1—R2的工序R1，压缩路径R3—R4的工序R4，项目周期缩短为15 d，总成本22.3万元.

第四次压缩，计算可得R1—R2和R3—R4均为关键路径，其工期相同.将两条路径同时加速1 d.但由于路径R3—R4已达到其应急时间，加速路径R1—R2的进程没有意义.停止优化过程.

④最后输出如表6所示的工期－成本优化结果，决策者再根据该表进行工期－成本平衡决策.

图3 工期－成本优化示例PERT网络图Fig.3 PERT network chart for demonstrating optimization of duration－cost

表6 工期－成本平衡决策示例Tab.6 Decision－making demonstration for duration－cost balancing

4 编程实现及实例分析

基于 MS－Project软件，利用VBA对上述方法进行了编程实现，并以大连某船厂生产的某油船的建造为实例，编制了分段建造计划PERT图，并进行了优化计算和分析.

程序的输入数据包括：（1）分/总段数据，主要有分段各工序标准工作量及成本估计数据、分段合拢顺序、总段合拢顺序；（2）船舶交工期；（3）分段可进入场地开始时间，及其他优化限定时间和工期.见表2～5.

输出数据包括：（1）工期－成本平衡决策表，如表7所示；（2）大节点计划表；（3）详细节点计划表，如表8所示；（4）分段制造计划表；（5）船体大合拢计划表.

该船共有114个分段，船体大合拢前共计32个总段或分段.通过分析计算，船舶制造总工期（至下水）从最初的104 d缩短到85 d，缩短了18.3%，总成本也由1380万元缩减到1260万元，减少了8.7%；通过计划协调，使每一个分段合拢完成的时间能够正好满足船体大合拢的进度，使分段合拢的进度满足船体大合拢、分段搭载的生产节拍要求，最终的计划满足了连续不断的准时生产的现代精益造船要求.

表7 工期－成本平衡决策表Tab.7 Decision－making table for duration－cost balancing

表8 详细节点计划表Tab.8 Schedule table of planning nodes

5 结 语

结合CPM的PERT网络分析法是一种有效的项目事前控制方法，并能根据工期与成本间的关系，对计划进行协调和优化.船舶建造项目事前可以根据船厂的实际情况制定比较准确和稳定的建造工艺，并且能根据船厂的经验数据较准确地估计各分段建造过程中各工序所需时间和资源，这样的项目适宜于利用PERT网络分析法对之进行计划与控制.利用PERT和CPM结合的方法，比较好地解决了船舶分段建造的计划协调与优化问题，方法简洁适用，加速了计划的完成，能够帮助船厂在船舶建造初期制定切实可行的建造计划.该方法的缺点是将船厂的资源相对于单船建造来说认为是无限满足的，即没有综合考虑船舶建造企业的资源约束问题.

[1]LEE T E，SONG J S.Searched－based heuristic algorithms for basic planning in a large shipyard[J].Journal of Ship Production，1996，12（4）：211－219

[2]NEUMANN R J.Network scheduling development in an MRPⅡenvironment [J].Journal of Ship Production，1994，10（4）：223－232

[3]PARK K，LEE K，PARK S，etal.Modeling and solving the spatial block scheduling problem in a shipbuilding company [J].Computers ＆ Industrial Engineering，1996，30（3）：357－364

[4]刘建峰，秦士元，应长春.船体分段制造日程计划的模拟与优化[J].中国造船，2000，41（4）：13－20

[5]姜礼玲.船台（坞）总装网络规划及其仿真研究[D].上海：上海交通大学，2008