1.一种含不可靠资源制造系统的鲁棒调度方法,其特征在于,包含以下步骤:
步骤1、构建含不可靠资源制造系统的Petri网模型(NU,MU0)及其关联矩阵A,其中NU=(PU,TU,FU)是一个有向图,代表由m个机器组成且能加工n类工件的制造系统;PU=Psf∪P∪Pr∪Pu表示库所集,Psf代表毛胚品的上传和卸载缓冲区,P代表加工操作集,Pr代表资源集,Pu为虚拟修复库所集;TU=T∪Tu是变迁集,T代表能引发正常加工操作的变迁组成的集合,每一个变迁表示上一个操作的结束,下一个操作的开始,TU是由描述不可靠资源发生故障及修复过程的变迁组成的集合;MU0表示为PU0→N,为初始标识集,其中N={0,1,2,…},代表系统的初始生产状态;A为关联矩阵,表示NU中变迁集TU和库所集PU的对应关系,是一个|TU|×|PU|的矩阵;FU=F∪Fu是弧集, 代表着资源的分配和释放,代表故障资源被移出去修复或者是修复完成重新回到加工过
程;
步骤2、进行编码和解码;
步骤3、随机生成初始种群,种群由固定规模的个体组成,每个个体对应一条染色体;令gen=0,gen表示当前种群的迭代次数;随机生成的染色体满足步骤2的编码要求,若不满足,则进行更正;
步骤4、进行检测和修复;
步骤5、计算加工时间和适应度值;
步骤6、判断是否满足终止条件gen>Maxgen,gen为当前种群的迭代次数,Maxgen为最大迭代次数;若满足终止条件则输出最优个体,不满足则执行步骤7;
步骤7、改进遗传操作,令第gen代种群更新到第gen+1代,随后执行步骤4至步骤6;
步骤8、输出最优个体,输出种群中最优个体的染色体序列,变迁序列以及对应的加工时间Makespan;
所述步骤4中检测和修复包含以下步骤:
步骤4‑1、从解码得到的变迁序列中的第一个变迁t1开始,检查t1能否在当前标识M下使能,若使能,则直接执行步骤4‑2,其中变迁使能的条件为前置操作库所和前置资源库所中都有token;若不能使能,则从t1之后随机选择一个能使能的变迁t2,将其移动到t1之前重新记为t1,再执行步骤4‑2;
步骤4‑2、在当前标识M下引发变迁t1,即M[t1>M1,将M1放入集合ζ,找出标识M1的所有后继标识,并将所有的后继标识放入集合ζ;
步骤4‑3、判断集合ζ中任一标识是否是死锁标识,如果ζ中所有标识均不是死锁标识,则允许t1在M下引发,否则,禁止t1在M下引发,然后从排在t1后面的变迁中找一个新的使能变迁t2,将其移动至t1之前重新记为t1,对t1继续执行步骤4‑2;
所述步骤7中改进遗传操作包含以下步骤:
步骤7‑1、选择操作,首先将种群中的个体按照适应度值从大到小排列,然后选择前Selectnum×Popsize个个体直接加入下一代,其中Selectnum为选择因子,Popsize为种群大小;
步骤7‑2、烟花爆炸操作,选择适应度最优的个体,适应度最差的个体以及其余的N‑2个随机个体,其中N为进行烟花爆炸操作的个体数量,对其进行烟花爆炸操作,爆炸半径SAi和爆炸火花数SNi的计算如公式(2)和(3)所示:其中MA为爆炸半径基值,MN为爆炸火花数基值,Adapti为第i个个体的适应度值,Ymax和Ymin分别为最大适应度值和最小适应度值,ε为常数;
步骤7‑3、交叉操作,首先从选择操作的个体中随机挑选一个个体,然后从其余个体中再随机挑选一个个体,随机选择两个插入点,将插入点之间两个个体的染色体片段进行交换;将原染色体中插入点之间的片段移动到工序序列的最前面,随后从前往后依次删除与插入的片段基因相同的基因;重复执行交叉操作,直到产生出完整的新一代种群;
步骤7‑4、标准化变异操作,对种群中所有个体进行标准化操作,使得在调度中同一类并且选择同一条路径的工件中,编号较小的工件总是优先被处理;标准化后找出种群中所有相同的染色体,每类只保留一条,其余执行变异操作;
变异操作的具体步骤为:在染色体中随机选择一个变异点,然后随机确定一个变异长度,若变异的位置在工序序列中,则将变异点前后变异长度的基因进行对调,若变异位置在路径序列中,则令变异点后变异长度个工件的路径选择更改为可更改的其他路径;
步骤4‑2中找出标识M1的所有后继标识包含以下步骤包含:
步骤4‑2‑1、将所有不可靠资源在M1下分成两类,一类是在M1下非零,即该类不可靠资源在M1下仍有空闲单元,记成A类;另一类是在M1下为零,即该类不可靠资源在M1下所有单元都参与了加工操作,没有空闲,记成B类;
步骤4‑2‑2、对于任一A类资源,找出所有使用了该资源的非零操作库所,即该操作库所在M1下包含token,将该操作库所中所有token移至对应虚拟修复库所中,得到的新标识记为M1′;
步骤4‑2‑3、对于任一B类资源,找出M1′下所有使用了该资源的非零操作库所,记成集合Bnonzero,选择Bnonzero中任一库所,将其库所token保留一个,其余的移至对应虚拟修复库所中,将Bnonzero中其余库所中所有token同时移至对应虚拟修复库所;找出B类资源所有的故障可能性对应的标识,将其放入集合ζ中;随后对集合ζ中的标识进行筛选操作,只保留后继标识;
其中,后继标识表示在某个给定的可达标识下,如果一个不可靠资源的所有单元同时在进行生产操作,最坏情况下只有一个单元在正常工作,其它都发生了故障;如果不是所有单元都在参加生产操作,则最坏情况下参加生产操作的这些单元同时发生故障,将这些最坏情况对应的标识称为后继标识。
2.根据权利要求1所述的含不可靠资源制造系统的鲁棒调度方法,其特征在于,所述步骤2中编码和解码包含以下步骤:步骤2‑1、进行编码,染色体由路径序列和工序序列组成;路径序列代表各个工件的路径选择,工序序列表示工件的加工顺序,长度为加工完所有工件需要的工序总数;用数字对各个工件和加工进行编号,得到染色体对应的一个数字串;
步骤2‑2、进行解码,首先根据路径序列中的数字判断工件的加工路径,其次工序序列中工件j的第n次出现代表工件j的第n个操作,依次将每个数字解码到对应的变迁,从而将编码的数字串解码成变迁序列。
3.根据权利要求1所述的含不可靠资源制造系统的鲁棒调度方法,其特征在于,所述步骤5中计算加工时间和适应度值包含以下步骤:步骤5‑1、计算加工时间,依次计算每一道工序的开始时间,通过比较工序对应工件的上一步工序的预估完成时间,以及当前工序使用的资源的空闲时间,取两者较大值作为当前工序的开始时间,同时该开始时间也是该工件上一步工序的实际完成时间,以及上一步工序所使用资源的实际释放时间,开始时间加上当前工序的操作时间为当前工序的预估完成时间;当计算完工序序列中的所有工序后,比较所有工件的完成时间,最大值为整个工序序列的加工时间Makespan;
步骤5‑2、计算适应度值Adapt,计算公式如公式(1)所示:
其中Maxspan为当前种群的所有个体中最大的加工时间,Minspan为所有个体中最小的加工时间,k为任意常数。