李黎　賈平　韓長吉　羅睿　史睿

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

[關(guān)鍵詞]訂單調(diào)度算法；先來先服務(wù)；基于優(yōu)先級調(diào)度

[DOI]1013939/jcnkizgsc201801142

1研究背景

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

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

2備件出入庫調(diào)度系統(tǒng)

21問題描述

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

22基于“先來先服務(wù)”的入庫訂單調(diào)度算法

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

3基于“先來先服務(wù)”的入庫訂單調(diào)度算法表示

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

步驟2：對入庫訂單隊列中所有的訂單，庫房調(diào)度系統(tǒng)根據(jù)其提交的時間順序依次進(jìn)行處理，處理完畢后將該訂單從入庫訂單隊列中提出，并在系統(tǒng)中更新相關(guān)的數(shù)據(jù)記錄。

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

步驟4：訂單全部完成，調(diào)度算法結(jié)束。

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

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

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

32備件庫調(diào)度

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

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

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

33訂單出庫的調(diào)度算法

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

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

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

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

a=T1-T2ni-1Ti

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

證明：由緊迫系數(shù)的公式可得：

當(dāng)a≤0時，訂單的提交日期大于等于交付日期，訂單過期。

當(dāng)a<1時，訂單的剩余時間小于訂單的準(zhǔn)備時間，時間緊迫，需要加班加點完成。

當(dāng)a=1時，訂單的剩余時間剛好等于訂單的準(zhǔn)備時間，可以按計劃完成。

當(dāng)a>1時，訂單的剩余時間大于訂單的準(zhǔn)備時間，時間充裕。

定理1證明完畢。

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

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

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

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

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

③當(dāng)訂單的備件準(zhǔn)備時間越大，訂單的優(yōu)先級越大。

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

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

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

411備件庫調(diào)度

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

步驟1：訂單調(diào)度算法首先檢測訂單對應(yīng)的備件庫是否滿足訂單的要求。

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

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

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

412訂單出庫的調(diào)度

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

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

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

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

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

步驟5：訂單全部完成，調(diào)度算法結(jié)束。

42實驗驗證

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

我們進(jìn)行了3組訂單數(shù)據(jù)的出庫調(diào)度模擬，其中每組訂單數(shù)包含5個訂單信息，訂單詳細(xì)信息如下表所示。

5結(jié)論

無人值守的全自動備件庫調(diào)度系統(tǒng)包括兩部分：出入庫調(diào)度和備件庫調(diào)度。

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

備件庫調(diào)度一般選擇預(yù)定的備件庫，當(dāng)出現(xiàn)預(yù)定的備件庫滿足不了緊急需求時，選擇一個代價最低的備件庫。

參考文獻(xiàn)：

[1]崔帥，楚藍(lán)天，高凱作業(yè)調(diào)度算法[J].科技向?qū)В?011（17）：110.

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

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