一种板材自动分拣系统的出入库调度规则研究

刘贵军

（广东工业大学广东省计算机集成制造系统重点实验室，广东广州 510006）

0 引言

分拣是配送的一种特殊功能要素，要求按规则将物品分门别类存放甚至按某种顺序输送，是仓储中劳动密集度最高成本最高的活动[1]。随着自动化技术的发展，RFID、二维码等技术也开始在订单分拣中得到应用[2]，对于自动化分拣的研究也逐渐深入[3]，国内自动化分拣最先在烟草、军工、医药等行业得到应用，对于分拣的研究应用也多涉及快递、烟草行业[4]。近年来随着“工业4.0”、“中国制造2025”概念的兴起以及家居定制化的热潮，又因为家居板材人工分拣劳动强度高，交货周期长且易出错的特点，一些家居企业也开始寻求自动高效的分拣方式[5]，来实现转型升级从而提高自身市场竞争能力。国内对于定制型家具板材的生产一般采用多订单合并统一排版下料，再细化到以板为基础的零部件进行加工，以工艺路线为导向。排版下料后依次是开料、封边、排孔、打胶粒清洗。这导致后期需按订单、按包装找齐板材再打包，即增加了分拣这个打包前的准备环节[6]，使得工作量剧增。

目前国内对于家居板材自动分拣的实际应用还较少，本文作者对一种概念型家居板材自动分拣系统的解决方案提出单元化分拣的思想，并对单元层调度规则进行探索研究。

1 问题描述

1.1 问题描述

分拣系统采用滚筒线、机械手、立体仓库，辅以识别与控制技术实现分拣（图1）。通常，采用这种分拣方法，分拣环节的布局、需要配置的机械手和立体书架因厂家的上游生产产能、可用空间、生产安排而异。因板材的尺寸差异大，为有效利用空间，库位的尺寸也会有多种，库位只能容纳相对更小的板材。将一个机械手与配套的立体仓库、输送线、辅助装置视为一个单元，信息层由单元管理器管理。进入分拣系统的板材会被扫码传感器与光眼传感器定位到大概位置并记录。该暂存在哪个单元由上层中央控制器的调度策略决定。而不是简单地均匀依次分配到各单元，当板材进入到单元时触发对该单元的入库任务，当中央处理器检测到分拣系统中有订单配齐时会向含有该订单板件的单元下达出库任务。入库与出库任务执行顺序由单元层调度规则确定。出库后的板材被送到出库的滚筒线上，最终经滚筒线在汇合处调整顺序被输送到特定的打包工位。

图1 分拣系统概念图

根据分拣解决方案结合分拣的实际要求可知，该类型的分拣系统单元，入库任务（记为A任务）单个产生，具有随机性，出库任务（以下记为B任务）多个同时产生，产生的间隔与产生的数量具有随机性。为了使B类任务从产生到被处理完的平均时间尽可能短即出库效率尽可能高，同时保证A类任务能顺利进入单元。显然，直接采取出库优先，A类任务可能在极其有限的输送线缓存区发生堵塞，导致无法接受到新的入库任务，降低该单元的利用率；直接采取入库优先的策略，会使得到齐的板件在各个单元中滞留无法被及时处理，导致出库效率低，产品部件在分拣系统中的周期延长。所以单元层应采用某种调度规则使得出入库优先级配置合理，配齐后快速输送至打包区，是本文作者的研究目标。

1.2 数学模型

采用数学方法描述板材分拣单元出入库过程，是一种可称为半马尔可夫决策过程(Semi-Markov Decision Pro⁃cess，SMDP)的模型。为了说明这个模型，先介绍马尔可夫决策过程(MDP)[7-8]。

马尔可夫决策过程(MDP)：

设S为状态空间。当系统在时刻tk∈T处于任意状态s∈S时，行动集合为As。在时刻t，状态s下，采取了行动为a，得到的回报或代价为rt(s,a)，该值必须在选择决策a之前已知，且不受未来决策的影响。当系统状态发生改变时（有多种可能的结果），状态转移的概率记为pt(·│s,a)。如果在时刻t+1时，系统状态发生了改变，预期的回报为rt+1(s,a)=，其中pt(j│s,a)为在时刻t+1时，系统的状态为 j∈S的条件（在时刻为t时，系统的状态为s，采取的行动为a）概率。且有：。所有的状态转移概率构成一个矩阵，列出任意状态i转移到任意状态j的条件概率，称为状态转移矩阵。这样的一组要素所组成的数学结构是{T,S,As,pt(·│s,a),rt(s,a)}。

半马尔可夫决策过程(Semi-Markov Decision Process，SMDP)：

SMDP中，时间是连续型随机变量，状态是离散型随机向量。SMDP与MDP的差异就在于，不是每个系统状态发生改变的时刻都可以去决策，只是在部分系统状态发生改变的时刻才可以进行决策。

概率结构：

针对面临的问题，状态在时刻tk改变（有A任务到达；有B任务到达；上一个任务刚完成）。系统状态向量：等待中的A任务数量NA，等待中的B任务数量NB。状态转移矩阵为，到达一个A任务的概率，同时到达i个B任务的概率p[i]，i=1,…,M，p[1]+...+p[M]=1。决策时刻：前一个任务执行完毕的时刻（执行该任务的时间段tk+1-tk为随机变量F(t│s,a)，当执行A任务时是一个给定的分布，当执行B任务时是另一个给定的分布）；或者机器人处在等待状态时，系统状态发生变化的时刻（即有新的A任务到达，或者有新的B任务下达）。由于任务执行过程的不可中断性，在每个任务执行过程中不能再采取决策，在此期间系统的状态变化对决策者而言也不必知道。但是在计算等待时间这样的优化目标时，系统的状态变化过程就需要确切地知道。在当前决策（采取了行动a）的时刻tk之后，经过时间t，系统的状态由s自然变成j的概率记为p(j│t,s,a)，注意，下一个决策时刻tk+1很可能晚于时刻t，即t＜ tk+1，tk+1取决于分布F(t│s,a)，转移概率p(j│t,s,a)是用来计算每个决策阶段中的累积回报量或累积支出的成本。如果在该决策阶段系统的状态没有发生变化的话，p(s│t,s,a)=1，0≤t≤tk+1。为了避免在有限长的时间内产生无限多次决策，对决策时间间隔的分布F(t│s,a)做以下的假设：

假设2.1：存在一个ε＞0和δ＞0，使得：F(δ│s,a)≤1-ε对所有的s∈ S和a∈ As都成立。

假设系统在时刻tk时状态为s，并且采取了行动a，到了决策时刻tk+1时状态为j，相应的概率可以记为Q(tk+1,j│s,a)。但是由于模型的复杂性，这一概率难以采用A任务到达概率、B任务到达概率以及执行A任务或B任务的持续时间概率分布的显式表达式表述。

设S为状态空间。当系统在时刻tk∈T处于任意状态s∈S时，行动集合为As。这里包括4种类型： As0={W}，s0=[0,0]； AsA={A}，sA=[NA,0]（没有等待中的B任务）； AsB={B}，sB=[0,NB]（没有等待中的A任务）；As={A,B}，s=[NA,NB]。与四类状态相对应的四类决策集合分类列如表1所示。

表1 状态相对应的决策集合分类列表

回报与成本函数：

在面临的问题中，将B任务在分拣库中的平均处理时间作为系统的成本。该成本不仅与以前的决策有关，而且与上个决策至下个决策之间的时段内系统的状态变化有关。

决策规则与策略：

d表示决策规则，DK表示决策规则类。D则专门用来表示确定性的MDP策规则类。π表示任意一个特定的策略，就是一个特定的决策规则序列，即：π=[d1,d2,…,]，π∈ΠK为一个策略类。对于一个特定的确定性MDP决策规则 d，定义 pd(j│t,s)=p(j│t,s,d(s))，Fd(t│s)=F(t│s,d(s))，Qd(t,j│s)=Q(t,j│s,d(s))，kd(s)=k(s,d(s))为决策者在状态s，并采取决策d(s)后一段时间内的累计回报值。

定义 坐 标 随 机 变 量 ：Xn(ω)=sn∈S ，Yn(ω)=an∈A ，τn(ω)=tn∈T，其中ω表示随机元。在时刻t，自然过程的状态是Wt。在第n个决策点至第n+1个决策点之间的决策执行时段内，瞬时回报速率记为c(Wt,Xn,Yn)。

经过时间(elapsed time)过程σn(ω)：，注意：。

在第一个决策时刻，系统的状态为s时，定义N个时段累计期望回报值(s)为：

在上述中，σ0，σ1，…表示后续的决策时间时刻，第一项对应着成本的累积和，第二项对应着第n个决策点至第n+1个决策点之间的决策执行区间中，动态成本率c(Wt,Xn,Yn)在该时间段上的累积效应。

由于最优决策规则序列难以获得，在实际应用中，往往采取近似求解规则求解该数学模型。这里，本文作者提出4种常规规则，并通过仿真比较这些规则与策略之间的相对优劣。

2 仿真模型的建立

结合实际情况，为研究不同出入库调度方法在不同场景下的应用效果并比较优劣，忽略其他无关的具体物理仿真细节，对模型做一定的简化抽象，搭建基于Tecnomatix Plant Simulation 12(eM-Plant)仿真软件的仿真模型，如图2所示，给出仿真模型的假设条件如下：

假设1：考虑两种任务输入系统，A类任务到达的时间间隔服从均值为λ1的负指数分布。B类任务到达的指令间隔服从均值为λ2的负指数分布，一个指令中包含的任务数量是某范围内的随机整数，长时间内单元中A类任务与B类任务产生的数量期望值相等。

假设2：A类任务的单元内缓存区长度为4，滚筒线输送能力相对机械手处理能力足够，A类任务具有长度属性值，单元内缓存区不能容纳属性值之和超过自身长度的A类任务。

假设3：A类任务的长度属性随机且符合某厂多年来的历史统计数据的概率分布。

假设4：未配齐的板件无法被处理，不记为任务，立体仓库的容量足够容纳这些板件。

假设5：机械手处理一个任务的时间为 ρ，假设服从正态分布（有上下界约束），执行任务不可中断。

图2 分拣单元仿真模型

这里值得注意的是Bag_Source表示订单或包配齐后下达一次出库指令，Source在出库指令下达后同时产生随机数量的B类任务，存放在缓存区B2中待处理。

3 实例与结果分析

3.1 四种备选调度规则

（1）入库优先：机械手空闲或刚完成一个任务后优先检测是否有入库任务，有入库任务时，先处理入库任务，无入库任务时才检测是否有出库任务，有出库任务则执行一个出库任务。

（2）出库优先：机械手空闲或刚完成一个任务后优先检测是否有出库任务，有出库任务时，先处理出库任务，无出库任务时才检测是否有入库任务，有入库任务则执行一个入库任务。

（3）轮流优先：如果机械手刚处理完的是入库，采用入库优先的规则。如果机械手刚处理完的是出库，则采用一次出库优先规则。

（4）参考警戒线优先：给入库缓存区设置警戒线系数（取值范围0～1），如果缓存被占用量达到警戒线水平（滚筒缓存区的长度*警戒线系数），机械手采用入库优先的规则。如果未达到警戒线则采用出库优先规则。

以上4种调度规则对应着实验中自变量ϕ的4种水平值（1，2，3，4），其中机械手在无任务时保持等待状态，等待状态采用先到先服务的规则。

3.2 其他的仿真实验因素

（1）辅助实验因素一：板材的尺寸属性

因为超大板材所占的比例极小，且容易区别于其他板材，在实际操作时就直接将其输送至包装区，无需自动分拣，这样可降低分拣硬件的设计性能要求。因此，是否剔除超大板材，对应着仿真实验中两种板材尺寸随机分布形式α两种的水平值（1,2）。

（2）辅助实验因素二：板材的包装属性

根据工厂的实际包装需求差异，既要求一个订单（产品）的板件都在立体仓库中配齐后才输送至包装区，又要求一个包的板件在立体仓库中配齐后即可出库。两种板材的包装属性分别对应着仿真实验中包装要求 β两种水平的值（1，2）。

3.3 仿真实验设计

设定A类任务到达相互独立且服从均值为λ=21的负指数 分布，缓存滚筒线长度为4 m，机械手处理一个入库任务所需时间为7.5～13 s，服从均值为10.5，方差为1.5的有边界约束的正态分布。处理一个出库任务所需时间为7～12.5 s，服从均值为9.5，方差为1.5的有边界约束的正态分布。

从实验设计的三要素：调度规则、板件的尺寸属性、板材的包装属性来看，这里3个实验因素的不同水平的全部搭配方式共有4×2×2=16种，即16个仿真场景，在任务拒绝率小于预设值2%的前提下，比较平均出库任务时间（主要评价指标）。此外，还有一些其他的评价指标，如拒绝率（次要指标）、最大库容占用量（参考指标）、机械手的利用率（参考指标）等。其中包装要求对应关系如表2所示。

表2 包装要求对应关系表

系统的评价指标是B任务平均处理时间AveTime，A任务拒绝率RejectRate。其他参考指标有：B任务最大堆积量（MaxVB），机械手利用率（RobotUtiRate）。

针对所有因素的16种组合情形分别进行实验，并比较实验结果。因为任务到达、任务属性、机械手处理速率都是随机分布，为了得到可靠的描述仿真实验的结果，对每组实验仿真时间设置为1 000天，且每组实验重复10次。在显著性水平小于0.05的情况下，基于大样本统计学原理，认为从仿真实验数据统计获得的系统评价指标的统计结果是可靠的。

3.4 仿真实例结果及分析

在使用警戒线调度规则（调度规则4）时，首先需要确定警戒系数。由表3可知，从部分仿真实验的结果看，警戒系数设定为0.34较为合理，因为在满足约束条件的情况下，警戒系数为0.34导致系统B类任务的平均处理时间较短（主要性能指标较好）。警戒系数过大，导致A类任务的拒绝率（次要性能指标）超过预设的比例要求，所以不能接受。

表3 警戒系数多级实验结果

多种因素的水平值组合，如111，表示调度方法参数ϕ=1，随机尺寸分布参数α=1，包装要求参数 β=1。即采用入库优先，不剔除超大板，按订单包装的实验。为方便直观地比较调度方法与应用场景的影响，将主要约束与目标的相关数据绘制在图3、4中。图3中剔除了调度规则2的绘制，因其拒绝率高达7%～13%，显然不符合要求。

图3 各因素对拒绝率的影响

图4 各因素对B类任务平均处理时间的影响

根据图3、4对实验数据进行比较，其中横坐标表示应用场景，后缀两位数字分别对应随机尺寸分布参数α，包装要求参数 β的水平值。如RejectRate11表示α=1，β=1，即不剔除超大板、按订单出库的应用场景。同一线条上的点表示同一种调度方法，对应ϕ的一个水平值。

对以上的实验结果进行分析，初步得到以下几点结论：

（1）横向依次比较调度方法与包装要求相同的情况下，比较任务尺寸属性不同的情况下（α=1，与α=2）的仿真系统输出结果。可知剔除超大板有利于降低A类任务的拒绝率，但对B类任务的平均处理时长无明显影响。

（2）同理比较，调度方法相同，任务尺寸属性相同情况下，包装要求对系统指标的影响。可知按包出库有利于减少B类任务平均处理时间，而对A类任务的拒绝率无明显影响。

（3）纵向依次比较，同种应用场景（即任务尺寸属性，处理要求相同的情况下），调度规则对两者都有一定影响。从入库优先，轮流优先，参考警戒线优先，出库优先。拒绝率逐渐提高，而B类任务平均处理时间逐渐减少。

综上可知，在滚筒缓存区容量有限的情况下，剔除超大板或提高入库优先程度，有利于降低入库任务的拒绝率；按包出库或提高出库的优先程度，有利于减少出库任务在系统中的滞留时间。在实际应用中，一般应用场景（就是说板材的尺寸属性与包装属性）都已经确定，只有通过调整调度规则来使其满足A类任务的拒绝率约束，同时使得B类任务的平均处理时间尽量短。而参考警戒系数这类方法，可以通过调整警戒系数来“恰好”满足约束条件。警戒系数越大，出库优先程度越高，警戒系数最大为1时，即出库优先；警戒系数越小，则入库优先程度越高，警戒系数最小为0时，即入库优先。因此调整警戒系数，可以在满足一定的约束条件下，尽可能获得出库优先，提高系统的主要性能指标。这样有利于减少出库任务在系统中的平均滞留时间，提高出库打包的效率。

5 结束语

针对某公司家具板材分拣系统的出入库调度问题，建立数学模型，并提出4种近似求解策略（调度规则）。为将所提出的方案应用于实际，将实际应用场景的因素映射为仿真系统的参数与变量，将调度规则用程序逻辑表示。在此基础上，建立系统的仿真模型，进行大量的系统仿真实验，统计仿真数据获得系统的性能指标来分析比较不同的应用场景、不同的调度规则对板材出入库性能的影响。通过仿真实验，发现板材的尺寸属性和包装属性不影响4种不同的调度规则之间的相对优劣，而采用警戒系数的调度规则，可以在满足一定的约束条件下，尽可能使得出库优先，提高系统的主要性能指标。这样有利于减少出库任务在系统中的平均滞留时间，提高出库输送至打包区的效率。因此该调度策略可灵活调整任务的优先程度来配置两类任务的优先级，使得系统在满足入库任务拒绝率不超过预设的约束条件下，出库任务总的平均处理时间缩短。