(19)國家知識產(chǎn)權(quán)局(12)發(fā)明專利地址310018浙江省杭州市下沙高教園區(qū)2張樺戴國駿(特殊普通合伙)33240一種基于D3QN和遺傳算法的作業(yè)車間分批21.一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征在于包括以下步驟：S1:根據(jù)生產(chǎn)車間機器數(shù)量、加工工件的種類以及每種工件的加工數(shù)量構(gòu)建作業(yè)車間分批調(diào)度問題的數(shù)學(xué)模型，調(diào)度的目標是使最大完工時間最?。籗2:作業(yè)車間分批調(diào)度問題的批量劃分方案由遺傳算法確定：基于實數(shù)序列的編碼形式將每個批次工件隨機拆分成若干個不同大小的子批進行組合，并以此生成初始種群；S3:將種群中的染色體進行交叉、變異操作，增加種群的多樣性；S4:對染色體進行解碼，得到工件的批量劃分方案；將工件批量劃分后的子批的工序排序問題用析取圖模型進行表示，基于該析取圖模型，建立馬爾科夫決策過程，設(shè)計過程的狀S5:利用圖神經(jīng)網(wǎng)絡(luò)對獲取析取圖節(jié)點特征信息進行表征學(xué)習(xí)，捕獲工序與工序之間的隱含關(guān)系，有效提取工序排序問題的特征狀態(tài)；S6:設(shè)計帶有優(yōu)先級經(jīng)驗回放的D3QN模型，并訓(xùn)練模型，為工件批量劃分后的子批的工序排序問題提供自適應(yīng)調(diào)度策略和完工時間，并將完工時間的倒數(shù)作為遺傳算法的適應(yīng)度函數(shù)值；S7:判斷遺傳算法的迭代是否滿足終止條件，若滿足，則輸出作業(yè)車間分批調(diào)度問題的最優(yōu)分批方案和調(diào)度策略，否則，采用輪盤賭方法選擇種群中的最優(yōu)個體進入下一代，執(zhí)行步驟S3。2.根據(jù)權(quán)利要求1所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征在于所述步驟S1中作業(yè)車間分批調(diào)度的數(shù)學(xué)模型建立過程如下：1-1.針對作業(yè)車間分批調(diào)度問題作如下描述：假設(shè)車間有n種工件需要在m臺機器上等待加工，每種工件可批量劃分為若干個子批，各子批的工件數(shù)量隨機分配，每種工件各子批包含k道工序，已知每道工序的加工機器和處理時間，調(diào)度的目標是合理對工件進行批量劃分和安排各子批工序的加工順序，使得最大完工時間最小；1-2.根據(jù)上述問題描述建立作業(yè)車間分批調(diào)度問題數(shù)學(xué)模型的符號定義：n:待加工工件的種類；j:工件i的工序號；k:工件i的子批批次號；B:工件i的總數(shù)量；Amax:工件最大的分批數(shù)量；P?:工件i的子批數(shù)量；Sik:工件i的第k批次的數(shù)量；PTim:工件i的第j道工序在機器m上加工的時間；STikjm:工件i的第k批次的第j道工序在機器m上加工的開始時間；ETikm:工件i的第k批次的第j道工序在機器m上加工的結(jié)束時間；Eikm:工件i的第k批次的最后一道工序在機器m上加工的結(jié)束時間；Xim:決策變量，若工件i的第j道工序在機器m上加工則為1,否則為0;C:工件i的完成時3式(1)表示模型優(yōu)化的目標是最小化完工時間；式(2)表示工件i所有子批的數(shù)量之和必須等于工件i的總數(shù)量；式(3)表示子批劃分的數(shù)量不能超過事先規(guī)定的最大劃分批次數(shù)量；式(4)表示工件i的第k批次的第j道工序在機器m上加工的完成時間等于加工開始時間示工件i的第j道工序只能在一臺機器上加工；式(7)表示最大完工時間等于所有工件完成3.根據(jù)權(quán)利要求2所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征在于所述步驟S3中的交叉是指隨機生成交叉位置r,1≤r≤n,然后對兩條父代染色體中編4.根據(jù)權(quán)利要求3所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征在于所述步驟S3中的變異是指隨機生成變異位置r,1≤r≤n,然后對編號為r的工件所對應(yīng)5.根據(jù)權(quán)利要求3或4所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法完工時間最??；6.根據(jù)權(quán)利要求5所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征47.根據(jù)權(quán)利要求5所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征度完成的時間步。8.根據(jù)權(quán)利要求7所述的一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法，其特征5式中δ;即TD-error,∈是一個很小的正數(shù)，防止抽樣概率接近0,用于保證所有樣本都有概率被抽樣到；當進行優(yōu)先級采樣時，不同的樣本被賦予了不同的概率，原先的期望分布也因此被改變，使用重要性采樣來消除這個偏差，重要性采用權(quán)重計算如下：將抽樣得到的數(shù)據(jù)輸入D3QN模型中，計算時間差分誤差TD-error,進而更新優(yōu)先回放經(jīng)驗機制中的優(yōu)先級；6-5.計算損失函數(shù)，通過隨機梯度下降法不斷更新D3QN網(wǎng)絡(luò)的權(quán)重參數(shù)，損失函數(shù)的計算方法如下：L=(r+rQ(s',argmaxaAQ(s',a;θ式中γ表示折扣因子；6-6.循環(huán)訓(xùn)練至累積獎勵收斂，得到最終工序排序問題的調(diào)度模型。6技術(shù)領(lǐng)域[0001]本發(fā)明屬于生產(chǎn)智能調(diào)度領(lǐng)域，提出了一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法。背景技術(shù)[0002]制造業(yè)是國民經(jīng)濟的支柱產(chǎn)業(yè)，也是國家綜合實力的體現(xiàn)。我國制造業(yè)逐漸向智能化、數(shù)字化進行轉(zhuǎn)型。車間調(diào)度是生產(chǎn)制造過程中的重要環(huán)節(jié)，如何實現(xiàn)高效率、智能化的調(diào)度系統(tǒng)，是提升企業(yè)競爭力的關(guān)鍵之一。作業(yè)車間調(diào)度問題是當前車間生產(chǎn)調(diào)度領(lǐng)域的重點研究方向。大多數(shù)關(guān)于作業(yè)車間調(diào)度問題的研究著眼于單個工件，而在實際生產(chǎn)中，為提高調(diào)度效率和降低成本，往往采用的是分批調(diào)度的模式。所以對作業(yè)車間分批調(diào)度問題的研究，對于提高企業(yè)生產(chǎn)效率、降低成本、收獲更多經(jīng)濟效益都有著重要的現(xiàn)實意義。[0003]作業(yè)車間分批調(diào)度問題需要解決批量劃分與工序排序兩個子問題，這極大提升了問題的復(fù)雜度以及解的搜索空間。近年來，國內(nèi)外學(xué)者針對作業(yè)車間分批調(diào)度問題的研究，大多采用遺傳算法進行求解?，F(xiàn)有技術(shù)存在以下不足：1、分批調(diào)度問題復(fù)雜且解空間巨大，遺傳算法難以在有限時間內(nèi)找到理想解；2、針對不同的分批方案，遺傳算法在求解子批工序排序問題時需重新迭代求解，泛化性較差。[0004]近年來深度強化學(xué)習(xí)在旅行商問題、路徑優(yōu)化問題等組合優(yōu)化領(lǐng)域上取得了較好的成果。因此，將深度強化學(xué)習(xí)應(yīng)用于調(diào)度問題是一個新穎的研究方向。目前尚未發(fā)現(xiàn)有利用深度強化學(xué)習(xí)求解作業(yè)車間分批調(diào)度問題的研究。D3QN(DuelingDoubleDQN,雙決斗DQN網(wǎng)絡(luò))算法是一種新型的深度強化學(xué)習(xí)算法，結(jié)合了DuelingDQN和DoubleDQN算法的解，以快速得到較優(yōu)的自適應(yīng)調(diào)度策略，從而優(yōu)化最大完工時間和大幅提升作業(yè)車間分批調(diào)度問題的求解速度。發(fā)明內(nèi)容[0005]針對現(xiàn)有技術(shù)中的缺陷，本發(fā)明提供一種基于D3QN和遺傳算法的作業(yè)車間分批調(diào)度方法。該方法采用分層迭代優(yōu)化策略，作業(yè)車間分批調(diào)度任務(wù)的分批方案由外層遺傳算法確定，基于外層批量劃分的結(jié)果，利用訓(xùn)練好的D3QN模型為內(nèi)層子批工序排序問題提供[0006]為了實現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案包括以下步驟：[0007]S1:根據(jù)生產(chǎn)車間機器數(shù)量、加工工件的種類以及每種工件的加工數(shù)量構(gòu)建作業(yè)車間分批調(diào)度問題的數(shù)學(xué)模型，調(diào)度的目標是使最大完工時間最小；[0008]S2:作業(yè)車間分批調(diào)度問題的批量劃分方案由遺傳算法確定：基于實數(shù)序列的編碼形式將每個批次工件隨機拆分成若干個不同大小的子批進行組合，并以此生成初始種7[0010]S4:對染色體進行解碼，得到工件的批量劃分方案；將工件批量劃分后的子批的工序排序問題用析取圖模型進行表示，基于該析取圖模型，建立馬爾科夫決策過程，設(shè)計過程[0011]S5:利用圖神經(jīng)網(wǎng)絡(luò)對獲取析取圖節(jié)點特征信息進行表征學(xué)習(xí)，捕獲工序與工序之間的隱含關(guān)系，有效提取工序排序問題的特征狀態(tài)；[0012]S6:設(shè)計帶有優(yōu)先級經(jīng)驗回放的D3QN模型，并訓(xùn)練模型，為工件批量劃分后的子批的工序排序問題提供自適應(yīng)調(diào)度策略和完工時間，并將完工時間的倒數(shù)作為遺傳算法的適應(yīng)度函數(shù)值；[0013]S7:判斷遺傳算法的迭代是否滿足終止條件，若滿足，則輸出作業(yè)車間分批調(diào)度問題的最優(yōu)分批方案和調(diào)度策略，否則，采用輪盤賭方法選擇種群中的最優(yōu)個體進入下一代，執(zhí)行步驟S3。[0014]所述步驟S1中作業(yè)車間分批調(diào)度的數(shù)學(xué)模型建立過程如下：[0015]1-1.針對作業(yè)車間分批調(diào)度問題作如下描述：假設(shè)車間有n種工件需要在m臺機器上等待加工，每種工件可批量劃分為若干個子批，各子批的工件數(shù)量隨機分配，每種工件各子批包含k道工序，已知每道工序的加工機器和處理時間，調(diào)度的目標是合理對工件進行批量劃分和安排各子批工序的加工順序，使得最大完工時間最小；[0016]1-2.根據(jù)上述問題描述建立作業(yè)車間分批調(diào)度問題數(shù)學(xué)模型的符號定義：n:待加工工件的種類；[0018]j:工件i的工序號；[0019]k:工件i的子批批次號；[0020]B:工件i的總數(shù)量；[0022]P?:工件i的子批數(shù)量；[0023]Sk:工件i的第[0025]PTi;3:工件i的第j道工序在機器m上加工的時間；[0026]STikjm:工件i的第k批次的第j道工序在機器m上加工的開始時間；[0027]ETikjm:工件i的第k批次的第j道工序在機器m上加工的結(jié)束時間；[0028]Eikm:工件i的第k批次的最后一道工序在機器m上加工的結(jié)束時間；[0029]Xijm:決策變量，若工件i的第j道工序在機器m上加工則為1,否則為0;C?:工件i的完成時間；[0030]Cmax:所有工件均完成的最大完工時間；[0031]1-3.根據(jù)上述定義，對作業(yè)車間分批調(diào)度問題可建立如下數(shù)學(xué)模型：8式(1)表示模型優(yōu)化的目標是最小化完工時間；式(2)表示工件i所有子批的數(shù)量次數(shù)量；式(4)表示工件i的第k批次的第j道工序在機器m上加工的完成時間等于加工開始量的乘積；式(5)表示同一工件必須在上一道工序加工結(jié)束之后才能加工下一道工序；式[0042]所述步驟S3中的交叉是指隨機生成一個整數(shù)r(1≤r≤n),然后對兩條父代染色體中編號為r的工件所對應(yīng)的染色體基因進行交[0043]步驟S3中的變異是指隨機生成一個整數(shù)r(1≤r≤n),然后對編號為r的工件所對應(yīng)的染色體基因隨機選擇兩個位置進行加1和減[0057]式子中U表示t時刻機器的利用率，其計算方式為：機器利用率=機器總工作時9[0060]式中h)表示目標節(jié)點v的第k代節(jié)點特征，h。表示連選擇動作a,系統(tǒng)給出獎勵r;[0064]6-3.將訓(xùn)練過程中獲得的當前狀態(tài)s、動作a、獎勵r以及下一個狀態(tài)s'以四元組[0067]式中a表示優(yōu)先級權(quán)重，α=0時表示均勻采樣，p;表示優(yōu)先級指標，其值與|T[0074]將抽樣得到的數(shù)據(jù)輸入D3QN模型中，計算時間差分誤差TD-error,進而更新優(yōu)先件的分批方案，利用訓(xùn)練完成的D3QN模型對子批附圖說明[0088]圖1是D3QN和遺傳算法解決作業(yè)車間分批調(diào)度問題的框架圖。本發(fā)明實施提供一k:工件i的子批批次號；B:工件i的總數(shù)量；Aax:工件最大的分批數(shù)量；P:工件i的子批數(shù)量；0.:工件i的第道工序，j=1,2,..STik;m:工件i的第k批次的第j道工序在機器m上加工的開始時間；ETik;m:工件i的第k批次的第j道工序在機器m上加工的結(jié)束時間；Eikm:工件i的第k批次的最后一道工序在機器m上加工的結(jié)束時間；X;m:決策變量，若工件i的第j道工序在機器m上加工則為1,否則為0;C:工件i的完成時間；C:所有工件均完成的最大完工時間；(3)根據(jù)上述符號定義，對作業(yè)車間分批調(diào)度問題可建立如下模型：minCmax=minmax{Cli=1,2,.約束條件：式(1)表示模型優(yōu)化的目標是最小化最大完工時間；式(2)表示工件i所有子批的數(shù)量之和必須等于工件i的總數(shù)量；式(3)表示子批劃分的數(shù)量不能超過事先規(guī)定的最大劃分批次數(shù)量；式(4)表示工件i的第k批次的第j道工序在機器m上加工的完成時間等于加工開始時間與該批次的工序加工時間之和，其中該批次的工序加工時間為工序加工時間與批次數(shù)量的乘積；式(5)表示同一工件必須在上一道工序加工結(jié)束之后才能加工下一道工序；式(6)表示工件i的第j道工序只能在一臺機器上加工；式(7)表示最大完工時間等于所有工件完成時間的最大值。[0119]S2、作業(yè)車間分批調(diào)度問題的批量劃分方案由遺傳算法確定，基于實數(shù)序列的編碼形式將每個批次工件隨機拆分成若干個不同大小的子批進行組合，并以此生成初始種[0120]S3、將種群中的染色體進行交叉、變異操作，增加種群的多樣性；對染色體進行解[0121]所述的交叉是指隨機生成一個整數(shù)r(1≤r≤n),然后對兩條父代染色體中編號為成的r=2,然后對兩條父代染色體q?、q?中編號為2的工件所對應(yīng)的染色體基因進行交換得[0122]所述的變異是指隨機生成一個整數(shù)r(1≤r≤n),然后對編號為r的工件所對應(yīng)的機生成的r=3,然后對染色體q中編號為3的工件所對應(yīng)的染色體基因選取1號位和2號位進[0129]式子中U表示t時刻機器的利用率，其計算方式為：機器利用率=機器總工作時擇動作a,系統(tǒng)給出獎勵r;本j被采樣的概率計算如下：[0143]式中δ即TD-error,∈是一個很小的正數(shù)，防止抽樣概率接近0,用于保證所有樣本都有概率被抽樣到；[0147]將抽樣得到的數(shù)據(jù)輸入D3QN模型中，計算時間差分誤差TD-error,進而更新優(yōu)先個，每個工件包含4道工序，已知每道工序?qū)?yīng)的加工機器及處理時間。[0154]表1作業(yè)車間調(diào)度問題實例(機器，時間)[0156]使用該方法的求解步驟如下：[0157]1)初始化遺傳算法參數(shù)：種群規(guī)模N=30,進化代數(shù)T=50,交叉概率p.=0.8,變異概率p=0.1,令當前迭代次數(shù)t=1;[0158]2)采用實數(shù)序列編碼并生成初始種群；[0160]3)解碼得到工件的批量劃分方案，基于批量劃分的結(jié)果，利用訓(xùn)練好的D3QN模型為子批工序排序提供自適應(yīng)調(diào)度策略和最大完工時間；[0161]4)將最大完工時間的倒數(shù)作為適應(yīng)度函數(shù)值，采取輪盤賭方法選擇N個最優(yōu)個體進入下一代種群；[0162]5)判斷t>=T,若成立，結(jié)束算法，輸出較優(yōu)分批方案和調(diào)度策略，否則跳轉(zhuǎn)到步驟3。[0163]用該方法求解得到的最大完工時間為322,每種工件的分批數(shù)量為：(1,2,3,4)、(1,1,1,7)、(1,2,3,4)、(2,2,3,3);使用遺傳算法求解得到最大完工時間為348;而不分批求解得到的最大完工時間為360,可知工件分批有利于提高生產(chǎn)效率。另外，在求解時間上，使用本發(fā)明提供的方法需用時