基于粒子群算法和仿真技术的RGV动态调度建模与优化

引言

RGV(Rai1GuidedVehic1e),即有轨制导车辆,又称有轨穿梭小车。目前,RGV广泛应用于自动化仓库和自动化物流系统等领域。已有研究表明,部分学者集中研究了一维平面上RGV的运动,主要以环形轨道和直线轨道上运行的多辆RGV为研究对象。

例如:吴焱明研究了基于遗传算法的环轨RGV动态调度问题,通过eM-P1ant软件验证了模型的有效性。顾红针对环形RGV的工作特点,建立了RGV搬运作业的多目标调度数学模型,提出了基于自学习和改进遗传算法的环形RGV实时调度算法。江唯提出路径最短和拥堵次数最少两个优化目标,建立数学模型,设计了基于规则的混合遗传算法求解环形轨道上RGV的调度问题。陈华以救灾物资自动化立体仓库为背景,提出了直线轨道上基于区域划分的2-RGV碰撞避免调度问题的混合整数线性规划模型和混合遗传算法。国外学者Jackon于1957年最早提出了动态调度的概念,主要的研究方法包括启发式方法和仿真方法。刘俨后定义了动态事件,称引起调度环境变化进而需要进行动态调度的事件为动态事件,动态事件主要包括订单相关、工序相关和机器相关的三种情况,在此基础上研究了制造系统受到随机事件干扰情况下即有紧急订单插入事件的动态调度问题。Peteghem等设计了分层遗传算法,解决了多资源约束条件下的动态调度问题。

上述研究多以RGV的调度策略为切入点,对机器相关、订单相关的事件进行调度,但均未考虑与工序相关的工序排布问题。仿真方法不足之处在于每一次仿真运行只是对实际加工过程的一次抽样,不能进行有效的优化。

本文主要研究一智能加工系统与工序相关、与机器相关的事件发生后对动态调度产生的影响。与工序相关指工序排布不同导致对作业效率的影响,与机器相关指按照一定的调度策略为各工序分配合适的加工机床进行加工。为了弥补单一优化的不足,本文的工作是将仿真方法、调度策略和粒子群算法相结合,实现智能加工系统的动态调度。

1多目标优化模型

1.1仿真模型框架

模型的组成:该智能加工系统由l0台计算机数控机床(ComputerNumberContro11er,CNC)、l辆轨道式自动引导车(Rai1 GuideVehic1e ,RGV) 、l条RGV直线轨道 、l条上料传送 带、l条下料传送带等附属设备组成 。RGV可根据指令自动控制移动方向和距离 ,并自带一个机械手臂、两只机械手爪和物料清洗槽 ,能够完成上下料及清洗物料等作业任务。CNC的编号按奇偶数分布在上下料传送带的两侧 ,如图1所示。

假设10台CNC上共加工N件物料 ,每件物料由K道工序组成。单道工序的物料可在M台设备中的任一 台CNC上加工完成。多道工序的物料分别由不同的CNC依次加工完成 ,每道工序完成时间不尽相同。

问题假设:

(1)忽略物料上下传送带的时间:

(2)传送带上的物料不存在积压:

(3)RGV抓取物料的时候 ,物料已经在传送带上准备到位:

(4)RGV接收CNC发送的需求信号 ,并根据所在位置按照一定调度策略就近选择服务:

(5) 一件物料的加工工序只能在一个班次(设定为8 h) 中进行:

(6)所有CNC在时刻l=0都可用:

(7)加工是非抢占式的 , 即在给定时间段内 , 一 台CNC只能加工一件物料,只有当前工序结束后才能开始加工其他物料。

1.2 数学模型

通过分析 , 物料状态对应分为三种: 生料 、熟料 、成料: CNC状态对应分为三种:加工、空闲、故障:RGV状态有四种:移动、上下料作业、停止等待、熟料清洗 。对变量定义如下:

对于物料:

N:待加工生料数量集合 ,j=(l ,2 , … ,N):

N':加工完成的熟料数量集合 ,s=(l ,2 , … ,N') :

Ⅹij亿:物料亿第j道工序在编号为i的CNC上加工与否 ,Ⅹij亿=1 表示加工 ,Ⅹij亿=0表示不加工:

K:物料的工序数量集合 ,亿={1 ,2 , … ,K):

ⅩEQ \* jc3 \* hps10 \o\al(\s\up 3(亿 :物料亿第j道工序在编号为i的CNC上加工开始时间:

ⅩEQ \* jc3 \* hps10 \o\al(\s\up 3(亿 :物料亿第j道工序在编号为i的CNC上加工结束时间。

对于CNC:

皿:计算机数控机床CNC集合 ,i={1 ,2 , … ,皿):

tij亿:物料j第亿道工序在编号为i的CNC上加工所需时间。

对于RGV:

tEQ \* jc3 \* hps10 \o\al(\s\up 3(亿g:RGV响应上下料作业j的第亿道工序 , 移动g个单位(g+1台相邻CNC间的距离)到编号为i的CNC机床位置正中间所需时间。

对于RGV而言 ,它的时间主要包括四项:移动时间 、停止等待时间、上下料时间和清洗作业时间。

移动时间为RGV通过一定规则移动到要为其服务的CNC 正中间位置所需时间 ,表示如下:

根据上述分析 ,建立两个目标函数:系统作业效率最大化和RGV移动时间最短。

对于目标函数1 ,系统的作业效率n定义为单位时间(设为 min)内加工熟料的数量 ,故目标函数可表述为:

对于目标函数2 ,RGV移动时间最短可表述为:

约束条件s.t. :

约束条件中 ,式(4)表示物料j只分配给某一 台CNC加工:式(5)表示物料j第亿道工序必须在第亿- 1道工序完成后才能开始:式(6)表示第i台CNC上不能同时加工两个任意不同的物料;式(7)表示CNC加工物料的时间约束。

2 调度策略的建立

调度策略的建立主要考虑两个方面 ,其一 目 的在于使用人为制定的规则使RGV有导向地向指定目标移动 ,为相应的 CNC进行作业;其二目的在于考虑CNC上的加工工序排布 ,可以更加高效地完成对多道工序的物料加工 。根据对问题的分析,设定了三种动态调度策略:CNC工序分配、CNC编号奇偶优先和RGV任务分派策略。

2. 1 CNC工序分配策略

CNC工序分配策略指的是 ,在智能加工系统通电启动后 , RGV处于CNC1#和CNC2#正中间的初始位置 ,所有CNC都处于空闲状态。此时 ,假设CNC1、2、3、4、5、6、7、8、9、10上需加工完成两道工序的物料 ,其加工工序为2、2、2、2、2、1、1、1、1、1 ,此时编号为2、4、6、8、10的CNC上分别加工物料的第2、2、1、1、1道工序 ,编号为1、3、5、7、9的CNC上分别加工物料的第2、2、2、1、1道工序。

2.2 CNC编号奇偶优先策略

对于两道不同的工序 ,影响有效物料生产个数的因素有两方面 ,主要因素在于CNC工序1和工序2的不同排布 ,次要因素在于同一工序排布状态下CNC的奇偶优先性 , 即在CNC处于空闲的状态 ,优先分配编号为奇数的CNC还是编号为偶数的CNC进行物料加工。

2.3 RGV任务分派策略

CNC向RGV发送需求信号 ,到达RGV的指令信号视为一个任务队列。当物料送入传送带 ,RGV在收到CNC的需求信号后 ,将根据需求指令决定作业路径 。当某一 台CNC完成加工物料操作 , 由加工作业状态转换为空闲状态时 ,若RGV没有执行其他作业且正好处于该空闲CNC正中间位置 , 则优先响应对应位置上的CNC;否则 ,RGV执行移动操作 ,按照最短路径移动至空闲CNC的正中间位置 ,进行上下料作业。

3 粒子群算法设计

1995年 ,Kennedy等人提出了基于鸟群觅食行为的粒子群优化算法(Ps0) ,简称"粒子群算法" 。粒子群算法对于约束优化中的规划 ,离散空间组合问题的求解非常有效。多目标优化问题是粒子群算法的主要研究方向。基于此 ,本文结合自动化生产领域的智能加工系统 ,提出基于工序编码的粒子群算法 ,在一个班次的工作状态下 ,对系统的作业效率和RGV移动时间进行优化。

3. 1 基于工序的粒子编码

根据图1的智能加工系统示意图 , 以10台CNC、1辆RGV、加工两道工序的物料为例 ,将粒子做出如图2所示的编码设计 。首先给出一组随机解 ,设为0000011111 ,其中0表示第一道工序, 1表示第二道工序。然后以此为出发点 ,通过迭代寻找最优解。

图2中的第一行表示CNC编号 ,第二行表示机床CNC是否进行物料第几道工序的加工 。例如 , 工序(0000011111) 中的(0)物料可在编号为1 ,2 ,3 ,4 ,5的CNC上其中任一 台进行加工 , (1)表示物料可在编号为6 ,7 ,8 ,9 , 10的CNC上其中任一 台 进行加工。

3.2 种群的初始化

根据3. 1的粒子编码方式 ,每一件物料的每道工序都可以在指定的CNC上进行加工 ,初始化粒子的位置和速度 ,根据模型的 目标函数式(2)和式(3)设计适应度函数 ,计算每个粒子的适应值 ,并记录个体极值点pBest、全局极值点gBest。

3.3 粒子位置的更新

在基本的粒子群算法中 ,粒子根据公式(8)和(9)来更新自己的速度和位置:

式中 ,w为惯性权重;c1、c2表示学习因子 ,也称为加速常数;r1、 r2为区间[0 , 1]范围内的随机数;pid为个体最优粒子位置;pgd为全局最优粒子位置;⑦、x分别表示粒子速度和粒子位置。

3.4 权重的更新

本文使用线性递减权重法 ,使惯性权重依照线性从大到小递减 ,其公式为:

式中 ,wmax表示权重最大值;wmin表示权重最小值;t表示当前迭代步数。

3.5 获取最优值

将每个粒子的适应值与粒子的最好位置比较 ,如果相近 ,则将当前值作为粒子最好的位置 , 比较当前所有的pBest和 gBest,更新gBest。在适应值的计算过程中 ,根据所有粒子的适应值按照由高到低的顺序进行排序 ,计算平均适应值 ,然后剔除适应值低于平均适应值的粒子 。随后再重新引入一批新的粒子。

3.6 算法是否终止

当算法达到最大迭代次数时 , 则停止搜索并输出最终结果 ,否则返回到3.3继续执行。

4 实例验证

下面对图1所示的智能加工系统进行仿真实验。根据前文所述 ,选择10台CNC加工1个班次两道工序的物料 。实验在PC 机上的0T框架下进行 ,所有代码均由C++语言编程实现 ,求解过程中分别代入表1中的三组参数 ,求解结果如表2~4所示。

在第一组数据计算结果中 ,系统作业效率为51.04% ,RGV 移动时间为6 751 s ,加工熟料的数量为245件 , 同 一 结果下 , CNC工序的分配有8种 ,奇偶优先结果相同。

在第二组数据计算结果中 ,系统作业效率为43.96% ,RGV 移动时间为7 482 s ,加工熟料的数量为211件 , 同 一 结果下 , CNC工序的分配有16种 ,奇偶优先结果相同。

在第三组数据计算结果中 ,奇偶优先结果不同。奇优先的情况下 ,系统作业效率为51.25% ,RGV移动时间为6 932 s ,加工熟料的数量为246件 ,CNC工序的分配有8种;偶优先的情况下 ,系统作业效率为50.83% ,RGV移动时间为6 672 s ,加工熟料的数量为244件 ,CNC工序的分配有32种 。本组数据说明奇偶优先策略不同 ,CNC工序分配差异较大。

5 结论与展望

本文基于智能加工系统给出了动态调度的数学模型 ,在调度过程中考虑了CNC工序分配策略 、CNC编号奇偶优先策略、RGV任务分派策略。

该模型结合粒子群算法进行求解 , 设计了基于工序编码的粒子编码方式 ,调整了惯性权重 ,对适应度值较低的粒子做了剔除以提高全局搜索能力 , 从而得出CNC的最优调度结果。

后续工作将结合自动化领域生产调度的实际问题 , 比如从CNC最优加工台数 、物料的多道工序 、CNC加工过程中出现故障的情况等角度入手展开更细致的研究。