采用AGV分拣的型材下料车间成组调度问题研究

汤洪涛，郑之恒，李英德，陈青丰，江伟光

(浙江工业大学 机械工程学院，浙江 杭州 310023)

型材下料车间(Profile Blanking Workshop, PBW)是指对钢制原材料进行切、冲、钻等基础加工处理的车间，通常由多条辊道流水线组成。一台套整机产品所需的不同型号的型材通常需要在多条线分头下料，一根型材在产线上通常切割成不同规格的零件以供不同台套整机产品使用。型材经切割后通常需根据后道工序生产要求按整机产品成套分拣，并送往后续车间生产。为了提高分拣效率和智能化水平，一种新的使用自动导引小车(Automated Guided Vehicle, AGV)进行成套分拣的新模式在下料车间出现。车间由数条切割下料生产线组成，需切割的型材通过辊道上料，经过切割加工后，从辊道下线至特定的料框中。AGV搬运各个料框分别在各条下料线的下线点之间移动，确保同一台套物料放入同一个料框，并最终将完成分拣的料框搬运至成品库。

考虑到型材重量和尺寸导致的搬运不便，下料时通常需要将一根型材全部切割完毕，不留余料，在生产排程时需以一根原材料为一组进行调度，因此可以归为成组调度(Group Scheduling, GS)。在传统GS研究方面，LOGENDRAN等[1]首次对具有序列不相关准备时间和一致并行机类型的混合流水车间成组调度问题进行了研究，分析了在单准备时间和多准备时间两种情况下GS问题的性质特征，并基于此对3种不同的组合启发式算法的性能进行了对比分析；
随后，LOGENDRAN等[2-5]对无关并行机、序列相关等各种情况下的组调度都进行了研究；
袁帅鹏等[6-7]对两阶段流水车间成组调度问题进行了研究；
随后又针对无关并行机类型的混合流水车间成组调度问题，在考虑序列相关准备时间的情况下，以最小化最大完工时间[8]为目标设计了一种改进的候鸟优化算法。传统成组调度的研究针对各种不同加工环境下的流水车间，而型材下料车间成组调度(Profile Blanking Workshop GS，PBWGS)与一般采用成组调度的作业车间相比，其工序相对较少，加工工艺简洁，无需考虑工艺间的调度，且节拍相对稳定，完工时间趋向于固定，若使用AGV进行成套分拣则需要型材生产排程与AGV调度密切配合，且成套分拣的需求将导致更复杂的AGV路线、更灵活的AGV调度方案、以及更高的AGV使用成本。

在AGV调度研究方面，研究仓库环境中的路径以及搬运时间优化的多AGV调度问题较多[9-10]；
ZHANG等[11]研究了矩阵式制造车间多台AGV的调度问题，设计了改进的迭代贪婪算法以优化运输成本；
为了解决考虑运输时间和多机器人的作业车间调度问题(Job Shop Scheduling Problem, JSSP)，NUORI等[12-13]开发了两种新的元启发式杂交算法；
AFSAR[14]等提出一种主/从方法来解决具有运输限制的JSSP；
AGV的应用及其成本的控制已经进入了研究的视野，但成组调度与AGV分拣的结合还仍有必要进行深入研究，面向PBW综合考虑生产排程与AGV调度，研究其调度方法有重要的理论意义和实用价值。

针对该问题，本文以最小化AGV使用成本为目标建立数学模型，在考虑型材下料车间实际加工生产特点的情况下提出一种采用多层编码方式的改进遗传算法，该算法采用带加工属性的多层编码方式区分加工要求，用不同层的属性来区分原料、台套和零件并分层交叉变异，设计了不同的邻域搜索机制来构造不同层的邻域结构，并提出了基于禁忌表的双层协同优化策略。最后分别与基础遗传算法、基础蚁群算法、变邻域改进遗传算法和改进蜂群算法进行综合对比，验证了本文算法的有效性与鲁棒性。

1.1 问题描述

型材下料车间加工工艺如图1所示，型材从原材料库到达各条平行的下料流水生产线，经过切割下料后，由机械手抓取切割后的零件放入AGV搬运的料框，将车间不同产线切割的属于同一台套的零件放入同一个料框中，最后以框为单位齐套入库。假设一个由3条产线构成的下料车间同时生产多个台套产品，如图2所示为一台AGV依次经过2—3—2—1—3号产线的5个下线点装载1号台套零件的过程，其中：连续的方框表示同一根型材，数字表示零件所属的台套编号，虚线框表示下线缓存区位置，带箭头连线表示AGV依次在各个产线的下线点装载下线的零件。

成材率是型材下料最重要的考虑因素，车间企业资源计划(Enterprise Resource Planning, ERP)系统安排每日加工任务时，首先根据最省型材原材料的原则进行初步排样。型材的生产排样涉及到每一根型材的先后切割顺序和每一根型材内部各段零件的先后切割顺序。本文研究AGV分拣的PBWGS问题是在车间ERP系统经过初步排样后对型材切割顺序及一根型材内部各段的切割顺序的二次调度，可描述如下：

(1)下料车间抽象为多台并行排列的性能不同的切割机；
(2)订单在上级ERP系统按最省原材料原则初步排样；
(3)同一根型材的各段零件只能在同一台机器上切割；
(4)零件切割完成后在缓存区等待机械手抓取下线进入料框；
(5)同台套的零件放入同一料框，料框由AGV背负在产线间移动，接收下线的零件；
(6)同一台套的料框的每次移动可以由任意一台AGV完成。

本文优化的目标是最小化AGV的使用成本。AGV的使用成本可以简化为由电池折旧成本和用电成本两部分组成。电池折旧成本可以视作与充放电[15-17]次数正相关，充放电次数与AGV的有效工作时间正相关；
用电成本也与AGV的有效工作时间正相关。因此，最终将AGV使用成本转换为AGV的有效工作时间(即搬运行走时间和举升/放下料框时间)。针对该问题，建立数学模型并设计合适的求解算法。

1.2 数学模型

根据以上对下料车间的描述，建立以下假设和约束：

(1)任一时刻一台机器只能切割一段零件，且每段零件只能被约定的机器所切割；
(2)切割过程不可中断，不考虑设备故障；
(3)零时刻，所有型材均可切割；
(4)假设所有设备切割一段零件用时相同；
(5)料框中的零件需齐套存储；
(6)一个料框可以容纳一台套零件，并且可以由一台AGV移动；
(7)忽略AGV行走过程中的拥堵等待；
(8)假设各条产线平行布置，依次顺序编号。

为描述该车间作业问题，对数学模型中的主要参数作如下定义：

表1 参数定义汇总表

优化的目标函数为：

(1)

(2)

s.t.

(3)

i,j,q∈N*；

(4)

xij+M(1-Api)+M(1-Zih)+

M(1-Zph)≥Cp+tijh,i,j,p∈N*；

(5)

xpj+M(Api)+M(1-Zih)+M(1-Zph)≥

Ci+tpjh，i,j,p∈N*；

(6)

(7)

m∈[1,Ik],i,j∈N*,k∈[1,K],h∈[1,H]；

(8)

i,j∈N*,k∈[1,K],h∈[1,H]。

(9)

其中：式(1)表示优化目标1为AGV所有转运任务完成所经过的路程之和最短。其中，加工完成顺序相邻的两段零件所处的加工产线间的距离为需要AGV接运的距离。式(2)表示优化目标2为加工完成时间顺序相邻的同台套的两个零件所属的加工产线不同，这种情况出现的次数最少，即物料下线时需要AGV搬运料框前往另一条产线承接物料的次数最少。式(3)和式(4)表示同一根型材的两段零件切割完工时间之差大于等于后一段的切割加工时间。式(3)和式(4)共同确定了同一根型材的各段零件切割的先后顺序。式(5)和式(6)表示同一条产线上后一根型材的任意一段的切割完工时间大于等于前一根型材的完工时间与该段型材的加工时间之和。式(5)和式(6)共同确定同一条产线各根型材之间的加工顺序。式(7)表示一根型材只能由一条产线加工；
式(8)将属于同台套的零件按加工完成的先后顺序排序，完工时间相同的按所在产线编号从小到大排序。式(9)确定了同台套的零件的加工产线。

由于采用AGV分拣的PBWGS问题具有强NP难的特点[18]，常采用遗传算法求解该类问题[19-21]，但也存在过早收敛和后期搜索效率低的问题，因此，结合研究问题的特点，本文提出了改进的遗传算法，采用三层编码，第一层表示型材型号，第二层表示零件所属的台套，第三层表示加工属性，同时在交叉变异时，将第一层与第二层分开处理，防止两者的同时变化丢失部分优秀基因，以增强全局搜索能力，并提出了不同的邻域搜索方式以构造两层不同的邻域，最后以双层禁忌表的方式将两层邻域协同优化，提高算法的效率和适用性。算法流程图如图3所示。

2.1 染色体的编码与解码

本文采用如图4所示的带加工属性的多层矩阵式编码，厂区有3条生产线，各自的任务互不相同。每层产线编码有三层，从上至下，第一层为原材料型号层，表示先下料的是外径50 mm，壁厚4 mm的圆钢，后续为外径50 mm，壁厚3 mm的圆钢；
第二层为台套属性层，表示第一根圆钢被切为4段，分别用于台套编号为第3、1、3、4的整机；
第三层为加工属性层，表示切割的4段零件长度分别是2 000 mm，1 800 mm，2 600 mm，3 300 mm。

2.2 适应度计算

如前文所述，本文优化的目标是最小化AGV的使用成本，最终可以转换为AGV的有效工作时间。相邻产线间转运一次需要完成两次转弯进接运区举升料框的动作，完成一次动作耗时为t，在产线间移动速度为v，产线间距为b。因此总时间为：

(10)

适应度函数值与染色体被选择概率成正比，AGV成本越低，表示优化效果越好，染色体越应该在进化过程中被保留，因此将适应度函数设置为：

(11)

2.3 初始种群生成

为了增加种群的丰富度，将第一层型材的下料顺序随机打乱并同时随机打乱第二层型材内部零件的排列顺序，以生成初始种群。

2.4 迭代过程

2.4.1 选择

采用轮盘赌规则对各个染色体进行选择，染色体的适应度值与被选择概率成正比。其选择概率为：

(12)

式中aj表示种群中的染色体。

为防止最优个体没有被选择到的特殊情况，本文采用精英选择模式，直接将最优个体放在新种群的第一位。

2.4.2 交叉

交叉算子：

(13)

其中：Pc为个体的交叉概率，Pc1和Pc2为最大、最小交叉概率，f′为个体适应度值，fmax为种群中的最大适应度值，favg为种群的平均适应度值。

由于染色体第一层的顺序变化和第二层的顺序变化都会对适应度值产生影响，两者同时交叉容易丢失最优解，本文采用第一层和第二层分开交叉的模式，50%的个体进行第一层的交叉，50%的个体进行第二层的交叉，两层交叉均采用两点交叉，如图5所示以一条产线的染色体为例说明第一层交叉的步骤。其中P1和P2代表两个父代个体，C1和C2分别代表其对应的交叉后的子代个体，具体步骤如下：

步骤1在种群中随机找到两个个体P1和P2，并在第一层随机找到两个交叉位置点a和b；

步骤2将父代个体P2的a和b之间的第一层基因O50×4和O102×6赋值给P1的子代个体C1相应的位置，同时将P1的a和b间的第一层基因O60×3.5和O50×3赋值给P2的子代个体C2相应的位置。而C1的O50×4和O102×6的第二、三层属性继承P1中的O50×4和O102×6的第二、三层属性。同理，C2的O60×3.5和O50×3的第二、三层属性继承P2中的O60×3.5和O50×3的第二、三层属性。

步骤3子代个体C1其他空缺基因位全部从P1中继承，按其在P1中的位置左右顺序在C1中从左到右填补。以图5所示为例，子代个体C1已经通过交叉确定了a、b之间O50×4和O102×6两段基因，然后将P1中剩余的O60×3.5、O50×3和O89×4三段基因依次填补在C1的3段空缺基因位上。同理，子代个体C2也从P2中继承并填补。

步骤4同理，对于种群中的其他个体也进行交叉操作，得到新的种群。

这样的方式避免了某些可能的优秀基因在交叉过程中丢失，如图5中，若C1直接继承了P2的a与b间的三层基因位，C2继承了P1的a与b间的三层基因位，则两个子代中的O50×4都将从P2继承，此时P1的O50×4的后两层属性就会在该过程中丢失。

第二层交叉的步骤与第一层类似：

步骤1如图6所示，在种群中随机找到P1和P2两个个体，并在P1中随机选择一段基因，如第一层编号为O50×4的基因。

步骤2在P2中找到第一层编号同样为O50×4的基因(若有多个第一层编号为O50×4的基因，则应该选择第二层同样具有4,2,2,1,3,5,5,1这8个片段的基因)。

步骤3在基因O50×4的后两层染色体中随机确定两个交叉位置a和b。

步骤4将P1的O50×4基因第二、三层的a和b之间的片段交叉给C2的O50×4基因第二、三层的a和b之间，同理可将P2的基因片段对应交叉给C1。

步骤5将C1的O50×4基因其他缺失位按照P1的O50×4基因中的剩余基因片段依次补齐。同理补齐C2的基因，完成第二层的交叉。

步骤6同理，对于种群中的其他个体进行交叉操作，得到新的种群。

2.4.3 变异

变异算子：

Pm=

(14)

其中：Pm1、Pm2为最大、最小变异概率。

变异操作是为了保持种群的多样性，防止算法早熟。变异操作同样分两阶段进行。首先，将每段基因的3层视为一个整体，随机选择两个基因位互换位置，完成第一阶段变异；
其次，随机选择某一段基因的第二和第三层，将其排列顺序做倒序互换，完成第二阶段变异。通过变异，在较强的局部搜索能力下，兼顾了全局搜索的能力[22]。

2.4.4 邻域解的生成

为了提高算法的局部搜索能力和效率，根据PBWGS问题的特点，设计了插入、反转、打乱等3种邻域构造方式。同时引入禁忌搜索算法中的禁忌概念，以双层禁忌表的形式将两层邻域协同优化为完整的邻域解。邻域解的生产流程如图7所示，在第一层邻域结构设计和第二层邻域结构设计的基础上，构建协同优化策略生成最终邻域解。

(1)第一层邻域结构设计

根据本文的染色体设计，染色体中各基因的第一层确定了各并行生产线上各型材的顺序，选用插入操作来构造邻域结构，步骤如下：

1)随机选择一个染色体，假设含有m+1个基因。在第一层中随机选择一个基因位。

2)将选择的基因位插回该染色体中，共有m+1种插法，可以构造m+1个邻域结构。其中基因的第二和第三层属性跟随第一层的移动而移动，但内部不发生变化。

3)计算m+1种邻域结构的适应度值，选择其中最优者作为第一层的邻域结构。

(2)第二层邻域结构设计

第二层确定了型材内各段零件的加工顺序，采用反转和打乱的方式构造邻域结构。

1)随机选择一个染色体，在第一层中随机选择一个基因位，提取该基因位的第二层基因。

2)在第二层基因中随机选择两个位置，将两个位置间的基因采用反转和打乱的方式构造邻域结构。第三层属性跟随第二层移动。

3)计算各邻域结构的适应度值，选择最优者作为第二层的邻域结构。

(3)组合生成邻域解

以上将染色体的第一、二两层分开构建邻域结构，但两层属性有很强的关联性[8]，对适应度值都有决定性作用，因此两层邻域结构的有效组合对算法的性能至关重要。为此，本文设计了基于禁忌表的协同优化策略来生成最终邻域解，思路如下：

1)随机选择染色体，随机选择第一层一个基因位，判断该基因是否已经在禁忌表1中，若是，则更换基因位;否则将其放入禁忌表1，然后构造第一层邻域结构；

2)选择第一层随机基因位，判断该基因是否已经在禁忌表2中，若是，则更换基因位;否则将其放入禁忌表2；

3)将选择的第一层基因位下的第二层基因构造邻域结构；

4)混合两层邻域结构，生成邻域解，其中第二层属性跟随第一层移动，第三层跟随第二层；

5)重复上述步骤，生成足够数量的邻域解。

以图6所示的P1染色体为例，邻域解的生成过程如图8所示。

以某塔吊型材下料车间为案例，验证算法的可行性。以该车间使用的某型号叉车AGV为例，该AGV使用锂电池，容量为24 V 210 Ah，负载情况下可运行时间约为6 h，直线速度v=1 m/s，产线间距3.2 m，转弯进接运区举升料框耗时30 s。则

(15)

鉴于企业实际数据保密的要求，如表2所示的算例数据基于实际数据进行适当地处理。其中：算例0为某日的实际生产数据，算例1和算例2为处理后的数据。

表2 算例参数表

3.1 参数设置

参数设置与问题规模有关，且对实验结果有显著影响，本文选用经典的遗传算法参数[23]，并结合大量实验结论[24]，确定了自适应变异参数。本文最终的参数设置如表3所示。

表3 算法运行参数表

3.2 仿真实验结果分析

为了验证算法有效性，将本文算法与基础遗传算法、基础蚁群算法、变领域改进遗传算法[25]，以及改进蜂群算法[26]在3种批量数据下进行对比。基础遗传算法采用种群规模50，迭代次数200，交叉概率0.9，变异概率0.1。基础蚁群算法采用启发式因子α=1，β=5，信息挥发系数ρ=0.6，信息素强度因子Q=1 000进行计算。由于作为对比的各种算法编码方式与本文模型不匹配，本文多层编码第一层和第三层属性只在于区分型材原料和零件参数，不会对迭代结果产生影响，因此将各算法原来的实数编码统一改为本文的多层编码，在此基础上对5种算法进行综合比对，每个算法进行10次运算，取最优值，仿真实验环境采用MATLABR2018a仿真软件，Intel(R)Core(TM)i5-9400F,2.90GHz处理器，内存为16.00GB，结果如表4所示。不同规模数据在5种算法下迭代效果对比如图9所示。

表4 5种算法在不同大小规模下的实验结果对比

由表4和图9可以看出，相对于随机生成的调度方案，几种算法均有显著改善，但改善效果仍有差异。本文采用多层编码的改进遗传算法在优化效果和效率上都优于其他算法。变邻域改进遗传算法在前期效果显著，但随着问题规模的加大，邻域结构越来越复杂，迭代出更优解的时间大幅增加，收敛速度较慢；
改进蜂群算法在全局搜索能力上有一定优势，但同样存在随着问题规模的加大导致收敛速度慢的不足。本文的改进遗传算法在求解采用AGV分拣的PBWGS问题上，首先采用多层编码的方式，相较其他算法，能更好地区分型材、台套和零件的关系。其次，在交叉变异过程中采用分层式处理的方式，避免优秀基因的丢失，增强了全局搜索能力。最后采用邻域搜索机制来构造不同层的邻域结构，并提出了基于禁忌表的双层协同优化策略，能有效构造出高质量的邻域结构，禁忌表的采用也减少了无效邻域的生成，大大增强了局部搜索能力。与其他算法相比，既有更好的收敛效果，也能很好地表达复杂的加工信息， 在该类问题的求解上具有显著优势。

实际生产应用中，算法的鲁棒性至关重要。相较于算法的优越性，每一次的求解高效且稳定对生产更为重要。本文对算法10次重复运行的结果进行统计分析，绘制箱线图如图10所示。

从图10可以看出，改进遗传算法在求解采用AGV分拣的型材下料车间成组调度问题上，在不同的批量数据下，都能保持较高的鲁棒性，更适合企业实际需求[27]。

本文针对型材下料车间智能化程度低、效率低、成本高的问题，采用了AGV分拣的新方式，并在此基础上优化AGV分拣的成本，对采用AGV分拣的型材下料车间成组调度问题建立混合整数规划模型，并针对该问题开发了改进的遗传算法。采用第一层表示型材型号、第二层表示零件所属台套号、第三层表示零件加工属性的多层编码方式，提出将第一层和第二层分层交叉变异的方法，同时采用插入、反转、倒序的方式构造不同层的邻域结构，并使用含有双层禁忌表的协同优化策略生成邻域解。通过算例将本文算法与其他算法进行对比，表明所设计算法在解决该问题上具有显著优势和较好的鲁棒性。

采用AGV分拣的型材下料车间调度问题涉及较多要素，如AGV数量约束等，实际生产中存在多条线可加工相同型材的情况等，以及本文将型材排样结果作为调度的输入条件，而型材排样方案与型材切割调度两者可以结合做联合优化等，这些都可以作为进一步研究的方向。

猜你喜欢产线型材邻域昆玉棒材轧制产线提速增效工艺改进措施山东冶金(2022年4期)2022-09-14基于混合变邻域的自动化滴灌轮灌分组算法农业工程学报(2022年7期)2022-07-09朗盛推出空心型材混合技术上海建材(2021年5期)2021-02-12梅钢1780产线高速钢轧辊使用维护冶金设备(2020年2期)2020-12-28稀疏图平方图的染色数上界吉林大学学报（理学版）(2020年3期)2020-05-29多品种小批量智能制造产线关键技术及应用探讨电子制作(2019年20期)2019-12-04宽厚板钢轧一体化智能制造示范产线推进实践山东冶金(2019年3期)2019-07-10被动房用四密封多断桥隔热铝塑共挤型材中国建筑金属结构(2019年4期)2019-05-15基于邻域竞赛的多目标优化算法自动化学报(2018年7期)2018-08-20一种用于低压开关柜“S”形型材的设计与运用山东工业技术(2016年15期)2016-12-01