个性化定制车间生产与物流协同调度研究

葛艳红,李书珍,李文锋

(武汉理工大学 交通与物流工程学院,湖北 武汉 430063)

个性化定制作为新一代智能制造模式下企业的重要转型方向[1],与传统的离散制造模式相比,由于客户订单产生时间的不确定性及种类的多样性,对车间内调度方案的及时性与有效性提出更高要求。

现有离散车间调度方案主要分为3种:预反应式调度、前摄性调度与完全反应式调度。完全反应式调度又分为生产资源控制(Machine control,MC)型与物流资源控制(Vehicle control,VC)型。个性化定制车间场景动态变化,前2种调度模式很难满足个性化定制对生产组织及时性与灵活性的需求,因此现有研究大多针对完全反应式调度展开,即将车间内加工单元、自动导引运输车(Automated guided vehicle,AGV)等设备模拟成独立的智能体,基于智能设备所具有的感知、交互、分析、决策以及执行能力,自组织完成订单加工过程。例如,Wang等[2]将讨价还价博弈理论应用于各智能体之间的协商机制中;朱云飞等[3]、刘科等[4]、胡晓辉等[5]从不同的角度对合同网机制进行改进,简化了任务分配流程;陈鸣等[6]在合同网基础上,引入智能体过滤机制,提升系统的动态调度效果;Zhang等[7]基于博弈理论搭建了云制造模式下的智能体调度框架;Qu等[8]在同时考虑云制造与物联网的特征下,改变任务触发方式,创新提出基于生产与物流协同的动态调度方法。纵观现有生产与物流协同调度的研究文献发现:现有完全反应式调度研究主要集中于智能体之间通信机制的研究上,对基于智能体局部信息感知能力的优化车间调度方案的研究较少;物流对象大多为单载量AGV,忽略了多载量AGV较强的任务执行能力对调度方案的影响。徐云琴等[9]基于车间AGV的边际效应进行研究,发现AGV数量在一定程度上影响调度方案的整体作用效果。为进一步研究车间内物流运输能力对调度方案的有效性影响,本文采用多载量AGV,针对当前个性化定制车间中完全反应式调度模式难以保证订单交货期的问题,基于车间内生产、物流过程协同,提出一种新的订单排产方案,同时搭建基于多载量AGV特性的代价评估机制,采用改进的粒子群编码算法进行求解。对本文方案与已有的2种完全反应式方案在交货期控制、加工单元利用率、车间功率等方面进行比较分析,以期提升订单交货期的可控性与实现车间资源优化利用。

1 基于生产与物流协同的订单排产方案

1.1 排产方案调度指标

(1)订单交货期。企业对交货期的准确预测与按时交付是企业信誉的关键,延期将造成客户流失、经济损失等无法逆转的负面影响。同时,若订单提前加工完成,需将产品放至库存区,占用车间库存资源。因此企业无论采用何种调度方法,均应最大程度保证产品的交货期,同时对在制品的加工进度进行严格控制,减少产品的库存时间。根据文献[10]对订单交货期的研究,采用订单提前/拖期指标评估订单的排产方案效果

(1)

(2)资源配置效果。从企业资源和效益角度考虑,个性化定制模式的关键在于提高车间资源利用率,降低单个产品的分摊成本。加工单元的利用率指标

(2)

(3)车间功率。功率是调度方案效果综合评估指标。产品加工过程中,智能体速度与功率之间具有一定的相关性。功率包括车间内所有加工单元与AGV的总功率

(3)

1.2 排产方案具体流程

个性化订单产生后,按照产品工序间的连续性,采用“插空”的调度思想,尽可能在已有加工任务基础上,最大化利用加工单元的空闲时间,提高设备利用率。新调度方案具有如下特点:

(1)当系统中存在多个处于未加工状态的订单时,根据调度指标,对比订单的执行代价,选择最优订单插入,且每次只插入1个订单;

(2)订单实际插入的时间为协同制造链首个加工单元的当前任务结束时刻,在该时刻之前,按照调度指标,智能体对该时刻所有可插入订单进行评估,产生最优的订单并插入;

(3)计算订单的执行代价时,考虑插入该产品的所有工序后系统增加的代价;

(4)新订单的调度方案基于各智能体间协同交互、自主决策形成。订单排产上,领导者(Leader)负责与其它各智能体交互,完成生产与物流协同调度方案的制订。订单产线中Leader的选择采用

(4)

式中:CPfree(j)代表加工单元剩余的计算资源;CPmax代表加工单元总计算资源。

与计算机中资源占用情况类似,加工单元的资源使用情况为加工单元实时状态统计数值,选择剩余计算资源最多的加工单元为该订单产线Leader。产线Leader是生产、物流系统交互协同的纽带,负责协调生产模块与物流模块。

图1 新订单产生后智能体的交互流程图

图2 加工单元新任务插入方法示意图

2 多载量AGV代价评估机制

本文提出的个性化订单的排产框架中,制订每道工序加工计划时均需考虑物流模块反馈结果,物流系统的效率对订单加工进度产生直接影响,物流调度系统研究至关重要。

2.1 AGV自适应评估模型

为实现AGV资源的合理配置,当物流任务产生时,采用合理的代价评估机制,选择代价最小的AGV来执行此任务。研究中做如下假设:

(1)在AGV容量约束允许的范围内,AGV同时可执行多个物流任务;

(2)不考虑在制品装载、卸载过程,装载、卸载时间合并到在制品在加工单元间的运输时间中;

(3)每辆AGV具有自己的运输任务队列;

(4)初始状态下,AGV可能存在正在执行的物流任务,初始位置不固定;

(5)不考虑AGV的路径冲突与电量约束。

函数定义见式(5)～式(17),符号定义见表1。目标函数

F=mintd

(5)

(6)

(7)

(8)

(9)

(10)

xi,jti+ti,j-tj≤0 (i,j)∈R

(11)

(12)

cj≤tj≤bjj∈N

(13)

ti≻tn+ii∈{P∪D′}

(14)

xi,j(Qi+qi-Qj)=0 (i,j)∈R

(15)

Qi≤Qi∈N

(16)

(17)

式(5)为本次调度目标,希望物流任务完成时间最小;式(6)、式(7)定义多物流网络结构;式(8)表示各端点的出度等于入度;式(9)定义每个物流任务只能被执行1次;式(10)定义同一任务装载和交付为同一个AGV。式(11)～(14)定义任务时间约束,表示根据AGV已有任务的加工作业时间安排,AGV访问每个任务节点的时间必须在时间窗[bi,ci]内,以保证调度的正常执行。对于等待执行的物流任务,AGV负责完成同一任务的装载、卸载过程,装载任务节点的访问时间在卸载任务节点时间之前。式(15)～(17)定义AGV负载约束,考虑AGV自身负载约束,AGV运行负载不能超过其额定最大负载。

表1 AGV调度算法符号定义表

2.2 AGV自适应评估方法

多载量AGV调度的复杂性与车间场景的动态性,对算法求解速度与精度都提出了较高要求。对AGV现有调度算法进行分析比较,考虑粒子群算法较快的计算速度与较强的适应能力,符合AGV调度求解需求,因此选用粒子群算法作为多载量AGV自适应调度方案的求解方法。粒子在迭代过程中根据粒子个体极值与群体极值进行自身位置、速度的变更。更新过程中的速度、位置变化规律如下

(18)

(19)

2.2.1 编码与解码

假设AGV有n个等待执行的物流任务,其装载点的集合为P={1,2,…,n},卸载点的任务集合为D′={n+1,n+2,…,2n}。对于第i个等待运输的物流任务,i表示AGV执行该任务装载操作时的任务编号,其中i∈P,n+i表示AGV执行该任务的装载卸载的任务编号,(n+i)∈D′,即i和n+i共同表示同一任务的装载、卸载过程。n和2n代表当前新产生的物流任务编号。初始状态下,AGV上存在正在执行的物流任务,其任务序列设为D={2n+1,…,2n+h},其中h为初始状态下AGV上正在执行的在制品数量,可知此时AGV系统中共有2n+h个任务需要被执行。

考虑到AGV已有物流顺序与约束的良好匹配性,基于新物流任务与AGV已有任务的相似度、AGV自身装载、卸载间的先后顺序,对每个参与竞争的AGV采用如图3所示的编码方式。

图3 粒子群算法编码方式示意图

对处于等待运输状态的物流任务,必须严格遵守先装载、再卸载的操作流程。因此,算法在产生初始种群时,每一个物流任务必须保证其装载任务编号所对应的任务次序小于卸载任务编号对应的任务次序,即AGV先执行装载过程,再执行卸载过程,保证AGV执行任务的合理性,生成合理的粒子种群。粒子群算法的解码过程如图4所示。

图4 粒子群算法解码过程示意图

2.2.2 算法步骤

根据粒子群算法的寻优思想,每个粒子的速度和位置变化过程中,逐步向算法的最优值靠拢。每个粒子经过1次循环后,得出当前搜索情况下的最优解,更新当前最优解与全局最优解。按照粒子飞翔规则,进行位置与速度的迭代。如此循环,直至找到算法迭代范围内的最优解。算法的具体步骤为:

(1)初始化算法相关系数,包括上下界、速度、位置等;

(2)采用改进的编码方式、参数粒子的初始种群;

(3)对种群中粒子的速度进行更新;

(4)计算粒子适应度值,根据对比结果,对全局最优与局部最优值更新;

(5)判断是否达到终止条件,若没有完成迭代次数,则返回步骤(3);

(6)输出算法求解结果,对算法结果进行评估。

2.3 单载量与多载量AGV效果对比

为证明多载量AGV在个性化定制车间中的优越性,结合本文提出的个性化车间制造过程中生产、物流的协同调度方案,对比分析多载量AGV自评估机制的有效性。具体的车间布局参数与订单的加工参数如表2、表3所示。为保证订单出现时间的随机性,采用订单出现间隔为[20,10,30]的三角分布模型,随机订单的出现时间为[0,17,36,55,79]。定义在制品的质量为[1,1.5,1,1.5,1],AGV的最大载重为3。改进的粒子群算法与遗传算法性能对比如图5所示,单载量AGV与多载量AGV的调度效果如图6、图7所示，AGVn,n表示正在运输的产品编号。

表2 产品工序表

表3 AGV在加工单元间行驶时间表

图5 算法性能对比图

图6 采用单载量AGV的调度方案图

根据图5可知,采用改进粒子群算法的性能比遗传算法的收缩速度快,算法寻优能力较强。如图7所示,AGV2同时执行J4与J5的出库任务,体现多载量AGV较高的任务执行能力。根据2种方案调度甘特图以及相应的统计结果分析,结合个性化定制的场景特性,采用多载形式的AGV能提高调度系统效率,节省物流环节的作业成本。同时,由于生产、物流环节的高度耦合性,物流系统效率提升对加工单元利用率、加工功率降低等方面带来积极影响,订单的完工时间大幅度降低。

图7 采用多载量AGV调度方案图

3 调度方案实验验证

为验证本文提出调度方案的应用效果,基于eM-plant仿真平台,根据benchmarks实验数据[12],设置了4种个性化定制车间。车间环境信息见表4～8,车间布局如图8所示。基于10组订单数据对本文提出的调度方案与2种完全反应式调度方案进行仿真对比,实验结果如图9所示。

表4 AGV在布局1中行驶时间矩阵表

表5 AGV在布局2中行驶时间矩阵表

表6 AGV在布局3中行驶时间矩阵表

表7 AGV在布局4中行驶时间矩阵表

图8 仿真环境4种类型车间布局图

图9 3种调度方案结果对比图

根据图9可知,本文提出的排产方案在订单提前/拖期代价、加工单元利用率、功率方面具有明显优势,与MC、VC 2种调度策略相比,本文方案中加工单元平均利用率提升9.75%和11.97%,调度优势明显。为进一步说明对比效果,采用配对样本T检验3种调度方案性能指标差异的显著性。Sig.值(或p值)代表2种方案的显著性水平。一般情况下,假设的显著性水平不超过0.05,即若2种方案对比结果的Sig.值小于0.05,则具有明显的差异。对比结果如表8所示。

表8 3种调度方案配对样本T检验结果表

4 结束语

本文针对个性化订单特性,改进了完全反应式调度机制,提出了基于生产与物流协同的实时订单排产方案。采用“插空”思想,最大化保证了产品交货期,提升了加工单元利用率,降低了单个订单的分摊成本。基于多载量AGV特性,搭建了物流模块中物流任务代价评估机制,并采用改进粒子群算法求解。对比单载量AGV与多载量AGV的调度效果,采用多载量AGV的情况下,调度方案优势较明显。同时,根据仿真结果可知,本文方案与现有完全反应式调度方法相比,在提前/拖期代价、加工单元利用率、最小完工时间等方面具有显著性差异,证明了本文调度方案的有效性。