（机械制造及其自动化专业论文）船台吊装顺序优化关键技术研究.pdf

哈尔滨t 程大学硕十学位论文 摘要 船舶工业是为航运交通和海洋开发提供主要装备的战略性产业，同时也 是保障国家安全和海洋权益维护的重要工业基础。船台总装是船舶建造的重 要环节，也是船舶建造各项计划制定的依据，船台吊装网络制定的好坏直接 影响着船舶建造的质量和建造周期。如何优化船台分段吊装顺序，实现资源 的充分利用和合理配置，有效地缩短船台周期有着重要的意义。 本文以船台吊装顺序优化为研究对象，以粒子群优化算法( p s o ) ，资源 受限项目调度问题( r c p s p ) 为理论依据，主要做了如下的研究： 分析了船台吊装技术及船台调度问题的研究现状，给出了船台吊装顺序 优化系统，阐述了系统各个部分的功能和实现方法；提出采用粒子群算法求 解船台吊装顺序优化问题，通过分析p s o 的基本原理，对算法进行改进；采 用带约束有向图搜索算法完成了船台吊装顺序规划，并对船台吊装网络图的 构建方法进行了研究； 将r c p s p 问题应用于船台吊装顺序优化中，构建了以最短工期为目标的 船台吊装顺序多资源优化模型，并结合实际吊装过程，构建了突发情况下的 船台吊装顺序优化模型；给出了改进粒子群算法求解船台吊装顺序优化问题 的实现方法，并使用典型r c p s p 问题算例验证实现方法的正确性。 将本文提出的船台吊装顺序优化方法应用到某型号油轮主船体船台吊装 顺序优化问题中。构建了该船主船体分段吊装网络图，采用改进p s o 对船台 吊装网络进行优化，得到最短吊装工期以及各个分段的起吊时间，并对优化 后的资源需求情况及算法收敛性进行了分析，证实了该方法用于船台调度问 题研究的可行性。 关键词：船台吊装；吊装顺序优化：资源受限；改进粒子群算法 哈尔滨t 秤人学硕十学伊论文 a bs t r a c t s h i p b u i l d i n gi n d u s t r yi sa l li m p o r t a n ts t r a t e g i ci n d u s t r yw h i c hp r o v i d e sm a i n e q u i p m e n tf o rs h i pt r a n s p o r t a t i o na n do c e a ne x p l o i t a t i o n , a n d i ti sa l s ot h e i n d u s t r yf o u n d a t i o nf o rs a f e g u a r d i n gn a t i o n a ls e c u r i t ya n dm a r i t i m er i g h t a sa c r u c i a lp r o c e s so fs h i p b u i l d i n g ，g e n e r a la s s e m b l yo nt h eb e r t hd e c i d e sh o wt o e s t a b l i s hs h i p b u i l d i n gp l a nt os o m ee x t e n t ，a n dd e s i g n i n gag o o dn e t w o r ko fb l o c k e r e c t i o no nt h eb e r t hh a sg r e a te f f e c to nt h eq u a l i t yo fs h i pt ob eb u i l ta n db e r t h c y c l e t h e r e f o r e ，h o wt oo p t i m i z et h en e t w o r ko fb l o c ke r e c t i o no nt h eb e r t hi n o r d e rt oe q u i p o i s et h er e s o u r c e su t i l i z a t i o na n ds h o r t e nt h eb e r t hc y c l ee f f e c t i v e l y i so fg r e a ti m p o r t a n c e t h i sp a p e rc h o o s e so p t i m i z a t i o no fb l o c ke r e c t i o ns e q u e n c eo nt h eb e r t ha s r e s e a r c ho b je c t ，a n dr e l e v a n tt h e o r yo fp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a n d r e s o u r c ec o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m ( r c p s p ) 嬲t h e o r yf o u n d a t i o n t h ef o l l o w i n gc o n t e n t sa r ei n c l u d e di nt h er e s e a r c h i nt h eb e g i n n i n g ，o p t i m i z a t i o ns y s t e mo fb l o c ke r e c t i o ns e q u e n c eo nt h e b e r t hi sb u i l tb a s e do nr e s e a r c ha n ds t a t ea n a l y s i sa b o u tt h es c h e d u l i n gp r o b l e mo n t h eb e r t h ，a n dd e t a i l e df u n c t i o na n dw a yt oi m p l e m e n to fe v e r yp a r to ft h es y s t e m a r ep r e s e n t e d a na p p r o a c ht os o l v et h ep r o b l e ma b o u tt h eo p t i m i z a t i o no fb l o c k e r e c t i o ns e q u e n c eo nt h eb e n hu s i n gp s oi sp r o p o s e da n dam o d i f i e dp a r t i c l e s w a m io p t i m i z a t i o ni sd e s i g n e do nt h eb a s i so fa n a l y s i sa b o u tt h eb a s i cp r i n c i p l e o fp s o t h ep l a n n i n gm e t h o do fb l o c ke r e c t i o ns e q u e n c eo nt h eb e r t hi sd i s c u s s e d w i t hc o n s t r a i n td i r e c t e dg r a p hs e a r c hm e t h o d ，a n dd e t a i l e dw a yt ob u i l dn e t w o r k o fb l o c ke r e c t i o no nt h eb e r t hi sa l s os t u d i e d r e l e v a n tt h e o r ya b o u tr c p s pi sa p p l i e dt oo p t i m i z a t i o no fb l o c ke r e c t i o n s e q u e n c eo nt h eb e r t h ，a n dam a t h e m a t i c a lm o d e lo fm u l t i r e s o u r c eo p t i m i z a t i o n 哈尔滨t 程人学硕+ 学位论文 o fb l o c ke r e c t i o ns e q u e n c eo nt h eb e n l li sb u i l tw i t ht h eo p t i m i z a t i o no b j e c to f m i n i m i z e db e r t hc y c l e ，a n da tt h es a m et i m e ，a c c o r d i n gt ot h er e a lb l o c ke r e c t i o n p r o c e s so nt h eb e r t h ，a n o t h e rm a t h e m a t i c a lm o d e lo fo p t i m i z a t i o no fb l o c k e r e c t i o ns e q u e n c eo nt h eb e r t hb a s e do nd e v i a n ts i t u a t i o ni se s t a b l i s h e d t h i s p a p e ra l s op r e s e n t sa na p p r o a c ht os e t t l et h eo p t i m i z a t i o np r o b l e mo fb l o c k e r e c t i o ns e q u e n c eo nt h eb e r t hw i t hm o d i f i e dp s o a n dac l a s s i cr c p s p e x a m p l e i se m p l o y e dt op r o v ev a l i d i t yo ft h i sm e t h o d t h eo p t i m i z a t i o nm e t h o do fb l o c ke r e c t i o no nt h eb e r t hd e v e l o p e di n t h i s p a p e ri sa p p l i e dt oa c t u a lo p t i m i z a t i o np r o b l e mo fb l o c ke r e c t i o no nt h eb e r t ho f a l lo i lt a n k e r sh u l l f i r s t l y , i t sn e t w o r kf i g u r eo fb l o c ke r e c t i o no nt h eb e r t hi s e s t a b l i s h e d t h e ni t sb l o c ke r e c t i o n s e q u e n c eo nt h eb e r t h i s g m n e du s i n g m o d i f i e dp s o ，a n dt h em i n i m i z e db e r t hc y c l ea n dt i m eo fe v e r yb l o c kt ob e e r e c t e da r e f i g u r e do u t f i n a l l y , d e m a n do fr e s o u r c ed u r i n gm i n i m i z e db e r t hc y c l e a n da s t r i n g e n c yo fm o d i f i e dp s ot ot h i sp r o b l e ma l ea n a l y z e d ，a n dt h ea n a l y s i s r e s u l t se n s u r ef e a s i b i l i t yo ft h em e t h o dp u tf o r w a r di nt h i sp a p e rt ob eu s e df o r r e s e a r c h i n gb e r t hs c h e d u l i n gp r o b l e m k e y w o r d s ：b l o c ke r e c t i o no nt h eb e r t h ；b l o c ke r e c t i o ns e q u e n c eo p t i m i z a t i o n ； r e s o u r c ec o n s t r a i n e d ；m o d i f i e dp a r t i c l es w a r mo p t i m i z a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。h 作者( 签字) ：稚谢呻 日期：二，o9 年乡月，日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 别答字) 邦 沙，9 年；月，乙日j 哈尔滨+ i ：科大学硕+ 学位论文 第1 章绪论 1 1课题研究的背景及意义 1 1 1 船舶制造业发展概述 船舶制造业是为航运交通和海洋开发提供主要装备的战略性产业，同时 也是保障国家安全，确保国家能源战略和海洋权益维护的重要工业基础。纵 观世界数百年的造船史，可以发现一条较为明显的演进趋势，即世界造船中 心由西方国家逐步向东方国家转移，随着经济的发展，船舶业已实现从先行 工业化国家到后期工业化国家的产业转移。到了上个世纪九十年代，东亚地 区日本、韩国、中国的造船产量己占到世界市场份额的7 5 以上1 。随着世 界造船技术水平的提高，对造船业提出了更高的要求，同时也增加了造船行 业之间的竞争，许多船舶企业及船舶研究单位纷纷开始了对造船技术的研究， 以提高船体建造的效率，缩短船台建造的周期，增加造船企业在行业间的竞 争力，并为船舶企业带来可观的经济效益。 在世界造船业在稳定发展的同时，我国的造船业也在稳步的发展，据中 国船舶工业行业协会的统计数据，2 0 0 7 年，全国造船完工量达1 8 9 3 万载重 吨，比上年增长3 0 ，新承接船舶订单9 8 4 5 万载重吨，比上年增长1 3 2 ， 手持船舶订单1 5 8 8 9 万载重吨，比上年增长1 3 1 。按英国克拉克松研究公 司对世界造船总量的统计数据，以载重吨计，我国造船完工量、新承接船舶 订单分别约占世界船舶市场分额的2 3 、4 2 和3 3 ，比上年分别提高了4 个、1 2 个和9 个百分点。2 0 0 7 年1 月1 1 月，全国规模级以上船舶工业企业 利润总额1 8 5 亿元，比上年同期增加7 8 5 亿元，同比增长1 3 6 。这些数据 都充分说明我国的造船业正稳步的向前发展，已经稳居世界第三大造船国的 地位，与造船强国韩r 的差距将越来越小。 但是，与产量和利润的迅速增长相比较，我国的造船技术水平与国际先 哈尔滨t 程人导：硕十学伊论文 进造船水平相比有着很大的差距。大力推进信息技术在造船领域的应用，建 立现代造船模式，控制造船成本，减少劳动力，提高总装化、自动化水平； 建成以中间产品组织生产为主要特征的总装造船模式，是我国提高造船水平 和造船效率，成为造船强国要解决的主要问题。 1 1 2 船体分段吊装概述 船台大合拢是船舶建造的最终阶段，船台大合拢计划是所有材料零部件 加工、制作、装配、分段合拢、分段预舾装、分段涂装作业计划的依据。船 台大合拢日程作业计划的内容包括：铺龙骨分段定位、分段吊装、船体对接 装配、船体对接焊接、搭脚手架、机电设备大型舾装件安装、电缆敷设、涂 装、外观检验、舱室密性试验、拆除脚手架、设备初步系泊试验等。船体大 合拢阶段是各个专业立体交叉的作业，需要安排周密的作业计划，同时需要 打破各专业的界限，实行现场区域的统一管理。船体大合拢计划必须根据船 厂的生产条件，如起重能力，场地面积等，进行综合优化后确定捌。 船体分段吊装是船台大合拢计划的主线，所有的计划日程都围绕着船体 分段吊装的计划展丌。在船体的建造过程中，吊装活动占相当大的比重，据 统计，吊装活动约占整个造船周期的4 5 以上，船台吊装活动的好坏将直接 影响到船体建造的质量和效率。研究改进分段吊装技术，将会提高造船企业 的竞争力，从而为企业带来可观的经济效益和社会效益。 船体分段吊装是指在船台上，使用起重设备，焊机等一些辅助设备将大 型船体分段吊运到指定的位置并进行焊接装配的过程。由于需要吊装的分段 体积和质量较大，吊装过程会涉及大量的人力、物力等资源的协调使用，吊 装过程中资源的合理配置显得尤为重要。船台( 船坞) 是船厂实现分段吊装 的主要场地，因此船体分段吊装有时也称为船台吊装，船台的数量和尺度是 决定船厂生产能力的主要依据。船台的生产能力决定船厂每年的生产量，因 此，船厂总是最大限度地发挥船台的能力，通过优化船台吊装顺序，合理安 排资源的使用情况，可以有计划地缩短船台周期。 2 哈尔滨r 秤大学硕十号：1 市论文 船台吊装主要有以下一些特点： ( 1 ) 需要吊装的分段质量大、体积大。在船台的吊装过程中包含许多分 段和总段，这些分段的质量和体积都非常大，占用场地面积大，对吊车的起 吊能力要求非常高，通常还需要其它一些辅助设备才能顺利完成吊装。 ( 2 ) 工作密集集中。船体分段的吊装都在船台上完成，船台上存在着分 段的起吊、运输、焊接以及资源的运送等多工作的同时进行，而船台的面积 是有限的，这使得船台上的工作十分密集，一旦某一环的工作出现停滞，就 会对其它工作产生很大的影响。 ( 3 ) 需要资源数量种类多。由于分段质量体积大，在进行搬运、吊装、 焊接时就需要大量的人力、起重设备以及其它资源来共同协作才能完成。同 时，在吊装完成后，还要进行分段焊接工作，这更加大了资源的使用数量。 因此，要求船体分段吊装计划的制定必须能够很好的协调各种资源的利用， 避免发生资源冲突，或资源等待状态。 ( 4 ) 吊装过程复杂。船台的吊装计划是制定造船计划的主要依据，吊装 过程不但涉及多资源的综合利用，而且直接影响到车间的分段装配、预舾装、 小分段合成大分段等作业的闩程计划。因此，要求船体建造部门必须对船台 分段吊装进行周密的计划，确保船舶建造的顺利进行。 1 1 ，3 课题研究的意义 通过分析，课题的研究具有如下几方面的意义： ( 1 ) 分段吊装技术是船舶建造过程中十分关键的环节，其占用的时间和 消耗的资源都非常大，因此对船体吊装技术进行研究，特别是对吊装过程中 资源的使用分配情况进行研究，使得在分段吊装过程中资源能够合理配置， 避免在工期的某段时间内所消耗的资源超出实际可供给的资源数量导致工期 的延误，也防止资源过剩的情况，这将对提高造船水平有着非常重大的意义。 本文旨在通过对船台吊装顺序优化问题的研究，为船体吊装技术的进一步发 展提供一种新的思路。 3 哈尔滨i ：科人学硕十学何论文 ( 2 ) 资源受限项目调度问题( r c p s p ) 就是在满足活动的紧前约束和资 源约束的日i 提下，为项目的所有活动分配资源并制定每个活动的具体开始时 间，使得项目的总工期最小或成本最低p 1 。将r c p s p 问题模型和研究方法应 用于船台吊装顺序优化问题中，根据吊装过程的特点建立船台吊装顺序优化 的数学模型，并进行求解，将优化结果应用到实际吊装过程中，使得吊装所 使用的资源得到合理配置，并得到最优的船台周期。 ( 3 ) 船台吊装顺序优化是非常复杂的n p 问题，一般优化方法很难解决， 粒子群算法( p s o ) 是近些年提出的一种仿生类算法，其原理简单，计算方 便，易编码。本文提出采用粒子群算法求解船台吊装顺序优化问题，首先对 粒子群算法进行改进，以提高其收敛效率，然后将改进p s o 用于船台吊装顺 序优化问题中，通过粒子群算法的引入提高船台吊装顺序优化的效率和精度， 使得所优化的结果更加符合实际的要求。 1 2 相关领域国内外研究现状 1 2 1 船台调度问题研究现状 有关船体吊装技术问题，国内外许多学者做了大量的研究，主要集中在 船台调度方面，即如何通过优化船台吊装顺序使得吊装过程所使用的资源得 到合理的利用。 1 国外研究现状 国外对船体分段吊装技术的研究起步较早，分别针对不同的方面提出了 不少的方法和体系结构，并应用到了实际的吊装过程控制中。 jkl e e 和kjl e e h l 等人在九十年代初期就开始了对船台调度问题的研 究，针对船舶的复杂建造过程中人力、材料和设备等各种资源的优化分配难 题，建立了d a s 系统，该系统采用带约束有向图搜索算法，空间优化理论以 及基于工时评价的神经网络方法对韩国d a e w o o 船厂的吊装工艺约束问题、 吊装顺序以及分段在船台上的堆放问题进行了研究，通过对该船厂的整个生 产装配线和吊装过程进行建模和动态仿真，来寻求满足吊装工艺约束情况下 4 哈尔滨t 稃人。7 ：硕十学何论文 的合理分段装配方式和船台吊装顺序。d a s 系统总共分为四个部分： d a s e r e c t 、d a s c u r v e 、d a s p a n e l 和d a s m h 。其中d a s e r e c t 是指船台分段吊装顺序优化问题，根据船台吊装约束得到船体各分段总段的 吊装顺序，并对分段在船台上存储的合理规划问题进行了研究；d a s c u r v e 是对车间内曲面分段的装配工艺顺序优化问题进行研究；d a s p a n e l 是对 车间内平面分段的装配工艺顺序优化问题进行研究；d a s m h 对分段装配及 总体吊装过程中使用的人力及工时情况进行估计和评价。d a s 系统成功地应 用于d a e w o o 船厂的实际船舶建造中，对合理的制定船舶建造计划和安排船 台吊装顺序起到了积极作用，但是该系统并没有把吊装网络，时间和资源约 束情况考虑进来，对吊装过程中资源的合理配置问题没有进行研究，使得系 统的应用具有一定的局限性。 此外，韩国学者kjl e e p l 等人针对船台上有限空间内的分段堆放问题进 行了详细的研究，建立了船体分段吊装空间优化专家系统。系统将分段假设 为凸多边形，并考虑到分段能够适合吊车的起吊和安装定位，其摆放均假设 定位在0 。，9 0 。，1 8 0 。，2 7 0 。四个方向，设定约束条件为吊车的起吊能 力、吊装周期、分段的优先权、分段之间摆放的最小要求距离和工作时的最 大等待时间，然后采用空间多边形优化理论对船厂的分段场地布置进行了优 化，优化的目标根据情况不同可以定为最小工期，最大空间利用率或最小等 待时间等，最终利用启发式方法进行计算求解以寻找最佳的分段堆放方式。 该专家系统极大的提高了船台的利用效率，降低了分段的储备成本，并能够 缩短船舶的建造周期。 c h a r l e sm c l e a n l 6 1 对船体建造仿真( s h i p b u i l d i n gs i m u l a t i o n ) 的目的和要 求进行了研究，通过对常见的船体建造过程仿真方法的分析，提出船体建造 仿真应能够对建造过程中的资源冲突问题，新技术或新设备的引入对建造计 划的影响，以及建造成本和建造周期问题等各个方面进行控制管理，并能针 对相应的问题提出解决方法。hk i m 和ssl e e p l 通过对造船业中的虚拟仿真 技术的研究，利用船舶建造过程仿真模型建立了船体建造虚拟装配仿真系统 哈尔滨l ：群人学硕十学位论文 ( v a s s s ) ，在虚拟环境中构建了船台，吊车等虚拟模型，对复杂的船舶建造 过程进行了模拟仿真，并将该系统成功地应用于实际的船舶建造过程中。 此外，r e i dd j 利用遗传算法构建了p e t r i 网模型，r e y e sa ，m o r oa r 等人利用启发式搜索算法对其进行了研究。k p a r k 喁1 对船厂生产过程瓶颈问 题分段制造同程计划进行了研究，考虑到每个分段的制造同程和空间柿局， 提出了部分枚举和分解调度的算法，设计了启发式搜索程序。t e l e e 网开发 了能力需求计划c r p ( c a p a c i t yr e q u i r e m e n tp l a n n i n g ) 系统。r j n e u m a n 认 为不能简单地像机械制造业那样应用m r p i i ，提出了包括m a r i i 和调度网络 混合的方法，用于船舶建造计划、日程表和管理。 2 国内研究现状 我国对船体吊装技术的研究起步比较晚，早期由于传统造船模式的影响， 船厂主要根据实际的生产经验对船体分段吊装过程进行控制。随着我国造船 量和造船水平的不断提升，许多学者也开始对船体分段吊装过程从不同的方 面进行了研究。 续爱民，金烨川从吊装过程中分段需求量不断变化的角度出发，通过对 吊装过程中所涉及的工艺约束情况，车间分段制造能力和分段储备成本进行 分析，构建了给定船坞周期下实现分段储备成本最小的优化模型，并采用改 进遗传算法对模型进行求解，得到了满足分段储备成本最小的分段起吊时间， 实现对分段需求量的控制，从而实现分段储备成本的降低，同时也避免了因 不合理的规划造成的分段储备过多或供应不足的情况，并以某货船船台吊装 顺序优化为实例，进一步说明了该方法能够降低船舶建造成本的j 下确性。 此外，续爱民“1 2 1 等人还根据船舶吊装过程中所涉及的吊装网络约束、场 地和设备约束，以及所消耗的时间等信息，采用时间p e t r i 网理论，提出了通 过共享合成建立吊装过程的t p n 模型，并对其可行性进行了分析，给出了一 种利用极大加法代数求解本模型中船舶吊装时间的算法。构建了实际多船吊 装过程t p n 模型，并采用改进的免疫遗传算法对所建立的吊装网络模型进行 优化，进一步说明了这种方法对解决船台吊装网络优化问题的有效性。但是 6 哈尔滨i j 群人学硕十学何论文 由于时间p e t r i 网构建船体分段吊装网络的复杂性，该研究实际应用具有很大 的局限性。 姜礼玲口1 研究了现代造船模式下的船台调度情况，提出了基于仿真的船 台吊装规划系统，对船台吊装网络多目标问题的优化方法进行了研究，结合 具体分段以及设备起吊能力等数据，从船台调度基本特点出发，基于蚁群算 法实现了对船台吊装网络的优化调度，改善了船台网络优化调度的效率。并 基于d e l m i a q u e s t 软件，开发了船台吊装原型系统，对船台吊装过程进 行仿真，该系统能够用于指导生产，并能够对企业资源进行配置、生产线规 划设计，缩短了船厂的生产准备时间，并能有效控制生产线的仿真运行，对 船厂的实际船台调度具有很好的指导价值。但是该文章对船台吊装网络优化 时，只考虑了起吊顺序和起吊能力两种约束情况，没有考虑到场地面积、人 员以及焊接设备等其他的资源约束情况。 上海交通大学刘建峰习等分析了船体分段制造同程计划一计划过程中的 瓶颈，以中间产品为导向，贯彻以“区域作业问题类型阶段”( z o n e p r o b l e m ) 分解任务包的思想来研究计划，形成较完整的模拟与优化方法。刘建峰还在 其博士论文中采用遗传算法对吊装的时间进行了优化，使得分段吊装设备的 负荷更加均衡。 刘寅东”训采用专家系统和a c t i m 模型研究了受资源约束问题的工程计 划方法在船体结构分段装配生产中的应用，建立了造船生产计划专家系统原 型，系统分为两部分：装配计划专家子系统和生产资源检验专家子系统。在 系统中建立启发式规则库，采用规则推理的方式根据数据库中有限的资源安 排分段的工艺顺序，对实现造船生产计划编制信息集成和自动化具有一定的 实际意义。 上述的对船台调度问题的研究都没有将资源的使用情况充分考虑到船台 总装过程中，只是从吊装前对场地的使用情况，分段的储备成本等方面对船 台调度进行了研究，对资源的研究更多地集中在船体分段建造装配中，没有 对船台吊装过程中多种资源的合理分配问题提供一种有效的解决方法。在实 7 哈尔滨t 稃人学硕十学何论文 际船台吊装过程中，由于资源的可提供数量对船台吊装顺序的制定有着很大 的影响，而且在船台总装时，针对多种资源的合理利用来优化船台调度问题 对船舶的建造有着重要的意义。因此，本文将从多资源的船台吊装顺序优化 问题入手，对船台调度进行研究。 1 2 2 资源受限项目调度问题研究现状 船台吊装顺序优化也即船台调度问题就是从实际吊装过程中有限的资源 出发，根据现有的资源对各个分段的起吊时间进行合理的安排，得到理想的 船台周期，并使得资源合理的利用，因此，船台台调度问题也是资源受限项 目调度问题( r e s o u r c e c o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m ，r c p s p ) 中的 一种，研究时可以结合r c p s p 理论对其进行研究，这也是本文应用r c p s p 理论的一个原因。 r c p s p 理论从资源受限的前提出发研究项目调度问题，典型r c p s p 可 简单描述为：在满足项目紧前约束与资源约束的前提下，对项目所有活动的 开始时间和结束时间合理安排，以便最小化项目总工期。r c p s p 约束要同时 服从于项目活动之间的紧前约束和资源数量约刺”1 司。在研究r c p s p 问题时 涉及到的因素很多，例如网络计划图的建立、活动模式的选取、资源类型及 数量的确定、数学模型的建立、求解方法的选择等。 1 资源受限项目调度问题的优化目标 船台吊装顺序优化问题，即船台调度问题，主要就是研究合理的安排每 个分段的吊装顺序和起吊时间，使得所需要的资源能够合理配置。船台吊装 顺序优化问题可以看作是资源受限项目调度问题在实际工程中的应用。通常 在进行优化时，会选定一个合适的标准作为船台吊装顺序好坏的评价依据， 也即优化的目标，优化目标的好坏对最终吊装顺序优化结果有着很大的影响。 下面是几种常见的资源受限调度问题的优化目标丌： ( 1 ) 最小化项目工期( m i n i m i z et h ep r o j e c td u r a t i o n ) 是在紧前约束和 资源约束的条件下的组合优化问题，解决如何在满足这两个约束条件下，确 8 哈，j ：滨t 稃火学硕十学伊论文 定各个活动的丌始时间，使得项目的总工期最小。 ( 2 ) 资源均衡( r e s o u r c el e v e l i n g ) ：目的是为了节约资源，对有限的资 源进行配置，合理安排项目中各项活动的进度，可以归结为最小化项目工期 问题中对资源分配利用问题的细化研究。 ( 3 ) 最小化项目运作总成本( m i n i m i z et h et o t a lp r o j e c to p e r a t i o nc o s t ) - 项目执行包含各种资源，每种资源消耗一定的成本，将资源折算成成本，在 满足约束条件下，以最小化项目运作总成本为目标进行优化调度。 2 解决资源受限调度问题的优化方法 。 多数的r c p s p 属于n p h a r d 问题，几十年来，由于r c p s p 问题的实际 应用价值，许多学者对其进行了大量的研究，求解的方法也在不断的改进， 总结起来可以归结为以下三种： 1 ) 精确算法( e x a c ts o l u t i o nt e c h n i q u e ) r c p s p 问题提出的初期，研究主要集中于使用精确的数学规划方法来对 这类优化调度问题进行建模和求解，这一方法可以很好地解决静态资源分配 问题，但是对于规模庞大的优化问题并不适用。为克服这一缺点，许多学者 对精确算法进行了深入的研究，分别提出了定界枚举法、分支定界法、隐含 枚举法等一系列有效的求解资源约束问题的方法，其中分支定界法是应用比 较广泛的一种。 分支定界法于2 0 世纪6 0 年代由l a n dd o i n g 和d a k i n 提出，由分支和定 界两部分组成，其主要原理就是利用搜索树将问题的解空间按照一定的规则 分割成多个子空间，然后通过合理的定界方法除去不必再进行搜索的子空间， 不断地重复以缩小搜索空间，直到最后找到最优解引。但是，由于分支定界 法占用的计算机内存空间大，求解时间过长，加上优化问题的规模不断增加， 使得该类算法越来越不适合这类问题的求解。 2 ) 启发式算法( h e u r i s t i ca l g o r i t h m ) 启发式算法是相对于精确算法提出的，由于一些组合优化问题还没有找 到求得最优解的算法，为避免搜索状态空间“组合爆炸现象，提出了启发 9 哈，j ：滨t 样人。学硕十号：何论文 式算法用来求解复杂的组合优化问题。采用启发式算法求解时虽然不能保证 求得的解是最优解，但是却可以在较短的时间内求得大规模问题的近似最优 解9 1 。启发式算法中具有重要意义的就是k e l l e y 提出进度生成机制( s g s ) 的概念，自此以后，许多学者以进度生成机制为框架，提出了多种启发式方 法。其中基于优先规则的启发式算法是求解r c p s p 问题的一种典型的启发式 方法。基于优先规则的启发式算法由进度生成机制和优先规则构成，进度生 成机制有两种，串行进度生成机制和并行进度生成机制。算法的有效性和效 率则取决于计算优先权系数所采用的优先规则2 1 1 。 启发式算法具有简单易行、比较直观、速度快、程序运行简单以及易于 修改等优点，但是同时也存在着诸如不能保证得到最优解、算法的性能依赖 实际经验，没有规律可循等缺点。 3 ) 智能优化方法 智能优化方法的出现为解决n p h a r d 问题提供了一种新的思路，许多学 者将其应用到r c p s p 问题求解中，并取得了较好的效果。其中l e e 和k i m 口引、 b o c t o r t 2 3 1 ，b o u l e i m e n 和l e c o c q 分别采用模拟退火算法对r c p s p 问题的求 解进行了研究；b a 一2 5 1l e e 和k i m 口甜，p i n s o n 雎6 1 则采用禁忌搜索算法对r c p s p 问题进行了研究；l e e 和k i m 伫2 1 在1 9 9 6 年提出用遗传算法求解r c p s p 问题， 文章中采用优先值的编码方式，并使用串行进度生成机制进行解码，而后 a l c a r a z 和m a r a t o 弘刀，h a r t m a n n 口剐也采用遗传算法对r c p s p 问题进行了研究； 另外我国学者也进行了相关的研究，张维存口叼等人提出用蚁群算法和粒子群 算法相结合的方式求解多模式资源受限项目调度问题，采用基于任务的编码， 串行进度生成机制解码；另外单洲源p 卅等人使用改进的粒子群算法求解 r c p s p 问题，都取得了较好的效果。 1 3 论文研究的主要内容 经分析，本文的研究内容主要有如下几部分： ( 1 ) 采用粒子群算法解决船台吊装顺序优化问题，分析粒子群算法的优 l o 哈尔滨+ 1 i 稃大学硕十学何论文 化原理，对粒子群算法进行改进，并采用典型的测试函数对改进p s o 的收敛 精度和收敛速度进行验证，确保改进p s o 应用于求解船台吊装顺序优化的可 靠性。 ( 2 ) 给出船台吊装顺序优化系统。采用带约束有向图搜索算法对船台吊 装顺序规划方法进行研究，阐述了船台吊装网络图的构建方法和参数计算方 法，为船台吊装顺序优化奠定基础。 ( 3 ) 分析船台吊装过程的特点，将r c p s p 问题应用于船台吊装顺序优 化问题中，构建以最短工期为优化目标的船台吊装顺序多资源优化模型；并 考虑到实际建造过程中会出现的突发情况对预定建造计划的影响，构建突发 情况下的船台吊装顺序优化模型。 ( 4 ) 设计改进p s o 应用于船台吊装顺序多资源优化问题的粒子编码和 解码方法，并给出具体的实现流程：分析突发情况下船台吊装顺序优化数学 模型的特点和优化目标，给出采用改进p s o 求解该问题的具体实现方法；最 后以典型的r s p c p 问题算例对所设计的改进p s o 求解船台吊装顺序优化问 题的方法进行验证，确保设计的合理性。 ( 5 ) 将本文提出的船台吊装顺序优化方法应用到某型号油轮主船体的分 段吊装顺序优化问题中。构建该船主船体分段吊装网络图，采用改进p s o 对 船台吊装网络图进行优化，得到最短吊装工期以及各个分段的起吊时间，并 对优化的结果进行分析。 哈尔滨一掣人学硕十学位论文 第2 章粒子群优化算法研究 船台大合拢阶段是船舶建造过程的最终环节，也是最关键的环节。船台 吊装网络的设计是非常复杂的问题。船台吊装过程包括许多工艺要求，如底 部的龙骨要首先进行吊装，需要大型辅助设备的分段，要在用以安放其辅助 设备的基础分段吊装完成后才能吊装。同时，船体分段吊装过程中涉及到大 量资源的使用，如何合理配置资源，需要制定详细的吊装顺序计划。对一艘 大型船舶，船体通常由几十个甚至几百个分段组成，传统的船台吊装网络优 化和实际吊装过程的实施，主要凭借技术人员的经验、资格和能力进行调度 和协调，造成船厂内各生产车间、部门、工种、船台之间在时间、空间上的 矛盾，无法从整体上进行协调，使计划失控，如果考虑资源的使用，情况将 更严重。因此，对船台吊装网络的优化需要采用新的方法。 随着计算机技术和优化方法的发展，一类智能优化方法逐渐发展起来， 并在实际工程应用中取得较好的效果，具有代表性的包括遗传算法，蚁群算 法等，但是这类算法存在着编码解码困难，优化速度慢等问题。粒子群算法 是近几年发展起来的一种智能仿生类优化方法，由于其良好的优化性能及其 编码简单的特点，很快得到了广泛的应用。本章提出采用粒子群算法对船台 吊装顺序进行优化，通过分析粒子群算法的基本原理，对算法进行改进，并 采用典型的测试函数验证算法的合理性，保证粒子群算法应用于船台吊装网 络优化问题的正确性。 2 1 粒子群算法的基本原理 由于受到人工生命研究中对鸟群社会行为模拟所得到结论的启发，j a m e s k e n n e d y 和r u s s e l le b e r h a r t p 。卯于19 9 5 年提出了粒子群优化算法( p a r t i c l e s w a r mo p t i m i z a t i o n ，p s o ) 。p s o 算法是一种基于群体智能方法的演化计算 技术，具有算法简单，易于实现，参数少等优点，在连续优化问题和离散优 1 2 哈尔溟i ：样人。孚：硕十导：伊论文 化问题中都表现出良好的效果，特别是其天然的实数编码特点非常适合于处 理实际优化问题。 2 1 1算法的数学描述 在粒子群算法中，优化问题的每个解都是搜索空间中的一个点，称之为 粒子，每个粒子具有一个适应值，适应值由具体优化问题的目标函数而定。 同时，每个粒子还具有自己的速度和位置，用来决定粒子的飞行方向和距离。 算法通过将解空间初始化为一群随机粒子，经过不断的迭代更新，来寻找优 化问题的最优解p 3 3 4 1 。 设在一个疗维的搜索空间内，有一个由m 个粒子组成的种群，表示为 x = x i ，薯，x m ，第f 个粒子的位置为薯= ( 确，t 2 ，薯3 ，) ，第i 个粒子 的速度为v = ( v i i , v ：，u 。，) ，第f 个粒子的个体最优位置为 b = ( b ，b 2 ，b 3 ，办) ，种群的全局最优位置为p g = ( 终l ，p s 2 ，熙3 ，) ， 一般来说，粒子的位置和速度都是在连续的实数空间内进行取值。粒子的位 置和速度的变化更新方程如下： 略1 = 吃+ q ( 以一) + c 2 吃( 砖一) ( 2 1 ) 嚣= + 略 ( 2 2 ) 其中，d = 1 ，2 ，3 ，z ，i = l ，2 ，3 ，m ，肌为种群规模，k 表示 种群当i j i 进化的代数。q 和岛称为学习因子或加速系数。和是均匀分布 在 o ，1 】之间的随机数。吃和分别表示粒子i 在第k 次迭代过程中第d 维 的速度值和当前位置值。p 0 表示粒子f 在第k 次迭代第d 维的个体最优位置 值，p 0 表示整个种群在第k 次迭代第d 维的全局最优位置值。为了防止粒子 在搜索过程中由于速度过大而偏离搜索空间，粒子的每一维速度屹都会被限 制在【- 瓤，v m 。】之间p 5 1 。 如图2 1 所示为粒子的迭代原理图p 6 1 ，粒子在下一次寻优时，其速度1 ，m 要受到粒子上次迭代速度v ，、粒子向个体最优位置飞行的速度，。和粒子向全 局最优位置飞行的速度v 。，三个因素的影响，由这三个分量的加权值构成。第 哈尔滨t 稃入学硕十学伊论文 一个是粒子自身的速度v j ，这是粒子飞行中的惯性作用，是粒子能够进行下 一次飞行的基本保证：第二个是个体最优引起的速度v 。，是粒子自我认知的 部分，表示粒子飞行中考虑到自身的经验，向自己曾经找到过的最好点靠近； 第三个是全局最优引起的速度v 。，是粒子的社会经验部分，表示粒子飞行中 考虑到