1.2　車間生產(chǎn)調(diào)度問題及研究現(xiàn)狀

1.2.1　車間生產(chǎn)調(diào)度問題

加工任務(wù)中有明確的工件個數(shù)，每個工件有相應(yīng)的工序，每個工序要經(jīng)過相應(yīng)的加工機器，車間生產(chǎn)調(diào)度是指在各種約束條件下，完成生產(chǎn)成本、行為情景等一個或多個目標(biāo)，實現(xiàn)人們對生產(chǎn)調(diào)度問題的規(guī)劃愿景。科學(xué)系統(tǒng)的方法論應(yīng)用到生產(chǎn)調(diào)度問題中以后，逐漸形成較為完整的理論體系以及相應(yīng)的模型和算法，取得了一系列具有理論和應(yīng)用價值的研究成果，為復(fù)雜的生產(chǎn)調(diào)度問題提供了解決方案。

工件、加工機器和優(yōu)化準(zhǔn)則是車間生產(chǎn)調(diào)度問題的三個基本要素，通常采用三元組α、β、γ進行描述［9］，其中α域表示加工機器環(huán)境，通常只包括單一的選項；β域表示加工特征和約束細(xì)節(jié)，可能包括多個選項，也可能不包括任何選項；γ域表示調(diào)度優(yōu)化的目標(biāo)，通常只包括一項。α域表示的加工機器環(huán)境情況如表1.1所示。

β域表示的加工特征和約束細(xì)節(jié)情況如表1.2所示。

γ域表示的調(diào)度優(yōu)化的目標(biāo)如表1.3所示。

車間生產(chǎn)調(diào)度問題一般具有如下特征：

復(fù)雜性：生產(chǎn)調(diào)度問題通常比較復(fù)雜，求解模型多為NP-hard性質(zhì)的問題，精確解優(yōu)化方法難以得到令人滿意的結(jié)果。

動態(tài)性：在生產(chǎn)調(diào)度過程中，隨機工件到達、機器故障、加工時間的不確定等因素都會導(dǎo)致調(diào)度問題具有一定的動態(tài)不確定性或模糊性。

多約束性：在生產(chǎn)調(diào)度過程中，機器的生產(chǎn)能力、工人的作息、產(chǎn)品的完工時間、生產(chǎn)成本等約束條件都會增加問題的求解難度。

多目標(biāo)性：在進行一項生產(chǎn)任務(wù)時，為了獲得最佳的經(jīng)濟效益和社會效益，需要用不同的指標(biāo)來衡量，導(dǎo)致在生產(chǎn)調(diào)度問題中會有不同的目標(biāo)，通常這些目標(biāo)是相互沖突的。

1.2.2　研究現(xiàn)狀

1.車間生產(chǎn)調(diào)度問題算法研究現(xiàn)狀

生產(chǎn)調(diào)度問題受到了工程技術(shù)、優(yōu)化、數(shù)學(xué)、計算機等領(lǐng)域研究者的共同關(guān)注，從調(diào)度問題的建模、算法設(shè)計和工程應(yīng)用等多個角度開展了深入的研究。隨著經(jīng)濟社會發(fā)展和科學(xué)技術(shù)的進步，新技術(shù)結(jié)合新時代生產(chǎn)調(diào)度問題的特點，涌現(xiàn)出了很多新的生產(chǎn)調(diào)度優(yōu)化方法，從問題解決方法的角度一般可分為運籌學(xué)方法、啟發(fā)式方法和智能優(yōu)化方法。

將傳統(tǒng)的運籌學(xué)方法應(yīng)用到生產(chǎn)調(diào)度問題中，比如用動態(tài)規(guī)劃法求解流水車間調(diào)度問題的最小加工時間問題［10］，分支定界法求解車間調(diào)度問題［11］，以及拉格朗日松弛法［12］和整數(shù)規(guī)劃法［13］求解生產(chǎn)調(diào)度問題。啟發(fā)式方法指人們在解決問題時所采取的一種根據(jù)經(jīng)驗規(guī)則解決問題的方法，在有限的搜索空間內(nèi)尋求問題的解決方案，這類方法未必能找到最優(yōu)解，但可通過建立科學(xué)合理的啟發(fā)式規(guī)則，利用啟發(fā)式函數(shù)在多項式時間內(nèi)找到問題的滿意解。比如隨機工件到達和機器故障等不確定問題，結(jié)合動態(tài)車間調(diào)度問題模型和啟發(fā)式算法進行問題求解［14］。在作業(yè)車間中受干擾的重調(diào)度或動態(tài)不確定問題，利用切換調(diào)度、無置換和純置換調(diào)度等啟發(fā)式算法，實現(xiàn)工件的加工時間加權(quán)延遲最小的目標(biāo)［15］。也有研究者基于已輸入的重調(diào)度中斷信息，產(chǎn)生新的時間表并輸出它們相關(guān)的性能度量，克服了其他重調(diào)度方法的缺點［16］。Lodree等［17］針對以最小拖期為優(yōu)化目標(biāo)的流水車間調(diào)度問題，將多機器問題分解為若干個單機器問題，通過求解單機問題的最優(yōu)解來獲取調(diào)度問題的最優(yōu)解。

研究表明，由于實際工程問題的復(fù)雜性、大規(guī)模性、不確定性、多約束性、非線性、多極值和建模困難等特點，要尋找最優(yōu)解非常困難，有工程意義的求解算法是在合理、有限的時間內(nèi)尋找到近似最優(yōu)的可行解。因此，基于統(tǒng)計式的全局搜索技術(shù)、遺傳算法和神經(jīng)網(wǎng)絡(luò)等元啟發(fā)式方法在生產(chǎn)調(diào)度領(lǐng)域得到快速發(fā)展，引起了國內(nèi)外研究者的共同關(guān)注。

（1）遺傳算法求解車間生產(chǎn)調(diào)度問題。

遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的方法，具備并行性和魯棒性等特點，被人們廣泛應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、信號處理和自適應(yīng)控制等領(lǐng)域［18］。基于規(guī)則的遺傳算法以最小化空閑時間和拖期懲罰為目標(biāo)，被成功應(yīng)用于求解工件隨機到達、批量可變的最小化延遲問題［19］。Chen等［20］在考慮優(yōu)先規(guī)則的基礎(chǔ)上，將基于遺傳算法的調(diào)度方法成功應(yīng)用于動態(tài)生產(chǎn)系統(tǒng)。馬衛(wèi)民等［21］在典型遺傳算法的基礎(chǔ)上對算法進行改進，利用改進的多種群遺傳算法求解作業(yè)車間調(diào)度問題，引入移民和升降級等機制提高算法的尋優(yōu)效率。Rezaeian等［22］結(jié)合遺傳算法提出了一種新的混合整數(shù)線性規(guī)劃模型，通過實例對遺傳算法的性能進行了分析，結(jié)果表明在合理的計算時間內(nèi)具有良好的性能。學(xué)者張紀(jì)會等研究了雙層優(yōu)化算法的外層工藝路線優(yōu)化問題［23］，學(xué)者劉愛軍等用基于自適應(yīng)遺傳算法的多目標(biāo)柔性動態(tài)調(diào)度算法解決多目標(biāo)調(diào)度問題［24］。

（2）蟻群算法求解車間生產(chǎn)調(diào)度問題。

蟻群算法是一種仿生算法，以信息素作為啟發(fā)信息，在復(fù)雜的組合優(yōu)化問題中得到廣泛應(yīng)用，具有計算精度高、速度快、易于實現(xiàn)等特點，較早就被用于解決流水車間調(diào)度問題。在開放車間和作業(yè)車間混合場景下，Blum［25］將作業(yè)車間調(diào)度問題中的工序映射為對應(yīng)的工序組，把蟻群算法與其他算法結(jié)合構(gòu)建了混合算法。陳暄等［26］在蟻群算法中采用質(zhì)量函數(shù)和收斂因子來保證信息素更新的有效性，結(jié)合蛙跳算法中交叉因子和變異因子來提高局部搜索效率。李燚等［27］設(shè)計了改進的蟻群算法，使用一種特定啟發(fā)式函數(shù)，并更改迭代過程中最優(yōu)解的評價方法后將其用于求解汽車混流裝配調(diào)度問題。Engin等［28］提出一種基于交叉變異機制的混合蟻群算法求解無等待流水車間調(diào)度問題的最大完工時間。對于多階段混合車間調(diào)度問題，Qin等［29］提出了一種兩級進化蟻群算法，將原問題分解成兩個高度耦合子問題，實驗證明了該算法在計算時間和穩(wěn)定性方面的優(yōu)越性。

（3）粒子群算法求解車間生產(chǎn)調(diào)度問題。

粒子群算法源于對鳥群等動物群體行為規(guī)律的研究，具有典型的群體智能特性，粒子群算法提出以后在生產(chǎn)調(diào)度領(lǐng)域得到了廣泛的應(yīng)用。Pan等［30］在完工時間和總流經(jīng)時間等多目標(biāo)的流水車間調(diào)度問題中，通過離散的粒子群算法和鄰域搜索算法有效提高了解的質(zhì)量。Eddaly等［31］應(yīng)用粒子群算法求解具有阻塞約束的流水車間調(diào)度問題。韓文民等［32］結(jié)合混合離散粒子群算法形成新的重調(diào)度決策方法，并用于解決重調(diào)度非線性整數(shù)規(guī)劃問題。李振等［33］通過在粒子的位置更新公式中加入創(chuàng)新因子，使之獲得了更好的探索能力，增強了種群在進化過程中的多樣性，提高了算法的全局搜索能力。顧文斌等［34］針對相同并行機混合流水車間調(diào)度問題，提出一種基于激素調(diào)節(jié)機制的改進粒子群算法，用于求解并行機混合流水車間調(diào)度問題，并驗證了所提算法的優(yōu)越性。呂媛媛等［35］針對多目標(biāo)混合多處理任務(wù)作業(yè)車間調(diào)度問題，以最小化最大完工時間和最小化總拖延時間為目標(biāo)建立雙目標(biāo)問題模型，提出一種新的改進多目標(biāo)粒子群算法對其求解。該算法以IPOX交叉和多輪變異策略更新粒子，根據(jù)動態(tài)鄰域思想設(shè)計新的外部種群尋優(yōu)機制尋找每一代較優(yōu)解，結(jié)合個體擁擠距離刪減并維護外部種群。結(jié)果表明，該算法在選取鄰域粒子數(shù)量為2時求解效果最好，并且通過與NSGA-Ⅱ算法進行對比，驗證了算法的有效性。

（4）其他元啟發(fā)式算法求解車間生產(chǎn)調(diào)度問題。

袁帥鵬等［36、37］針對兩階段流水車間成組調(diào)度問題，在同時考慮序列不相關(guān)準(zhǔn)備時間和階段間雙向運輸時間約束的情況下，以最小化最大完工時間為目標(biāo)建立了混合整數(shù)線性規(guī)劃模型，結(jié)合問題特征提出一種協(xié)同進化迭代貪婪算法。算法將工件組之間排序和各工件組內(nèi)部的工件排序兩個子問題進行統(tǒng)一編碼，設(shè)計了不同的啟發(fā)式規(guī)則產(chǎn)生問題的初始解，并提出一種協(xié)同導(dǎo)向迭代貪婪規(guī)則對兩個子問題進行聯(lián)合優(yōu)化，進而給出了問題的三個下界以評估算法的性能。通過不同規(guī)模的數(shù)據(jù)實驗和與對比算法的比較分析，驗證了所提算法的高效性和穩(wěn)健性。張源等［38］針對混合流水車間調(diào)度問題，以最小化最大完工時間為目標(biāo)函數(shù)建立了仿真優(yōu)化模型，并提出了一種改進差分進化算法進行求解，將算法結(jié)合反向?qū)W習(xí)策略生成初始種群，在差分進化中進一步引入自適應(yīng)差分因子，并在個體選擇機制中引入模擬退火算法的Metropolis準(zhǔn)則，有效提高了該算法的全局搜索能力。黎陽等［39］為解決大規(guī)模（工件數(shù)＞100）置換流水車間調(diào)度問題，提出一種改進的模擬退火算法，改進了初始退火溫度的設(shè)置，給出相應(yīng)的計算函數(shù)；采用基于概率的多策略協(xié)同搜索生成新解，并引入并行搜索和記憶功能概念，以提升大規(guī)模問題下解的質(zhì)量，以及把發(fā)動機連桿部件實際制造車間等作為數(shù)值和工程案例，對算法進行了性能驗證，表明了所提方法的有效性。

（5）神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)求解車間生產(chǎn)調(diào)度問題。

深度學(xué)習(xí)源于人工神經(jīng)網(wǎng)絡(luò)，其模型通常由多層非線性運算單元組合而成，將原始樣本數(shù)據(jù)作為輸入，將低層的輸出作為更高一層的輸入來學(xué)習(xí)數(shù)據(jù)的抽象特征。深度學(xué)習(xí)通過監(jiān)督學(xué)習(xí)或非監(jiān)督學(xué)習(xí)的方式進行訓(xùn)練，其中監(jiān)督學(xué)習(xí)是通過外部帶標(biāo)注的訓(xùn)練集進行學(xué)習(xí)，而非監(jiān)督學(xué)習(xí)是通過訓(xùn)練來尋找未標(biāo)注數(shù)據(jù)中的隱含結(jié)構(gòu)。本書的深度學(xué)習(xí)特指通過非線性神經(jīng)網(wǎng)絡(luò)進行函數(shù)或曲面的逼近，以端到端的方式進行特征學(xué)習(xí)，取代了手工標(biāo)注特征的傳統(tǒng)方法，通過多層神經(jīng)網(wǎng)絡(luò)來識別數(shù)據(jù)間的關(guān)系，學(xué)習(xí)到的特征具有更強的泛化能力；同時，為了能夠充分利用相關(guān)先驗知識，提升深度學(xué)習(xí)對中間特征層的高層語義表達能力，將深度學(xué)習(xí)方法與知識引導(dǎo)模型進行結(jié)合，可以構(gòu)建更加有效的深度學(xué)習(xí)機制［40］。

2016年3月，DeepMind公司研發(fā)的以深度學(xué)習(xí)等技術(shù)為核心的圍棋程序AlphaGo以4∶1的成績戰(zhàn)勝圍棋世界冠軍李世石［41］；2017年5月，圍棋程序AlphaGo Master以3∶0的成績戰(zhàn)勝世界圍棋冠軍柯潔。在16萬個圍棋棋譜基礎(chǔ)上，它通過學(xué)習(xí)獲得的圍棋能力已超過人類職業(yè)圍棋頂尖水平。此后，DeepMind公司發(fā)布以強化學(xué)習(xí)為核心技術(shù)的新圍棋程序AlphaGo Zero［42］，在給定規(guī)則的情況下，不依靠人類棋譜，僅通過強化學(xué)習(xí)等技術(shù)進行自我對弈學(xué)習(xí)，自主學(xué)會圍棋中的高級概念和博弈技巧，經(jīng)過3天的訓(xùn)練，以100∶0的成績戰(zhàn)勝AlphaGo版本；經(jīng)過40天的訓(xùn)練，成功擊敗了AlphaGo Master版本。

2006年，Hinton等［43］提出先通過非監(jiān)督學(xué)習(xí)方式對網(wǎng)絡(luò)進行逐層貪婪預(yù)訓(xùn)練，再通過監(jiān)督學(xué)習(xí)方式對整個網(wǎng)絡(luò)進行微調(diào)的基本訓(xùn)練原則，這種新穎的方法在很大程度上降低了神經(jīng)網(wǎng)絡(luò)的優(yōu)化難度。Azadeh等［44］提出一種離散事件模擬與人工神經(jīng)網(wǎng)絡(luò)相結(jié)合的元模型，利用神經(jīng)網(wǎng)絡(luò)的反向傳播機制成功求解調(diào)度問題的最大完工時間。有學(xué)者利用神經(jīng)網(wǎng)絡(luò)對現(xiàn)有基準(zhǔn)問題最優(yōu)解提取特征知識，再通過訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)對新的調(diào)度問題預(yù)測序列位置信息，經(jīng)驗證對更大規(guī)模的調(diào)度問題同樣有效［45、46］。Sim等［47］將神經(jīng)網(wǎng)絡(luò)用于調(diào)度規(guī)則實時選擇，根據(jù)當(dāng)前系統(tǒng)狀態(tài)和車間工況參數(shù)選擇最合適的調(diào)度規(guī)則，通過仿真優(yōu)化確定了神經(jīng)網(wǎng)絡(luò)參數(shù)，結(jié)果表明神經(jīng)網(wǎng)絡(luò)能夠動態(tài)選擇有效的調(diào)度規(guī)則。Adibi等［48］在事件驅(qū)動的策略重新調(diào)度問題中，由可變鄰域搜索響應(yīng)動態(tài)事件觸發(fā)，將目標(biāo)函數(shù)作為多目標(biāo)績效測度來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，再利用訓(xùn)練好的人工神經(jīng)網(wǎng)絡(luò)更新變鄰域搜索參數(shù)，也得到了令人滿意的結(jié)果。Zhou等［49］結(jié)合深度學(xué)習(xí)提出一種工件調(diào)度系統(tǒng)，使用一種簡單的貪婪機制定期對全部工件完成調(diào)度排序。

（6）強化學(xué)習(xí)算法求解車間生產(chǎn)調(diào)度問題。

強化學(xué)習(xí)通過與環(huán)境交互獲得反饋信號，其目的是最大化獎勵信號。因此，一般將強化學(xué)習(xí)理解為監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)之外的第三種機器學(xué)習(xí)方式。需要在學(xué)習(xí)過程中權(quán)衡“探索”和“開發(fā)”之間的關(guān)系，智能體根據(jù)信號采取相應(yīng)的動作，在交互中逐步改進策略，以獲得最大的累積獎勵。

強化學(xué)習(xí)通過馬爾可夫決策過程對序貫決策問題進行建模，通過與環(huán)境不斷交互試錯來實現(xiàn)狀態(tài)到動作的映射［50］。Zhang等［51］利用平均獎勵強化學(xué)習(xí)方法求解平行機調(diào)度問題。Gabel等［52］將作業(yè)車間調(diào)度問題理解為順序決策問題，提出了一種使用少量實值參數(shù)的調(diào)度表示方法，使用策略梯度強化學(xué)習(xí)來調(diào)整算法參數(shù)以提高策略的性能。崔建雙等［53］提出了一種基于Q-learning的超啟發(fā)式模型求解多模式資源約束項目調(diào)度問題，結(jié)果表明算法在目標(biāo)值、通用性、魯棒性等多項性能指標(biāo)上均表現(xiàn)優(yōu)異。Aydin等［54］根據(jù)模擬環(huán)境的實際情況，實時選擇最合適的優(yōu)先級規(guī)則，通過改進的強化學(xué)習(xí)算法對智能體進行訓(xùn)練，使其在學(xué)習(xí)階段中作出調(diào)度決策。潘燕春等［55］將強化學(xué)習(xí)算法與其他算法結(jié)合用于解決生產(chǎn)調(diào)度問題，針對流水車間調(diào)度問題設(shè)計了一種遺傳強化學(xué)習(xí)算法，引入狀態(tài)變量和行動變量，把組合優(yōu)化的排序問題轉(zhuǎn)換成序貫決策問題加以解決。Cunha等［56］提出一種基于機器學(xué)習(xí)的作業(yè)車間調(diào)度問題新方法，通過創(chuàng)建一個新的體系結(jié)構(gòu)，將強化學(xué)習(xí)整合到調(diào)度系統(tǒng)中，以強化學(xué)習(xí)代理解決作業(yè)車間調(diào)度問題，實驗證明了算法可以在極短的時間內(nèi)高質(zhì)量地解決任何問題，并接近于最優(yōu)方法。賀俊杰等［57］針對等效并行機在線調(diào)度問題，以加權(quán)完工時間和為目標(biāo)，提出了一種基于長短期記憶近端策略優(yōu)化強化學(xué)習(xí)的在線調(diào)度方法。作者通過設(shè)計融合LSTM的智能體記錄車間的歷史狀態(tài)變化和調(diào)度策略，進而根據(jù)狀態(tài)信息進行在線調(diào)度。

動態(tài)調(diào)度問題是一類更復(fù)雜的生產(chǎn)調(diào)度問題，Aissani等［58］提出一種多智能體的動態(tài)調(diào)度方法用于石油工業(yè)，并取得了很好的實驗結(jié)果。趙也踐等［59］提出了一種基于改進Q-learning算法和調(diào)度規(guī)則的動態(tài)調(diào)度算法，以“剩余任務(wù)緊迫程度”的概念來描述動態(tài)調(diào)度算法的狀態(tài)空間；設(shè)計了以“松弛越高，懲罰越高”為宗旨的回報函數(shù)，通過引入以Softmax函數(shù)為主體的動作選擇策略來改進傳統(tǒng)的Q-learning算法，調(diào)度結(jié)果明顯優(yōu)于使用單一調(diào)度規(guī)則以及傳統(tǒng)優(yōu)化算法等常規(guī)方法。陳勇等［60］針對大型裝備制造企業(yè)擾動多、影響大的問題，以元胞機模型為框架構(gòu)建了多擾動車間生產(chǎn)調(diào)度模型，設(shè)計了基于設(shè)備平均利用率與工件平均流程時間雙目標(biāo)最優(yōu)的目標(biāo)函數(shù)，采用強化學(xué)習(xí)算法優(yōu)化了元胞機的自組織演化規(guī)則，建立了基于元胞機與強化學(xué)習(xí)算法的多擾動車間柔性調(diào)度模型，并通過仿真求解驗證了算法與模型的有效性與可靠性。Shahrabi等［61］針對動態(tài)調(diào)度問題，考慮隨機工件到達和機器故障等因素，采用強化學(xué)習(xí)算法來選擇重調(diào)度的參數(shù)，并將參數(shù)質(zhì)量作為強化學(xué)習(xí)的獎勵函數(shù)，通過與普通變鄰域搜索算法進行對比，實驗證明所提方法的有效性。韓忻辰等［62］構(gòu)建了以各列車在各車站延誤時間總和最小為目標(biāo)函數(shù)的高速鐵路列車動態(tài)調(diào)度模式，在此基礎(chǔ)上設(shè)計了用于與智能體交互的仿性環(huán)境，采用Q-learning算法進行求解。最后，通過實例驗證了仿性環(huán)境的合理性以及Q-learning算法用于高鐵動態(tài)調(diào)度的有效性，為高鐵調(diào)度員作出優(yōu)化決策提供了良好的依據(jù)。尹愛軍等［63］提出一種基于強化學(xué)習(xí)的改進NSGA-Ⅱ算法，利用強化學(xué)習(xí)動態(tài)優(yōu)化種群迭代過程中的拆分比例參數(shù)以保持多樣性，改善算法收斂性能。最后，通過Kacem標(biāo)準(zhǔn)算例進行了仿真實驗與性能分析，驗證了算法的有效性與優(yōu)越性。

多智能體強化學(xué)習(xí)在調(diào)度優(yōu)化問題中也得到了成功的應(yīng)用。Gronauer等［64］綜述了當(dāng)前多智能體深度強化學(xué)習(xí)領(lǐng)域的研究進展，列舉了多智能體領(lǐng)域獨有的挑戰(zhàn)，回顧了用來應(yīng)對這些挑戰(zhàn)的方法，討論了進展和可能的發(fā)展方向。Lee等［65］基于單智能體強化學(xué)習(xí)案例中的實證提出了一種預(yù)處理增強的多智能體強化學(xué)習(xí)算法，使用行為克隆的方式作為預(yù)處理神經(jīng)網(wǎng)絡(luò)手段，通過求解模型來驗證所提方法的有效性，三種場景的實驗結(jié)果表明，所提出的方法是可行的解決方法，在求解質(zhì)量和計算時間方面具有一定的優(yōu)越性。Kim等［66］提出了一個使用多智能體系統(tǒng)和強化學(xué)習(xí)的智能制造系統(tǒng)，其特點是具有智能體的機器使系統(tǒng)具有決策自主權(quán)，與其他系統(tǒng)交互的社交性，以及智能學(xué)習(xí)動態(tài)變化的環(huán)境。在該系統(tǒng)中，具有智能代理功能的機器對作業(yè)的優(yōu)先級進行評估，并通過協(xié)商進行分配。通過比較提前完工、生產(chǎn)率和延遲調(diào)度問題的結(jié)果，驗證了該系統(tǒng)和調(diào)度規(guī)則的性能。結(jié)果表明分布式人工智能制造系統(tǒng)在動態(tài)環(huán)境下具有競爭力。

多目標(biāo)優(yōu)化調(diào)度問題是當(dāng)前優(yōu)化調(diào)度學(xué)科的另一個熱點研究方向，袁景凌等［67］針對異構(gòu)云環(huán)境多目標(biāo)優(yōu)化調(diào)度問題，設(shè)計了一種AHP定權(quán)的多目標(biāo)強化學(xué)習(xí)作業(yè)調(diào)度方法。首先定義了執(zhí)行時間、平臺運行能耗、成本等多個目標(biāo)，其中定義服務(wù)延遲成本用來描述用戶對服務(wù)質(zhì)量的滿意程度。其次設(shè)計了面向異構(gòu)資源的多目標(biāo)調(diào)度綜合評價方法，該方法利用層次分析法確定了各個目標(biāo)的權(quán)重。最后將該方法引入Q-learning的獎勵值計算，使其能反映異構(gòu)云環(huán)境下作業(yè)的總體執(zhí)行情況，并對后續(xù)抵達的作業(yè)起到良好的經(jīng)驗借鑒作用。實驗結(jié)果表明本書提出的方法優(yōu)于大部分對比方法，能較好地優(yōu)化作業(yè)執(zhí)行效率和保障用戶及服務(wù)提供商的利益。

（7）深度強化學(xué)習(xí)算法求解車間生產(chǎn)調(diào)度問題。

深度強化學(xué)習(xí)將深度學(xué)習(xí)的感知能力和強化學(xué)習(xí)的決策能力結(jié)合起來，為解決復(fù)雜的決策問題提供了方法。在圍棋、機器人等領(lǐng)域的矚目成果顯示了其強大的學(xué)習(xí)能力與序貫決策能力。鑒于此，近年來涌現(xiàn)出了多個利用深度強化學(xué)習(xí)方法解決組合優(yōu)化問題的新方法，具有求解速度快、模型泛化能力強的優(yōu)勢，為組合優(yōu)化問題的求解提供了一種全新的思路［68］。較典型的深度強化學(xué)習(xí)技術(shù)框架有深度Q網(wǎng)絡(luò)（Deep Q-Network，DQN）［69］，其核心思想是利用深度神經(jīng)網(wǎng)絡(luò)計算動作值函數(shù)，使DQN具有穩(wěn)定的學(xué)習(xí)結(jié)構(gòu)。此外，在DQN網(wǎng)絡(luò)基礎(chǔ)上，還有一系列成功的應(yīng)用，如Prioritized Experience Replay［70］、Double DQN［71］和Dueling Network［72］等。

深度強化學(xué)習(xí)以通用的形式將深度學(xué)習(xí)的感知能力與強化學(xué)習(xí)的決策能力相結(jié)合，并通過端對端的學(xué)習(xí)方式實現(xiàn)從原始輸入到輸出的直接控制［73］。針對Q值在一定條件下容易震蕩和過估計的問題，Chen等［74］提出了一種基于價值函數(shù)逼近的深度強化學(xué)習(xí)集成網(wǎng)絡(luò)結(jié)構(gòu)，通過降低目標(biāo)方差來穩(wěn)定訓(xùn)練過程，從而提高訓(xùn)練效果。黎聲益等［75］提出了一種面向設(shè)備負(fù)荷穩(wěn)定的智能車間調(diào)度方法，通過一個含有深度神經(jīng)網(wǎng)絡(luò)調(diào)度模型的調(diào)度智能體，分析車間生產(chǎn)狀態(tài)與設(shè)備負(fù)荷間的相關(guān)性，及時輸出滿足期望目標(biāo)的調(diào)度方案。其所提出的方法在MiniFab半導(dǎo)體生產(chǎn)車間模型中進行了驗證，實驗驗證了其所提出的調(diào)度方法能實現(xiàn)對智能車間設(shè)備負(fù)荷的控制。Elfwing等［76］通過深度強化學(xué)習(xí)在雅達利2600游戲中獲得了人類水平的表現(xiàn)，且表明策略學(xué)習(xí)方法是取得成功的關(guān)鍵因素。Adamski等［77］對分布式深度強化學(xué)習(xí)進行了研究，提出了一種可擴展的深度強化學(xué)習(xí)算法，針對多產(chǎn)品單服務(wù)器調(diào)度問題構(gòu)建動態(tài)控制策略，以在制品庫存和缺貨懲罰成本等因素中優(yōu)化成本函數(shù)，得到了合理的動態(tài)調(diào)度策略。Hubbs等［78］在化工生產(chǎn)調(diào)度中，將深度強化學(xué)習(xí)用于在線動態(tài)調(diào)度，通過強化學(xué)習(xí)系統(tǒng)實現(xiàn)調(diào)度系統(tǒng)的實時優(yōu)化。Wang等［79］在動態(tài)資源調(diào)度中，通過深度強化學(xué)習(xí)實現(xiàn)了一種新的動態(tài)調(diào)度方案，以提高自動、高效的優(yōu)化和端到端服務(wù)的可靠性。Shahmardan等［80］基于深度強化學(xué)習(xí)框架研究了車輛調(diào)度問題，將問題構(gòu)建為一個混合整數(shù)規(guī)劃模型并加以解決。劉冠男等［81］針對救護車動態(tài)重定位調(diào)度問題，提出了一種基于強化學(xué)習(xí)的調(diào)度策略結(jié)構(gòu)，基于深度Q值網(wǎng)絡(luò)方法提出了一種考慮多種調(diào)度交互因子的算法RedCon-DQN，以在給定環(huán)境狀態(tài)下得到最優(yōu)的重定位調(diào)度策略，最后在模擬器中通過大規(guī)模數(shù)據(jù)實驗，驗證了模型得到的調(diào)度策略相比已有方法的優(yōu)越性，并分析了在不同時段下調(diào)度策略的有效性及其特點。Shi等［82］提出了一種基于深度強化學(xué)習(xí)的智能調(diào)度算法求解自動化生產(chǎn)線的調(diào)度問題。崔鵬浩等［83］針對機器劣化過程的多機流水線，基于馬爾可夫鏈構(gòu)建了流水線瞬態(tài)性能評估模型，綜合考慮在制品庫存成本、缺貨懲罰成本和預(yù)測性維護成本，以最小化系統(tǒng)總成本為目標(biāo)，基于馬爾可夫決策過程建立了流水線預(yù)測性維護決策優(yōu)化模型，利用深度強化學(xué)習(xí)算法對問題進行了近似求解，獲得了有效的流水線預(yù)測性維護策略。Cals等［84］提出了將深度強化學(xué)習(xí)方法用于決定如何確定訂單的處理順序，以最小化延遲訂單的數(shù)量，創(chuàng)建了一個深度強化學(xué)習(xí)解決方案，通過與環(huán)境交互學(xué)習(xí)策略，并通過一個近端策略優(yōu)化算法解決問題。結(jié)果表明，深度強化學(xué)習(xí)方法可以開發(fā)出良好的解決方案，并且在大多數(shù)測試案例中比所提出的啟發(fā)式算法性能更好。

2.啟發(fā)式調(diào)度規(guī)則研究現(xiàn)狀

研究啟發(fā)式調(diào)度規(guī)則對構(gòu)建調(diào)度算法具有重要意義，Baker等［85］較早進行了啟發(fā)式規(guī)則的相關(guān)研究，并分析了不同情況下調(diào)度規(guī)則對調(diào)度結(jié)果的影響。Gere［86］對調(diào)度規(guī)則、分配規(guī)則、優(yōu)先規(guī)則等進行了定義，明確了這些概念的區(qū)別與聯(lián)系。Ren等［87］對啟發(fā)式規(guī)則的內(nèi)涵和分類進行了系統(tǒng)的研究，從三個不同方面詳細(xì)分析了啟發(fā)式規(guī)則在生產(chǎn)調(diào)度問題中的應(yīng)用。王家廞［88］提出了一種新的啟發(fā)式調(diào)度規(guī)則，在以拖期時間為評價目標(biāo)的問題中，該規(guī)則優(yōu)于簡單的調(diào)度規(guī)則。針對敏捷制造調(diào)度環(huán)境的不確定性、動態(tài)性以及混合流水車間調(diào)度問題的特點，王芊博等［89］提出一種針對混合流水車間環(huán)境的插值排序算法。范華麗等［90］以最小化工件平均加權(quán)拖期為調(diào)度目標(biāo)，考慮了加工準(zhǔn)備時間的動態(tài)作業(yè)車間調(diào)度問題，用基于遺傳規(guī)劃的方法設(shè)計了用于問題求解的調(diào)度規(guī)則。王成龍等［91］針對復(fù)雜大規(guī)模動態(tài)調(diào)度問題提出基于調(diào)度規(guī)則的求解方法，實驗證明了算法的有效性。朱偉［92］、王芳等［93］針對柔性作業(yè)車間調(diào)度問題，將優(yōu)先級調(diào)度規(guī)則和其他算法結(jié)合，形成了針對柔性作業(yè)車間的調(diào)度規(guī)則組合。

綜合國內(nèi)外文獻可見，智能算法在求解車間生產(chǎn)調(diào)度問題中取得了豐碩的研究成果，在調(diào)度方案質(zhì)量和時間效率等方面有很大的優(yōu)越性。但同時也存在不足之處，比如為了降低求解難度，問題求解中過多的假設(shè)使得問題模型與實際的生產(chǎn)環(huán)境存在較大差異；數(shù)據(jù)之間的關(guān)鍵特征及其相互約束關(guān)系難以識別和提取，模型未能真正反映調(diào)度問題的真實特征。另外，不同智能算法蘊含了不同自然機理，所用知識差別較大，算法的應(yīng)用范圍較小，甚至在同類問題中由于問題規(guī)?；騾?shù)的不同，解的質(zhì)量也存在非常大的差異。由以上元啟發(fā)式方法對車間生產(chǎn)調(diào)度或其他類似問題的求解可見：所求解的問題需要建立有效的數(shù)學(xué)模型，而實際應(yīng)用中問題的約束因素非常多，只能根據(jù)經(jīng)驗選擇若干約束因素進行建模，實際上是對問題的一種理想化處理方式，如果考慮更多的約束因素，又會導(dǎo)致問題過于復(fù)雜而無法建立模型，這種簡化處理方式導(dǎo)致所得到的解決方案只能是問題的近優(yōu)方案；當(dāng)要處理的問題規(guī)模較大時，計算時間復(fù)雜度和空間復(fù)雜度呈指數(shù)級增長，有時甚至難以收斂；應(yīng)對動態(tài)因素的能力較差，在出現(xiàn)緊急插單、機器故障、客戶需求變更等動態(tài)因素時，對算法的設(shè)計改進方面工作量極大，同時處理結(jié)果難以滿足實際需求；對分布式調(diào)度問題處理能力較差，缺乏成熟的分布式調(diào)度問題的模式和思路，調(diào)度結(jié)果難以滿足需要。

因此，還需要結(jié)合實際應(yīng)用，深入挖掘相關(guān)領(lǐng)域知識，實現(xiàn)自動識別生產(chǎn)任務(wù)的數(shù)據(jù)特征關(guān)系，以達到自主學(xué)習(xí)和決策的目的。通過深度學(xué)習(xí)、強化學(xué)習(xí)和深度強化學(xué)習(xí)在生產(chǎn)調(diào)度中的成功應(yīng)用可以發(fā)現(xiàn)，深度神經(jīng)網(wǎng)絡(luò)具有強大的識別感知能力，通過學(xué)習(xí)工業(yè)數(shù)據(jù)，可以自動識別生產(chǎn)任務(wù)和調(diào)度方案之間的對應(yīng)關(guān)系，無須人為提取任務(wù)特征，使算法具備解決不同類型的生產(chǎn)調(diào)度問題的能力。同時，利用強化學(xué)習(xí)的決策能力，將生產(chǎn)任務(wù)作為特殊的序貫決策問題，結(jié)合深度學(xué)習(xí)的感知能力，可以進一步提高算法的性能，擴大應(yīng)用領(lǐng)域。

通過梳理分析強化學(xué)習(xí)或深度強化學(xué)習(xí)解決生產(chǎn)調(diào)度問題的成果可以發(fā)現(xiàn)，此類方法和元啟發(fā)式方法相比具有以下優(yōu)勢：強化學(xué)習(xí)通過智能體與環(huán)境進行交互學(xué)習(xí)得到最優(yōu)策略，減少了對組合優(yōu)化問題建模的依賴程度；強化學(xué)習(xí)方法采用值函數(shù)逼近或直接策略搜索的相關(guān)算法，可以有效應(yīng)對問題的高維度困境；強化學(xué)習(xí)在與環(huán)境交互中學(xué)習(xí)最優(yōu)策略，可以敏感捕捉到環(huán)境的動態(tài)因素，具有天然的應(yīng)對緊急插單、機器故障等動態(tài)隨機因素的能力；強化學(xué)習(xí)在與環(huán)境交互時可以在線生成并存儲樣本，因此在不確定環(huán)境下處理序列決策問題時對線下樣本的依賴程度較低；強化學(xué)習(xí)具備應(yīng)對復(fù)雜環(huán)境的泛化能力，具有更好的適應(yīng)性和通用性。

可見強化學(xué)習(xí)在處理序貫決策問題時具有明顯的優(yōu)勢，但同時也存在一些問題和困難：強化學(xué)習(xí)算法的數(shù)學(xué)理論基礎(chǔ)不完善，部分核心算法步驟缺乏嚴(yán)格的數(shù)學(xué)推理證明；強化學(xué)習(xí)序列決策中易出現(xiàn)不穩(wěn)定性、獎勵值的稀疏性、離散狀態(tài)的稀疏性、高維空間中動作的稀疏性，這些因素導(dǎo)致算法容易陷入局部最優(yōu)，甚至難以收斂；強化學(xué)習(xí)在求解車間生產(chǎn)調(diào)度問題時，算法框架中的狀態(tài)、獎勵值、動作等較難定義，缺少成熟的定義標(biāo)準(zhǔn)，過于依賴專家經(jīng)驗，不當(dāng)?shù)臓顟B(tài)、獎勵值、動作定義導(dǎo)致解的質(zhì)量不穩(wěn)定，甚至?xí)?dǎo)致問題求解失??；復(fù)雜的多智能體強化學(xué)習(xí)或分層強化學(xué)習(xí)在組合優(yōu)化領(lǐng)域的應(yīng)用還處于初步探索階段，現(xiàn)有成果較少。

通過對強化學(xué)習(xí)求解車間生產(chǎn)調(diào)度等組合優(yōu)化問題的優(yōu)點和存在問題的分析，立足幾種典型的車間生產(chǎn)調(diào)度問題，可采用深度強化學(xué)習(xí)和其他相關(guān)算法進行求解：提升馬爾可夫決策模型的精準(zhǔn)程度，使之更加符合車間生產(chǎn)調(diào)度問題的實際情況，具備更好的通用性；探索車間生產(chǎn)調(diào)度問題的強化學(xué)習(xí)算法動作、獎勵值、動作等要素的定義方式，降低主觀因素的不利影響；基于深度強化學(xué)習(xí)求解車間生產(chǎn)調(diào)度問題，以深度學(xué)習(xí)、強化學(xué)習(xí)和深度強化學(xué)習(xí)等新一代人工智能技術(shù)為主，但同時充分利用其他算法的優(yōu)點，通過成熟的元啟發(fā)式算法來提高深度強化學(xué)習(xí)等算法的有效性，彌補其不足；對多智能體強化學(xué)習(xí)在車間生產(chǎn)調(diào)度問題中的應(yīng)用展開初步探索，在馬爾可夫博弈框架下，研究分布式生產(chǎn)調(diào)度問題的多智能體強化學(xué)習(xí)解決方法，考慮智能體的回報函數(shù)彼此之間的相互關(guān)聯(lián)性，引入NASH均衡概念并將多智能體學(xué)習(xí)收斂到均衡點。