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

Scheduling algorithm for flexible job shop based on pruning and layering

作　　者：桂忠艳 杨静[1] 谢志强[3] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]黑龙江中医药大学医学信息工程学院,哈尔滨150040 [3]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《控制与决策》2017年第11期1921-1932,共12页Control and Decision

基　　金：国家自然科学基金项目(61672179;61370083;61402126;61370086);高等学校博士学科点专项科研基金项目(20122304110012);黑龙江省博士后基金项目(LBH-Z14071)

摘　　要：针对柔性作业车间调度中工序间存在的冗余调度次序约束关系问题和工序-设备间存在的多加工模式情况,提出基于剪枝分层的柔性加工车间调度算法.该算法首先用有向无环图表示工序及工序间的调度次序关系,采用剪枝法消除图中的冗余弧,采用分层法对图中结点分层;其次对加工模式进行分类,制定工序-设备预约策略和工序-设备预分配策略;最后,采用事件驱动策略,驱动时刻按所提出的柔性加工策略调度工序加工.理论分析和实例表明,所提出的算法具有较好的调度效果.In flexible job shop scheduling, two problems are studied,which are the redundancy scheduling sequence constraint among procedures and the multi-mode processing between procedures and devices. Therefore, a scheduling algorithm for flexible job shop based on pruning and layering is proposed. The algorithm first uses the directed acyclic graph（DAG） to represent the procedures and the scheduling sequence constraints among procedures, the pruning strategy to eliminate the redundant in the DAG, and the layering strategy to layer the nodes in the DAG. Then the processing mode of procedures is classified, and the procedure-device booking strategy and procedure-device pre-allocation strategy are designed. Finally, by using the event-driven scheduling strategy, at the driver moment. The procedure is scheduled according to the proposed flexible processing strategy. Theoretical analysis and practical examples proves that the proposed algorithm has a better result.

关 键 词：剪枝分层 工序-设备预约 工序-设备预分配 柔性加工策略 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]