存在多设备工序的综合调度算法.pdfVIP

学兔兔 第 50卷第 24期 机 械 工 程 学 报 VO1．50 NO．24 2014年 12月 JOURNALOFMECHANICALENGINEERING Dec． 20l4 DoI： lO．3901／JM E．2014．24．191 存在多设备工序的综合调度算法术 谢志强 ，2 齐永红 杨 静2 f1．哈尔滨理工大学计算机学院 哈尔滨 150080； 2．哈尔滨工程大学计算机学院 哈尔滨 150001) 摘要：针对工序集中存在需要多台设备协同完成加工的多设备工序的综合调度问题，提出一种把多设备工序设计成在多个相 关设备上同时加工的多个虚拟工序的方法。该算法把产品加工树转化为多设备工序被设计成虚拟工序组的虚拟加工工艺树， 为了优先调度虚拟工序组，将虚拟加工工艺树分解为以虚拟工序组为根结点的子树和剩余标准工序组成的子树，优先调度以 虚拟工序组为根结点的子树；当以虚拟工序组为根结点的子树不唯一时，按子树上虚拟工序组个数多少确定子树的调度次序； 对每个以虚拟工序组为根结点的子树，优先调度虚拟工序组个数较多的路径上工序：为了使相关虚拟工序同时开始加工，提 出虚拟工序动态调整策略。理论分析和实例表明，所提出的调度算法能够较好地解决存在多设备工序的综合调度问题。 关键词：综合调度；多设备工序；虚拟工序；虚拟工序组；虚拟工序动态调整策略 中图分类号：TP278 IntegratedSchedulingAlgorithm withM ultiple--devices-·operation XIEZhiqiang， QIYonghong YANGJing (1．CollegeofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080； 2．CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001) Abstract：Aimingatintegratedschedulingproblem withmultiple—devices-operation，amethodtochangemultiple·devices—operation into multiple related virtualoperationswhich processeson multiplerelated machinesatthe same timeisproposed．Product processingtreeischangedintovirtualprocessingtree，onwhicheachmultiple—devices—operationischangedintoavirtualoperation group．Virtualprocessingrteeisdecomposedintosubtreewhoserootnodeisvirtualoperationrgoupandsubtreethatcomposedof remainingstandardoperations．Thesubtreewhoserootnodeisvirtualoperation groupisscheduledpreviously；W henthesubtree whoserootnodeisvirtualoperationgroupisnotunique，theschedulingorderofthesubtreeisdeterminedaccordingtothenumberof virtualoperationgroup．Theschedulingorderofoperationson subrteewhoserootn