一種改進(jìn)的多處理機(jī)約束混合車間調(diào)度算法

楊思娜 瞿華

[摘? ? 要] 具有多處理機(jī)任務(wù)要求的多步調(diào)度問題在網(wǎng)絡(luò)并行計(jì)算系統(tǒng)中十分普遍。這樣的問題可以使用“具有多處理機(jī)任務(wù)約束的混合作業(yè)車間調(diào)度”（Hybrid Job-shop Scheduling with Multiprocessor Tasks，HJSMT）模型來表示，并使用“混合粒子群的優(yōu)化算法”（Hybrid Particle Swarm Optimization，HPSO）求解。改進(jìn)的算法在HPSO算法的基礎(chǔ)上進(jìn)行改進(jìn)：原HPSO算法在求一個(gè)任務(wù)的最早開始時(shí)間時(shí)使用窮舉法，每次從時(shí)間0開始向后，逐個(gè)單位時(shí)間嘗試;改進(jìn)后的算法運(yùn)用動(dòng)態(tài)規(guī)劃法求解。實(shí)驗(yàn)結(jié)果表明，相比原始算法的改進(jìn)算法，運(yùn)行速度有明顯的提升，原算法進(jìn)行一次迭代的時(shí)間，新算法已經(jīng)完成了一次實(shí)驗(yàn)（一次實(shí)驗(yàn)包含多次迭代），在保證HJSMT問題有效解決的同時(shí)提升了算法的時(shí)間效率。

[關(guān)鍵詞] 多處理機(jī)任務(wù);作業(yè)車間調(diào)度;混合粒子群優(yōu)化算法;動(dòng)態(tài)規(guī)劃

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2020. 17. 051

[中圖分類號(hào)] F270.7;TP315? ? [文獻(xiàn)標(biāo)識(shí)碼]? A? ? ? [文章編號(hào)]? 1673 - 0194（2020）17- 0113- 03

1? ? ? 引? ? 言

在并行計(jì)算領(lǐng)域中，網(wǎng)絡(luò)并行計(jì)算作為關(guān)鍵的發(fā)展方向，涉及各個(gè)領(lǐng)域，如集群計(jì)算、可擴(kuò)展計(jì)算、元計(jì)算、異構(gòu)計(jì)算、網(wǎng)格計(jì)算等。然而，由于網(wǎng)絡(luò)并行計(jì)算系統(tǒng)的復(fù)雜性，其涉及的領(lǐng)域較多，實(shí)現(xiàn)起來比較困難，因此還需要解決許多問題，如資源調(diào)度[1]。在網(wǎng)絡(luò)并行計(jì)算機(jī)系統(tǒng)中，為了完成具有多種資源需求的任務(wù)之間的協(xié)調(diào)調(diào)度，達(dá)到預(yù)期效果，需要在時(shí)間和空間上考慮資源的合理搭配組合。

傳統(tǒng)的資源調(diào)度問題可以分為并行系統(tǒng)中多處理機(jī)的任務(wù)調(diào)度（Multiprocessor Task Scheduling，MTS）和作業(yè)車間調(diào)度問題（Job-shop Scheduling Problem，JSP）兩大類。其中，MST問題每項(xiàng)任務(wù)需要多項(xiàng)資源，必須充分合理地利用一切可用資源，按某種順序安排所有待處理的多處理器任務(wù)，使加工處理總執(zhí)行時(shí)間盡可能小[2];JSP問題則對(duì)于給定的一組待加工工件與機(jī)器集合，每個(gè)工件都包含多道工序，且有特定的加工順序，每個(gè)工序中工件的加工只能由一臺(tái)機(jī)器進(jìn)行處理。同時(shí)JSP問題也是難解的NP-hard問題，開發(fā)有效的算法求解此類調(diào)度問題一直是資源調(diào)度和優(yōu)化領(lǐng)域的重要課題。然而，在一般化的網(wǎng)絡(luò)并行計(jì)算中，一項(xiàng)計(jì)算任務(wù)通常需要多個(gè)步驟來完成，并且每個(gè)步驟需要多個(gè)資源參與，相當(dāng)于MTS和JSP的混合，即“具有多處理機(jī)任務(wù)約束的混合作業(yè)車間調(diào)度”（Hybrid Job-shop Scheduling with Multiprocessor Tasks，HJSMT）模型。

例如文獻(xiàn)[3]給出的一個(gè)例子：有三個(gè)應(yīng)用（任務(wù)）A、B和C在各自的步驟中對(duì)資源a、b、c、d、e和f的需求如表1所示。

HJSMT問題是生產(chǎn)調(diào)度中一個(gè)典型的問題，不僅具有重要的理論價(jià)值，同時(shí)它在社會(huì)生產(chǎn)中具有重要的實(shí)際意義。首先隨著世界貿(mào)易競(jìng)爭越來越激烈，更優(yōu)的生產(chǎn)調(diào)度意味著更低的生產(chǎn)成本和更高的生產(chǎn)效率，采用高效的優(yōu)化技術(shù)，可以對(duì)生產(chǎn)過程中的突發(fā)事件做出快速、科學(xué)的反應(yīng)，改善生產(chǎn)性能指標(biāo)，有效提高生產(chǎn)效率。其次生產(chǎn)調(diào)度復(fù)雜的生產(chǎn)流程可以通過理論被應(yīng)用到實(shí)際生產(chǎn)中，使得密集型的生產(chǎn)需求得以在生產(chǎn)系統(tǒng)中實(shí)現(xiàn)。本文使用動(dòng)態(tài)規(guī)劃法對(duì)HJSMT問題的HPSO求解算法進(jìn)行改進(jìn)，提升了原算法的解碼效率，可以更加高效地求解網(wǎng)絡(luò)并行計(jì)算中的HJSMT問題。

2? ? ? 問題描述

3? ? ? 改進(jìn)的求解HJSMT的混合粒子群優(yōu)化算法

3.1? ?混合粒子群優(yōu)化算法HPSO

文獻(xiàn)[5]提出的混合粒子群優(yōu)化算法，是結(jié)合群智能算法和本地搜索算法的優(yōu)點(diǎn)，在粒子群算法的基礎(chǔ)上，增加了一種基于模擬退火的局部搜索算法，用來求解網(wǎng)絡(luò)并行計(jì)算中的HJSMT問題。

粒子群優(yōu)化算法（PSO）的基本思想源自鳥群捕食行為，從鳥群飛向食物的行為特點(diǎn)得到啟發(fā)。在該算法中，稱種群為“粒子群”，稱種群中的每個(gè)個(gè)體為“粒子”，對(duì)應(yīng)于每個(gè)優(yōu)化問題的一個(gè)候選解。首先進(jìn)行種群初始化，并隨機(jī)生成一群粒子，每個(gè)粒子都是優(yōu)化問題（目標(biāo)函數(shù)）的一個(gè)解。每次迭代，在解空間中飛行的所有粒子，通過追尋個(gè)體最優(yōu)Pbest和群體最優(yōu)Gbest這兩個(gè)極值來更新自身的速度和位置。個(gè)體最優(yōu)Pbest是某個(gè)粒子在一次迭代中找到的個(gè)體最優(yōu)解，Gbest是所有個(gè)體在一次迭代中找到的種群最優(yōu)解。通過不斷地迭代使粒子不斷更新自己的速度和位置，從而產(chǎn)生新的個(gè)體最優(yōu)和種群最優(yōu)，通過比較得出目標(biāo)函數(shù)的最優(yōu)解。針對(duì)HJSMT問題的特點(diǎn)，HPSO在此基礎(chǔ)上采用新的位置更新方式和基于模擬退火的局部搜索方式，保證了算法性能。HPSO流程如圖1所示。

3.2? ?粒子編碼和解碼策略

為了產(chǎn)生滿足約束條件（2）和（3）的粒子，采用基于步驟的編碼方式：將一個(gè)粒子表示成一個(gè)長度為■|Ji|的向量V，向量V的每個(gè)元素代表對(duì)應(yīng)的工件，工件i出現(xiàn)|Ji|次，出現(xiàn)的順序代表該工件對(duì)應(yīng)的加工工序。通過解碼可以將粒子還原成對(duì)應(yīng)的調(diào)度方案，根據(jù)文獻(xiàn)[5]給出一種HJSMT的主動(dòng)調(diào)度解碼算法進(jìn)行解碼：

輸入：粒子向量

輸出：粒子的最大完工時(shí)間

解碼策略產(chǎn)生的調(diào)度滿足約束條件（3）。編碼和解碼策略的結(jié)合使用，使粒子能夠在可行域內(nèi)找到最優(yōu)解。

4? ? ? 解碼策略的改進(jìn)

4.1? ?算法改進(jìn)思想

上述HPSO的主動(dòng)調(diào)度解碼算法使用窮舉法，每次搜索可行的加工步驟從時(shí)間0向后開始，逐個(gè)嘗試單位時(shí)間，尋找符合當(dāng)前加工任務(wù)中下一待加工步驟的處理機(jī)器，若找到符合加工步驟的剩余機(jī)器則開始加工;若該時(shí)刻沒有剩余機(jī)器，則等待，重復(fù)上述搜索步驟;若工件完成所有加工步驟，則輸出加工時(shí)間，未完成所有加工步驟則繼續(xù)加工。由于該解碼方式每搜索完成一次待加工步驟的最早開始時(shí)間就將時(shí)間初始化為0，下次搜索從時(shí)間0開始，若多次迭代測(cè)試，計(jì)算機(jī)處理時(shí)間較長，效率較低。

動(dòng)態(tài)規(guī)劃法是解決多階段決策最優(yōu)化問題一種常用的方法，從整體來看算法的實(shí)現(xiàn)是按照遞推關(guān)系式進(jìn)行遞推，在搜索時(shí)能體現(xiàn)高時(shí)效性。相比于其他算法，動(dòng)態(tài)規(guī)劃法不僅減少了大量的計(jì)算量，而且得到當(dāng)前狀態(tài)對(duì)目標(biāo)狀態(tài)的最優(yōu)值的同時(shí)還得到了中間狀態(tài)的最優(yōu)值，豐富了計(jì)算結(jié)果。它所解決的問題需要滿足最優(yōu)性原理和馬爾可夫性（無后效性）。

最優(yōu)性原理簡單地說就是各個(gè)子問題的最優(yōu)解構(gòu)成原問題的最優(yōu)解;馬爾可夫性則是指現(xiàn)在時(shí)刻的隨機(jī)變量的狀態(tài)和過去某一時(shí)刻的隨機(jī)變量狀態(tài)有關(guān)， 但和過去的所有隨機(jī)變量的狀態(tài)無關(guān)，即n時(shí)刻的狀態(tài)只與n-1時(shí)刻相關(guān)，且能被前一次狀態(tài)推算出來。

HPSO算法的粒子解碼問題（求最大完工時(shí)間）滿足最優(yōu)性和無后效性的證明如下：

令Cij為步驟Oij的最早結(jié)束時(shí)間，pij為其處理時(shí)間（見問題描述）。Aij為步驟Oij的前一道步驟，C（Aij）為其最早結(jié)束時(shí)間，p（Aij）為其處理時(shí)間。Bij為步驟Oij中用到的所有處理機(jī)集合，m為Bij中的任一處理機(jī)，C（m）為其最早結(jié)束時(shí)間，p（m）為其處理時(shí)間。則必有

因此，步驟Oij的最早結(jié)束時(shí)間Cij只與C（Aij）和C（m），m∈Bij有關(guān)，即HPSO算法的粒子解碼問題同時(shí)滿足最優(yōu)性條件和無后效性條件，可以用動(dòng)態(tài)規(guī)劃法求解。

4.2? ?算法改進(jìn)步驟

根據(jù)動(dòng)態(tài)規(guī)劃法，對(duì)解碼策略的具體改進(jìn)為：直接找待加工步驟所依賴的前序步驟中結(jié)束時(shí)間中最晚的一個(gè)，作為待加工步驟的開始加工時(shí)間。實(shí)施步驟如下：

輸入：粒子向量

輸出：粒子的最大完工時(shí)間

改進(jìn)后的解碼算法如圖2所示。

4.3? ?實(shí)驗(yàn)結(jié)果

為驗(yàn)證改進(jìn)后算法的性能，使用Java 8語言實(shí)現(xiàn)了原算法和改進(jìn)的算法，并進(jìn)行性能測(cè)試。硬件環(huán)境為： CPU 2.50GHz、內(nèi)存4.00GB;軟件環(huán)境為：Windows 10操作系統(tǒng)，Java 8。

生成一批規(guī)模不同的HJSMT算例：

（1）任務(wù)數(shù)量n=5。

（2）步驟數(shù)量q=5。

（3）每個(gè)步驟占用的處理機(jī)數(shù)量|mij|～[1，5]。

（4）步驟的加工時(shí)間pij～[1，99]。

（5）種群數(shù)量PopSize=40。

兩種算法程序運(yùn)行時(shí)間如表2所示。

從表2中可見，改進(jìn)的解碼策略在測(cè)試時(shí)速度有明顯提升，當(dāng)處理機(jī)數(shù)量為25、迭代次數(shù)為100時(shí)，速度提高為原來的111.4倍。這意味著新的算法可以在更短的時(shí)間內(nèi)處理更復(fù)雜的問題，或者在相同的時(shí)間內(nèi)用不同的初始種群進(jìn)行更多次實(shí)驗(yàn)，以得到更優(yōu)的結(jié)果。

5? ? ? 結(jié)? ? 論

本文從具有多處理機(jī)任務(wù)約束的混合作業(yè)車間調(diào)度HJSMT問題出發(fā)，在已提出的HPSO算法的基礎(chǔ)上，利用動(dòng)態(tài)規(guī)劃法對(duì)解碼策略進(jìn)行改進(jìn)。實(shí)驗(yàn)證明，改進(jìn)的算法極大地提高了計(jì)算效率，能夠在相同的時(shí)間內(nèi)進(jìn)行更多次隨機(jī)計(jì)算，從而獲得更優(yōu)的結(jié)果。在未來的研究中，可以對(duì)資源調(diào)度問題涉及的其他算法進(jìn)行研究，例如粒子的搜索、粒子最優(yōu)解的選取等，進(jìn)一步優(yōu)化算法、提升效率，提升調(diào)度的效果，使其更具時(shí)效性。

主要參考文獻(xiàn)

[1]黃金貴，陳松喬，陳建二.網(wǎng)絡(luò)并行計(jì)算系統(tǒng)中基于多處理機(jī)任務(wù)的資源調(diào)度模型[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（29）：54-58.

[2]黃金貴.任意處理時(shí)間的多處理機(jī)任務(wù)調(diào)度近似算法[J].計(jì)算機(jī)工程與應(yīng)用，2008（33）：7-9.

[3]都志輝，陳渝，劉鵬.網(wǎng)格計(jì)算[M].北京：清華大學(xué)出版社，2002.

[4]Drozdowski M.Scheduling Multiprocessor Tasks- An Overview[J].European Journal of Operational Research，1996， 94（2）：215-230.

[5]王蒙，樊坤，翟亞飛，等.網(wǎng)絡(luò)并行計(jì)算中多處理機(jī)任務(wù)調(diào)度問題研究[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（10）：264-270.