基于改進(jìn)分布估計(jì)算法的作業(yè)車間調(diào)度

戴 敏, 張玉偉, 曾 勵(lì), 竺志大, 張 帆

(揚(yáng)州大學(xué)機(jī)械工程學(xué)院, 江蘇 揚(yáng)州 225127)

由于先進(jìn)制造技術(shù)與物聯(lián)網(wǎng)、云計(jì)算、霧計(jì)算、大數(shù)據(jù)等信息技術(shù)的迅猛發(fā)展, 智能制造模式成為制造業(yè)的重要發(fā)展方向[1-2]．生產(chǎn)車間調(diào)度作為智能制造系統(tǒng)的重要環(huán)節(jié), 其調(diào)度效率是制造系統(tǒng)智能化水平的重要體現(xiàn),而作業(yè)車間調(diào)度(job-shop scheduling problem, JSP)是生產(chǎn)車間的一種代表性調(diào)度類型．JSP可描述為[3]: 假設(shè)存在n個(gè)任務(wù)組成的任務(wù)集T={T1,T2,…,Tn}和m臺(tái)機(jī)器組成的機(jī)器集M={M1,M2,…,Mm}, 每個(gè)任務(wù)Ti有Ni道工序, 所有工序按照規(guī)定的加工工藝路線在m臺(tái)機(jī)器上完成操作．調(diào)度目標(biāo)是確定每臺(tái)機(jī)器上工序的排列次序, 以實(shí)現(xiàn)生產(chǎn)指標(biāo)(完工時(shí)間、生產(chǎn)成本等)效率最優(yōu)化．同時(shí)生產(chǎn)調(diào)度過(guò)程滿足以下假設(shè): 1) 所有任務(wù)和機(jī)器在0時(shí)刻均可進(jìn)行操作; 2) 同一任務(wù)的工序間有先后約束關(guān)系; 3) 每臺(tái)機(jī)器在任意時(shí)刻只加工1道工序; 4) 工序不可中斷．JSP本質(zhì)上是NP完全問(wèn)題(non-deterministic polynomial hard, NP-Hard), 其求解方法分為精確算法和近似算法2類[4]．精確算法在求解小規(guī)模問(wèn)題上具有一定優(yōu)勢(shì), 但隨著問(wèn)題規(guī)模的擴(kuò)大,近似算法的求解優(yōu)勢(shì)較顯著．分布估計(jì)算法(estimation of distribution algorithm, EDA)作為近年興起的一種近似算法在車間調(diào)度問(wèn)題研究方面?zhèn)涫荜P(guān)注[5]．張守剛等[6]對(duì)硫化車間調(diào)度進(jìn)行研究,設(shè)計(jì)了一種離散的分布估計(jì)算法求解調(diào)度問(wèn)題;肖世昌等[7]提出一種混合分布估計(jì)算法對(duì)隨機(jī)工時(shí)的作業(yè)車間調(diào)度問(wèn)題進(jìn)行了研究．EDA是一種基于概率模型的廣度搜索算法, 但在深度優(yōu)化方面容易陷入局部最優(yōu)．模擬退火算法(simulated annealing,SA)自從1953年被提出以來(lái)就廣泛應(yīng)用于各個(gè)領(lǐng)域,Laarhoven等[8]首次使用SA求解JSP問(wèn)題;Akram等[9]通過(guò)快速模擬退火與淬火相結(jié)合的方法改進(jìn)SA算法,并通過(guò)JSP標(biāo)準(zhǔn)案例驗(yàn)證改進(jìn)算法的有效性．雖然SA算法深度搜索能力顯著,但是采用單點(diǎn)迭代搜索效率較低．

本文綜合EDA和SA的優(yōu)點(diǎn),提出一種改進(jìn)的分布估計(jì)算法(enhanced estimation of distribution algorithm, EEDA)求解作業(yè)車間調(diào)度問(wèn)題．首先,針對(duì)JSP設(shè)計(jì)基于概率模型的分布估計(jì)算法對(duì)問(wèn)題進(jìn)行廣度搜索,獲取優(yōu)良解集; 然后, 采用模擬退火算法對(duì)選擇優(yōu)良解進(jìn)行深度搜索;同時(shí),基于激素調(diào)節(jié)機(jī)制設(shè)計(jì)新的模擬退火函數(shù),進(jìn)一步加強(qiáng)算法搜索能力．

1 EEDA算法設(shè)計(jì)

EEDA算法的流程如圖1所示．首先, 設(shè)定算法的各種參數(shù)和終止條件,根據(jù)研究問(wèn)題的特點(diǎn)給出概率模型公式及其更新機(jī)制;其次,計(jì)算完工時(shí)間作為適應(yīng)度值,并對(duì)適應(yīng)度值進(jìn)行排序;然后,基于關(guān)鍵路徑的狀態(tài)生成函數(shù)形成新群體Sj, 并設(shè)初始迭代參數(shù)i=0;最后,基于模擬退火準(zhǔn)則并設(shè)計(jì)新的退火函數(shù)來(lái)判斷個(gè)體優(yōu)劣,從而保留更多優(yōu)秀個(gè)體,并計(jì)算適應(yīng)度值來(lái)尋求最優(yōu)解．

1.1 基于關(guān)鍵路徑的狀態(tài)生成函數(shù)設(shè)計(jì)

狀態(tài)生成函數(shù)的設(shè)計(jì)首先要確保SA產(chǎn)生的候選解盡可能遍布全部解空間,本文采用基于關(guān)鍵路徑的領(lǐng)域結(jié)構(gòu)設(shè)計(jì)狀態(tài)生成函數(shù): 設(shè)A,B是兩個(gè)可行解, 若B是通過(guò)移動(dòng)A的某關(guān)鍵塊中除首尾工序外的任一道工序至該關(guān)鍵塊工序之前或之后得到的可行解, 則B是A的鄰域,由此獲得的鄰域較小．

1.2 概率模型構(gòu)建及更新機(jī)制

1.3 基于模擬退火函數(shù)設(shè)計(jì)

在模擬退火溫度更新操作中,一般采用函數(shù)Tk+1=λTk(0<λ<1)來(lái)控制溫度的退火速度, 式中Tk+1表示當(dāng)前退火溫度,Tk表示上一次退火溫度．采用這種方法, 溫度下降速度完全取決于λ值的選取, 實(shí)際過(guò)程中動(dòng)態(tài)選值難度較大,且低溫階段難以獲取更多優(yōu)秀個(gè)體．在人體血糖調(diào)節(jié)行為中,激素調(diào)節(jié)規(guī)律函數(shù)具有較好的收斂性, 使胰島素與胰高血糖素能快速達(dá)到動(dòng)態(tài)平衡,保持人體的正常血糖水平．受此啟發(fā), 本文根據(jù)激素調(diào)節(jié)規(guī)律(即Hill函數(shù)分布規(guī)律)[10], 提出新的退火函數(shù)調(diào)控SA的溫度更新, 其表達(dá)式為Tk+1=ε/(1+kn)-kΔTexp(-k), 式中常量系數(shù)ε一般取初始溫度值,k為迭代次數(shù),n為Hill函數(shù)系數(shù), ΔT為當(dāng)前溫度與上一次溫度的差值．

2 數(shù)值試驗(yàn)與結(jié)果分析

2.1 參數(shù)敏感性分析

在EEDA算法設(shè)計(jì)中參數(shù)設(shè)置直接影響算法性能, 重要參數(shù)包括種群大小NIND、最大迭代次數(shù)max、學(xué)習(xí)率α和Hill系數(shù)n．本文以10個(gè)任務(wù)在10臺(tái)機(jī)器上進(jìn)行加工, 每個(gè)任務(wù)包括10道工序的隨機(jī)事件為例進(jìn)行測(cè)試, 表1給出了不同的參數(shù)設(shè)置對(duì)平均完工時(shí)間的影響．由表1可知, 增大NIND, max和α均會(huì)縮短平均完工時(shí)間．值得注意的是無(wú)限增大上述任一參數(shù)值, 均會(huì)犧牲算法的運(yùn)行時(shí)間, 因此應(yīng)合理選擇參數(shù), 本文取NIND=20, max=2 000,α=0.5．此外, 由表1中可見當(dāng)n=2時(shí)能求解平均完工時(shí)間的最優(yōu)值或近似最優(yōu)值．

表1 算法的不同參數(shù)設(shè)置對(duì)平均完工時(shí)間的影響

2.2 性能分析

為了驗(yàn)證EEDA算法性能的有效性, 本文對(duì)2類基準(zhǔn)事件進(jìn)行測(cè)試: Fisher和Thompson設(shè)計(jì)的事件FT06,FT10,FT20; Lawrence設(shè)計(jì)的事件LA01～LA40．EEDA算法與其他文獻(xiàn)中的EDA算法、SA算法、分布差分進(jìn)化算法(EDA-DE)、遺傳退火算法(GA-SA)、 基于優(yōu)先級(jí)規(guī)則的遺傳算法(P-GA)、 種群規(guī)模分別為40和60的基于移動(dòng)瓶頸的遺傳算法(SBGA-40/60)、 種群初始化類型分別為參數(shù)化、無(wú)延遲和主動(dòng)初始種群的混合遺傳算法(HGA-Param/HGA-Non-delay/HGA-Active)的比較結(jié)果如表2所示．表2顯示在43個(gè)測(cè)試事件中通過(guò)EEDA算法能獲得30個(gè)事件的最優(yōu)解,求解質(zhì)量明顯高于SA、EDA算法．與文獻(xiàn)中的相關(guān)算法相比,EEDA在求解基準(zhǔn)問(wèn)題上更具優(yōu)勢(shì)．

表2 不同算法的試驗(yàn)結(jié)果

表3 EEDA和其他算法相比較的試驗(yàn)結(jié)果