基于剪枝分层的柔性加工车间调度算法

《基于剪枝分层的柔性加工车间调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第32卷第11期控制与决策Vol.32No.112017年11月ControlandDecisionNov.2017文章编号:1001-0920(2017)11-1921-12DOI:10.13195/j.kzyjc.2016.1018基于剪枝分层的柔性加工车间调度算法桂忠艳1;2,杨静1y,谢志强3(1.哈尔滨工程大学计算机科学与技术学院，哈尔滨150001；2.黑龙江中医药大学医学信息工程学院,哈尔滨150040；3.哈尔滨理工大学计算机科学与技术学院，哈尔滨150080)摘要:针对柔性作业车间调度中工序间存在的冗余调度次序约束关系问题和工序-设备间存在的多加工模式情况,提出基于剪枝分层的

2、柔性加工车间调度算法.该算法首先用有向无环图表示工序及工序间的调度次序关系,采用剪枝法消除图中的冗余弧,采用分层法对图中结点分层;其次对加工模式进行分类,制定工序-设备预约策略和工序-设备预分配策略;最后,采用事件驱动策略,驱动时刻按所提出的柔性加工策略调度工序加工.理论分析和实例表明,所提出的算法具有较好的调度效果.关键词:剪枝分层；工序-设备预约；工序-设备预分配；柔性加工策略中图分类号:TP278文献标志码:ASchedulingalgorithmforflexiblejobshopbasedonpruningandlayeringGUIZhong-yan1;2,YANGJing1y,XI

3、EZhi-qiang3(1.CollegeofComputerScienceandTechnology，HarbinEngineeringUniversity，Harbin150001，China；2.CollegeofMedicalInformationEngineering，HeilongjiangUniversityofChineseMedicine，Harbin150040，China；3.CollegeofComputerScienceandTechnology，HarbinUniversityofScienceandTechnology，Harbin150080，China)Abs

4、tract:Inflexiblejobshopscheduling,twoproblemsarestudied,whicharetheredundancyschedulingsequenceconstraintamongproceduresandthemulti-modeprocessingbetweenproceduresanddevices.Therefore,aschedulingalgorithmforflexiblejobshopbasedonpruningandlayeringisproposed.Thealgorithmfirstusesthedirectedacyclicgraph(

5、DAG)torepresenttheproceduresandtheschedulingsequenceconstraintsamongprocedures,thepruningstrategytoeliminatetheredundantintheDAG,andthelayeringstrategytolayerthenodesintheDAG.Thentheprocessingmodeofproceduresisclassified,andtheprocedure-devicebookingstrategyandprocedure-devicepre-allocationstrategyar

6、edesigned.Finally,byusingtheevent-drivenschedulingstrategy,atthedrivermoment.Theprocedureisscheduledaccordingtotheproposedflexibleprocessingstrategy.Theoreticalanalysisandpracticalexamplesprovesthattheproposedalgorithmhasabetterresult.Keywords:pruningandlayering；procedure-devicebooking；procedure-devi

7、cepre-allocation；flexibleprocessingstrategy0ᕅ言描述不一致、编码译码方法复杂等问题),提出了柔性车间调度问题(FJSP)[1-2]是对传统作业车间一种基于遗传算法求解FJSP的方法,将带有部分柔调度问题(FJSP)[3-4]的扩展,它突破了机器约束和作性和准时生产要求的JSP转换为一般FJSP,并给出业加工路线固定的限制,每道作业可以在一台或多台了统一的数