首页 | 本学科首页   官方微博 | 高级检索  
     

可动态生成具有优先级工序集的动态Job-Shop调度算法
引用本文:谢志强,杨静,杨光,谭光宇.可动态生成具有优先级工序集的动态Job-Shop调度算法[J].计算机学报,2008,31(3):502-508.
作者姓名:谢志强  杨静  杨光  谭光宇
作者单位:1. 哈尔滨理工大学计算机科学与技术学院,哈尔滨,150080
2. 哈尔滨工程大学计算机科学与技术学院,哈尔滨,150001
3. 哈尔滨理工大学机械动力工程学院,哈尔滨,150080
基金项目:国家自然科学基金(50575062),黑龙江省自然科学基金(F0309,F200608),黑龙江省教育厅重大科学研究项目(10551z0008),哈尔滨市科技攻关项目(2005AA1CG061-11)资助
摘    要:为了在满足约束条件的前提下使不同时刻加入到作业集合中的全部作业所用的加工总时间尽可能地少,提出算法:根据动态的作业集合构造虚拟加工树,虚拟加工树上的叶结点代表最先加工的工序,虚拟根节点代表最后一道工序,边代表偏序关系;以层优先为虚拟加工树上的工序设置优先级,工序的优先级可作为调度过程中考虑的一个因素;除了在工序需要动态调整的情况下,在调度过程中始终遵循着机器忙原则.在调度过程中,首先根据虚拟加工树动态地生成备选工序集合,然后根据工序的优先级并且结合其它的调度策略从备选集合中调度工序,直到备选集合为空,即所有作业加工完毕.这里提到的调度策略包括短用时策略、长路径策略和动态调整策略.通过实例验证,该算法对于动态Job-Shop问题可以获得比较好的解.

关 键 词:车间调度  虚拟加工树  优先级  备选工序集  动态调整
修稿时间:2006年10月25

Dynamic Job-Shop Scheduling Algorithm with Dynamic Set of Operation Having Priority
XIE Zhi-Qiang,YANG Jing,YANG Guang,TAN Guang-Yu.Dynamic Job-Shop Scheduling Algorithm with Dynamic Set of Operation Having Priority[J].Chinese Journal of Computers,2008,31(3):502-508.
Authors:XIE Zhi-Qiang  YANG Jing  YANG Guang  TAN Guang-Yu
Abstract:To make the total processing time of job added into job set at different time as short as possible,subject to the constraint,a new algorithm is proposed:A virtual manufacturing tree is constructed according to dynamic job set,where leaf nodes denote the operations to process firstly,root nodes denote the operations to process last and edges denote the partial relation,that is constraint between operations;the priority of operations is set according to level of operation in the virtual manufacturing tree and is regarded as a factor considered to schedule operations;A strategy of keeping machine busy is adopted to make machine try its best to process operations continually except that operations need be modified dynamically.Standby operation set is generated dynamically according to the virtual manufacturing tree,and operations in the standby operation set,subject to the priority,are scheduled with Short-time strategy,Long-path strategy and Dynamic-adjustment strategy until the set is empty,that is all operations unscheduled are finished.The example shows that the algorithm proposed can obtain favorable result for dynamic Job-Shop scheduling problem.
Keywords:Job-Shop  virtual manufacturing tree  priority  standby operation set  dynamic adjustment
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号