姜國(guó)仙

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 實(shí)驗(yàn)測(cè)試集準(zhǔn)備

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

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

表1 實(shí)例屬性表

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

圖2 實(shí)驗(yàn)項(xiàng)目網(wǎng)絡(luò)圖

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

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

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

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

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

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

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

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

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

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

2.3 資源實(shí)時(shí)使用量分析

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

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

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

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

3 結(jié)語(yǔ)

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