一种基于分解多目标进化算法的柔性车间鲁棒调度方法   0    0

本发明公开了一种基于分解多目标进化算法的柔性车间鲁棒调度方法,(1)读取柔性作业车间的作业和机器属性等输入信息；定义优化目标，设定约束条件；(2)初始化算法的参数；(3)确定每个子问题的邻域，产生初始父代群体，从初始群体中确定出所有的Pareto非支配解构成外部存储器；(4)生成子代群体。进行交配选择，采用自适应变异算子和基于修复的交叉算子繁殖子代个体，并更新外部存储器；(5)利用生成的子代群体对各子问题的当前最优个体进行更新，构成新的父代群体；(6)判断个体目标评价次数若达到最大，则输出外部存储器，即一组Pareto非支配的柔性作业车间调度解；未达到则跳转至(4)。本发明快速高效地实现柔性作业车间中的调度任务。

1.一种基于分解多目标进化算法的柔性车间鲁棒调度方法，其特征在于，包括以下步骤：
步骤(1)、读取柔性作业车间的输入信息，定义优化目标，设定约束条件：
车间的输入信息包括每项作业的工序数、每项作业中每道工序可分配的机器集合、各工序在相应机器上的加工时间、正常工作的机器数目；优化目标包括作业完工时间、机器的最大负载、调度性能的鲁棒性；约束条件包括工序优先级约束和禁止抢先占有的约束；
步骤(2)、初始化基于分解的多目标进化算法的参数：
设置迭代次数NmbEvl、群体规模N即为子问题的个数、产生N个均匀分布的目标权向量λ1,…,λN、子问题的邻域规模T，繁殖算子中的父代个体从邻域里选取的概率δ、邻域个体允许被每个子代个体替换的最大数目nr，评价鲁棒性时采样的不确定场景个数Q，以及交叉概率CR；
步骤(3)、确定每个子问题的邻域，产生初始父代群体：
(3.1)、对第i个子问题，i＝1,…,N，确定邻域B(i)＝{i1,…,iT}；分别计算第i个子问题的权向量λi和其它(N-1)个子问题权向量间的欧拉距离，将T个距离λi最近的权向量所对应的子群体序号{i1,…,iT}构成B(i)；
(3.2)、随机产生初始父代群体{x1,…,xN}，其中，个体xi为第i个子群体的当前解；群体中的每个个体包括工序序列向量和机器分配向量；随机采样一组不确定性场景θq，q＝1,
2,...,Q；计算初始父代群体中每个个体的目标值f1＝makespanI、f2＝workloadI和f3＝robustness；makespanI和workloadI分别表示初始景象下的作业完工时间和机器最大负载，robustness表示调度性能的鲁棒性；从初始父代群体中确定出所有的Pareto非支配解构成外部存储器Arc；设置目标评价次数计数变量ct＝N；归一化各目标值，将每个个体xi的第j个目标值fj(xi)映射到区间[0,1]之间，产生xi在第j个目标上的归一化值fnoj(xi)，即：
其中， 和 分别表示当前父代群体中的所有个体在第j个目标上的最大值和最小值，j＝1,2,3；
(3.3)、设置进化代数t＝0；
步骤(4)、生成子代群体：
随机采样一组不确定性场景θq；设置子代群体 令i＝1；
(4.1)、交配选择；
产生一个均匀分布的随机数rand1∈[0,1]；设置第i个子问题的更新邻域P(i)：
基于以下规则产生3个不同的父代个体 和
(4.2)、繁殖；
采用基于微分进化算法的繁殖算子，由 和xi生成子代个体ui；
(4.3)、更新外部存储器；
评价ui的目标值，并归一化各目标值；令ct＝ct+1；将ui加入外部存储器Arc；并删除当前Arc中所有重复解和Pareto支配解；设Chipop＝Chipop∪ui；如果i＜N，则令i＝i+1，转至(4.1)，否则执行步骤(5)；
步骤(5)、解的更新：
设混合群体Mixpop＝{x1,…,xN}∪Chipop，令i＝1，
(5.1)、令计数器c＝0；
(5.2)、从第i个子问题的更新邻域P(i)中随机选取一个子群体的序号k，k∈P(i)；
(5.3)、对于第k个子问题，从Mixpop中确定最佳解；
设标记变量mark＝0；给定第k个子问题的权向量 为第j个目标的权
值， 和参考向量 为第j个目标的参考点，j＝1,2,
3，采用切比雪夫法求得任意一个个体x在第k个子问题的合成目标函数为：
由于采用归一化目标值，设置参考向量z*＝(0,0,0)；对于Mixpop中的每个个体xyl和第k个子问题的当前解xk，如果下述3个条件中有一个满足：(i)gte(xyl|λk,z*)＜gte(xk|λk,z*)；
te l k * te k k * l k te l k * te k k
(ii)g (xy|λ,z)＝g (x |λ,z)且xy Pareto支配x ；(iii)g (xy |λ,z)＝g (x|λ,z*)且xyl在鲁棒性能f3＝robustness上的目标值小于xk，则令xk＝xyl，FVk＝F(xyl)，Fnok＝Fno(xyl)，且mark＝1；其中，FVk表示xk的目标向量，即FVk＝F(xk)＝[f1(xk),f2(xk),f3(xk)]，F(xyl)表示xyl的目标向量，即F(xyl)＝[f1(xyl),f2(xyl),f3(xyl)]，Fnok表示xk经归一化后k k k k l l
的目标向量，即Fno＝[fno1(x),fno2(x),fno3(x)]，Fno(xy)表示xy 经归一化后的目标向量，即Fno(xyl)＝[fno1(xyl),fno2(xyl),fno3(xyl)]；
(5.4)、如果mark＝1，则令c＝c+1；
(5.5)、从P(i)中删除序号k；如果c＜nr且P(i)非空集，则转至(5.2)；否则，如果i＜N，则令i＝i+1，转至(5.1)，否则转至步骤(6)；
步骤(6)、终止准则判断：
如果ct＞NmbEvl，则终止迭代，输出外部存储器Arc，即一组Pareto非支配的柔性作业车间调度解；否则，令t＝t+1，转至步骤(4)。

2.根据权利要求1所述的一种基于分解多目标进化算法的柔性车间鲁棒调度方法，其特征在于，步骤(1)中所述优化目标中的作业完工时间表示完成柔性作业车间中的所有作业所花费的时间开销，定义为：
其中，Cv和Sv分别表示在第v项作业中，最后一道工序的加工完成时间和第一道工序的加工开始时间，v＝1,2,…,n，n为柔性作业车间中所有作业的总数；I表示初始景象，即针对不确定属性，设它的值为某一预估值确定不变，在此情况下计算作业完工时间；
步骤(1)所述优化目标中的机器最大负载表示各台机器加工时间的最大值，定义为：
其中，m是柔性作业车间内机器的总台数； 是根据调度方案，在第s台机器上按第r个顺序进行加工的工序Osr的加工时间；ws是分配到第s台机器上的工序个数；
步骤(1)所述优化目标中，调度性能的鲁棒性是衡量调度方案的作业完工时间和机器的最大负载对不确定因素的敏感程度，定义为：
鲁棒性采用基于景象的方法定义，将一个调度方案在不确定属性的多种采样值{θq|q＝
1,2,…,Q}下进行仿真，以比较作业完工时间和机器最大负载的实际值与初始预估值之间的差值；其中，makespanq和workloadq分别是θq下相应的作业完工时间和机器最大负载目标值；
步骤(1)所述的工序优先级约束是指每项作业的各道工序是按事先确定的顺序进行加工的；在柔性作业车间问题中，每道工序可以在它允许的机器集合中任一台上进行加工；
步骤(1)所述的禁止抢先占有的约束包括：(i)每道工序的加工，只能在同一作业中排在它之前的所有工序都完成之后才能开始进行；(ii)如果将一道工序分配给了某台机器，只有在这台机器完成之前调度的所有工序之后，才能开始该道工序的加工。

3.根据权利要求1所述的一种基于分解多目标进化算法的柔性车间鲁棒调度方法，其特征在于，步骤(3.2)所述的随机产生初始群体是指，每个个体中的工序序列向量通过随机排列所有作业中的所有工序生成；对于机器分配向量，将每道作业工序随机分配到它机器集合中的任一台上进行加工。

4.根据权利要求1所述的一种基于分解多目标进化算法的柔性车间鲁棒调度方法，其特征在于，步骤(4.3)和步骤(5.3)所述的Pareto支配是指：设x1和x2为多目标优化问题的两个解，问题的目标个数为m1，假设所有目标均需最小化，称x1Pareto支配x2当且仅当且
其中，g和h分别表示目标的某一个序号，fg(x1)和fg(x2)分别表示x1和x2在第g个目标fg上的目标值，fh(x1)和fh(x2)分别表示x1和x2在第h个目标fh上的目标值。

5.根据权利要求1所述的一种基于分解多目标进化算法的柔性车间鲁棒调度方法，其特征在于，步骤(3)和步骤(6)所述的Pareto非支配解是指，如果在某一集合中不存在任何其它解x'Pareto支配解x，则称x为该集合中的Pareto非支配解。

6.根据权利要求1所述的一种基于分解多目标进化算法的柔性车间鲁棒调度方法，其特征在于，步骤(4.2)所述的繁殖算子是指，基于微分进化算法中的变异算子和交叉算子，设计一种改进的自适应变异算子和基于修复的交叉算子，由父代个体 和第i
个子问题的当前个体xi，生成子代个体ui；其中，改进的自适应变异算子的实施方法如下：
-0.015t
β＝e ,
其中，F1，F2和F3是变异因子，它们的值分别从[0.5,1]中均匀随机生成； 是当前外部存储器Arc中，距离xi最近的解， 参数β的值随着进化代数t的取值而变化；yi是由改进的自适应变异算子生成的个体；
对于个体的工序序列向量和机器分配向量，分别实施上述所述改进的自适应变异算子；对于生成的yi中的工序序列向量ysi，将它的各个元素按从小到大的顺序进行排列，得到ysi的排序向量tysi，并将排序后的每个元素在原向量ysi中的位置索引记录在索引向量Ii中；将xi的工序序列向量xsi中各个元素按从小到大的顺序进行排列，得到xsi的排序向量i i i i i i i i i
txs ，并令ys (I)＝txs，ys(I)表示ys中所有在I记录的位置上的元素；对于生成的y中的机器分配向量ymi，针对每个元素，搜索其对应工序的机器集合，从中确定出与该元素值最接近的机器，并将该机器替代此元素；如果有两台以上机器同时满足此条件，则从中随机选择一台机器替换对应元素；更新后的工序序列向量ysi和机器分配向量ymi构成新个体yi；
所述基于修复的交叉算子的实施方法如下：
(a)、将由改进的自适应变异算子生成的个体yi与xi组合，构成子代个体ui：
其中， 分别是ui,yi,xi的第ll个元素，L是个体xi的长度，CR∈[0,1]是交叉概i
率， 是从[0,1]中均匀随机产生的一个数，Irand是从集合{1,2,…,L}中随机选择的一个整数；
在机器分配向量的表示方法中，yi的机器分配向量ymi与xi的机器分配向量xmi在相同位置上的机器对应于同一道工序；上述交叉算子直接作用于ymi和xmi,交叉得到的结果即为子代个体ui的机器分配向量umi；
针对yi的工序序列向量ysi与xi的工序序列向量xsi，进一步实施以下步骤：
(b)、将步骤(a)求得的ui的工序序列向量usi中，将来自于xsi的元素位置索引记录在1号索引向量index1中，将来自于ysi的元素位置索引记录在2号索引向量index2中；令usi＝xsi，临时索引向量tempindex2＝index2,测试向量test＝usi(index1)，usi(index1)表示usi中所有在index1记录的位置上的元素,索引删除向量donor_delete＝[]，[]表示空集合；
(c)、对test中的每个元素ue，确定在ysi(index1)中是否存在一些元素等于ue；如果存在，则从中均匀随机地选择一个元素，将选中的元素在ysi中的位置索引加入donor_delete，并将该索引从index1中删除；否则，找出在ysi(index2)中等于ue的元素，从中均匀随机地选取一个，将它在ysi中的位置索引加入donor_delete，并将该索引从index2中删除；
其中，ysi(index1)表示ysi中所有在index1记录的位置上的元素，ysi(index2)表示ysi中所有在index2记录的位置上的元素；
(d)、将donor_delete中的元素从集合{1,2,…,L}中移除，即令索引保留向量donar_reserve＝{1,2,…,L}\donar_delete，且usi(tempindex2)＝ysi(donar_reserve)；其中，\表示去除，usi(tempindex2)表示usi中所有在tempindex2记录的位置上的元素，ysi(donar_reserve)表示ysi中所有在donar_reserve记录的位置上的元素。