基于择时的二车间综合调度算法  

Integrated scheduling algorithm of two workshops based on optimal time

作　　者：张晓欢 谢志强[1] 辛宇[1] 杨静[2] ZHANG Xiaohuan XIE Zhiqiang XIN Yu YANG Jing(College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China College of Computer Science and Technology , Harbin Engineering University, Harbin 150080, China)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080 [2]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150080

出　　处：《计算机集成制造系统》2017年第9期1938-1949,共12页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61370086;61370083;61772160);黑龙江省教育厅科技计划资助项目(12531105);黑龙江省博士后基金资助项目(LBH-Q13092;LBH-Z15096);中国博士后资助项目(2016M591541);高等学校博士学科点专项科研基金资助项目(20122304110012)~~

摘　　要：针对现有二车间综合调度算法在处理具有相同设备资源的二车间综合调度问题时,注重工艺树的横向并行处理,忽略纵向串行工序之间的紧密度,将二车间均衡处理或减少工序迁移次数一并做为调度目标导致不必要时间开销的问题,提出了基于择时的二车间综合调度算法。同时,提出了工序序列排序策略,将加工工艺树划分为若干工序序列,并根据其路径长度确定调度次序;提出了二车间择时调度策略,为工序寻找加工开始时间和加工车间,生成使当前部分产品加工总用时最小的工序调度方案。若该方案不唯一,则选择在二车间中该工序加工结束时间最早的工序调度方案。所提算法既保证了并行工序的并行处理,又有效地提高了串行工序的紧密度,避免了无效工序迁移带来的时间开销。通过实例说明了所提算法的有效性。Aiming at the problems that the existing integrated scheduling algorithm of two workshops was always paid attention to the parallel processing but neglected the compactness of serial operations when processed the integrated scheduling problem of two workshops with the same facility resources,and the more time expense would be appeared by taking the balanced processing of two workshops and the migration times as parts of objective,an integrated scheduling algorithm of two workshops based on optimal time was proposed.The sorting strategy of operation sequence was put forward to sort operations,and the scheduling sequences were confirmed based on length of operation sequences.The strategy for optimal time of two workshops was proposed to search the start time and processing workshops for operations,and the operation scheduling scheme which made the current processing time be minimum was generated.If the scheme was not unique,the scheme in which the start time of the operation was earliest would be selected.With the proposed algorithm,parallel processing of operations was assured,compactness of serial operations was raised,and unnecessary time expense caused by migration of operations was avoided.The effectiveness of the proposed algorithm was illustrated by examples.

关 键 词：工序序列 择时策略 二车间 综合调度算法 

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