全渠道供應鏈網絡節點約束存儲轉發調度方法

寧 克，劉志偉，侯 濱

（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 結束語

為了改善供應鏈網絡節點轉發調度效率，提出全渠道供應鏈網絡節點約束存儲轉發調度方法。實驗證明，所提出的調度方法可以有效地提高網絡節點約束存儲轉發調度效率，且調度時間短，表明研究方法通過供應鏈協調決策來實現訂單計劃，可以有效地改善供應鏈中的整體效率。