基于改进元胞机的多品种多工艺多单元制造调度方法

摘要

一种基于改进元胞机的多品种多工艺多单元制造调度方法，法包括以下步骤：1）建立车间调度系统的元胞自动机模型，（a）每个工件都是依照一定的工艺顺序进行加工的，只有前一道工艺加工完毕才能进入下一工位进行加工，（b）每台机器每个时间段只能同时加工一个工件，只有当一个工件结束加工后才能开始加工下一工件；（c）工件在机器上加工时不能被打断，直至该工序加工完毕；2）建立多目标函数，条件为：2.1）工件所有工序最大完成时间最短；2.2）工件的最大延迟最小；2.3）各工位设备平衡率高。通过权重法得到元胞自动机的每个离散单元在每个时步内的调度总目标函数。本发明实现动态监控、鲁棒性良好。

主权项

1.一种基于改进元胞机的多品种多工艺多单元制造调度方法，其特征在于：所述调度方法包括以下步骤：1）建立车间调度系统的元胞自动机模型，模型表达式如下：A_s={L₂,S,N,R,F_s}（4）式（4）中：A_s—多品种多工艺多单元制造企业生产车间调度系统元胞自动机模型；L₂—d=2，二维网格机构；S—工位元胞的状态；N—领域元胞状态；R—约束条件；F_s—调度规则；车间调度系统约束条件如下：（a）每个工件都是依照一定的工艺顺序进行加工的，只有前一道工艺加工完毕才能进入下一工位进行加工，这是工艺约束条件，用数学公式描述如下：st_ij≥et_i(j-1)其中，i＝1,2,..,n；j=1,2,...,m    （5）式（5）中：st_ij—Starting Time，表示第i个工件的第j道工序的加工开始时间；et_ij—Ending Time，表示第i个工件的第j道工序的加工结束时间；因此，第i个工件的第j道工序的加工开始时间必然在第j-1道工序结束之后；（b）每台机器每个时间段只能同时加工一个工件，只有当一个工件结束加工后才能开始加工下一工件，这是机器的能力约束条件，用数学公式描述如下：st_ij≥et_(i-1)j  其中，i＝1,2，...,n；j=1,2,...,m    （6）式（6）中：只有当第i-1个工件的第j道工序加工结束，第i个工件的第j道工序才能在同一台设备上进行加工；（c）工件在机器上加工时不能被打断，直至该工序加工完毕；2）建立多目标函数，所述多目标函数的条件为：2.1）工件所有工序最大完成时间最短：工件i在机器j上的加工时间记作T_ij，工件离开整个加工系统的时间为将各个子目标函数进行统一，因此第一个子目标函数为$F_1=\frac{\Sigma \min T_i}{\Sigma T_i},(i=\mathrm{1,2},...,n)---\left(7\right)$式中，分子表示的是工件i选择加工时间最短的工位进行加工时总的加工时间，这是理想情况下的最小值，因此0<F₁≤1；2.2）工件的最大延迟最小。工件i的交货期为d_i，则工件i的延迟定义为L_i=T_i-d_i    （8）当T_i-d_i>0时为延期交货，T_i-d_i=0时为准时交货，T_i-d_i<0时为提前交货。为了使三个子目标表达形式能够统一，考虑到L_i可能有等于0的情况，故第二个子目标函数为$F_2=\frac{1}{\max L_i+1}=\frac{1}{\max (T_i-d_i)+1}---\left(9\right)$2.3）各工位设备平衡率高：根据则有：$R_{\mathrm{lb}}=\frac{\Sigma T_i}{C_{\max }\times m}---\left(10\right)$式中，C_max表示负荷最大的工位所消耗的加工时间，m为此工位组的工位总数，因此第三个子目标函数为${F_3=R}_{\mathrm{lb}}=\frac{\Sigma T_i}{C_{\max }\times m}---\left(11\right)$通过权重法得到元胞自动机的每个离散单元在每个时步内的调度总目标函数：F=max(w₁F₁+w₂F₂+w₃F₃)（12）3）依照上述总目标函数，实现调度步骤为：3.1)遗传算法优化元胞自动机模型：设某生产车间由n个单元组构成，将元胞机各调度每个时步内的模型描述为：n个工件粒子在包含m个同类工位的单元组中进行加工，各工位加工效率不同，每个工件在此单元组中只需完成一道工序，每道工序根据实际要求可供选择的工位是单元组中的某几个或全部，每道工序在不同工位上加工所需的时间不一；设：（1）工件粒子集P={p₁,p₂，…,p_n}；（2）一个单元组内的工位集s={s₁,s₂，…,s_m}；（3）工序O_ij表示第i个工件的第j道工序，由于研究范围内每个工件只有唯一一道工序，因此每个工件对应的只有一个j；3.2)染色体编码与解码（1）工位染色体：静态调度单元中，每个工件包含一道工序，工件数等于本单元组调度中的工序数n，这n道工序的编号和工件编号一致，根据时间表依次往下排，各工序可选择的工位的子集分别为{S₁,S₂，…,S_m}；（2）工序染色体:研究部分每个工序包含一道工序，所以工序染色体中基因数等于单元中总工件数，这部分染色体表示为g′₁,g′₂,g′₃,…g′_i，…g′_n，融合两种编码，形成一条染色体，对应时间、空间离散的单元调度的一个可行解；解码，先根据工位染色体部分确定每道工序的加工工位，再根据工序染色体部分确定分配到每个工位的工序的加工顺序，结合所有静态调度单元的调度方案，获得元胞机模拟的整个车间的调度方案；3.3)初始种群生成及适应度函数直接以min(wl÷pe)为工位选择标准获得工位选择方案，及根据FCFS规则结合工件加工优先级获得的工件排序方案，分别对应编码中的工位选择染色体和工序排序染色体，获得遗传算法初始解；在获得初始解过程中，设置一个工位时间数组，用于记录每个工位的累计加工时间，工序染色体的初始解根据设备时间组中的时间变化点确定，遇到两个工件加工开始时间相同时，任取一个放在前面；采用优先权值设定法，设置各子目标的优先权值，将全体目标按照权值合成一个标量效用函数，把多目标优化问题转化成单目标优化问题，将目标函数设为适应度函数：$\mathrm{fit}\left(F\right)=F=0.4\times \frac{\Sigma \min T_i}{\Sigma T_i}+0.3\times \frac{1}{\max (T_i-d_i)+1}+0.3\times \frac{\Sigma T_i}{C_{\max }\times m}---\left(13\right)$3.4）选择，交叉及变异：采用前者按比例的适应度分配，若个体i，其适应度为f_i，其被选取的概率表示为：$P_i=\frac{f_i}{\underset{i=1}{\overset{M}{\Sigma }}{f}_i}---\left(14\right)$选择轮盘赌选择法，采用双切点交叉；第二部分的工序染色体中，工序排序染色体的交叉选用部分匹配交叉，基于路径表示的部分匹配交叉(PMX)操作，要求一个个体的染色体编码中不出现有重复的基因码，PMX操作要求随机选取的两个交叉点，以便确定一个匹配段，根据两个父代个体中两个交叉点之间的中间段给出的映射关系生成两个子个体；工位染色体的变异，采用在基因串中随机选择一个位置，在此工序的工位集中随机选择一个与其不相等的整数，替换当前基因；3.5）遗传算法总进化过程选择初始种群NP=10、交叉概率P_c=0.6、变异概率P_m=0.001，然后根据这个过程反复迭代，直到满足终止条件，此时得到的染色体可视为经遗传算法寻优后得到的元胞自动机演化的最优规则。