可动态生成具有优先级工序集的动态JobShop调度算法(.doc

PAGE  PAGE 10 可动态生成具有优先级工序集的动态Job-Shop调度算法?本课题得到国家自然科学基金, 黑龙江省自然科学基金 , 黑龙江省教育厅重大科学研究项目(10551z0008)和哈尔滨市科技攻关项目(2005AA1CG061-11)资助．谢志强，男，1962年生，博士研究生，教授，研究方向为CIMS和调度优化．E-mail： HYPERLINK mailto:xzq011@ xzq011@．杨静，女，1962年生，博士，教授，博士生导师，研究方向为数据挖掘和调度优化．杨光，男，1982年生，硕士研究生，研究方向为调度优化．谭光宇，男，1957年生，博士，教授，博士生导师，研究方向为先进制造技术． 谢志强1) 杨 静2) 杨 光1) 谭光宇3） 1) (哈尔滨理工大学 计算机科学与技术学院 哈尔滨 150080) 2) (哈尔滨工程大学 计算机科学与技术学院 哈尔滨 150001) 3) (哈尔滨理工大学 机械动力工程学院 哈尔滨 150080) 摘 要 为了在满足约束条件的前提下使不同时刻加入到作业集合中的作业所用的加工总时间尽可能的少，提出算法：根据动态的作业集合构造虚拟加工树，虚拟加工树上的叶结点代表最先加工的工序，虚拟根节点代表最后一道工序，边代表偏序关系；以层优先为虚拟加工树上的工序设置优先级，工序的优先级可作为调度过程中考虑的一个因素；除了在工序需要动态调整的情况下，在调度过程中始终遵循着机器忙原则．在调度过程中，首先根据虚拟加工树动态地生成备选工序集合，然后根据工序的优先级并且结合其它的调度策略从备选集合中调度工序，直到备选集合为空，即所有作业加工完毕．这里提到的调度策略包括短用时策略、长路经策略和动态调整策略．通过实例验证，该算法对于动态Job-Shop问题可以获得比较好的解． 关键字 车间调度；虚拟加工树；优先级；备选工序集；动态调整 中图分类号 TP278 Dynamic Job-Shop Scheduling Algorithm with Dynamic Set of Operation Having Priority XIE Zhiqiang 1) YANG Jing2) YANG Guang1) TAN Guangyu3) 1) (School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080) 2) (School of Computer Science and Technology, Harbin Engineering University, Harbin 150001) 3) (School of Mechanical Power Engineering, Harbin University of Science and Technology, Harbin 150080) 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