基于改进遗传算法的柔性制造车间等量分批调度问题

时间:2023-10-21 17:44:03 来源:网友投稿

吴亮,周学良,冷杰武,吴瑶

(1.湖北汽车工业学院机械工程学院,湖北十堰 442002;
2.广东工业大学机电工程学院,广东广州 510006)

柔性作业车间调度问题是传统作业车间调度问题的扩展。当前生产调度研究大多基于单件调度[1],但实际生产中产品加工往往是成批生产。产品生产采用批量分割的方式能提高生产效率,降低机床负荷。批量分割主要包含等量分批、一致分批和可变分批,等量分批是将工件划分为数量相同的若干子批[2]。针对柔性车间等量分批调度问题,国内外众多学者进行了深入研究,并取得一定成果。在建立批量数学模型方面,Alyn等[3]以批量和调度作为2 个阶段,提出MIP 启发式算法,并结合混合整数线性规划解决实际大规模转运问题;
Zhou[4]等建立了批量混合生产数学模型,并在案例分析中讨论批量和非批量方案,提出了基于批次的排产方法;
李聪波等[5]针对柔性车间多工艺批量生产,提出了面向能耗的分批优化模型。在设计算法求解方面,周亚勤[6]基于机床的负荷和工件批量约束,提出了双层嵌套式遗传算法,设计设备优先的解码算子来确定子批工件工艺路径;
黄夏宝等[7]针对不同生产类型的批量调度问题,设计了遗传模拟退火算法,在批量生产下确定最优分批数;
Xu[8]等针对工件批次调度和划分成指数增长问题,提出了批次定向和搜索空间可预测的启发式方法,使生产周期变短;
孙志骏等[9]针对作业车间多工艺路线批量作业计划优化,提出了新的染色体编码方式,优化子批数量和获取较优的子批加工排序,缩短了产品加工的时间;
张奎[10]针对柔性作业车间分批调度问题,提出FR 分批,缩短了产品的生产周期,但算法寻优上存在优化空间。上述学者通过设计高效的算法进行求解,但对于批量调度研究仍存在求解精度不足的问题。文中针对柔性制造车间等量分批调度问题,在标准遗传算法(genetic algorithm,GA)的基础上,改进适应度函数,增加个体区分度,使用保留亲代交叉机床基因策略,采用混合变异的方法选择加工机床。通过自适应交叉变异概率提高算法的寻优和收敛速度。采用标准GA与改进GA进行算例测试对比,验证改进GA的有效性。

1.1 调度问题

有N种工件在M台机床上加工,每种工件可以均分为1个或多个子批,每个子批都有确定的工艺次序。每类工件不同子批的每道工序可以根据自身工艺顺序在若干个机床上加工,加工过程中子批具有柔性加工路径。调度目标是将每类工件的所有子批送入机床加工,确定最优加工路线,使完工时间最小化,调度基本参数如表1所示。调度过程中必须满足以下约束:1)任意批次的工件只属于一类工件;
2)将所有调度子批送入机床的概率相同;
3)初始时刻,所有子批只要满足工序机床选择都可能被加工;
4)任意子批只能在当前工序加工完成之后才能加工下一道工序;
5)不同子批之间没有先后加工顺序的约束;
6)任意时刻,每台机床上只能加工任意一种工件的工序;
7)机床加工任意批次的工件,必须将该批次内的工件全部加工完后才能加工下一个批次;
8)不考虑机床准备时间和换刀时间。

表1 调度问题参数

1.2 数学模型

目标函数为

约束条件为

式(2)是对加工任务排队时间的约束;
式(3)是对加工任务工艺路线的相关约束;
式(4)表示同时刻同1台机床只能加工1道工序;
式(5)是对批次零件数量和批次总数的定义;
式(6)表示初始时刻上机概率相等;
式(7)表示任意工件的子批工序只能在1台机床上加工。

1.3 等量分批策略

实际生产中,工件总数存在不能完全等分的情况。工件i待加工数量为Qi,基准批量为Bi,分割成s个子批,每个批次的批量为

GA 是运用最广泛的算法,对求解复杂柔性车间分批问题有较强的适用性,并能得到相对满意的结果。染色编码由两部分组成,前半部分是每个子批的工序,后半部分是子批工序选择的加工机床。改进GA 流程如图1 所示。利用改进的适应度函数,结合自适应交叉变异概率,重新调整交叉和变异算子,使算法在广域搜索范围内维持种群多样性、局域搜索保持收敛性。

图1 改进GA流程图

2.1 染色体的编码与解码

染色体前半部分选用基于工序编码,后半部分是基于机床编码,假设有2 类工件待加工,每类工件有2 道工序,工件数量均为8 个,均分为2 批,编码如图2 所示。图2a 中前半部分表示子批的工序编码,后半部分表示子批工序选择机床的编码。染色体编码含义如表2所示。

图2 染色体分段编码

表2 染色体编码数字说明

解码是将染色体转化成调度结果的过程。工件的批量均分使同一种工件不同批次工序之间相互独立,不存在先后工序约束,整个加工过程可以并行运行。解码步骤如下:1)从左至右依次遍历染色体中子批工序基因,取出工序基因分隔符0左边的工件i和右边的批次s,并由工件种类i和子批工序p重复出现的次数确定加工机床;
2)比较当前工序待加工机床累计时间与该工件工序加工累计时长,选出较大值作为当前批次工序加工的开始时间,并利用数学模型中式(2)计算完工时间;
3)遍历染色体基因,将每个工序基因开始和完工时间放入1个矩阵数组中,利用数学模型中式(4)计算;
4)遍历步骤3)中完工时间矩阵数组,将完工时间最小染色体作为当代种群中最优染色体。

2.2 计算适应度与选择算子

完工时间越小,则染色体的基因越优良。染色体适应度用于评判染色体的优劣,适应度越大,被选择的概率越大。采用改进适应度函数使染色体区分度更加明显,也使劣质基因有一定概率被选中。

假设当前有5个批次的工件,每个批次的完工时间、传统的适应度函数(取最大完工时间倒数),改进后的适应度函数以及染色体被选中概率如表3所示。改进的适应度函数为

表3 不同批次工件参数变化

式中:λ1为s(i)的最小值;
λ2为s(i)的最大值;
c为任意较大常数,算法求解中取100,采用轮盘赌的方法选择算子。

2.3 交叉操作

交叉操作是GA 的关键部分,是种群保持多样性的途径,交叉有利于产生优秀的个体,从而获得优质的调度解。染色体编码由子批工序和机床选择基因构成,因此交叉包含批次工序基因交叉和机床选择基因交叉。

针对子批工序基因交叉,采用部分映射交叉[11],交叉步骤如图3所示:1)从2到1/2染色体长度中随机产生1个整数作为交叉点,假设产生的交叉点为4,取出交叉点后的染色体基因,P1 交叉部分为C1′,P2 部分为C2′,将C2′从右往左,C1′从左往右依次删除相同部分基因位,得到新的C1 和C2,如图3a 箭头指向所示;
2)处理P1 和P2 中多余和缺失的基因,遍历P1未交叉部分的工序基因位,如图3b中箭头指向所示,P1基因位101与C2中的基因位101 相同,则用P1 中101 基因位由C1 中的基因201替换。P2中未交叉部分的处理方式和P1一致。子代S1和S2如图3c所示。

图3 染色体批次工序的交叉过程

机床选择基因在交叉时,与工序交叉同等重要,决定算法在搜索过程中的全局收敛性。根据染色体在交叉过程中子代继承父代优良特征,针对机床基因采用新的交叉方式,即交叉部分保持父代中基因不变,未交叉部分重新选择机床,机床基因交叉步骤如图4所示:1)交换染色体P1、P2批次工序基因同时交换工序对应的机床基因,机床基因未交叉部分暂时用0代替,得到S1和S2;
2)遍历S1中未交叉工序基因位和P1的工序基因,若S1中工序基因与P1中工序基因相同,则将P1工序基因对应的机床基因复制到S1中工序基因位对应机床基因位置处替换0;
3)重复前2个步骤,将S2染色体中0位置用P2中机床基因进行替换。

图4 机床基因交叉过程

2.4 变异操作

变异操作有助于算法在收敛过程中跳出局部最优,交叉之后通过变异操作获得新的染色体,利用较小扰动增加种群的多样性。针对工件分批提出混合变异的方法,基于随机和轮盘赌相结合的方式选择机床基因,变异过程如图5 所示:1)产生一个不大于工件种类总数N的随机整数n1,取出第n1类工件子批工序基因和机床选择基因,将子批工序基因逆序排列,获得新的工序基因,子批工序对应的机床基因设为0;
2)从n1类工件子批集合{s1,s2…si}中随机产生1 个s整数,遍历第s子批的工序基因,根据工件种类n1和加工工序获得所有可能的加工机床J1和所有可能的加工时间T1;
3)根据工件可能加工时间T1,使用轮盘赌的方式选择具体的加工时间t,从而为工件子批工序选择相应的加工机床;
4)将n1类工件子批集合剩余子批使用随机方式,选择加工机床;
5)将变异后产生的工件子批工序基因和机床选择基因替换变异前染色体基因位。

图5 染色体变异过程

2.5 自适应交叉变异概率

算法求解前期,采用较小的交叉率,种群难以选出较优的调度方案。伴随算法的推进,针对适应度较高的个体采用大的交叉率和变异率,使优质染色体遭到破坏,算法陷入局部最优。采用文献[12]提出的自适应交叉和变异概率,算法的收敛性和鲁棒性都有所改善,交叉概率和变异概率为

式中:系数A为9.903;
pcmax为交叉率上限;
pcmin为交叉率下限;
pmmax为变异率上限;
pmmin为变异率下限;
fmax、fmin、favg分别为种群中最大适应度和最小适应度以及平均适应度;
f′为参与交叉的2 个体中最大适应度;
f为变异个体适应度。

在Windows10 操作系统中利用MATLAB2019a进行实验,利用文献[9]的实例数据验证改进GA的有效性。针对4类工件,每类工件8个,有6台加工机床,每类工件有3 道工序,每道工序可以在多台机床上加工。采用等量分批的方式,使用标准GA和改进GA分别求解。

3.1 相同分批方案不同算法对比

将工件进行均等分批调度,试验所得最佳分批结果为[3,3,3,3],4类工件都均分为3批,每类子批的批量为[3,3,2],即子批1批量为3个,子批2批量为3个,子批3批量为2个。算法初始参数见表4。

表4 算法初始化参数

调度甘特图如图6 所示,改进GA 最佳调度时间为71 h,相比于标准GA 缩短29 h。图7 为工件完工时间搜索过程,标准GA 在92 代左右收敛,最小完工时间为100 h,过早陷入局部最优,改进GA在76代左右收敛,最大完工时间为71 h,获得较优调度解,明显改善算法全局部寻优能力。文献[9]中工件加工最大完工时间为87 h,最优子批为13,相当于文献[9]使用更少的子批,使得生产管理简化,体现改进算法的优越性。种群在每次迭代过程中当代种群的最小完工时间和种群完工时间的平均值如表5所示。

图6 调度甘特图

图7 算法搜索过程

表5 某代运行结果对比h

3.2 算法稳定性分析

为验证算法稳定性,采用文献[9]中实例数据在改进GA 和标准GA 中分别单独运行30 次,仿真结果如图8 所示。图8 为比较试验,改进GA 与标准GA使用相同参数以及相同分批方案,经过独立的30 次运行测试。改进GA 求出4 次最优解71 h,优于标准GA的1次最优解91 h,且改进GA稳定在71~76 h,标准GA 在91~103 h 且波动较大。改进GA 平均最小完工时间为73.47 h,而GA 平均最小完工时间为97.27 h,验证了改进GA对柔性制造车间等量分批调度问题求解的稳定性。

图8 算法独立运行对比

3.3 算法有效性分析

为检测算法有效性,从30 组运算结果中随机抽选5组样本进行ANOVA检验,假设改进GA对调度解无显著影响。随机抽选的数据如表6所示。

表6 样本数据

ANOVA 检验之前,对样本数据进行方差齐次检验,基于最小完工时间平均值显著性为0.318,大于0.05,故ANOVA 分析有效。样本数据ANOVA分析结果如表7 所示。表7 中F值远大于其临界值,因此拒绝原假设,即改进GA 对调度解显著相关,关系强度为

表7 ANOVA分析

式中:SSA 为组间误差平方和;
SST 为总误差平方和;
R为关系强度统计量。由式(12)得R为0.97,大于0.8,因此改进GA影响程度为重度相关。

3.4 改进GA性能讨论与分析

相比于标准GA,当种群中染色体区分度较小时,改进适应度函数将目标值进行尺度变换,不仅使个体之间具有较高的区分度,并且使较差的个体仍有繁殖的机会,强化了算法的选择功能。

在标准GA 交叉过程中,待交叉的工序任意选择可加工机床。改进GA交叉过程中,保留部分父代工序基因对应的机床基因,使得染色体在寻优过程中能较好地遗传父代优质基因,避免工序随机匹配加工机床,有效防止优质解流失,从而提高算法的全局寻优能力。

标准GA通过交换工序中任意2个基因位及其对应的机床基因位实现变异,可能导致待加工工序和可选加工机床集不对应,从而产生不可行解,需要对解重新检查并处理。改进GA在变异操作中,针对某类工件所有子批工序进行变异,在改变子批工序顺序的同时,采用轮盘赌的方式选择加工时间较短的机床,避免无效解的产生,同时使变异过程具有方向性和目的性,使算法期望搜索效率更高。

文中研究了柔性车间分批调度问题,以最小完工时间作为优化目标,对个体的适应度、染色体的交叉方式以及变异方式进行了改进,并利用自适应交叉变异概率动态调整交叉和变异过程。相比整批调度方式,等量分批能大幅度缩短车间加工时间,提高机床加工效率。在相同的分批方案下,改进GA 求解能得到较好的收敛结果。文中未考虑机床换刀时间、机床负荷以及机床功耗等问题,这是后续研究的重点。

猜你喜欢机床交叉工件带服务器的具有固定序列的平行专用机排序杭州电子科技大学学报(自然科学版)(2022年4期)2022-08-23机床展会中国设备工程(2022年12期)2022-07-11带冲突约束两台平行专用机排序的一个改进算法杭州电子科技大学学报(自然科学版)(2022年3期)2022-06-08菌类蔬菜交叉种植一地双收今日农业(2021年12期)2021-11-28工业机器人视觉引导抓取工件的研究智能制造(2021年4期)2021-11-042021第24届青岛国际机床展开幕智能制造(2021年4期)2021-11-04一类带特殊序约束的三台机流水作业排序问题杭州电子科技大学学报(自然科学版)(2020年3期)2020-06-08《机床与液压》投稿要求汽车零部件(2019年7期)2019-08-16“六法”巧解分式方程初中生世界·八年级(2019年6期)2019-08-13连数小学生导刊(低年级)(2016年9期)2016-10-13

推荐访问:分批 柔性 调度