機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度方法設(shè)計

姜國仙

（濰坊科技學(xué)院機電技術(shù)學(xué)院，濰坊 262700)

0 引言

制造業(yè)水平與生產(chǎn)力水平息息相關(guān)，隨著生產(chǎn)技術(shù)的發(fā)展，社會對產(chǎn)品的需求越來越多樣化、動態(tài)化，制造業(yè)也逐漸從半自動化向著全自動化發(fā)展[1]。機械設(shè)備自動化的實現(xiàn)離不開資源調(diào)度，隨著制造車間對資源需求的增大，資源調(diào)度任務(wù)也隨之增加，合理的對資源進行調(diào)度是提高機械設(shè)備自動化制造的一個重要問題[2]。

在目前的研究中，國外學(xué)者提出了多種啟發(fā)式規(guī)則，并取得了重要的理論成果，這些成果為后續(xù)的研究工作提供了多種思路，在一定程度上提高了資源的調(diào)度效率[3]。國內(nèi)學(xué)者在早期的一些研究基礎(chǔ)上，展開了更深層次的研究，兼顧了制造過程中各種資源分配問題，但是隨著調(diào)度規(guī)模的增大，調(diào)度問題難度越來越高，一般的調(diào)度方法已經(jīng)很難滿足實際的資源調(diào)度需求，比較常見的調(diào)度方法在執(zhí)行過程中，受到動態(tài)環(huán)境影響比較大，資源調(diào)度過程中通訊信息延遲比較大，往往需要更多的時間才能完成調(diào)度任務(wù)，調(diào)度方法的適用性需要提高[4]。因此，提出機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度方法設(shè)計，解決以往調(diào)度方法中存在的一些問題。

1 機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度方法設(shè)計

1.1 構(gòu)建基于資源優(yōu)化的制造過程模型

按照機械設(shè)備自動化制造需求，將整個制造過程分為多個制造節(jié)點，不同的制造節(jié)點需要的資源各不相同，通過這一情況可知，整個制造過程具有明顯的復(fù)雜特性。在構(gòu)建制造過程模型時，以三元組G（a,e,r）表示，其中a表示制造節(jié)點集合，a={a1,a2,…,an}；e表示連邊的集合，e={eij|i,j=1,2,…,m}，表示不同調(diào)度任務(wù)中資源節(jié)點之間形成的連邊；r表示權(quán)重集合，r={eij|i,j=1,2,…,u}，i和j表示制造節(jié)點。構(gòu)建的制造過程模型如圖1所示。

圖1 基于資源優(yōu)化的制造過程模型

在制造車間資源調(diào)度方案中，各個制造任務(wù)存在相互制約的關(guān)系，并不是獨立存在，在建立理想調(diào)度目標函數(shù)時，考慮制造任務(wù)之間的干擾。

在實際制造過程中，制造節(jié)點之間在執(zhí)行上存在先后順序，在資源優(yōu)化調(diào)度時存在時序約束。制造過程模型中存在四種時序關(guān)系，分別是：

完成-開始關(guān)系：任務(wù)j在任務(wù)i開始之前完成；

完成-完成關(guān)系：任務(wù)j在任務(wù)i完成之前完成；

開始-開始關(guān)系：任務(wù)j在任務(wù)i開始之前開始；

開始-完成關(guān)系：任務(wù)j在任務(wù)i完成之前開始；

在制造過程資源優(yōu)化調(diào)度過程中采用上述方式描述各個調(diào)度任務(wù)之間的邏輯關(guān)系，建立理想調(diào)度函數(shù)。

1.2 建立理想調(diào)度目標函數(shù)

假設(shè)理想調(diào)度目標函數(shù)的變量為H={hij|i,j=1,2,…,m}，將調(diào)度方案描述為：

理想調(diào)度目標函數(shù)中包含時間、質(zhì)量、成本、資源消耗和邏輯關(guān)系影響，以各個指標作為目標，則資源優(yōu)化調(diào)度目標表示為：

其中T表示時間，W表示質(zhì)量，Y表示成本，S表示資源消耗，Z表示關(guān)系影響。考慮到資源優(yōu)化調(diào)度涉及到多個邏輯關(guān)系，因此對于關(guān)系影響系數(shù)的確定，以矩陣的形式表示：

式中zkij表示第k種資源屬性值的區(qū)間數(shù)，具體形式為：

式中z(-)kij、z(+)kij均大于等于0。根據(jù)區(qū)間數(shù)的運算規(guī)則，計算出效益型和成本型的屬性值。計算公式為：

其中式(5)表示效益型資源屬性值，式(6)表示成本型屬性值。利用上述公式計算出屬性值與理想值的偏離度：

偏離度表示了調(diào)度任務(wù)受到資源環(huán)境影響的程度，在建立理想目標函數(shù)時，將偏離度引入其中。

假設(shè)各個目標函數(shù)之間的相互關(guān)系矩陣為：

由此可確定，理想模型的目標函數(shù)之間的相互聯(lián)系矩陣權(quán)重，表示為：

由上述內(nèi)容，確定調(diào)度方案變量和調(diào)度目標體系之間的映射關(guān)系，從而得到理想的調(diào)度目標函數(shù)。理想調(diào)度目標函數(shù)表示為：

對目標函數(shù)求解，得到制造過程資源優(yōu)化的調(diào)度的最優(yōu)解。

1.3 求解調(diào)度最優(yōu)解

制造過程中待調(diào)度的資源分為可更新資源和不可更新資源，考慮資源優(yōu)化調(diào)度存在的時序約束和資源約束的問題，在求最優(yōu)解過程中，當調(diào)度過程中占用可更新資源時，同時保證其他調(diào)度任務(wù)的可更新資源量不變；在占用不可更新資源時，減小其他調(diào)度任務(wù)同等的可更新資源量，使資源平衡，達到約束資源的目的。

將每個資源優(yōu)化調(diào)度任務(wù)的執(zhí)行順序以編碼表示，通過編碼和解碼的更新迭代得到調(diào)度的最優(yōu)解。為編碼中每一個元素賦予一個區(qū)間在區(qū)間為[0,1]的隨機數(shù)，將隨機數(shù)作為編碼元素的優(yōu)先權(quán)值，生成的優(yōu)先權(quán)值是不重復(fù)出現(xiàn)的值，判斷隨機數(shù)的大小，生成隨機數(shù)大的調(diào)度任務(wù)優(yōu)先執(zhí)行，按照大小順序依次執(zhí)行其他調(diào)度任務(wù)。在編碼結(jié)束后，定義所有已經(jīng)完成調(diào)度任務(wù)的已調(diào)度集合，同時確定任務(wù)執(zhí)行的時間，在解碼時，從結(jié)合中選擇優(yōu)先權(quán)值大的資源調(diào)度任務(wù)優(yōu)先調(diào)度，確定資源調(diào)度任務(wù)最早可行時間。在調(diào)度完成后，計算完成時間，并將完成的任務(wù)從集合中刪除，按照上述過程，重復(fù)每一個資源優(yōu)化調(diào)度任務(wù)，直到所有資源完成調(diào)度，此時解碼結(jié)束，獲得所有任務(wù)的最遲完成時間。

根據(jù)返回的結(jié)果計算出調(diào)度方案的個體適應(yīng)度，若適應(yīng)度沒有達到最優(yōu)，更新編碼前優(yōu)先權(quán)值和編碼后模式值。由于編碼中的模式數(shù)必須是正整數(shù)，在更新過程中不能使用常規(guī)的更新方式進行更新，在更新過程中，判斷隨機數(shù)的大小，如果產(chǎn)生的隨機數(shù)小于原值，則不改變模式數(shù)；如果產(chǎn)生的隨機數(shù)大于原值，則將原值替換為經(jīng)過取整處理的隨機數(shù)。在更新完成后，檢查每一個資源優(yōu)化調(diào)度任務(wù)對應(yīng)的模式值，保證資源提供量能夠滿足模式值對應(yīng)的資源消耗[5]。遍歷制造過程中所有資源調(diào)度優(yōu)化調(diào)度任務(wù)，直到所有任務(wù)達到最優(yōu)解，結(jié)束計算與更新。經(jīng)過上述過程輸出的最優(yōu)解就是機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度的最佳方案。

2 機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度方法實驗研究

2.1 實驗測試集準備

由機械設(shè)備自動化制造過程資源調(diào)度項目組成測試集，根據(jù)項目網(wǎng)絡(luò)特性構(gòu)造不同類型的調(diào)度問題實例，在實驗研究中以典型的實例標準庫作為測試集，使用不同的調(diào)度方法對測試集進行求解，進而方便分析調(diào)度方法的性能。

實例標準庫中包含多個不同類型的測試集，每一種測試集包含的任務(wù)數(shù)量各不相同，針對機械設(shè)備自動化制造過程資源特點，從測試集中選取十個實例進行分析驗證，采取目前比較常見的兩種調(diào)度方法用于實驗中，通過對比實驗的方式進一步分析設(shè)計的調(diào)度方法在動態(tài)環(huán)境中的適應(yīng)性。實驗中選擇的實例均為抽象的數(shù)據(jù)表格，包括時序約束部分、資源約束部分和執(zhí)行成本部分。每一個調(diào)度任務(wù)均有三種選擇的模式，每個模式下消耗的資源和時間如表1所示。

表1 實例屬性表

利用MATLAB軟件編寫十個實例的網(wǎng)絡(luò)結(jié)構(gòu)，形成的網(wǎng)絡(luò)圖如圖2所示。

圖2 實驗項目網(wǎng)絡(luò)圖

在獲得實例的詳細信息后，使用不同的調(diào)度方法求解測試集，獲得資源調(diào)度消耗總時間的收斂曲線，同時計算出實驗結(jié)果與測試集理想結(jié)果的偏差率，根據(jù)實驗結(jié)果對比分析各個調(diào)度方法的適應(yīng)性。

2.2 調(diào)度時間最優(yōu)解比較分析

實驗中使用的調(diào)度方法分別是基于IMPACT的調(diào)度方法、基于灰狼算法的調(diào)度方法以及提出的調(diào)度方法，使用MATLAB軟件輸出各個調(diào)度方法的實驗結(jié)果，如圖3所示。

圖3 不同調(diào)度方法調(diào)度消耗總時間收斂曲線

根據(jù)圖中顯示的結(jié)果，計算出各個調(diào)度方法最優(yōu)解與測試集中最優(yōu)解的偏差率。設(shè)實驗中所有測試實例的最優(yōu)解百分比為100%，偏差率計算公式為：

式中u表示偏差率，t1表示調(diào)度方法執(zhí)行得到的資源調(diào)度總消耗時間，t表示測試集中實例的最優(yōu)解。經(jīng)過多次實驗和計算可得，基于IMPACT的調(diào)度方法的偏差率為3.49%，基于灰狼算法的調(diào)度方法偏差率為4.76%，提出的調(diào)度方法得到的最優(yōu)解與測試集中的最優(yōu)解偏差率為0.03%。將偏差率與資源調(diào)度總消耗時間收斂曲線結(jié)合共同分析可知，在三組調(diào)度方法實驗結(jié)果中，提出的資源優(yōu)化調(diào)度方法在求得資源調(diào)度最優(yōu)解過程中最少，與理想最優(yōu)解相近程度高。考慮到機械設(shè)備自動化制造過程是一個動態(tài)變化過程，在上述實驗的基礎(chǔ)上，改變項目網(wǎng)絡(luò)圖，使調(diào)度方法處于動態(tài)環(huán)境中，改變后的網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示。

圖4 重組后的實例項目網(wǎng)絡(luò)圖

以圖中顯示的網(wǎng)絡(luò)結(jié)構(gòu)作為實驗條件，使用不同的調(diào)度方法執(zhí)行資源調(diào)度任務(wù)，輸出總消耗時間收斂曲線并計算與理想最優(yōu)解的偏差率。實驗結(jié)果如圖5所示。

圖5 重組實例項目網(wǎng)絡(luò)后的調(diào)度消耗總時間實驗結(jié)果

經(jīng)過計算，基于IMPACT的調(diào)度方法的偏差率為7.29%，基于灰狼算法的調(diào)度方法偏差率為8.03%，提出的調(diào)度方法得到的最優(yōu)解與測試集中的最優(yōu)解偏差率為0.04%。通過圖中顯示的實驗結(jié)果以及計算的偏差率可知，三組實驗結(jié)果中，提出的調(diào)度方法在達到調(diào)度最優(yōu)解的時間消耗最少，其他兩種調(diào)度方法面對改變后的實例網(wǎng)絡(luò)結(jié)構(gòu)，資源調(diào)度所需時間有些許增長，并且與理想最優(yōu)解之間的偏差也出現(xiàn)了增加。綜上所述，提出的機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度方法面對動態(tài)環(huán)境能夠自動適應(yīng)，及時調(diào)整，使資源調(diào)度所需要的時間達到最小。在此基礎(chǔ)上，從實際需求出發(fā)，研究實際應(yīng)用中，資源實時使用情況，分析各個調(diào)度方法在動態(tài)環(huán)境下執(zhí)行過程中，資源使用量能否滿足機械設(shè)備自動化制造需求。

2.3 資源實時使用量分析

以調(diào)度任務(wù)和自動化制造過程資源使用量作為實驗變量，將兩組變量輸入到第三方軟件中，執(zhí)行三種不同的調(diào)度方法，設(shè)置虛擬資源量，在圖中一條虛線表示虛擬資源量，矩形表示調(diào)度任務(wù)，實驗中要求矩形的高度不能超過虛線。在調(diào)度方法執(zhí)行完成后，輸出實驗結(jié)果，具體內(nèi)容如圖5所示。

圖6 不同調(diào)度方法的資源實時使用量實驗結(jié)果

從上圖可知，在項目實例一致的情況下，提出的調(diào)度方法實驗結(jié)果中資源余量充足，在調(diào)度過程中，可以抽調(diào)多余的資源量繼續(xù)進行機械設(shè)備自動化制造，因此當設(shè)備出現(xiàn)故障或其他變化時，依然能夠保持穩(wěn)定，完成資源調(diào)度。而其他兩組實驗結(jié)果中，部分調(diào)度任務(wù)無限接近標記的虛線，對調(diào)度任務(wù)影響比較大，在動態(tài)環(huán)境中不能靈活調(diào)用資源量。

經(jīng)過兩組實驗驗證可得出一下結(jié)論，提出的機械設(shè)備自動化制造過程資源優(yōu)化調(diào)度方法在動態(tài)環(huán)境下調(diào)度消耗時間少，資源充足，適應(yīng)性良好。提出的調(diào)度方法優(yōu)于常見的調(diào)度方法，適合應(yīng)用在實際項目中。

3 結(jié)語

本文以機械設(shè)備自動化制造作為研究背景，對制造過程資源調(diào)度問題進行了研究與分析，在建立資源優(yōu)化調(diào)度方法的基礎(chǔ)上，給出了制造過程中資源調(diào)度的最優(yōu)解。為了證明提出的調(diào)度方法的性能，以常見的資源調(diào)度方法作為參考，通過對比實驗證明了提出的資源優(yōu)化調(diào)度方法在動態(tài)環(huán)境下?lián)碛懈玫倪m應(yīng)性，能夠積極適應(yīng)各種變化，在調(diào)度過程中保持穩(wěn)定。本文研究的內(nèi)容雖然在資源優(yōu)化調(diào)度上取得了一定成果，但是面對復(fù)雜的自動化環(huán)境，資源調(diào)度面臨的約束條件也有很多，并且各不相同，對調(diào)度方法的研究仍然需要不斷完善，在未來研究中，將從調(diào)度的智能化方面展開研究與討論，提高機械設(shè)備自動化制造的工作效率。