李黎　賈平　韓長吉　羅?！∈奉?/p>

[摘要]文章對國家電網備件庫的訂單調度進行了研究。根據備件庫訂單調度特點，在對比“先來先服務”的調度算法和基于優(yōu)先級調度算法的優(yōu)缺點基礎上，提出了無人值守的全自動備件庫調度：①出庫優(yōu)先于入庫；②基于先來先服務的入庫訂單調度算法；③基于優(yōu)先級的出庫訂單調度算法，大大提高了訂單的調度效率。

[關鍵詞]訂單調度算法；先來先服務；基于優(yōu)先級調度

[DOI]1013939/jcnkizgsc201801142

1研究背景

文章針對國家電網備件庫的信息化目標——全自動無人值守備件庫系統進行研究。無人值守的全自動備件庫系統具備如下特點：①各級備件庫庫存減少到警戒線時能夠預警并自動預測各備件的采購量并生成采購單，采購單確認后開始采購；②備件使用單位上報備件需求時，系統根據庫存情況、備件需求的緊急情況確定出庫單優(yōu)先級，優(yōu)先級高的優(yōu)先滿足；③對于庫存可以滿足的出庫單（不需采購），綜合考慮各使用單位分布情況和各級備件庫的庫存情況決定從哪個（或者哪些）備件庫出庫；④備件入庫、出庫不需人工干預。

文章研究的國家電網的備品備件庫的訂單調度算法，其訂單特點為種類多、需求變動頻繁、實時性強，在此背景下，同時具有很多訂單的時候，計劃與調度要具有敏捷性，能夠解決訂單的計劃與調度的實時性，高效率地安排這些訂單并滿足訂單需求。本文針對這一問題，首先對多訂單的出入庫調度進行研究，并提出相應的調度算法；其次，對于備件使用單位的備件需求，根據各級備件庫的庫存情況，設計調度算法，確定該需求從哪個（些）備件庫下出庫單。

2備件出入庫調度系統

21問題描述

國家電網的庫房中的備品、備件支撐整個企業(yè)的日常生產，如何保證庫房中的備品備件有效地支撐企業(yè)的日常生產，成為一個亟待解決的問題。在日常的調度中，當庫房中的備品、備件消耗后要及時補充相應物品，以保證生產的正常運行；當需要備品、備件的多個訂單同時提交時，要及時響應訂單，保證及時高效地完成所有訂單需求。根據以上需求，我們將庫房的訂單調度模型抽象成兩部分：訂單入庫和訂單出庫，通過相關的調度算法，及時響應各種訂單信息。在同時需要進行入庫和出庫時，優(yōu)先進行出庫操作，當出庫單都已經操作完成，或者現有庫存已經不足以進行出庫時，再進行入庫操作。

22基于“先來先服務”的入庫訂單調度算法

在日常的庫房維護中，庫房管理員會根據備件庫預警信息、日常的訂單以及用戶的反饋采購相應的備品、備件。當庫房管理員采購來備品、備件準備放入庫房，調度模型即生成一個入庫的訂單，并記錄備品備件的名稱、數量、價格、采購時間等相關的屬性。該入庫訂單提交給庫房調度系統，系統依據先來先服務的調度算法，根據訂單的提交順序依次處理，將備品、備件放在庫房的相應位置，并做好記錄，在系統數據庫中更新相關信息。

3基于“先來先服務”的入庫訂單調度算法表示

步驟1：對采購的備品、備件生成相應的入庫訂單，并根據訂單的實際情況對備品、備件的名稱、數量、價格、采購時間的等相關屬性進行賦值，然后將訂單放入入庫訂單的等待隊列中。

步驟2：對入庫訂單隊列中所有的訂單，庫房調度系統根據其提交的時間順序依次進行處理，處理完畢后將該訂單從入庫訂單隊列中提出，并在系統中更新相關的數據記錄。

步驟3：若隊列中仍有訂單等待，轉向步驟2，否則，轉向步驟4。

步驟4：訂單全部完成，調度算法結束。

31基于優(yōu)先級的出庫訂單調度算法

當用戶需要相應的備品、備件時，其會向庫房調度系統提交一個出庫訂單，包含其所需要的備品、備件。庫房調度系統會根據其相應的調度算法，及時響應訂單，滿足用戶的需求。在日常的使用中，通常面臨兩個方面的問題：①備件庫無法滿足當前訂單需求，如何快速有效地通過備件庫調度來滿足訂單需求；②備件庫面臨提交的多個訂單時，如何快速響應訂單要求，滿足訂單需求。如何完善地解決上面兩個問題，成為庫房調度系統設計成敗的關鍵。

基于優(yōu)先級的出庫訂單調度算法主要包括兩部分內容：備件庫的選調度和出庫訂單的調度兩部分。當用戶提交出庫訂單后，庫房調度系統首先根據訂單的內容，首先判斷對應備件庫是否能滿足訂單需求，若不能滿足通過備件庫的調度能否滿足訂單需求。若滿足需求后，備件庫接收訂單，根據出庫訂單調度算法進行訂單的出庫。

32備件庫調度

國家電網備件庫包括不同級別的多個備件庫，并且分布在不同的區(qū)域。原則上，每個備件庫都有其固定的服務范圍（使用單位），在備件庫的庫存允許范圍內，各個使用單位的備件需求都由相應的備件庫提供。當備件訂單需求十分急迫，但是對應的備件庫因為備件不足難以提供時，采用優(yōu)化算法，選擇其他備件庫，給該備件庫生成出庫單。選擇算法如下：

①尋找那些可以滿足本身服務任務基礎上，能夠額外滿足該需求的備件庫。

②選擇一個代價（運費）最低的備件庫。

33訂單出庫的調度算法

在庫房調度系統的多訂單調度問題中，最常見的調度模型為先來先服務和最短時間優(yōu)先服務兩種模型。[1]先來先服務調度模型實現最簡單，誰先來先處理誰，但是效率較低；最短時間優(yōu)先的模型是將時間最短的訂單優(yōu)先處理，但是該模型對大訂單不利，可能使得大訂單長時間得到不解決。[2]文章提出一種按訂單的優(yōu)先級進行調度的模型。[3]在每次調度前，調度算法計算每個訂單的優(yōu)先級，并且每次都安排優(yōu)先級最高的訂單進行處理。

4訂單優(yōu)先級的定義

在基于優(yōu)先級的訂單調度模型中，訂單需要交付的時間記為T1，訂單提交時間為T2，訂單中包含備件數量記為n，每個備件的準備時間為Ti（i=1，2，…，n），訂單的價值記為V，訂單預定義優(yōu)先級為P1，當前時間記為T。endprint

定義1：訂單的緊迫系數a，訂單越臨近交付時間，其緊迫系數越高，計算公式為：

a=T1-T2ni-1Ti

定理1：當緊迫系數a大于0時，值越小，就越緊迫，優(yōu)先級就越高。

證明：由緊迫系數的公式可得：

當a≤0時，訂單的提交日期大于等于交付日期，訂單過期。

當a<1時，訂單的剩余時間小于訂單的準備時間，時間緊迫，需要加班加點完成。

當a=1時，訂單的剩余時間剛好等于訂單的準備時間，可以按計劃完成。

當a>1時，訂單的剩余時間大于訂單的準備時間，時間充裕。

定理1證明完畢。

定義2：訂單的優(yōu)先級我們記為Pn，定義訂單的優(yōu)先級計算公式為：

Pn=lg（V+ni=1TiT1-T）a×P1

由訂單優(yōu)先級的計算公式我們可以得知：

①當訂單越緊迫時，訂單的優(yōu)先級越大。

②當訂單的交付時間越臨近，訂單的優(yōu)先級越大。

③當訂單的備件準備時間越大，訂單的優(yōu)先級越大。

④當訂單的備件價值越大時，訂單的優(yōu)先級越大。

⑤訂單預定義的優(yōu)先級越高，訂單的優(yōu)先級越大。

41基于優(yōu)先級的出庫訂單調度算法

411備件庫調度

用戶提交出庫訂單，我們將訂單記做Di，首先選擇訂單的服務備件庫：

步驟1：訂單調度算法首先檢測訂單對應的備件庫是否滿足訂單的要求。

步驟2：若滿足要求，將該訂單發(fā)到其對應備件庫的訂單隊列中，然后轉向②部分。

步驟3：若不滿足，訂單調度算法掃描所有的備件庫信息，并根據備件庫選擇原則選出最優(yōu)備件庫，然后將訂單發(fā)到該備件庫的訂單隊列中，然后轉向②部分。

步驟4：若仍沒有滿足條件的備件庫，發(fā)出備件信息預警并生成采購訂單。訂單調度失敗，通知訂單人員，調度算法結束。

412訂單出庫的調度

在訂單等待隊列中的訂單Di的優(yōu)先級為Pi，其屬性分別如定義1和定義2，基于優(yōu)先級的訂單調度算法表示如下：

步驟1：對訂單等待隊列中的所有訂單Di，根據訂單的實際情況對訂單需要交付的時間、訂單提交時間為T2、訂單中包含備件數量、訂單中每個備件的準備時間、訂單的價值以及當前時間等屬性進行賦值。

步驟2：對隊列中所有的訂單，通過定義1計算其緊迫系數a，若a<0，則表示訂單已經過期，將其從訂單隊列中剔除。

步驟3：對隊列中的所有訂單，通過定義2計算其優(yōu)先級Pn，選取優(yōu)先級最大的訂單進行處理（若訂單的優(yōu)先級相同，選擇等待時間長進行處理），并從隊列中剔除該訂單。

步驟4：若隊列中仍有訂單等待，轉向步驟2，否則，轉向步驟5。

步驟5：訂單全部完成，調度算法結束。

42實驗驗證

根據上述描述的訂單備件庫調度算法，我們在實驗室環(huán)境下模擬了基于優(yōu)先級的出庫調度算法，并與先來先服務的調度算法進行比較，實驗過程如下。

我們進行了3組訂單數據的出庫調度模擬，其中每組訂單數包含5個訂單信息，訂單詳細信息如下表所示。

5結論

無人值守的全自動備件庫調度系統包括兩部分：出入庫調度和備件庫調度。

出入庫調度系統，根據庫房的實際操作過程將整個過程分為入庫訂單調度和出庫訂單調度兩部分，并根據各自的特點選擇相應的調度算法。訂單入庫調度算法，選擇了先來先服務的調度算法，保證所有的入庫訂單依次完成入庫。訂單出庫的調度算法，對訂單的優(yōu)先級進行了定義，使用基于優(yōu)先級的調度算法，保證優(yōu)先級高的訂單能夠及時地響應，并且能夠在很大程度上避免先來先服務和短訂單優(yōu)先的算法帶來的弊端，保證訂單調度算法具有較好的性能，對實際生產中的訂單調度算法具有較好的參考價值。

備件庫調度一般選擇預定的備件庫，當出現預定的備件庫滿足不了緊急需求時，選擇一個代價最低的備件庫。

參考文獻：

[1]崔帥，楚藍天，高凱作業(yè)調度算法[J].科技向導，2011（17）：110.

[2]張繞學，史美林計算機操作系統教程[M].2版北京：清華大學出版社，2004.

[3]劉洋，桂小林，徐玉文網格工作流中基于優(yōu)先級的調度算法研究[J].西安交通大學學報，2006（4）.endprint