全渠道供应链网络节点约束存储转发调度方法

宁 克，刘志伟，侯 滨

（1.国网山西物资公司，山西 太原 030006；2.山西财经大学，山西 太原 030006）

网络技术的迅速发展和新兴业务的出现，增加了海量数据传送要求。数据中心备份、大科学计算等传统数据传送的典型应用，需要数百个兆位、数吉比特每秒的带宽传送数据，给数据中心带来了较大的考验。因为海量信息的传送需要很长的一段时间，所以数据常常会传送延时。为了解决以上问题，刘斌等[1]提出了基于风险感知策略的调度方法，在多个运算节点基础上，建立了以最短完成作业为最优的目标函数，并根据作业的完成期和边界节点进行风险觉察的作业指派。不同的链路带宽可用性存在着巨大差别，使得所能传送时间非常短，很难适应海量信息的传送需求；国强等[2]提出了基于动态簇的节点调度方法，采用粒子滤波对下一时间的目标进行定位，通过预测方位和协方差估计方法，得到下一时刻的椭圆区域。该方法基于节点的剩余电量进行排序，大规模的数据传送是端到端的，然而由于网络中的频谱利用率存在着时空不平衡问题，因此很难在更大的网络中进行数据传输。面对上述问题，提出了全渠道供应链网络节点约束存储转发调度方法。

1 网络节点约束存储转发调度框架搭建

时移多层图是一种面向存储转发的调度框架，其是一种以多层次为基础的结构，每个层次都是一个特定的时间结构，体现了在一定时间内最大限度地利用存储转发调度的灵活性[3]。基于最大灵活性调度策略，在所有节点部署网络场景开展过程中，实现了网络场景完全部署，基于时移多层的存储转发调度框架如图1 所示。

图1 基于时移多层的存储转发调度框架

由图1 可知，在这个框架中，利用时移多层图作为中继存储器进行路由查找，实现了空间和时间上的双向传送，将传送计划问题转化为一维传送问题。这种方法可以帮助优化存储转发调度，提高数据传输效率，并使数据在网络中能够按照预定时间到达目的地。通过将数据传输问题转换为一维问题，可以更加高效地管理和控制数据传送过程。

因为可选的路线共用了一段时间链路，所以预定失效比率应当与此有关[4]。为了使问题更简单，假定每个选择的路径之间时序是彼此独立的，所以只有在没有可选的通路不能提供有效资源的情况下，请求才会被阻塞，从而得到：

式中，P0表示请求未能在一条链路上找到所需带宽的概率；n表示备选路径；l表示时移层数。其中备选路径n和时移层数l决定了时移多层规模大小，其中增加备选路径n表示选择了一条较长的路由传输路径，增加时移层数l表示扩展了时间维度范围，允许在更长时间段内进行数据缓存[5-7]。

2 网络节点约束存储转发调度

2.1 调度决策目标函数构建

充分考虑全渠道供应链随机订单在[t1,t2]网络节点约束存储转发时间段内抵达转发目的节点的概率，将区间时间段离散化处理，计算不确定订单在离散时间点t0抵达目的节点的概率[8]。为了解决初始时刻点随机订单可能抵达的概率[9-10]，根据订单实际抵达情况对其规划，建立相应的子调度模型。在未考虑随机订单抵达情况下，确定子调度的具体情况[11]。根据子调度构造一个主要的决策模式，在实际订单抵达情况下，预先安排不确定的生产和不安排不确定的生产所节约的费用，以及在没有预定的情况下，构建调度决策目标函数，如下所示：

式中，a表示订单索引；A表示确定订单总数；b表示协同索引；ma表示a订单总数；ιa表示订单超期时间；Z1表示协同企业b处的生产成本；Z2表示订单等待成本；Z3表示惩罚成本；Z4表示库存成本[12]。同时，在考虑协同企业间的配送时间基础上，对同一订单在不同协同企业的完成时间进行了约束。

2.2 节点约束存储转发调度路径设计

在供应链中，两个企业之间的协作作业一般可以根据某一供应链中某一节点生产次序协调[13]。因为供应商和制造商都有自己的生产原则和生产目的，所以为了达到最佳的生产效果，必须对两者进行协调。工件需要两道工序加工完成，以单方节点为主导的协调计划只解决一个问题，而忽视了另外一个问题[14]。而从供应链节点的优化排序来看，其协同作业效率要优于前者。该问题的限制是：同一工件无法在同一机床上进行，各工序仅由一台机床进行，各机床仅执行一项工艺，同一时间内仅可处理一件产品，该过程中工件的处理时刻是不确定的，但是其分布是等概率分布的。

工件在供应商处先对其初加工，将其送到制造商处深加工处理，直至得到制成成品[15]。针对上述流程，调整网络节点约束存储转发顺序，如图2所示。

图2 网络节点约束存储转发顺序调整

由图2 可知，以单方供应商节点作为协调计划节点，制造商根据满足供应商的作业次序进行协调，其中1、3、4 节点为正常节点，可按编号依次处理，2节点为异常节点，应放在最后处理，避免出现节点阻塞问题，该过程所需的时间由以下公式表示：

式中，κ表示生产商数量；tij表示i工件在j机器上的加工时间。通过对两个工序的分析，得出了整个工序的总体工期。根据时间长短确定一条可执行的序列，将此可能的解决方案作为一个输入条件，再寻找下一个可能的解决方案。

为了在指定的层数目中搜寻一个有效的通路，需要减少运算的复杂性。在给定的时间维度中，有效的路线决定了时间维度调度搜索范围，因此，时间调度范围也会发生相应改变[16]。在对这一问题的研究过程中，将资源预约窗口日期确定为层与层之间的时间间隔，此时节点约束存储转发调度的最小周期可表示为：

式中，T′表示前一个转发节点调度周期；Tc、Td分别表示转发空闲时间和空闲参考时间；α表示节点存储转发时间最小公倍数。

获取节点存储转发时间数据后，通过路由到达目标集群点，当集群点接收到该指令后，接收节点进入待存储转发阶段。此时所接收节点根据待存储转发编号计算转发延迟，计算公式为：

式中，Ts、Tr分别表示节点发送和接收时间。当待存储转发节点数量为k时，每个节点转发调度周期一致，此时供应链网络节点约束下的存储转发成功率为：

当随意选择一个节点调度时，资源预约窗口大小会发生变化，构建的调度模型为：

式中，G表示实际资源预约窗口；λ(t)表示资源预约窗口变化系数。通过该公式可确定空间链路时间层是否被选择或移除，由此实现节点约束存储转发调度。

3 实验

3.1 实验问题描述

供应商为制造商提供多项处理作业，制造商向顾客供应其所需的商品，受供应商与制造商各自作业时间约束，以及各个加工任务时间和服务对象限制，整个供应链协同来安排各个加工任务的加工顺序，对同一个服务对象形成经济的批量调度。工件要通过供应商和制造商两个过程来完成加工，依据单边主导的协调计划，从供应商和制造商的角度出发，将产品的加工顺序分开。在合理的时间表下，不存在堵塞的情况。基于这种情况，可以作出以下假设：

假设1：在同一时段内，供应商和制造商都只能进行一项作业，不得在同一时段内进行多项作业。

假设2：对于同样的服务目标来说，一项工作完成时间一定比下一项工作完成时间提前，并且交付时间肯定要比后者小。

假设3：从供应商到制造商，从制造商到客户，任一批量货物的运输时间都是可以被忽视的。

对于上述三个假设条件，分析其调度路径，调度结果如图3 所示。

图3 预先设定的调度路径

由图3 可知，假设1 情况下路径相对于假设2、3情况下路径要短，且相对平滑。

3.2 调度路径实验分析

在上述三个假设条件下，分别使用基于风险感知策略的调度方法、基于动态簇的节点调度方法和节点约束存储转发调度方法对比分析调度路径是否与预先设定路径一致，对比结果如图4 所示。

图4 不同方法调度路径实验分析

由图4 可知，采用所研究的节点约束存储转发调度方法在三种假设条件下，与预先设定的调度路径完全吻合，采用基于风险感知策略的调度方法、基于动态簇的节点调度方法与预先设定的调度路径不一致。

3.3 调度时间实验分析

调度时间是衡量调度效率的关键性指标，文中对比分析三种方法的调度时间，结果如表1 所示。

表1 不同方法调度时间实验分析

由表1 可知，使用基于动态簇的节点调度方法调度时间最长，其次是基于风险感知策略的调度方法，调度时间最短是所研究方法，且最短的调度时间为30 s。由此可知，研究方法调度时间最短，说明其调度效率高。

4 结束语

为了改善供应链网络节点转发调度效率，提出全渠道供应链网络节点约束存储转发调度方法。实验证明，所提出的调度方法可以有效地提高网络节点约束存储转发调度效率，且调度时间短，表明研究方法通过供应链协调决策来实现订单计划，可以有效地改善供应链中的整体效率。