基于工序集的动态关键路径多产品制造调度算法

《基于工序集的动态关键路径多产品制造调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３４卷第２期计算机学报Ｖｏｌ．３４Ｎｏ．２２０１１年２月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＦｅｂ．２０１１基于工序集的动态关键路径多产品制造调度算法谢志强１），２）杨静１）周勇２）张大力３）谭光宇４）１）（哈尔滨工程大学计算机科学与技术学院哈尔滨１５０００１）２）（哈尔滨理工大学计算机科学与技术学院哈尔滨１５００８０）３）（卡尔加里大学数学与统计系加拿大）４）（哈尔滨理工大学机械动力工程学院哈尔滨１５００８０）摘要针对已有的树状结构多产品加工和装配综合调度方法，不能兼顾树状结构纵横双向、影响调度结果的问题，提出

2、基于工序集的动态关键路径多产品制造调度算法．该算法首先采用根对齐的方法，将多个树状结构的产品转化成一个虚拟加工树，使多产品调度问题简化为单产品调度问题；在调度过程中，根据虚拟加工树动态生成可调度的备选工序集合，按提出的动态关键路径策略和短用时调度策略从备选集中选择工序，并应用首次适应调度法调度工序，直到备选集合为空，即所有产品加工完毕，实现以纵向为主兼顾横向的双向调度优化．实例证明，算法对多产品加工和装配综合调度问题可以获得更优的解．关键词动态关键路径；虚拟加工树；备选工序集；多产品制造；首次适应调度法中图法分类号ＴＰ２７８犇犗

3、犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１１．００４０６犇狔狀犪犿犻犮犆狉犻狋犻犮犪犾犘犪狋犺狊犕狌犾狋犻犘狉狅犱狌犮狋犕犪狀狌犳犪犮狋狌狉犻狀犵犛犮犺犲犱狌犾犻狀犵犃犾犵狅狉犻狋犺犿犅犪狊犲犱狅狀犗狆犲狉犪狋犻狅狀犛犲狋ＸＩＥＺｈｉＱｉａｎｇ１），２）ＹＡＮＧＪｉｎｇ１）ＺＨＯＵＹｏｎｇ２）ＺＨＡＮＧＤａＬｉ３）ＴＡＮＧｕａｎｇＹｕ４）１）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犎犪狉犫犻狀犈狀犵犻狀犲犲狉犻狀犵犝狀犻狏犲狉狊犻狋狔，犎犪狉犫犻狀１５０００１）２）（犛犮犺狅狅犾

4、狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犎犪狉犫犻狀犝狀犻狏犲狉狊犻狋狔狅犳犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犎犪狉犫犻狀１５００８０）３）（犇犲狆犪狉狋犿犲狀狋狅犳犕犪狋犺犲犿犪狋犻犮狊犪狀犱犛狋犪狋犻狊狋犻犮狊，犝狀犻狏犲狉狊犻狋狔狅犳犆犪犾犵犪狉狔，犆犪狀犪犱犪）４）（犛犮犺狅狅犾狅犳犕犲犮犺犪狀犻犮犪犾犘狅狑犲狉犈狀犵犻狀犲犲狉犻狀犵，犎犪狉犫犻狀犝狀犻狏犲狉狊犻狋狔狅犳犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犎犪狉犫犻狀１５００８０）犃犫狊狋狉犪犮狋Ａｉｍｉｎｇａｔｔｈｅｐｒｏｂｌｅｍｔ

5、ｈａｔｍｕｌｔｉｐｒｏｄｕｃｔｐｒｏｃｅｓｓｉｎｇｏｆｔｒｅｅｓｔｒｕｃｔｕｒｅａｎｄａｓｓｅｍｂｌｙｉｎｔｅｇｒａｔｅｄｓｃｈｅｄｕｌｉｎｇｆｏｒｓｃｈｅｍｅｓｅｘｉｓｔｉｎｇｃａｎｎｏｔｔａｋｅｉｎｔｏａｃｃｏｕｎｔｖｅｒｔｉｃａｌａｎｄｈｏｒｉｚｏｎｔａｌｏｆｔｈｅｔｒｅｅｓｔｒｕｃｔｕｒｅｓｏｔｈａｔａｆｆｅｃｔｔｈｅｓｃｈｅｄｕｌｉｎｇｒｅｓｕｌｔ，ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓｍｕｌｔｉｐｒｏｄｕｃｔｍａｎｕｆａｃｔｕｒｉｎｇｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｄｙｎａｍｉｃｃｒｉｔｉｃａｌｐａｔｈｓｂ

6、ａｓｅｄｏｎｏｐｅｒａｔｉｏｎｓｅｔ．Ｔｈｅａｌｇｏｒｉｔｈｍｃｏｎｖｅｒｔｓｍｕｌｔｉｐｒｏｄｕｃｔｓｏｆｔｒｅｅｓｔｒｕｃｔｕｒｅｉｎｔｏａｖｉｒｔｕａｌｍａｎｕｆａｃｔｕｒｉｎｇｔｒｅｅｉｎｔｈｅｗａｙｏｆｒｏｏｔａｌｉｇｎｍｅｎｔ，ａｎｄｓｉｍｐｌｉｆｉｅｓｔｈｅｍｕｌｔｉｐｒｏｄｕｃｔｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｔｏｔｈｅｓｉｎｇｌｅｐｒｏｄｕｃｔｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ．Ｉｎｔｈｅｐｒｏｃｅｓｓｏｆｓｃｈｅｄｕｌｉｎｇ，ａｓｔａｎｄｂｙｏｐｅｒａｔｉｏｎｓｅｔｉｓｄｙｎａｍｉｃａｌｌｙｇｅｎｅｒａ

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

8、ｃａｌａｎｄｈｏｒｉｚｏｎｔａｌｓｃｈｅｄｕｌｉｎｇｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｔｉｓｖａｌｉｄａｔｅｄｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｏｂｔａｉｎｆａｖｏｒａｂｌｅｒｅｓｕｌｔｆｏｒｔｈｅｍｕｌｔｉｐｒｏｄｕｃｔｐｒｏｃｅｓｓｉｎｇａｎｄａｓｓｅｍｂ