动态空间调度的混合遗传算法

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

1、第２２卷第２期运筹与管理Ｖｏｌ．２２，Ｎｏ．２２０１３年４月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＡｐｒ．２０１３动态空间调度的混合遗传算法马少辉，王景秋，陆春霞，葛世伦（江苏科技大学经济管理学院，江苏镇江２１２００３）摘要：提出了一种基于混合遗传算法的动态空间调度方法。首先利用遗传算法产生多个可行的分段调度序列，再采用动态决定分段位置的启发式算法———平均最大空闲矩形策略对遗传算法产生的调度序列进行解码。同时以完工时间和平台利用率的加权和作为适应度函数，充分考虑了空间调度问题所特有的动态性和时空关联性。遗传进化过程收敛后得到近似最

2、优解，实现了调度方案的全局优化。对船厂实际生产数据进行了实证分析以及与其它算法的对比分析，证明了所提方法在空间调度问题上的有效性和实用性。关键词：运筹学；动态空间调度；遗传算法；启发式定位策略中图分类号：Ｆ４２３．１文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０２-００９９-０６ADynamicSpatialSchedulingApproachBasedonHybridGeneticAlgorithmＭＡＳｈａｏ-ｈｕｉ，ＷＡＮＧＪｉｎｇ-ｑｉｕ，ＬＵＣｈｕｎ-ｘｉａ，ＧＥＳｈｉ-ｌｕｎ（SchoolofEconomicsandManagement，Unive

3、rsityofScienceandTechnology，Zhenjiang２１２００３，China）Abstract：Ｉｎｔｈｉｓｐａｐｅｒｗｅｐｒｏｐｏｓｅａｄｙｎａｍｉｃｓｐａｔｉａｌｓｃｈｅｄｕｌｉｎｇａｐｐｒｏａｃｈｂａｓｅｄｏｎｈｙｂｒｉｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ（ＧＡ）．ＧＡｉｓｕｓｅｄｔｏｄｅｔｅｒｍｉｎｅｔｈｅｏｐｔｉｍａｌｐｒｏｃｅｓｓｉｎｇｓｅｑｕｅｎｃｅ．Ｉｎｔｈｅｐｒｏｃｅｓｓｏｆｄｅｃｏｄｉｎｇ，ｔｈｅｌｏｃａｔｉｏｎｏｆｗｏｒｋｐｉｅｃｅｓｉｓｄｅｔｅｒｍｉｎｅｄｂｙａｄｙｎａｍｉｃｈｅｕｒｉｓｔｉｃｌｏｃａｔｉｏｎｓｔｒａｔｅｇｙ，

4、ｃａｌｌｅｄａｎａｖｅｒａｇｅｍａｘｉｍｉｚｅｄｉｄｌｅｒｅｃｔａｎｇｌｅｓｔｒａｔｅｇｙ．Ｗｅｕｓｅｔｈｅｗｅｉｇｈｔｅｄｃｏｍｐｌｅｔｉｏｎｔｉｍｅａｎｄｓｐａｃｅｕｔｉｌｉｚａｔｉｏｎａｓｔｈｅｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎ，ｗｈｉｃｈｆｕｌｌｙｃｏｎｓｉｄｅｒｓｔｈｅｄｙｎａｍｉｃｎａｔｕｒｅａｎｄｔｈｅｃｏｒｒｅｌａｔｉｏｎｂｅｔｗｅｅｎｔｉｍｅａｎｄｓｐａｃｅｉｎａｓｐａｃｅｓｃｈｅｄｕｌｅｐｒｏｂｌｅｍ．Ｅｖｅｒｙｉｎｄｉｖｉｄｕａｌｉｎｐｏｐｕｌａｔｉｏｎｉｓａｓｃｈｅｄｕｌｉｎｇｓｅｑｕｅｎｃｅ，ａｎｄｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｃａｎｂｅｆｏ

5、ｕｎｄｉｎｔｈｅｐｒｏｃｅｓｓｏｆｅｖｏｌｕｔｉｏｎ．Ｆｉｎａｌｌｙ，ｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓａｎｄｔｈｅｐｒａｃｔｉｃａｂｉｌｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍａｒｅｃｏｎｆｉｒｍｅｄｂｙｂｏｔｈａｓｉｍｕｌａｔｉｏｎｓｔｕｄｙａｎｄｅｍｐｉｒｉｃａｌｃｏｍｐａｒａｔｉｖｅｓｔｕｄｙｂａｓｅｄｏｎｔｈｅａｃｔｕａｌｄａｔａｏｆａｓｈｉｐｙａｒｄ．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈ；ｄｙｎａｍｉｃｓｐａｔｉａｌｓｃｈｅｄｕｌｉｎｇ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｈｅｕｒｉｓｔｉｃｌｏｃａｔｉｏｎｓｔｒａｔｅｇｙ０引言空间调度问题是一类时间

6、和空间耦合的调度问题。除了具有基于时间约束的传统调度问题所具有的分段的开工时间、加工时间、交货期等时间属性外，还包括了另一类重要的资源———空间资源。空间资源有一定的大小，一般具有规则的形状，在加工过程中被加工对象占用，可重复使用。空间上要求与加工空间边界以及其他在加工物之间互不干涉；时间上要求满足加工顺序、完成时间等时间约束。调度方案要在同时满足时间和空间约束的基础上，给出加工对象的开工时间和加工的具体位置及放置方向。空间调度问题起源于船舶建造领域。一艘大型船舶通常由上百个分段在船坞焊接而成。这些分段通常有百吨重，且大小不一、形状各异、加工周期不同，需要在车间的特定地

7、点在起重机的协助下进行预先建收稿日期：２０１１-０７-０９基金项目：国家自然科学基金资助项目（７０８７１０５７，７１１７１１００，７０９７１０５６）作者简介：马少辉（１９７２-），男，河北承德人，博士，副教授，主要研究领域为决策支持系统；王景秋（１９８７-），女，湖北十堰人，硕士生，主要研究领域为工业工程；陆春霞（１９８７-），女，山东冠县人，硕士生，主要研究领域为决策支持系统；葛世伦（１９６３-），男，浙江天台人，博士，教授，主要研究领域为管理信息系统。１００运筹与管理２０１３年第２２卷造。由于车间的空间有限，且分段在船坞的组装顺序和时