基于混合遗传算法的液压元件装配流水车间调度

2022-10-10胡小建李睿豪

合肥工业大学学报（自然科学版） 2022年9期

胡小建, 李睿豪

(合肥工业大学管理学院,安徽合肥 230009)

0 引言

高端液压元件制造一直是我国工程机械产业发展中的“卡脖子”难题。为解决这一难题,在中国制造2025战略指导下,安徽BY公司受工信部“高端液压元件制造数字化车间”项目支持,建设了液压元件数字化车间并投入生产。BY公司液压元件的生产过程包括零件加工、在制品库存、部件装配和总装4个环节。综合考虑液压元件车间实际生产环境,合理安排产品的生产顺序,减少在制品库存,提高生产效率,是亟待研究的问题。通过回顾与梳理以往的研究发现,虽然两阶段装配流水车间调度问题(two-stage assembly flowshop scheduling problem,TSAFSP)综合考虑了加工阶段与装配阶段,与BY公司生产过程相似。但是目前关于液压元件装配流水车间调度问题的研究较少。

TSAFSP可以描述成:n个待加工工件,每个工件有m个零件;第1阶段有m台机器并行加工m个零件;第2阶段的一台装配机将m个加工完成的零件组装成一个产成品。TSAFSP的研究主要集中在目标函数与机器配置。目标函数涉及文献[1]的完工时间、文献[2]的总完工时间和文献[3]的迟到等研究目标。关于机器配置问题，文献[4-5]在以往学者研究基础上,将装配阶段的机器数量扩展到多台;文献[6-7]研究了TSAFSP与产成品配送的集成调度问题;文献[8-9]在TSAFSP基础上额外考虑了两阶段中间的在制品批量运输,研究了加工、运输和装配三阶段的集成调度优化问题。目前,无论是关于目标函数还是机器配置的研究,都忽略了加工、装配之间的缓冲过程。

BY公司液压元件的生产过程比TSAFSP更加复杂,不仅装配阶段包括部装和总装,而且有专门的立体货架负责在制品库存。本文从BY公司实际车间出发,提出了一种新的机器配置方法:多台并行加工机器、一个在制品库存、多台并行部装机器和一台总装机器。其中，在制品库存作为衔接加工、装配阶段的核心纽带,在新的机器配置中具有重要地位,因此本文在目标函数中考虑了在制品库存。关于在制品库存的计算方法,文献[10]考虑了2个混流装配车间的缓冲区库存成本,并假设储存成本与储存数量呈正相关;文献[11]考虑了多品种混流加工作业车间和流水装配车间之间的缓冲区库存量,实现零部件加工完成后的即时装配。本文使用待装配零件的库存时长表示在制品库存,结合上文的机器配置,提出一种新的在制品库存计算方法。首先由加工机器推动加工完成的零件入库,加工完成时间即为入库时间;然后由总装机器拉动零件出库,总装开始时间减去零件部装时长即为零件出库时间。这种推拉结合的出入库方式,能够保证产品的所有部件同时完成部装,即刻开始总装,确保部装与总装之间的生产连贯性。

本文从BY液压元件车间实际需求出发,首先以TSAFSP为基础,在企业生产环境中提炼出一种新的机器配置和推拉结合的在制品库存计算方法;然后以总完工时间与在制品库存加权和最小为目标函数,建立了液压元件装配流水车间调度模型(hydraulic components assembly flowshop scheduling problem,HCAFSP)。在设计求解算法时,提出一种遗传算法孤岛模型混合粒子群算法(genetic algorithm island model-particle swarm optmization,IsLandGA-PSO),通过仿真分析并与其他算法进行对比,表明了该算法能加快收敛速度,避免陷入局部最优，能够有效解决较大规模的HCAFSP调度问题。

1 问题描述

液压元件装配流水车间调度问题如图1所示,可以描述为:n个待生产的产品,每个产品有m个零件和a个部件;n个产品按一定次序在m台并行机器加工完成后,进入在制品库存S;由1台总装机器拉动m个零件出库,在a台并行部装机器上完成部装;最后n个产品以相同次序在1台总装机器上总装自己的a个部件。使用总装机器拉取的方式出库,保证a台部装机器和1台总装机器之间没有在制品库存,整个生产过程的在制品库存都汇聚在S。

图1 液压元件装配流水车间调度模型

1.1 假设

所有机器在0时刻均可用;不考虑运输时间;每个零件的加工、部装时长不同;所有部件准备就绪才开始总装;每个零件唯一对应1个加工机器和1个部装机器;通过总装机器拉取出库,保证1个产品的所有部件同时完工。

1.2 变量

本文采用的变量如下：n为产品个数;m为并行加工机器(零件)个数;a为并行部装机器(部件)个数;j为产品编号,j=1,…,n;i为产品加工顺序编号,i=1,…,n;k为加工阶段机器(零件)编号,k=1,…,m;p为装配机器(部件)编号,p=1,…,a+1;tjk为产品j的零件k在机器k上加工时长;Tjkp为产品j的零件k在部装机p上部装的时长,若不在p上部装则为0;Tja+1为产品j的总装时长;Cmax为总完工时间;Cinventory为在制品库存;Iik为第i个生产的产品的零件k在机器k上完工(入库)时间;Oik为第i个生产的产品的零件k开始部装(出库)时间;Si为第i个产品开始总装时间;xji为决策变量,xji当产品j第i个生产为1，否则为0。

2 模型建立

目标函数主要考虑总完工时间和在制品库存2个方面。首先总完工时间保障生产效率;其次在制品库存作为加工、装配的纽带,降低在制品库存可以更加精准地衔接各个环节,使得整个生产过程更加流畅。

2.1 目标函数

以最小化总完工时间与在制品库存时间加权和为目标,α为权重。

minZ=αCmax+(1-α)Cinventory

(1)

2.2 在制品库存

分别计算零件的入库时间Iik、开始总装时间Si、出库时间Oik和总库存时长Cinventory。

(1) 入库时间Iik。第i个产品的零件k开始加工时间是第i-1个产品的零件k在机器k上的结束时间,加工完成的零件直接推动入库。因此Iik为:

∀i=1,…,n且∀k=1,…,m

(2)

(2) 总装开始时间Si。第i个产品开始总装,首先要保证第i-1个产品总装完成,使总装机器处于空闲状态;其次要求所有部装件准备就绪,因此第i个产品总装开始时间要大于所有部装机中最晚完工时间。因此Si为:

(3)

(3) 出库时间Oik。第i个产品的零件k由总装开始时间拉动出库,出库时间是第i个产品开始总装的时间Si减去其零件k的部装时长。因此Oik为:

∀i=1,…,n且∀k=1,…,m

(4)

(4) 在制品库存Cinventory。第i个产品的零件k的库存时长为出库时间与入库时间之差。因此Cinventory为:

(5)

2.3 总完工时间

总完工时间是最后一个生产的产品的总装结束时间，即

(6)

2.4 其他约束

其他约束条件如下：

(7)

(8)

(9)

(10)

其中：(7)式表示1个生产顺序编号只能分给1个产品;(8)式表示1个产品只能有1个生产顺序编号;(9)式表示每个加工机器上的第1个生产的产品开始加工时间为0;(10)式表示第1个生产的产品总装时总装机器处于空闲状态。

3 混合算法设计

由于两阶段装配流水车间调度已被证明是NP难问题,常采用启发式算法和智能优化算法获得近似解。本文研究的液压元件装配流水车间调度的机器配置更加复杂,而且考虑到BY公司数字化车间改造后调度规模扩大,因此本文采用智能优化算法求解的同时,要求算法对大规模调度问题仍有效。

遗传算法(genetic algorithm,GA)和粒子群优化算法(particle swarm optimization,PSO)求解小规模问题都有良好表现,但是随着问题规模增大,2种算法均有缺陷。为了利用遗传算法较强的全局搜索能力和粒子群的快速收敛能力,本文考虑在并行遗传算法中常用的孤岛模型(IsLandGA)中引入粒子群,设计一种遗传算法孤岛模型和粒子群优化的混合算法(IsLandGA-PSO)。

算法种群的组织方式如图2所示，共分为如下2层：底层是IsLandGA包含多个GA子种群,每个GA种群执行遗传算法操作,种群之间定期迁移分享优秀个体;顶层是一个PSO,对底层传递上来的优秀个体进行精确局部搜索,获得更加优秀的基因,再反馈给底层。

图2 IslandGA-PSO算法种群组织方式

3.1 种群迁移设计

IsLandGA-PSO算法的种群迁移需要考虑如下2个方面:

(1) 底层IsLandGA内部GA种群之间的迁移。

(2) 底层IsLandGA和顶层PSO种群之间的迁移。

3.1.1 底层遗传种群的迁移设计

底层是一个典型的遗传算法孤岛模型,其种群迁移设计[12]主要包括迁移规模、迁移策略和迁移拓扑3个方面。迁移规模的大小对算法求解有重要影响,大规模迁移会破坏种群多样性,陷入局部最优;迁移规模小,会导致无法充分分享其他种群优秀个体。迁移规模由迁移周期与迁移率控制。本文通过对比实验,对常用典型迁移规模进行分析,最终选择迁移周期为5,迁移率为0.1。迁移策略选择用前一个种群最优个体代替被迁入种群最差个体的方法。迁移拓扑确定了子种群之间个体的迁移路径。

因为单向环拓扑不仅保证了优良基因在群体间的扩散,而且较好地隔离了子群体，所以本文选择单向环拓扑。

3.1.2 底层与顶层种群的迁移设计

本文采用文献[13]提出的迁移策略,把上层与下层之间完成一次迁移看作一轮。在每轮中,底层IsLandGA进化100代后,从每个遗传种群选出10%最优秀个体组成顶层粒子群。粒子群独立进化20代后,底层每个遗传种群从该粒子群中随机选择2个个体替换自己表现最差的2个个体,至此完成一轮进化。

3.2 遗传算法操作设计

3.2.1 编码与解码

因为HCAFSP是生产排序问题,所以采用基于工序编码方式,每条染色体代表一种产品的生产顺序。例如染色体{4,2,5,1,3}表示4号产品第1个生产,3号产品最后一个生产。

由于染色体编码只确定了生产顺序,而解码获得的甘特图需要确定每个零部件在各个机器上的开始及结束时间。因此解码时需要遵循以下规则:① 加工机器的加工是连续的;② 部装机器和总装机器需要等待其所需的所有零部件均完工才能开始。在以上规则的前提下,HCAFSP的解码通过产品的生产顺序、前后工艺约束和机器加工时长,确定产品的零件、部件在各个机器上的开始和结束时间。

以BY公司车间机器配置为例进行解码,BY公司拥有4台并行加工机器,2台部装机器和1台总装机器。染色体{4,2,5,1,3}解码后的调度甘特图如图3所示。从图3可以看出，通过拉取的方式出库,每个产品的所有部件同时完工。

图3 解码后的甘特图

3.2.2 适应度函数与选择操作

采用轮盘赌选择适应度更高的个体进入下一代。由于目标函数为最小化总完工时间与在制品库存时间加权和,为了适应轮盘赌选择的要求,使用目标函数的倒数作为染色体的适应度,适应度函数f如下:

(11)

3.2.3 交叉与变异

交叉决定了全局搜索能力,算子的选择至关重要。生产顺序决定了染色体的优劣,而两点交叉可以有效保留基因间相对位置,因此本文采用两点交叉。变异可以跳出局部最优,避免早熟,决定了局部搜索能力。插入变异可以有效改变基因顺序,且不会产生不可行解,因此本文采用插入变异,随机选择个体的某基因插入到另一基因位前面。

3.3 PSO设计

PSO的思想是每个粒子从个体历史最优值和种群最优值获得信息,根据此信息进行局部搜索,其速度、位置更新公式决定了PSO适合用来求解连续优化问题,不适合组合优化与离散优化问题。因为HCAFSP是离散优化问题,所以本文保留PSO算法从个体和群体获取信息的核心思想,重新定义位置、速度的更新方式。算法具体步骤如下:

(1) 种群初始化。

(2) 计算每个粒子的适应度。

(3) 每个粒子都从自己历史最优位置和种群最优位置获得更新消息。

(4) 进行局部搜索和位置更新。

(5) 若达到停止准则,则输出种群最优粒子;否则转步骤(2)。

新的速度、位置更新公式使用遗传算法的交叉操作从其他个体获取信息。(12)式是新的速度更新公式,粒子i的速度Vit与粒子i的历史最优个体Pbestit和粒子i所在种群的最优个体Gbestgt交叉获得更新后的速度Vit+1;(13)式是新的位置更新公式,粒子i现在的位置Xit与更新后的速度Vit+1交叉获得新的位置Xit+1。

(12)

(13)

其中,⊗为遗传算法的交叉操作。

3.4 算法求解流程

IslandGA-PSO算法求解流程如图4所示，步骤如下:

图4 算法求解流程

(1) 初始化最大迭代次数为maxGen,计数器gen为0,种群总规模为P,GA种群个数为N,交叉概率为Pc,变异概率为Pm。

(2) 随机生成P个染色体,平均分配给N个GA种群,每个GA种群有P/N个染色体。

(3)N个GA种群独立进化5代,步骤①～步骤④循环执行5次后,执行步骤(4)。步骤①～步骤④如下：① 计算每个染色体适应度;② 使用轮盘赌选择个体;③ 使用交叉概率Pc完成交叉;④ 使用变异概率Pm完成变异。

(4) 每个GA种群向下一个GA种群迁移自己种群最优的前10%个体,替代下一个种群的最差个体。

(5) gen为gen加5,若gen%100为0,即GA种群在本轮中进化了100代(共迁移了20次),则执行步骤(6);否则继续执行步骤(3)。

(6) 从底层每个GA种群抽取最优的前10%个体组成顶层PSO种群。

(7) PSO种群独立进化20代。若达到最大迭代次数gen为maxGen,则执行步骤(8);否则每个GA种群从PSO种群中随机抽取2个个体,替代自己最差的2个个体,然后执行步骤(3)。

(8) 输出最优结果,迭代完成。

4 仿真实验

4.1 参数设置

为了验证混合算法IslandGA-PSO求解大规模问题的有效性,分别对不同规模的调度问题进行实验。工件数n取{20,40,80,160},并选择同样是多种群优化算法的多粒子群协同优化算法PSCO[14]和IslandGA进行对比实验。由于多种群优化算法中的种群数量对算法有一定影响,因此每种算法的种群数量N分别取{1,4,8,16}。当N=1时,只有1个种群,PSCO为标准粒子群算法PSO;IslandGA为标准遗传算法GA;IslandGA-PSO是一种采用并行混合方式的遗传算法和粒子群优化混合算法GA-PSO[15]。

所有算法采用相同的遗传算子,算子参数设为:Pc为0.9,Pm为0.1,maxGen为2 000,P为400。关于模型参数,机器配置按照BY车间实际情况有4个加工机器、2个部装机器和1个总装机器;每个零件、部件的处理时长服从[50,100]的均匀分布,权重α取0.5。

4.2 结果分析

因为每种算法的种群数量N和工件数n均有多个取值,所以把-N-n看作一个组合,例如IsLandGA-PSO-16-80表示拥有16个GA种群的IsLandGA-PSO算法求解规模n=80的调度问题。

每种算法都有16组实例,为了排除随机性,每次试验独立运行10次,使用10次结果的最优值(目标函数最小)、平均值和方差衡量结果。仿真结果见表1所列。

表1 仿真结果

首先分析种群数量N对IsLandGA-PSO算法的影响,结果如图5所示。从图5a、图5b可以看出，求解小规模调度问题(n=20,40)时,3种算法基本均收敛至同一全局最优解3 152和13 797。从图5c、图5d可以看出,调度规模n增大(n=80,160)时,IsLandGA-PSO-4-n与IsLandGA-PSO-8-n2种算法陷入局部最优,而IsLandGA-PSO-16-n由于种群个数最多,获得最优结果时长为32 140和106 526;当n=160时,16种群的IsLandGA-PSO算法求解的最小总完工时间和在制品库存,相比于4种群和8种群算法的结果,分别降低了23%和12%。

图5 不同规模下种群个数对IsLandGA-PSO算法的影响

因此在使用该混合算法求解HCAFSP调度问题时,若问题规模增大,则可以通过增加种群个数N获得更加优秀的结果,有效降低总完工时间和在制品库存。

从上文可以得知IsLandGA-PSO-16-n表现最好。为了验证IsLandGA-PSO算法先进性,分别在调度规模n=40、80、160时与PSCO-16-n、IsLandGA-16-n和IsLandGA-1-n(GA)算法进行对比，结果如图6所示,IsLandGA-PSO算法的收敛速度和最优值优于其他3种算法。

从图6a可以看出，当规模调度为n=40时,IsLandGA-PSO-16-n获得了更小的总完工时间和在制品库存13 797,比GA降低了11%,比PSCO降低了8%,比IsLandGA降低了5%。

从图6b可以看出，当规模调度较大时,IsLand GA-PSO算法解决了其他3种算法陷入局部最优的问题,最优值为32 140相比其他3种算法分别降低了43%、33%、15%。

从图6c可以看出，调度规模越大(n=160),IsLandGA-PSO算法相比于其他3种算法优势越明显,最优值分别降低59%、52%、45%。