可动态生成具有优先级工序集的动态Job-Shop调度算法谢志强1)杨静2)杨光1)谭光宇3）1)(哈尔滨理工大学计算机科学与技术学院哈尔滨150080)2)(哈尔滨工程大学计算机科学与技术学院哈尔滨150001)3)(哈尔滨理工大学机械动力工程学院哈尔滨150080)摘要为了在满足约束条件的前提下使不同时刻加入到作业集合中的作业所用的加工总时间尽可能的少，提出算法：根据动态的作业集合构造虚拟加工树，虚拟加工树上的叶结点代表最先加工的工序，虚拟根节点代表最后一道工序，边代表偏序关系；以层优先为虚拟加工树上的工序设置优先级，工序的优先级可作为调度过程中考虑的一个因素；除了在工序需要动态调整的情况下，在调度过程中始终遵循着机器忙原则．在调度过程中，首先根据虚拟加工树动态地生成备选工序集合，然后根据工序的优先级并且结合其它的调度策略从备选集合中调度工序，直到备选集合为空，即所有作业加工完毕．这里提到的调度策略包括短用时策略、长路经策略和动态调整策略．通过实例验证，该算法对于动态Job-Shop问题可以获得比较好的解．关键字车间调度；虚拟加工树；优先级；备选工序集；动态调整中图分类号TP278DynamicJob-ShopSchedulingAlgorithmwithDynamicSetofOperationHavingPriorityXIEZhiqiang1)YANGJing2)YANGGuang1)TANGuangyu3)1)(SchoolofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080)2)(SchoolofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001)3)(SchoolofMechanicalPowerEngineering,HarbinUniversityofScienceandTechnology,Harbin150080)AbstractTomakethetotalprocessingtimeofjobaddedintojobsetatdifferenttimeasshortaspossible,subjecttotheconstraint,anewalgorithmisproposed:avirtualmanufacturingtreeisconstructedaccordingtodynamicjobset,whereleafnodesdenotetheoperationstoprocessfirstly,rootnodesdenotetheoperationstoprocesslastandedgesdenotethepartialrelation,thatisconstraintbetweenoperations;thepriorityofoperationsissetaccordingtolevelofoperationinthevirtualmanufacturingtreeandisregardedasafactorconsideredtoscheduleoperations;astrategyofkeepingmachinebusyisadoptedtomakemachinetryitsbesttoprocessoperationscontinuallyexceptthat本课题得到国家自然科学基金(50575062),黑龙江省自然科学基金(60503020),黑龙江省教育厅重大科学研究项目(10551z0008)和哈尔滨市科技攻关项目(2005AA1CG061-11)资助．谢志强，男，1962年生，博士研究生，教授，研究方向为CIMS和调度优化．E-mail：xzq011@tom.com．杨静，女，1962年生，博士，教授，博士生导师，研究方向为数据挖掘和调度优化．杨光，男，1982年生，硕士研究生，研究方向为调度优化．谭光宇，男，1957年生，博士，教授，博士生导师，研究方向为先进制造技术．1operationsneedbemodifieddynamically.Standbyoperationsetisgenerateddynamicallyaccordingtothevirtualmanufacturingtree,andoperationsinthestandbyoperationset,subjecttothepriority,arescheduledwithShort-timestrategy,Long-pathstrategyandDynamic-adjustmentstrategyuntilthesetisempty,thatisalloperationsunscheduledarefinished.TheexampleshowsthatthealgorithmproposedcanobtainfavorableresultfordynamicJob-Shopschedulingproblem.Keywordsjob-shop;virtualmanufacturingtree;priority;standbyoperationset;dynamicadjustment1引言理论上已经证明了作业车间调度问题是NP-Hard问题．本文所研究的问题是在满足三个约束条件的前提下使分批加工的作业所用的总时间尽可能的少，这三个约束条件是：（1）对于每道工序来说，必须等待其所有的前继工序加工完毕后才能加工此道工序；（2）对于每台机器来说，任意时刻只能加工一道工序，且必须满足加工完一道工序后才能加工另一道工序[1]；（3）不存在相同设备．本文首先对单个作业的加工环节进行分析，在遵循机器忙原则基础上提出了四种调度策略．然后提出了一种构造方法，把动态作业...