物联网环境下混流生产车间两级动态调度研究*

汤洪涛，王大国，支文全

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

0 引 言

混流车间的生产调度问题是指当不同型号的加工件到达生产线开始加工任务时，在各类诸如紧急插单、机器故障等的动态扰动下，产品的加工序列需要重新调整，以使得调度目标得到持续优化[1]。

当前，混流生产调度问题受到了广泛的关注。THOMOPOULO[2]通过最小化装配线的等待和超载时间进行建模，并采用了一种启发式算法对其求解；HYUN等[3]提出的数学模型关注于物料消耗速率均衡化、生产成本最小化，创新设计了以PS-NC选择机制为基础的改进遗传算法；MULLEN MC等[4]将物料消耗均衡化及负荷平衡化作为优化目标进行调度，设计了改进的模拟退火算法进行了求解；蒋艳等[5]以空闲与超载时间之的和值最小化为目标进行调度研究，提出了借鉴小生境技术的改进遗传算法进行求解。

从文献分析可以看出：以往多数研究的重调度背景是传统生产环境，信息化程度低、信息采集缓慢，调度结果存在严重的迟滞性；另外，在求解方面也存在容易陷入局部最优的问题。

在混流生产调度的问题上，本文将建立一种基于射频识别技术(RFID)的物联网制造环境，形成闭环调度系统，提升混流生产系统的鲁棒性。

1 基于RFID的物联网实时调度平台构建

混流生产的动态调度需要建立及时的信息反馈环境，因此本文提出一个在混流生产车间实现信息共享的物联网基础架构，采用RFID即插即用方式实现Multi-Agent封装，构建基于RFID-Bus的实时信息传递模式并提出相应部署策略，为两级动态调度提供调度数据来源。

1.1 Multi-Agent封装与接入

在混流生产实际环境下，本研究对设备、工具与RFID阅读器等数据采集设备进行绑定，将其封装成主动智能对象；对工件、操作者与RFID标签绑定，构成被动智能对象，这些智能对象通过部署在车间现场的无线传感网络组成Multi-Agent系统，从而实现实时信息之间的交互流转[6]。RFID设备服务提供程序应用接口(DSPI)定义了封装RFID设备的驱动程序，设定各设备的访问模式为同一方式，实现RFID设备的即插即用。

整体访问接入模型如图1所示。

图1 RFID访问接入模型

1.2 RFID-Bus实时响应机制

RFID设备所传递的实时信息采用RFID-Bus机制进行响应处理，该机制能够对日志、订阅、动作、消息等数据库进行管理，并且可以通过原语与第三方应用连接，实现信息的响应与处理。

1.3 两级RFID-Bus物联网环境建立

为实现不同层级的业务需要，本研究在混流生产物联网环境中进行两级RFID-Bus的构建。底层一级为部署在生产现场中的消息集成总线，实现Agent系统的信息传递与反馈响应；上层一级为业务集成总线，以SOA架构实现WebService消息服务，进而对业务实现集成。体系结构如图2所示。

图2 两级RFID-Bus体系结构

1.4 物联网架构组件部署

在完成Multi-Agent封装、明确响应机制后，本研究将物联网环境下的基础组件在混流生产环境中进行正确部署。其中，RFID中间件和消息集成总线安置在实际环境中信息采集设备等主动智能体上，这些设备与被动智能体进行交互后将消息传送至消息集成总线进行相应反馈。业务集成总线布局在企业业务服务器上，接收底层消息总线及系统管理程序的消息，同时与ERP等系统进行交互。由此，建立的物联网环境即可为实时自适应调度提供反馈。

2 混流生产预调度与算法设计

在完成物联网环境构建之后，本研究根据车间生产能力和加工任务即开始进行车间生产的预调度，在扰动发生后可以根据此调度结果进行重调度动态优化。

2.1 问题描述

装配线待加工产品序列中有M种产品，总装线包含N个工作站，流水线速度v恒定，各种产品的待加工量为Di(i=1，2，…，M)，产品i在第n道工位的加工时间为tin。设生产循环次数为r，则在一个最小生产单元内，每种产品的装配量di=Di/r，对其进行排序，r次循环之后，即能够实现排产期的生产调度。

2.2 预调度模型建立

混流生产车间的调度是一个复杂优化问题，因此，混流生产的预调度建模即考虑以物料消耗速率均衡化、最短化最小生产周期作为双重优化目标。

在最小生产循环周期中，物料消耗速率均衡化的目标为：

(1)

式中：di—M种型号产品对应的需求量；Kij—型号i(i=1，2，…，M)需要零件j(j=1，2，…L)的数量；XRi—前R个产品中，M种产品型号的数量。

设第R个产品在工位n的开始作业时间为SRn，作业持续时间为TRn，则其完成时间为ERn=SRn+TRn。假设最小生产循环周期为EdN，则最短化最小生产循环周期的目标为：

f2=min(EdN)

(2)

具体约束如下：

在投产顺序中每个位置有且只能有一个产品，XRi表示前R个位置，i种产品的型号数量为：

(3)

每种型号的产品在调度序列中出现的次数正好等于该产品的需求产量，Xdi表示一个最小循环生产周期中，i种产品型号的数量为：

Xdi=di

(4)

在加工过程中，一个工位在同一时间能且只能加工唯一一种产品，PRn为0-1变量，如果工位n上的产品为第R个产品，则PRn=1，否则为0，即：

(5)

后一个产品只能等待该工位加工完成，才能在该工位进行加工，即：

SRn-E(R-1)n≥0

(6)

在加工过程中，同一个产品只能在上道工序生产完之后，才能送去下道工序加工，即：

SRn-ER(n-1)≥0

(7)

2.3 预调度求解算法设计

布谷鸟算法是由YANG等[7]提出的，其在路径规划、生产调度等方面有着成熟的应用[8-11]。后来，国外SRIVASTAVA P R等[12-14]对CS算法进行了改进，国内王李进等[15-17]也对CS算法进行了研究。但原始CS比较适合连续型优化问题的求解，对离散性、有约束的多目标问题还需进一步研究。本文将小生境技术融入CS算法，将种群划分成若干块，之后依据适应度函数值挑选出每块中适应度值最佳的个体组成一个精英群体，以此来求解多目标的优化问题。算法具体设计如下：

(1)初始化。设定解的维数M，宿主个数N，被宿主发现的概率Pa，最大迭代次数为K，搜索上界为ub，下界lb，其中初始档案为空集(Archive=[])，小生境半径为σs，最大容量为ArchiveMax，初始迭代次数t=0，并随机生成M*N的初始鸟巢位置矩阵y0(t)；

(2)编码与解码。采用基于位置的编码方式，设定每个鸟巢都是一个n维向量，代表工序的排列;

(3)若t>k，则停止计算，输出Archive，否则转(4)；

(4)位置更新。根据Levy飞行原理，将鸟巢的位置更新，新的鸟巢矩阵为y1(t):

(5)适应度的择优。找出鸟巢的最优位置，计算鸟巢的矩阵y’的适应度值，根据适应度值进行排序，将前N个对应解作为新矩阵y2(t)；

(6)随机淘汰。设定随机数wi，根据被宿主发现概率Pa来淘汰y2(t)中的解，可以得到新矩阵y3(t):

(7)适应度的择优。重复(4)计算y2(t)与y3(t)组成的矩阵的适应度，择优组成新的矩阵y4(t);

(8)档案的更新以及预处理。将y4(t)放入档案Archive中，则Archive=[Archive,y4(t)]，按照Pareto支配关系，剔除被支配解，并保留非支配解；

(9)档案缩减。当档案中解的个数大于ArchiveMax时，则通过小生境技术进行档案缩减，档案中解的个数刚好在档案的限制范围内时，则得到新的档案集并返回到(2)中继续搜索，直至满足终止条件。

3 混流车间重调度研究

3.1 重调度策略

重调度对原有生产计划进行更新，因此也会对原有计划完成时间产生影响，在重调度实施中既要注重调度的有效性，同时也要避免调整的偏差性过大造成完工时间剧烈波动。本文选用以工件数量进行衡量的滚动窗口技术，同时基于事件驱动与周期混合的再调度策略在扰动发生后进行动态调度，先把调度过程分解成连续的静态调度区间，然后进行每个区间的调度优化。

滚动重调度窗口如图3所示。

图3 基于工件的滚动重调度窗口

3.2 重调度实施流程

(8)

当扰动事件发生时，本研究将还未进行调度处理的完工时间与预调度方案中完工时间的偏离度θ代表评估扰动事件影响的指标，其计算式为：

(9)

因此，本研究设定一个效能偏差值ρ，若θ≤ρ，则不需要进行重调度，只需要利用车间内部的调整来消除扰动事件的影响。通过ρ可以消除影响较小的扰动动事件，减少系统的负担，从而保持整个调度系统的稳定性。

3.3 重调度算法设计

重调度算法同样是基于布谷鸟算法进行改进设计，与预调度算法相较之下，重调度算法需要依据扰动事件的具体情况进行构建。设定扰动发生时刻为t，则重调度从t时刻开始。对于正在加工的工件，其下一道工序的开始时间是这个工件在该工序的加工完成时间与上一个工件在下道工序的完工时间的最大值。对于未加工的工件，其第一道工序的开始时间是t时刻与前一个工件在第一道工序加工的完成时间的最大值。算法流程如图4所示。

图4 重调度算法流程

4 实例仿真

本研究选取某公司5种产量较大且工艺近似的产品(A、B、C、D、E)为调度仿真对象，对预调度、重调度的模型及算法进行验证。5种产品的工序及工艺时间如表1所示。

表1 产品工艺及时间

同时，以上5种产品的月订单量已知，如表2所示。

表2 各产品月订单量

4.1 预调度仿真

本研究选用Matlab作为程序开发平台，采用混合布谷鸟搜索算法对预调度模型进行求解，参数取值解的维数M=10，宿主个数N=30，被宿主发现概率Pa=0.25，步长因子a=0.5，迭代次数K=100，小生境半径为σs=0.05，最大容量为ArchiveMax=100。同时为了充分验证本文所提算法具备良好的搜索、收敛性能，选取遗传算法、蚁群算法算法在该算例下同步运行。其中：遗传算法的种群规模P=100,交叉概率Pc=0.8，变异概率Pm=0.1，终止代数为200；蚁群算法中，启发因子α=2，期望启发式因子β=2，信息素挥发因子ρ=0.15，蚂蚁数量m=100，信息总量Q=20，迭代次数NC=200。3种算法求得的Pareto解集如图5所示。

图5 3种算法的Pareto前沿求解结果

以上3个算法中，混合布谷鸟算法完成求解的时间为6.49 s，蚁群算法为9.23 s，遗传算法为10.14 s。同时由图5可以看出：混合布谷鸟算法产生的解数量更多，分布较为均匀，并且能较好地靠近Pareto前沿。

在混合布谷鸟算法运算结果下经层次分析选出Pareto最优解为：f1=51.8，f2=873。预调度的甘特图如图6所示。

图6 预调度甘特图

预调度第一个循环周期装配时间为873 s，总时间为468 405 s，而车间自主调度结果中第一个循环周期装配时间为1 021 s，总时间为504 517 s，可以证实预调度结果是有效可行的。

4.2 重调度仿真

本研究分别对插单、物料延迟到达、机器故障这3类扰动实施重调度仿真。重调度策略参数取值为pk=1，1-a=0.05，β=0.1，ρ=0.001。

(1)插单。在t=11 752 s时刻，接到紧急订单F，其订单数量为1 000，交货期为5 d，产品在各个工序的加工时(24,27,25,31,22,28,26,25,29,32,34,31,26,30,19,0,24,21,23,27)，故一个生产循环周期生产内A∶B∶C∶D∶E∶F=5∶4∶4∶3∶2∶5，循环周期数为200，θ=0.06，采用局部重调度策略，自第25个循环周期开始，利用混合布谷鸟搜索算法进行局部重调度，重调度后的总加工时间为495 405 s；

(2)机器故障。在t=8 750 s时刻，生产设备出现故障，导致A生产停滞，设备修复时间为1 500 s,则θ=0.003，故采用右移重调度，重调度后的总加工时间为468 312 s；

(3)物料延迟。在t=214 760 s，产品B的物料发生延迟，延迟时间为t=61 000 s，则θ=0.13，采取完全重调度策略，在第442个循环周期中，利用混合布谷鸟搜索算法进行重调度，重调度后的总加工时间为478 612 s。

将各扰动事件的重调度结果与预调度方案进行比较，结果如表3所示。

表3 重调度结果与预调度方案进行比较

由表3可知：除了物料延迟对预调度方案产生较大影响外，其余扰动的重调度方案结果与预调度差别不大且有效性良好，证明重调度的实施较好地解决了扰动对混流生产的影响。

5 结束语

本文以混流生产车间为研究对象，构建了以Multi-Agent系统、RFID-Bus机制为基础的物联网制造环境，建立了以物料消耗速率均衡化、最小生产循环周期最短化为目标的预调度模型，并为其设计了混合布谷鸟搜索算法，根据发生的扰动情况，重新构建了混合布谷鸟求解算法。

仿真实例验证了调度模型、策略以及混合布谷鸟搜索算法的有效性。