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