船体不规则分段的动态空间调度算法

《船体不规则分段的动态空间调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第６期运筹与管理Ｖｏｌ．２３，Ｎｏ．６２０１４年１２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＤｅｃ．２０１４船体不规则分段的动态空间调度算法马少辉，陆春霞（江苏科技大学经济管理学院，江苏镇江２１２００３）摘要：提出了一种基于遗传算法的针对船体不规则分段的动态空间调度方法．基于遗传算法和临界多边形算法直接对不规则分段进行优化调度，提高空间的利用率。首先，利用遗传算法产生多个可行的分段调度序列。然后，基于临界多边形算法及重心最低策略，根据分段调度序列一一确定各不规则分段的空间位置。

2、充分考虑到空间调度问题所特有的动态性和时空关联性，同时以场地利用率和未延迟加工分段所占比例的综合加权和作为评价函数，实现了调度方案的全局优化。以江苏澄西船厂大型散货船的１１９个不规则分段作为实验数据，并通过多个算法的比较，发现该动态调度算法可以快速收敛得到较优解，并且在空间利用率和延迟分段指标上有了提高，最终可以得到比较理想的调度结果，证明了所提方法在动态空间调度问题上的有效性和优越性。关键词：动态空间调度；临界多边形；遗传算法；不规则分段中图分类号：Ｆ４２３．１文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０６-

3、０２８１-０７ADynamicSpatialSchedulingAlgorithmforIrregularBlocksinShipbuildingＭＡＳｈａｏ-ｈｕｉ，ＬＵＣｈｕｎ-ｘｉａ（SchoolofEconomicsandManagement，JiangsuUniversityofScienceandTechnology，Zhenjiang２１２００３，China）Abstract：Ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｄｙｎａｍｉｃｓｐａｔｉａｌｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｉｒｒｅｇｕｌａｒｂｌｏｃ

4、ｋｓｉｎｓｈｉｐｂｕｉｌｄｉｎｇ．Ｗｅｓｃｈｅｄｕｌｅｔｈｅｉｒｒｅｇｕｌａｒｂｌｏｃｋｓｄｉｒｅｃｔｌｙｂａｓｅｄｏｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ（ＧＡ）ａｎｄｎｏ-ｆｉｔｐｏｌｙｇｏｎ（ＮＦＰ）ａｌｇｏｒｉｔｈｍ．Ｆｉｒｓｔ，ＧＡｉｓｕｓｅｄｔｏｄｅｔｅｒｍｉｎｅｔｈｅｏｐｔｉｍａｌｐｒｏｃｅｓｓｉｎｇｓｅｑｕｅｎｃｅ．Ｔｈｅｎｗｅｕｓｅｎｏ-ｆｉｔｐｏｌｙｇｏｎａｎｄｌｏｗｅｓｔｓｈａｐｅｇｒａｖｉｔｙｃｅｎｔｅｒｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｔｏａｌｌｏｃａｔｅａｌｌｔｈｅｂｌｏｃｋｓｉｎａｇｅｎｅｓｅｑ

5、ｕｅｎｃｅｇｅｎｅｒａｔｅｄｂｙｇｅｎｅａｌｇｏｒｉｔｈｍｉｎｔｏｔｈｅｗｏｒｋ-ｐｌａｃｅ，ａｎｄｔｈｅｎｗｅｃａｎｏｂｔａｉｎｔｈｅｆｉｎａｌｓｐａｃｅｓｃｈｅｄｕｌｅｌａｙｏｕｔｇｒａｐｈ．Ｗｅｕｓｅｂｏｔｈｔｈｅａｖｅｒａｇｅｓｐａｃｅｕｔｉｌｉｚａｔｉｏｎｒａｔｉｏａｎｄｔｈｅｎｕｍｂｅｒｏｆｕｎｄｅｌａｙｅｄｂｌｏｃｋｓａｓｔｈｅｏｂｊｅｃｔｉｖｅｓ，ａｎｄｉｎｔｅｇｒａｔｅｔｈｅｔｗｏｏｂｊｅｃｔｉｖｅｓｉｎｔｏｏｎｅｅｖａｌｕａｔｉｏｎｆｕｎｃｔｉｏｎｗｉｔｈｗｅｉｇｈｔｓ，ｗｈｉｃｈｆｕｌｌｙｃｏｎｓｉｄ

6、ｅｒｓｔｈｅｄｙｎａｍｉｃｎａｔｕｒｅａｎｄｔｈｅｃｏｒｒｅｌａｔｉｏｎｂｅｔｗｅｅｎｔｉｍｅａｎｄｓｐａｃｅｉｎａｓｐａｔｉａｌｓｃｈｅｄｕｌｅｐｒｏｂｌｅｍ．Ｆｉｎａｌｌｙ，ｗｅｕｓｅｔｈｅｄａｔａｉｎｃｌｕｄｉｎｇ１１９ｂｌｏｃｋｓｏｆａｂｉｇｂｕｌｋｃａｒｇｏｃａｒｒｉｅｒｗｈｉｃｈｗａｓｂｕｉｌｔｂｙｔｈｅＣｈｅｎｇｘｉｓｈｉｐｂｕｉｌｄｉｎｇｃｏｍｐａｎｙｉｎＪｉａｎｇｓｕｐｒｏｖｉｎｃｅｏｆＣｈｉｎａａｓｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｄａｔａ．Ｗｅｃｏｍｐａｒｅｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｗｉｔｈ

7、ｓｅｖｅｒａｌｃｏｍｐｅｔｉｎｇａｌｇｏｒｉｔｈｍｓ，ａｎｄｆｉｎｄｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｄｙｎａｍｉｃｓｃｈｅｄｕｌｅａｌｇｏｒｉｔｈｍｃｏｎ-ｖｅｒｇｅｎｃｅｓｓａｔｉｓｆｙｔｈｅｓｏｌｕｔｉｏｎｒａｐｉｄｌｙ．Ｂｏｔｈｔｈｅｓｐａｃｅｕｔｉｌｉｚａｔｉｏｎｒａｔｅａｎｄｄｅｌａｙｅｄｂｌｏｃｋｃａｎｂｅｉｍｐｒｏｖｅｄｃｏｍｐａｒｅｄｔｏｔｈｅｒｅｓｕｌｔｆｒｏｍｃｏｍｐｅｔｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐｒｏｖｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃａｎｏｂｔａｉｎｉ

8、ｄｅａｌｓｃｈｅｄｕ-ｌｉｎｇｒｅｓｕｌｔｓａｎｄｉｓｅｆｆｅｃｔｉｖｅａｎｄｓｕｐｅｒｉｏｒｉｎｄｅａｌｉｎｇｗｉｔｈｄｙｎａｍｉｃｓｐａｃｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ．Keywords：ｄｙｎａｍｉｃｓｐａｔｉａｌｓｃｈｅｄｕｌｉｎｇ；Ｎｏ-ｆｉｔＰｏｌｙｇｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔ