基于GEP-DES的柔性流水车间机器与AGV集成实时调度方法

白朝阳,张昊楠,苗琪琪+,刘晓冰,熊 麟

(1.大连理工大学 经济管理学院,辽宁 大连 116024;2.制造管理信息化技术国家地方联合工程实验室,辽宁 大连 116024;3.中国国际工程咨询有限公司,北京 100048)

0 引言

随着社会经济水平的提高,用户需求趋向于定制化和个性化。为了满足市场多样化需求,提高制造柔性与资源利用率,以及降低制造成本,制造企业的生产模式也由传统的专线生产转向灵活机动的多品种小批量混流生产模式[1]。其中,柔性流水车间综合柔性生产以及流水生产的优势,能够适应多样化、差异化产品的混线生产,现已成为制造企业应对多品种小批量混线生产的主流模式[2],特别是造纸、纺织、制药、化工、汽车和半导体等领域。

关于柔性流水车间的研究,普遍聚焦于解决机器优化调度问题,即为每个工件的每道工序选择合理的加工机器、制定合理的加工顺序以达到优化生产的目的[3-4]。但在大多数研究中,忽略了工件在不同工序间的流转运输过程,这与实际情况不符。近年来,智能制造已成为一种巨大的趋势,制造企业大量引进自动化生产与物流装备。其中,自动导引小车(Automated Guided Vehicle,AGV)因其高效、灵活、自动化等特点被广泛用于车间生产中,完成加工过程中的工件搬运任务。然而生产物流会变得更加复杂,只考虑单个因素会影响资源配置的效果,进而影响整个车间的生产管理效率。因此,越来越多的研究开始考虑多资源集成问题,即将机器与AGV集成起来调度以达到提高生产系统敏捷性以及系统工作效率的目的。从长远来看,这也是实现智能制造的必然要求。

有关柔性流水车间机器与AGV集成调度的研究,学者们多数基于智能优化算法进行求解。LEI等[5]基于改进的文化基因算法对存在AGV配送的多阶段柔性流水车间问题进行了研究,考虑两种不同缓冲区状态的设定并分别进行求解;FAROOP等[6]在对纺织流水车间中AGV与机器集成调度问题求解时,设计了改进的遗传算法;耿凯峰等[7]考虑存在工序跳跃的柔性流水车间中AGV与机器集成调度问题,以最小最大完工时间和总能耗作为优化目标,基于启发式算法对问题进行了求解;廖勇等[8]针对考虑AGV运输的柔性流水车间问题,通过改进的状态空间分解法进行排队网建模与分析,并进行仿真实验证明了所提出方法的有效性。但上述研究均基于静态视角,即所有信息均已提前获知,而在实际生产过程中往往存在复杂的不确定因素,如订单时间到达不确定、订单品类不确定、工序加工时间长短不确定、加工设备故障等不确定因素[9],这些不确定因素使得企业提前制定的计划往往与执行之间出现偏差,原始调度方案不再有效[10]。如今,在智能制造环境下,传统车间中融入了大量的物联网信息技术,如无线射频技术、RFID等,车间生产中的相关信息可以通过一系列智能车间装置实时感知[11],实时数据的可用性越来越高,有利于减少不确定因素对生产的影响,但也使得高效实时调度成为一个非常具有挑战性的问题。

有关实时调度的研究,现有文献通常采用调度规则的研究方法,由于调度规则在算法求解时具备较低的时间复杂度,能够针对扰动及面对的动态因素做出快速的响应,非常适用于实际车间生产[12]。但尽管存在以上有优点,传统意义上的单一的调度规则很难在复杂的场景中表现出很好的适配性[13]。因此,如何针对不同场景下的生产调度问题提出有效的调度规则是提高系统效率的关键。

目前关于选择合理调度规则的方法可以被归纳为两类:

(1)采取枚举法遍历调度规则集合,通过仿真实验对比确定最合理的调度规则。但仅适用于小规模问题,当研究场景变得复杂时,问题的时间复杂度也会提升,不再具备求解优势。

(2)结合智能优化算法对调度规则进行选择,主要的求解思路也可以被归纳为以下两种:①构建开发调度规则库,结合具体的车间环境参数通过优化算法完成规则的选择。如吴秀丽等[14]从历史数据中提取调度知识挖掘的样本,利用人工神经网络完成生产系统状态和调度规则之间的映射训练,指导车间的实时调度;OUKIL等[15]针对存在多目标优化的流水车间调度问题,基于数据包络分析法对不同参数下的车间调度问题进行调度规则的选择;GUH等[16]针对柔性生产系统,综合多个性能指标,给出了基于自组织映射 (Self-Organising Maps,SOM)的实时多调度规则选择机制。②结合智能优化算法挖掘出新的调度规则。常用的智能优化算法有遗传规划,如马丽萌等[17]基于仿真优化与遗传规划 (Simulation Optimization-Genetic Programming,SO-GP)算法对智能车间调度规则进行挖掘,以在优化生产性能的同时满足车间实际生产中实时调度的需求;范华丽等[18]将工件平均加权拖期最小化作为调度目标,利用遗传规划的方法挖掘新的调度规则,并与其他传统规则对比证明挖掘规则的优越性。

除此之外,基因表达式编程算法(Gene Expression Programming,GEP)广泛应用于函数挖掘、规则发现等领域,很多研究通过GEP算法来完成调度规则的挖掘。比如,NIE等[19]考虑工件动态到达的情况,提出了基于GEP算法的调度规则挖掘方法;ZHANG等[20]将GEP算法应用于考虑能源消耗问题的车间调度中,并对所提出的GEP算法进行改进,弥补了传送方法易陷入局部最优的缺点,证明了由改进GEP算法所得出的调度规则在提升车间效率以及减少车间能源消耗问题上的优势;TEYMOURIFAR等[21]考虑了工件及设备故障的不确定因素,设计了基于GEP算法与离散事件仿真相结合的调度方法,并与其他调度规则对比证明了其在生产效率方面的优势。由此可见,通过GEP算法为特定的调度环境生成有效的调度规则是可行有效的,但在解决柔性流水车间加工机器与配送AGV集成调度的问题上还没有得到应用。

基于以上讨论,本文针对柔性流水车间中机器与AGV集成调度问题,考虑工件随机到达(工件品类与到达时间随机)以及加工时间波动的不确定因素,以最小化最大完工时间作为优化目标建立集成实时调度模型并提出将基因表达式编程算法与离散事件仿真(Gene Expression Programming and Discrete Event Simulation, GEP-DES)相结合的实时调度方法。首先在离线阶段完成对机器与AGV集成实时调度问题的编码设计,然后通过DES建立并验证多种规则下机器与AGV集成实时调度方案,接着挖掘出有效的调度规则以指导在线阶段的实时调度,最后通过实验算例表明该方法的合理性和有效性。

1 问题分析

1.1 问题描述

本文所研究的柔性流水车间机器与AGV集成调度问题场景如图1所示。柔性流水车间布局已知,总共有M台存在缓冲区的机器和V台AGV。P种类型的I个工件实时到达,且到达时间不可预测。最初,工件i被存放在初始库中,为进行第一道工序的加工,工件须在可供选择的m台并行机内挑选一台进行加工,在选定之后发出搬运指令呼叫AGV,从v辆AGV中选择一辆完成搬运任务。若选定的第v辆AGV没有排队的任务,则空载前往工件i所加工完成的机器位置并搬运其到下一工序j所选的机器缓存区的位置;若选定的第v辆AGV已经有排队中的任务,则应待任务均完成后再执行工件i的搬运任务。在进行第二道工序以及以后的每道工序时,首先考虑工件类型、缓冲区工件数量、机器处理时间等规则进行机器选择决策,即工件i选择加工机器m;其次考虑工件完工时间、交货期时间、延迟成本等规则进行作业选择决策。当缓存区存在多个待加工工件则需给机器安排作业顺序(即工件的加工顺序),否则机器的作业顺序确定。最后,考虑任务量、空闲时间、利用率等规则进行AGV选择决策。根据AGV选择结果完成相应的搬运任务。该问题的研究目标是将工件类型与到达时间不确定的工件调度到可用的机器上,确定机器的作业排序方案,并安排有限的AGV完成工件在不同工序的搬运流转任务,最小化最大完工时间,最终完成是实时环境下的机器与AGV集成调度方案,促进柔性流水车间资源有效利用,提高生产效率。

结合实际并考虑到问题的复杂性,本文作出以下常见假设:①在初始时刻,所有机器和AGV均可以使用,AGV全部位于AGV起始点处;②过程中不存在AGV或机器出现故障的情况;③不考虑AGV电池容量问题;④每台AGV的容量为1,即只可负载一个工件;⑤每台机器只能同时处理一个工件;⑥每台机器拥有一个缓冲区,等待机器加工的工件与完成加工的工件共用这一个缓冲区,缓冲区容量为无限;⑦机器与AGV一旦开始作业就不能停下直到该作业完成;⑧为防止AGV产生路径冲突问题,在AGV完成运输任务而等待下一任务到达时可围绕轨道进行自动路由。

1.2 柔性流水车间机器与AGV集成调度数学模型

1.2.1 参数定义

i表示工件的索引,i=1,2,…,I;

j表示工件的加工工序,j=1,2,…,J;

p表示工件的类型,p=1,2,…,P;

m表示机器的索引,m=1,2,…,M;

v表示AGV的索引,v=1,2,…,V;

PSijm表示工件i的第j道工序在m机器上的加工时间;

ri表示工件i到达系统的时间;

lip,如果工件i属于类型p则为1,否则为0。

1.2.2 决策变量

MSijm为工件i的第j道工序在m机器上的加工开始时间;

MCijm为工件i的第j道工序在m机器上的加工完成时间;

MCi为工件i的最终加工完成时间;

BSijm为工件i的第j道工序在到达m机器缓冲区后待加工等待时长;

BCijm为工件i的第j道工序在m机器加工完成后在缓冲区的等待时长;

Xijm若工件i的第j道工序在m机器上加工则为1,否则为0;

Yijv若工件i的第j道工序由第v辆AGV进行搬运则为1,否则为0;

Ziji′j′m若工件i的第j道工序优先于工件i′的第j′道工序在m机器上加工则为1,否则为0。

1.2.3 数学模型建立

(1)

s.t.

(2)

(3)

(4)

MCijm=MSijm+PSijm;

(5)

(6)

(7)

(8)

(9)

MSijm≥MSi′j′m×(1-Ziji′j′m);

(10)

MSi1m>ri。

(11)

其中:式(1)表示本文的目标函数是使最小化最大完工时间。式(2)表示工件的每道工序最多只能由一台机器来加工;式(3)表示工件的每道工序最多只能由一辆AGV进行转运;式(4)表示每个工件只能属于一种类型;式(5)表示工件在机器上的加工完成时间等于工件在机器上的开始加工时间加上加工时长;式(6)表示工件在机器上的加工开始时间等于AGV负载运输结束时间加上待加工工件在对应机器缓冲区的等待时间;式(7)表示AGV开始负载的时间等于工件上一阶段完成加工时间加上已经完成上一阶段加工任务的工件在缓冲区的等待时间;式(8)表示AGV的空载结束时间等于AGV的空载开始时间加空载运输时间;式(9)表示AGV负载运输开始时间不早于AGV空载运输结束时间;式(10)代表加工工序顺序的约束;式(11)表示工件在其到达生产系统之前不能被处理。

2 基于GEP-DES的调度规则挖掘

2.1 问题结构化分解

考虑到所建模型的复杂性,借鉴文献[22]中复杂问题结构化分解的思想,将原问题分解柔性流水车间调度问题和AGV调度问题。针对问题分解的组合调度构造过程如图2所示。首先通过结构化分析对原有问题进行分解,然后针对分解后的子问题构建相应的调度规则,最后对各子问题对应的调度规则进行组合形成求解模型的组合调度规则。

对于柔性流水车间调度问题中,首先确定到达工件的种类,根据工件工艺要求需要使用不同的机器进行加工。同时,机器的缓冲区工件数量、机器的工作效率以及机器的最早可用时间等属性是影响其优先级的因素,因此确定机器选择规则安排工件的每道工序需要由哪台并行机器进行加工,即机器选择过程。其次,确定各道工序中工件的加工顺序,即工件排序过程。这一过程需要考虑工件的到达时间、工件的交货期以及工件的加工时间等属性,进而确定工件排序规则实现工件排序过程。而对于AGV调度问题,基于AGV的完成任务数量、空闲时间等属性确定AGV选择规则,进而确定AGV的优先级以解决工件的工序流转由哪辆AGV来执行,即AGV选择过程。

因此,对以上分析的3个子问题的调度规则进行组合,形成求解柔性流水车间机器与AGV集成调度问题的组合调度规则DR,可用式(12)表示,其中,MS代表机器选择规则、JS代表作业排序规则、AS代表AGV选择规则。

DR={MS,JS,AS}。

(12)

2.2 基于GEP-DES的柔性流水车间机器与AGV集成调度规则挖掘框架

为了有效解决柔性流水车间机器与AGV集成实时调度问题,将GEP算法与DES方法相结合。GEP是一种进化算法,通过GEP算法为本问题挖掘出新的高质量的调度规则。针对调度规则评价需要基于实时工况数据,评价模型难以构建的问题,采用DES进行参数化建模,构建可复用的调度仿真模型。此外,由于此问题具有组合性质和动态不确定性,而DES方法在动态不确定系统方面是有效的[24],通过DES方法可以获取目标函数值以实现GEP指标性能的评估。因此DES方法可以被用来验证柔性流水车间机器与AGV集成实时调度环境下多种规则的有效性。鉴于上述考虑,提出基于GEP-DES的柔性流水车间机器与AGV集成实时调度框架,如图3所示。主要包括离线调度规则挖掘阶段与在线调度优化方案生成阶段两个阶段。离线调度规则挖掘阶段的主要目的是应用GEP-DES算法挖掘高质量的调度规则,这是实现在线实时调度的核心关键技术,因此本文重点对此进行研究。在离线调度规则挖掘过程中,解空间较大,耗时较长,但挖掘得到优秀调度规则有利于丰富企业的调度资源规则库和帮助企业更好的应对不同场景下的调度规则选择。特别值得注意的是,挖掘出的优异调度规则是有关各个属性的多项式,其在在线实时调度中的时间开销与传统的简单规则相当,并不会明显提升在线调度时间[17]。因此,在线调度阶段主要是应用离线阶段挖掘出的高质量调度规则,通过感知车间中的实时工况数据做出即时调度决策。

离线调度规则挖掘阶段首先确定车间相关参数如工件到达数量、工件交期、车间布局等参数以及需要决策的调度目标的输入,为构建调度规则库做准备。在此基础上,GEP组合调度规则生成模块结合DES组合调度规则评价模块实现规则的自动挖掘,这一步骤的详细过程为:

(1)对组合调度规则进行编码完成初始种群的生成。由上文可知,本文所研究的问题主要包括机器选择、作业排序与AGV选择3个子问题,因此每一条染色体由这3部分内容构成,代表一组挖掘出的规则。

(2)对挖掘出的规则进行遗传操作,包括交叉操作、变异操作、RIS插串操作等,将操作完成的染色体输入DES组合调度规则评价模块。

(3)将输入的染色体进行解码,并结合输入转化的参数、解码后得到的染色体以及构建的车间调度仿真模型进行仿真,最终得到该组挖掘规则下的适应度函数值。再将得到的适应度函数值输入回挖掘规则生成模块。

(4)进行种群的选择,选择之后判断是否满足迭代次数,如满足则输出最终的挖掘调度规则,否则返回遗传操作部分。

在线调度阶段通过射频识别器,二维码扫描器、GPS定位等数据采集设备获得实时生产资源状态数据,实现信息实时交互,每当需要进行调度决策的时候,将采集到的机器缓冲区数量、机器完工时间、工件到达种类、数量与时间、AGV空闲时间等实施工况数据输入在线调度模块。基于离线挖掘阶段挖掘出的调度规则计算设备优先级、工件优先级和AGV优先级,指导实际生产中机器与AGV运作。

2.3 GEP算法设计

2.3.1 函数集和端点集

(1)函数集

(2) 端点集

传统研究多使用车间参数作为研究的端点集合,但相关文献[23]指出,利用传统调度规则的优化效果要比传统的车间参数的效果更好。基于2.1节中所提到的问题结构化分解过程,将分解后的作业排序、机器选择、AGV选择3个子问题的传统调度规则作为本文研究的端点集合。

本文将作业排序、机器选择、AGV选择3个子问题的传统调度规则作为本文研究的端点集合,具体如表1所示。

表1 传统调度规则

2.3.2 编码与解码

(1)编码

(2)解码

在解码时首先对K-表达式进行广度优先遍历,将其转化为表达树的形式,即整个基因片段的第一位基因作为表达树的根节点,随后按照顺序将基因依次置于表达树上的节点位,直到最后一层表达树的全部节点位均属于端点集中的符号;其次,采用中序遍历算法对表达树进行遍历,即按照左子树-根节点-右子树的顺序实现整个表达树的遍历。以上文中提到的图1为例,图5所示为对其进行解码的具体过程。

2.3.3 适应度计算

对解码后的染色体进行适应度函数的计算,适应度的计算方式按照解码后得到的组合调度规则表达式进行。在计算过程中为避免端点集合中所选参量量纲不统一的问题,对相关参数进行归一化处理,具体计算过程如式(13)所示。

(13)

式中:kmax和kmin表示端点集合中工件、设备或者AGV参数值的最大值和最小值;k为工件、设备或者AGV的参数k的值。k是经过归一化处理后的参数值,以此作为确定工件优先级的标准值。

2.3.4 基于有效长度的遗传操作

在GEP算法的编码过程中会存在部分基因片段在解码后的函数表达式中并无作用的情况,因此传统意义上的遗传操作可能并不能保证种群的有效进化,需基于染色体的有效长度进行遗传算子的设计。以图1及图2中提到的染色体为例,该染色体的有效

长度定义为在转化成K-表达树后所包含的节点个数,为{5,8,5}。下面将具体介绍本文所述的遗传操作。

(1)选择算子

本文采取带精英选择算子与锦标赛算子相结合的方法进行染色体的选择。即保留种群中一定比例的最优适应度值的染色体,剩下的染色体通过锦标赛的方法,即随机选取两条染色体进行对比,保留适应度值更优的染色体,直到达到种群数量。

(2)交叉算子

本文设计两种交叉算子,分别为单点位交叉算子以及双点位交叉算子。前者是在染色体的有效长度内任取一点位作为基因交叉点,指将两条染色体基因位交叉。如图6a所示,首先计算需要执行交叉操作的两条染色体中有效长度的最小值Lmin以及最大值Lmax。其次在[1,Lmin]中随机选择一点作为交叉位。后者是指在染色体的有效长度内任取两点作为基因交叉点位,交换两条染色体两点位之间的染色体。如图6b所示,首先计算出Lmin以及Lmax,其次在[0,Lmin]中随机选择点作为起始交叉位C1,然后在[C1,Lmax]之间随机选择另一个点位作为终止交叉点位C2。

(3)变异算子

本文采取单点交叉算子,选择基因片段与头部长度的较小值作为变异点位的最大临界值Lmax。具体如图6c所示,在[0,Lmax]内选择一点位作为染色体的变异点,当选择的位置处于头部片段时,应从函数集或端点集中选择一元素作为该点位的替代基因,而当选择的位置处于尾部片段时,应从端点集中选择一元素作为该点位的替代基因。

(4)RIS插串算子

RIS(root insertion sequence)插串算子是GEP方法中独有的算子,其作用在于通过破坏染色体的表达结构进而增强算法的求解搜索能力,具体操作如下图6d所示,首先在长度为h的头部片段中选取一基因点位R1,其需要满足是函数集中某一元素。其次在[R1,h+t]范围内随机选择另一个基因点位R2。之后将[R1,R2]所包含的基因片段移动至该条染色体的首置位置,对应的其他元素按顺序后移。最后,从原头部片段末尾位置删除与插入片段相同长度的基因段,从而确保获得合理结构的染色体。

3 实验设计及结果分析

3.1 算例设计与算法参数设计

3.1.1 算例设计

本文的优化目标函数为最小化最大完工时间,因此参照LI等[24]提出的算例设计方案,并考虑设备的利用率和工件的交货期紧张因子。针对本文所研究的柔性流水车间中机器与AGV集成调度问题,对原有算例进行扩展,具体算例参数如表2所示。该算例参数表包含阶段数目、工件数量、工件品类、交货期紧张因子以及设备利用率5个参数,参数的分布范围分别设置3个水平值。

表2 参数设置

本文考虑实际生产中由于加工设备损耗程度不同、实际操作的工人的作业熟练程度不同而引发的加工时间存在波动的情况,设定机器的加工时间服从下界为30 s,上界为100 s,即U(30,100)的均匀分布。工件权重分布采取文献中常使用的“四二一”的方法[25]:非常重要的工件占比20%,其对应的权重为4;次重要的工件占比60%,其对应的权重为2;剩余工件占比20%,其对应的权重为1。工件j的交货期DDj的设定方法采取文献[26]中应用的计算方式,如式14所示。本文考虑的工件到达时间间隔服从参数为α的泊松分布,依照文献[27]中的计算方法,如式15所示。仿真场景的AGV的数量固定设置为3台,在4.3节实验中将会对仿真场景中的AGV数量进行调整实验。

DDj=C×Pj+ADj,

(14)

α=t×n/(m×U)。

(15)

其中:C表示上文所述的交货期紧张因子;Pj表示工件j的总加工时间;ADj表示工件j到达生产系统的时间。t表示加工工序的平均加工时间;n表示工件的加工工序数目;m表示仿真场景中所有的加工机器数目;U表示设备利用率。

正交试验法是研究具有不同水平的多种参数影响下一种高效且便捷的设计方法,其可以在缩短实验的同时满足解决问题的需求[28]。由于本文涉及多个影响参数且每个参数都包含多个水平,采用正交试验法提高处理效率。基于IBM SPSS Statistics 19平台生成如表3所示的16个不同规模的正交算例。

表3 算例设置

3.1.2 算法参数设计

为保证GEP-DES算法的有效性以及考虑实际车间调度的效率,经过多次仿真预实验,本文将GEP算法参数设置为:种群规模为20,遗传迭代次数为50,头部长度设置为[8,10,8],交叉率为0.5,RIS插串概率为0.7,变异概率为0.1,精英保留比率为10%。

本文的算法及仿真实验均是在操作系统为Windows 10,处理器为IntelI CoreI i5-10200H CPU @ 2.60 GHz,内存为2 G的环境下运行,基于Plant Simulation 16.0仿真平台进行实验。Plant Simulation是一款广泛应用于企业界和学术界的仿真软件,其功能强大,不仅可以实现离散事件仿真过程,还可以基于SimTalk编程语言融入优化算法并验证算法的有效性。围绕3.1.1节所设计的动态场景,仿真场景及仿真逻辑控制的构建结果如图7所示。仿真实验部分包括仿真场景、算法部分、规则部分等多个组成模块。

3.2 实验结果分析

为验证本文所提出的GEP-DES调度规则挖掘方法的有效性,针对上述设计的16组算例分别进行实验。整个算法的搜索过程如图8所示,每组算例的最大完工时间都是逐渐减小并收敛的,且通过算法收敛图可见大部分算例都是在30代以内开始收敛,证明了算法可以有效且快速的获得最优解,也证明了本文所提出的GEP-DES调度规则挖掘算法的有效性,可以在求解工件动态到达、工时不确定环境下的柔性流水车间生产与物流资源集成调度问题中发挥作用。如图9所示为针对算例2运用GEP-DES调度规则挖掘方法所得出的调度结果甘特图。其中,不同的颜色代表了不同的工件,不仅反映了每个工件在各个加工阶段的机器资源选择情况以及每个加工任务的开始时间与结束时间,还反映了每个配送任务的AGV资源选择情况,并包括了负载与空载过程的每个配送任务的开始时间与结束时间。表3以算例2的一次实验结果为例,给出经由GEP-DES算法挖掘出的一组调度规则。

表3 基于DES-GEP的调度结果挖掘

为证明本文提出的GEP-DES算法所挖掘的组合调度规则对于缩短工件最大完工时间的有效性,将其与传统最优的调度规则进行比较。传统最优的调度规则的获得步骤为:①根据上文模型中所提到的问题分解思想将规则表中的3个子问题的传统调度规则组合而成,因此构成3×5×3共计45组传统调度规则组合;②应用45组传统调度规则组合分别对上述设计的16组算例进行仿真实验,每组仿真实验进行10次;③最终得到的45组传统调度规则组合在16个算例下的性能平均排名顺序,如图10所示。由图10可见,最优的调度规则组合13(WSPT+WSW+MHT)、调度规则组合15(WSPT+WSW+LUR)和调度规则组合45(ATC+SP+LUR)。

将3组传统最优的调度规则组合和所提出的GEP-DES算法所挖掘的组合调度规则进行对比,实验结果如表4和图11所示。由图11形象地看出,基于GEP-DES算法所挖掘的组合调度规则总是位于最优位置。同样的结论也可由表4得出。进一步分析,与调度规则组合13相比,基于GEP-DES挖掘的调度规则优化比在5.3%～22.96%之间,平均缩短工件最大完工时间15.97%左右。与调度规则组合15相比,基于GEP-DES挖掘的调度规则优化比在5.84%～23.37%之间,平均缩短工件最大完工时间13.47%左右。与调度规则组合45相比,基于GEP-DES挖掘的调度规则优化比在5.21%～18.03%之间,平均缩短工件最大完工时间11.58%左右。总之,相较于传统的调度规则,基于GEP-DES调度规则挖掘算法可以有效减少工件的最大完工时间。

表4 基于GEP-DES算法挖掘规则与传统组合调度规则对比优化值

3.3 不同AGV数量对完工时间的影响

本文研究了AGV数量对车间工件最大完工时间的影响,分别选取AGV数量为1、2、3、4、5、6,对不同数量AGV的柔性流水车间机器与AGV集成调度问题进行求解。所用算例延用上文所设计的16组不同参数的算例,同样的每组算例重复仿真10次,以最后的平均值作为该组算例的最终结果,具体结果如图12和表5所示。

表5 不同AGV数量对最大完工时间的影响

由上述结果可知,系统中每增加一辆AGV,会对系统的最大完工时间有所减少,当系统中有2辆AGV时,比1辆AGV平均最大完工时间缩短了38.84%;当系统中有3辆AGV时,比2辆AGV平均缩短了21.69%;当系统中有4辆AGV时,比3辆AGV所需要的最大完工时间缩短了16.83%;当AGV数量来到5辆的时候,平均缩短的时间比只有10.21%。而当AGV数量来到6辆的时候,平均缩短的时间比只有7.03%。由此可见,随着AGV数量的增加,虽然工件的最大完工时间会有所缩短,但由AGV增加带来的最大完工时间缩短比却在不断减少,由AGV增加所带来的增益效果也在逐渐减少,因此,制造企业需要考虑车间资源的成本以及带来的收益,确定合理的AGV数量。

4 结束语

本文针对多种工件动态到达、工时不确定环境下的柔性流水车间机器与AGV集成实时调度问题进行了研究。首先,建立了以最小化最大完工时间为优化目标的机器与AGV集成调度模型。然后,考虑到问题的复杂性,将原问题分解为机器选择、作业排序以及AGV选择3个子问题,并设计GEP-DES实时调度方法。本文提出的方法包括离线阶段与在线阶段,其中离线阶段对组合调度规则进行挖掘,得到新的调度规则;在线阶段则采集现场实时数据,再使用所挖掘出的算法给出实时优化调度方案。最后,为了验证所提方法的合理性与有效性,设计不同车间参数下的16个算例的实验,证明了基于GEP-DES方法所挖掘出的规则与传统调度规则相比具有更明显的优势,能够大幅缩短工件的最大完工时间,提高制造系统的效率,满足车间生产中所需要的对生产资源与物流资源进行集成实时调度的需求。此外,基于不同数量的AGV进行仿真实验可知,所提出的基于GEP-DES的调度规则挖掘算法仍然有效,且当AGV数量增多时,工件的最大完工时间也在缩小,但平均缩短时间比却在减小,因此建议企业不要盲目引进AGV而是做好AGV数量规划。

在未来的研究工作中,一方面根据不断变化的环境增加更多的候选规则进而采用GEP-DES方法挖掘出更多高质量的调度规则,另一方面对挖掘出的高质量的调度规则进一步构建知识图谱来支持管理者高效决策。