连续物料订单分拣完全-并行限定(k=1)轮询控制机理

冉文学，刘会娟，余丽艳

(云南财经大学物流学院，云南 昆明 650221)

1 引言

中国人口总量世界第一，约占世界总人口的1/5，制定高效的粮食安全策略是社会稳定的基础条件。然而，我国食品供应链存在一些问题，例如：计划生产不准确，忽视市场预测，食品批号老化，对客户需求反应灵敏度低，渠道渗透率低，安全责任难以划分等，这些都属于供应链运作的问题并与供应链模式选择密切相关[1-2]。食品产业链未来倡导个性化和定制化的新流通模式，即按需定制，以此来实现粮食产业的供给侧改革。

为了满足消费者个性化需求，连续物料的精准、高效分拣包装将推动“新流通”模式的发展。以粮食等连续物料为例的“新流通”商业模式，简单概述为：在居民生活区周边建立线上线下配销一体化物流中心——粮油站(主要销售粮食等连续物料，如面粉、大米、粮油等)，站内产品直接由工厂配送中心配送。粮油站是精简供应链的节点，在站内布置连续物料分拣设备，消费者可以在线上或者线下下单，根据自己的实际需求灵活的选择想要购买的商品数量，也可以按照金额进行购买，消费者由被动消费变为主动消费。这种供应链精简的商业模式可以从源头保证粮食安全，并且极大地便利人们的生活，能够真正的实现粮食产业的供给侧改革。

为了进一步提高配送中心订单分拣效率，轮询理论开始被应用于订单分拣系统。轮询是一种周期性的资源动态调度分配系统，具有高效性、公平性、灵活性和实用性等特性[13-15]。尽管国内外学者对轮询理论和如何提高订单分拣效率已经做了比较深入的研究，但是将轮询理论应用于分拣系统的研究还极其有限。Gong Yeming和De Koster[16]做了开拓性的研究，他们应用轮询理论描述和分析了电子商务环境下半自动化的动态订单分拣系统，研究结果表明基于轮询理论的动态分拣系统相比传统的分拣方法(例如订单批处理等)更节省分拣时间。Gong Yeming等[17]拓展了上述研究，在轮询动态分拣系统中引入随机变量，有效的提高了分拣系统的效率，但是，他们的研究主要适用于半自动化的动态分拣系统，而对于电子商务环境下逐步已实现自动化的配送中心仓储作业指导有限。冉文学[18]将轮询理论应用到单元物料订单分拣中，并将轮询经典控制机理拓展到二级并行控制并比较研究多种轮询系统模型在订单分拣中的应用及其求解方法，但是其之前研究的轮询分拣机理为单元物料范畴，本文研究连续物料的轮询分拣。

我国粮食需求总量巨大，所以本文研究以消费者为核心的粮食等连续物料订单分拣完全-并行限定(k=1)的轮询控制机理，来推动粮食产业的供给侧改革。本文建立完全-并行限定(k=1)的二级优先级订单分拣轮询控制模型，并运用数学方法对理论模型求解，通过数值计算分析，求解轮询控制系统的一阶系统特性和二阶系统特性，验证模型的可靠性。

2 连续物料订单分拣轮询控制模型环境变量和工作条件

2.1 环境变量定义

采用嵌入式Markov链、概率母函数以及拉式变换方法来研究订单分拣的轮询系统控制模型，为了完成系统的精确分析，定义以下环境变量：

ξi(n)：普通队列i(i=1,2,…,N)在tn时刻其队列内物料量；ξh(n)：在tn时刻系统优先队列内的物料量；ξh(n*)：从队列i转换分拣优先队列tn*时刻优先队列内的物料量；vi：普通队列i中物料量的分拣服务时间；vh：优先队列中物料量的分拣服务时间；ui：由队列i转向优先队列的转换时间；ηj(vi)：在vi时间内进入第j号队列(j=1,2,…,N,h)内需分拣的普通订单物料量；ηj(vh)：在νh时间内进入第j号队列(j=1,2,…,N,h)内需分拣的优先订单物料量；μj(ui)：在ui时间内进入第j号队列(j=1,2,…,N,h)内需分拣的物料量。

分拣机在tn+1时刻的状态变量仅和上一个分拣服务时刻tn*时刻的系统状态有关，为无后效性的Markov过程。在稳定状态条件下，该Markov过程是齐次、非周期、不可约和各态历经的。

2.2 工作条件描述

3 连续物料订单分拣完全-并行限定(k=1)轮询控制系统

连续物料订单分拣完全-并行限定(k=1)的两级轮询控制系统模型可以描述为：系统基本模型由一个分拣机和优先订单、普通订单共N+1个订单队列组成，分拣机对1个优先订单队列和N个普通订单队列采用并行作业的方式，其次优先订单队列采用完全控制策略，普通订单队列采用限定(k=1)的服务控制策略。分拣机开始工作时，如果普通订单队列需要分拣，不为空，对普通订单队列进行并行限定(k=1)分拣服务，分拣完一个订单队列后立即转向对优先订单队列，优先对优先订单队列进行分拣作业。模型中订单分拣轮询控制过程包括订单的到达过程、分拣机对每个订单的分拣服务过程和订单间的轮询转化过程。

3.1 连续物料订单分拣轮询控制系统状态概率母函数

(1)

(2)

分拣机在tn+1时刻轮询服务队列i+1时，系统状态变量的概率母函数为:

(3)

(4)

(5)

3.2 连续物料订单分拣轮询控制系统一阶特性

(1)平均分拣服务时间

订单分拣完全-并行限定(k=1)轮询控制系统的平均分拣服务时间为分拣机对系统中的N+1个队列按相应的服务规则完成一次服务所用时间的统计平均值，由分拣时间和订单转换时间构成。根据概率母函数关系求得：

(6)

(7)

对式(6)(7)进一步化简、整理得系统的平均分拣服务时间为：

(8)

(2)优先订单队列的平均排队队长

(9)

(10)

将式(2)和式(3)分别代入式(9)和式(10)求导后化简，计算后求得轮询控制系统优先订单队列的平均排队队长为：

(11)

3.3 连续物料订单分拣轮询控制系统二阶特性

(1)普通队列的平均排队队长

(12)

(13)

(14)

(15)

(2)平均时延

订单分拣作业的等待时间wj即从订单进入j(j=1,2,…,N,h)队列到其分拣完毕被发送出去的这段时间，中心队列、普通队列顾客的平均等待时延分别用E(wh)和E(wi)表示。

(16)

完全服务系统信息分组的平均等待时延为：

(17)

限定-1服务系统信息分组的平均等待时延为：

结合上述计算方法，可分别得到该系统模型中的普通队列和优先队列订单的平均等待时延。

普通订单顾客的平均等待时延为：

(18)

优先订单顾客的平均等待时延为:

(19)

4 数值分析与验证

理论计算和实验结果如图2至图10所示。

如图2至图10所示，理论计算与MATLAB仿真实验的结果具有较高的一致性，进一步分析该轮询系统模型有如下特点：

图2 不同队列数下平均订单分拣服务时间随顾客到达率的变化趋势图

图3 不同队列数下平均订单分拣服务时间随分拣服务时间的变化趋势图

图4 不同队列数下平均订单分拣服务时间随订单切换时间的变化趋势图

图5 不同队列数下平均排队队长随顾客到达率的变化趋势图

图6 不同队列数下平均排队队长随分拣服务时间的变化趋势图

图7 不同队列数下平均排队队长随订单切换时间的变化趋势图

图8 不同队列数下订单平均等待时延随订单到达率变化趋势图

图9 不同队列数下订单平均等待时延随服务时间变化趋势图

图10 不同队列数下订单平均等待时延随订单切换时间变化趋势图

(1)图2至图4显示出轮询系统的平均订单分拣服务时间随顾客到达率、分拣服务时间和订单切换时间变化的趋势。随着顾客到达率的增加，不同队列数量的系统平均分拣服务时间都呈现非线性增大，队列数量少时，系统轮询分拣周期较短，具有较好的稳定性和较快的周期响应特性。同时，从图中三条曲线的上下分布来看，三条曲线在顾客不断增多时都没有出现交叉的情况，系统的平均订单分拣服务时间根据队列数目垂直分布。随着分拣服务时间的延长，不同队列数量的系统平均分拣服务时间也呈现非线性增大，队列数量少时，系统轮询分拣周期较短，具有较好的稳定性和较快的周期响应特性。随着订单切换时间的延长，不同队列数量的系统平均分拣服务时间也呈现非线性增大，但相对缓和，队列数量少时，系统轮询分拣周期较短，系统更加稳定，响应更快。

(2)从图5至图7显示了系统稳定条件下，优先队列与普通队列的平均排队队长分别随顾客到达率、分拣服务时间和订单切换时间变化的趋势。图中曲线可以很明显的看出，普通队列的订单越小，曲线的陡度越大，而优先队列则相反，订单越大其曲线的陡度越大。随着分拣服务时间的延长，不同队列数量的系统平均排队队长也呈现非线性增大。随着订单切换时间的变化，优先订单队列相比于普通订单队列变化更明显。

(3)从图8至图10显示出高低优先级业务的顾客的平均等待时延随顾客到达率、分拣服务时间和订单切换时间变化的趋势。与平均排队队长类似，高低优先级业务的顾客的平均等待时延同样得到显著的区分。在队列数N和到达率λ增加的情况下，优先队列和普通队列中顾客的平均等待时延都在不断增大，但与普通队列顾客数的平均排队时延相比较，高优先级业务的顾客的平均等待时延一直以较小值平稳变化，并保持较好的稳定性。随着订单切换时间的变化，普通订单和优先订单的平均等待时延都呈现线性增长，证明系统稳定性比较强，同时优先订单队列三条线几乎重合，变化并不明显，稳定性更强。

5 结语

本文研究了基于完全-限定(K=1)条件下的连续物料自动化订单分拣轮询控制机理，并在轮询系统中，区分了优先订单和普通订单，确保优先订单顾客得到更优质服务和订单分拣系统的公平性，最后通过算例分析验证了连续物料订单轮询分拣系统的稳定性和高效率。本文的研究成果扩大了轮询理论应用深度，拓展了订单分拣理论研究的广度，探寻了成本最小化且高效率的物流分拣模式，对于实现粮食产业的供给侧结构性改革具有重要意义。