陳 亮，閻春平，陳建霖，侯躍輝

(重慶大學(xué) 機(jī)械與運(yùn)載工程學(xué)院，重慶 400044)

在企業(yè)的實(shí)際管理中，生產(chǎn)計(jì)劃的制訂是企業(yè)實(shí)現(xiàn)生產(chǎn)資源合理分配的重要步驟，生產(chǎn)調(diào)度是保證完成生產(chǎn)計(jì)劃的重要環(huán)節(jié)，車(chē)間調(diào)度問(wèn)題是企業(yè)生產(chǎn)過(guò)程必須考慮的重要問(wèn)題。隨著市場(chǎng)需求不斷變化，為了提高自身的競(jìng)爭(zhēng)力，企業(yè)必須能夠快速適應(yīng)市場(chǎng)的變化，提高自身的柔性制造能力，因此產(chǎn)生了柔性制造系統(tǒng)[1]?；诖吮尘暗娜嵝宰鳂I(yè)車(chē)間調(diào)度問(wèn)題被提出，成為了研究熱點(diǎn)[2]。而在柔性作業(yè)車(chē)間調(diào)度過(guò)程中，常常受到不確定事件的干擾，比如設(shè)備故障、緊急訂單插入等，需要經(jīng)常性地調(diào)整原調(diào)度計(jì)劃，造成調(diào)度不穩(wěn)定。所以筆者將結(jié)合以上內(nèi)容研究柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題(dynamic flexible job shop scheduling problem，DFJSP)。

1 柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度優(yōu)化模型

1.1 問(wèn)題描述

現(xiàn)有待加工工件集J={J1,J2,…,JN}和加工設(shè)備集A={A1,A2,…,AM}，每個(gè)工件Ji包含Oi道工序，根據(jù)柔性作業(yè)調(diào)度的要求，每道工序可有一臺(tái)或多臺(tái)設(shè)備供選擇。根據(jù)工件的工藝路徑和各自工序的可選加工設(shè)備集合，將各道工序分配給滿(mǎn)足加工條件的設(shè)備。同時(shí)，在滿(mǎn)足工藝約束和符合設(shè)備加工條件的前提下，對(duì)各個(gè)加工設(shè)備上分配到的工序集進(jìn)行排序。

對(duì)DFJSP問(wèn)題，需要考慮動(dòng)態(tài)不確定因素的影響，比如機(jī)器故障或阻塞、不合格工件重返工、訂單變化等隨機(jī)性事件。同時(shí)，為了提高動(dòng)態(tài)調(diào)度的穩(wěn)定性，提高模型的預(yù)見(jiàn)性和整體性，還需要進(jìn)行周期性重調(diào)度?；谏鲜鰡?wèn)題，考慮機(jī)器故障、到達(dá)時(shí)間不確定、緊急訂單插入3種不確定事件對(duì)調(diào)度模型的影響，在周期性重調(diào)度的環(huán)境下，合理地進(jìn)行設(shè)備分配和工序作業(yè)分配，使延期懲罰、能耗、偏差度3項(xiàng)指標(biāo)達(dá)到最優(yōu)。

基于以下假設(shè)構(gòu)建模型：

假設(shè)1 同一工件的工序之間有順序要求，不同工件之間沒(méi)有順序要求；

假設(shè)2 在開(kāi)始加工時(shí)，所有加工設(shè)備資源均可使用，所有工件均可被加工；

假設(shè)3 一道工序只能選擇一臺(tái)設(shè)備，一臺(tái)設(shè)備在任一時(shí)刻只能加工一道工序；

假設(shè)4 加工設(shè)備在加工過(guò)程中不會(huì)故障，不考慮工序加工中斷的情況；

假設(shè)5 系統(tǒng)內(nèi)所有設(shè)施緩沖區(qū)無(wú)限，忽略運(yùn)輸時(shí)間、準(zhǔn)備時(shí)間等；

假設(shè)6 工件的加工路線(xiàn)不變，所有工件的優(yōu)先級(jí)一致。

本模型中使用的參數(shù)和指標(biāo)如下：

N表示工件總數(shù)；

i表示工件索引號(hào)，i∈{1,2,…,N}；

Oi表示工件i的最大工序數(shù)；

j為工序索引號(hào)，j∈{1,2,…,Oi}；

M表示可用加工設(shè)備數(shù)；

m表示加工設(shè)備索引號(hào)，m∈{1,2,…,M}；

u表示一臺(tái)設(shè)備上工序的加工順序索引號(hào)；

Qm表示加工設(shè)備m上安排生產(chǎn)的工序總數(shù)；

Di表示工件i的交貨期；

Gm(u)表示在生產(chǎn)設(shè)備m上按順序開(kāi)始加工工序u的起始時(shí)間;

Bi,j表示工件i的工序j的開(kāi)始加工時(shí)間;

Cmax表示整個(gè)調(diào)度過(guò)程的最大完工時(shí)間；

Ci,j表示工件i的工序j的完工結(jié)束時(shí)間；

Ec表示加工總能耗；

Ec(i,j,m)表示工件i的工序j在設(shè)備m上的所產(chǎn)生的能耗；

Ek表示空載總能耗；

Xa為衡量機(jī)器在調(diào)度開(kāi)始后發(fā)生故障時(shí)刻的隨機(jī)變量；

Xr為衡量機(jī)器維修時(shí)間的隨機(jī)變量；

Xg為衡量工件到達(dá)時(shí)間的隨機(jī)變量；

Xe為衡量緊急訂單到來(lái)時(shí)刻的隨機(jī)變量。

1.2 優(yōu)化目標(biāo)

為保證模型的有效性，以最小化平均延期懲罰FEDP、最小化能耗Ep為優(yōu)化目標(biāo)。同時(shí)，為了兼顧動(dòng)態(tài)調(diào)度過(guò)程中對(duì)穩(wěn)定性的要求，需要評(píng)定動(dòng)態(tài)調(diào)度中調(diào)度計(jì)劃調(diào)整的程度，即相對(duì)于原始調(diào)度計(jì)劃的偏離程度，故以最小化偏差度FDV作為第3個(gè)優(yōu)化目標(biāo)，并以此建立優(yōu)化模型:

min(FEDP,Ep,FDV)。

(1)

1.2.1 平均延期懲罰

基于均衡生產(chǎn)理念，將調(diào)度目標(biāo)確定為最小化平均延期懲罰FEDP:

(2)

(3)

(4)

(5)

1.2.2 能耗

柔性作業(yè)車(chē)間的能耗主要體現(xiàn)為生產(chǎn)能耗和輔助環(huán)節(jié)能耗。生產(chǎn)能耗主要是指與加工環(huán)節(jié)直接相關(guān)的能源消耗，包括加工能耗、換刀能耗、換夾具能耗、機(jī)床空載等待能耗等。輔助環(huán)節(jié)能耗主要是在輔助生產(chǎn)的過(guò)程中產(chǎn)生的能源消耗，比如切削液的能耗、工件運(yùn)輸能耗等。由于部分能耗對(duì)調(diào)度結(jié)果的影響不大，且實(shí)際測(cè)量復(fù)雜，故根據(jù)問(wèn)題的描述簡(jiǎn)化對(duì)能耗的定義，只考慮因加工順序不同和分配方式的差異而變化較大的能耗，包括加工能耗和設(shè)備空載能耗。

加工能耗包括整個(gè)調(diào)度流程中所產(chǎn)生的切削能耗、空切能耗、換刀能耗和裝夾能耗等。所以，實(shí)際生產(chǎn)中的加工能耗為：

(6)

用對(duì)所有設(shè)備的上下道工序之間的時(shí)間間隔的累積表示設(shè)備的等待能耗：

(7)

故總能耗為：

Ep=Ec+Ek。

(8)

1.2.3 偏差度

偏差度是衡量在重調(diào)度時(shí)刻，舊調(diào)度計(jì)劃中待加工工序的開(kāi)始時(shí)間與新調(diào)度計(jì)劃中待加工工序的開(kāi)始時(shí)間的差值。

(9)

1.3 約束條件

Bi,j+1Ci,j，j∈{1,2,…,Oi-1};

(10)

(11)

(12)

(13)

(14)

Bi,j≥0，Gm(u)≥0；

(15)

(16)

Xa～G(αa,βa)，Xr～G(αr,βr)，Xg～G(αg,βg)，Xe～G(αe,βe)。

(17)

式中：αa和βa為發(fā)生故障時(shí)刻的伽馬分布的參數(shù)，G(αa,βa)為發(fā)生故障時(shí)刻的伽馬分布；αr和βr為機(jī)器維修時(shí)間的伽馬分布的參數(shù)，G(αr,βr)為機(jī)器維修時(shí)間的伽馬分布；αg和βg為工件到達(dá)時(shí)間的伽馬分布的參數(shù)，G(αg,βg)為工件到達(dá)時(shí)間的伽馬分布；αe和βe為緊急訂單到來(lái)時(shí)刻的伽馬分布的參數(shù)，G(αe,βe)為緊急訂單到來(lái)時(shí)刻的伽馬分布。

式(10)表示同一工件內(nèi)的工序滿(mǎn)足工藝路線(xiàn)約束；式(11)表示一道工序只能選擇一臺(tái)設(shè)備加工；式(12)表示加工設(shè)備約束，一臺(tái)設(shè)備在任一時(shí)刻只能加工一道工序；式(13)表示設(shè)備m上加工的工序總數(shù)約束；式(14)為工件的交貨期約束；式(15)表示對(duì)決策變量在數(shù)值上的約束；式(16)表示在調(diào)度時(shí)刻正在機(jī)器上加工的工序?qū)⒉皇苡绊懀^續(xù)完成原來(lái)的加工；式(17)表示動(dòng)態(tài)事件的隨機(jī)變量均服從伽馬分布。

1.4 動(dòng)態(tài)調(diào)度響應(yīng)策略

采用基于DQN和QGA的動(dòng)態(tài)調(diào)度響應(yīng)策略。該策略結(jié)合了動(dòng)態(tài)事件重調(diào)度和周期性重調(diào)度，是一種完全反應(yīng)式調(diào)度策略，在動(dòng)態(tài)事件和周期性重調(diào)度的觸發(fā)下，基于當(dāng)前系統(tǒng)的狀態(tài)，動(dòng)態(tài)地根據(jù)基于DQN和QGA的調(diào)度算法進(jìn)行重調(diào)度，制定新的調(diào)度計(jì)劃，以適應(yīng)車(chē)間制造環(huán)境的動(dòng)態(tài)變化。

為了準(zhǔn)確地描述當(dāng)前系統(tǒng)狀態(tài)，將工序分為以下5類(lèi)：已完工工序、正在加工工序、已調(diào)度但待加工工序、不可調(diào)度工序、待調(diào)度工序。已完工工序是指在重調(diào)度時(shí)刻已經(jīng)完成加工的工序，正在加工工序指在重調(diào)度時(shí)刻正在加工的工序，已調(diào)度但待加工工序指上一個(gè)調(diào)度周期內(nèi)已經(jīng)分配但等待加工的工序，不可調(diào)度工序指上一個(gè)調(diào)度周期和本調(diào)度周期內(nèi)，按照工藝流程下一步不可進(jìn)行加工的工序，待調(diào)度工序指上一調(diào)度周期內(nèi)不可調(diào)度但當(dāng)前調(diào)度周期內(nèi)可調(diào)度的工序。重調(diào)度需要解決的是在當(dāng)前重調(diào)度周期內(nèi)需要匯總可調(diào)用工序，包括已調(diào)度但待加工工序和待調(diào)度工序，并對(duì)其進(jìn)行調(diào)度和安排加工。

在重調(diào)度時(shí)刻對(duì)系統(tǒng)的狀態(tài)進(jìn)行描述，選擇耦合性低、對(duì)目標(biāo)影響大的屬性，主要有與時(shí)間有關(guān)的屬性和與能耗有關(guān)的屬性。與時(shí)間有關(guān)的屬性包括工序加工時(shí)間TP、工件剩余工序數(shù)NR、各工件剩余加工時(shí)間TR、工序到達(dá)時(shí)間TA、設(shè)備的可用時(shí)間Tm、交貨期D、工件的權(quán)重ω。與能耗有關(guān)的屬性包括工序的加工能耗EP、工件的剩余加工能耗ER。

2 基于QGA和DQN的動(dòng)態(tài)調(diào)度算法

2.1 量子遺傳算法

量子遺傳算法是一種將具有概率性的量子計(jì)算與GA算法融合在一起的算法[14]。該算法在一般的編碼過(guò)程中添加了對(duì)基因的量子矢量表達(dá)，一位基因可由兩位量子比特表示，并利用量子旋轉(zhuǎn)門(mén)對(duì)量子比特的相位旋轉(zhuǎn)實(shí)現(xiàn)染色體進(jìn)化，與一般的遺傳算法相比有更好的收斂和多樣性。

種群個(gè)體的染色體采用基于量子比特形式的編碼解碼方式，即傳統(tǒng)算法中表達(dá)信息的一位基因用兩位基因來(lái)表達(dá)，該段信息數(shù)據(jù)處于“0”態(tài)和“1”態(tài)的疊加態(tài)中，根據(jù)概率具體選擇處于某種量子態(tài)中的基因。這賦予QGA算法更好的多樣性特征。量子比特在物理意義上表示同時(shí)處在兩個(gè)量子態(tài)的疊加態(tài)，如式(18)所示：

|φ〉=α|0〉β|1〉。

(18)

式中：0〉和1〉分別對(duì)應(yīng)量子計(jì)算中的“0”態(tài)和“1”態(tài)；(α,β)表示處于“0”態(tài)和“1”態(tài)的概率幅，也就是以多大的概率取到0或1。該參數(shù)滿(mǎn)足如下條件：

|α|2+|β|2=1。

(19)

量子遺傳算法的收斂通過(guò)量子旋轉(zhuǎn)門(mén)更新來(lái)實(shí)現(xiàn)，一個(gè)量子比特b經(jīng)過(guò)量子門(mén)的相位調(diào)整后，會(huì)逐漸向某一狀態(tài)傾斜，最終收斂于局部最優(yōu)解。量子旋轉(zhuǎn)門(mén)的表達(dá)式如下：

(20)

量子比特的相位上的調(diào)整如下：

(21)

量子旋轉(zhuǎn)門(mén)的原理是通過(guò)比較當(dāng)前個(gè)體和最優(yōu)個(gè)體的適應(yīng)度，選擇合適的旋轉(zhuǎn)角大小和方向使相應(yīng)的基因向適應(yīng)度更高的方向演化，從而收斂于局部最優(yōu)解。

表1 旋轉(zhuǎn)角調(diào)整策略

2.2 深度Q學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)算法

深度Q學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)算法是一種結(jié)合強(qiáng)化學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)的算法。該算法定義了一種智能體，該智能體能夠?qū)?fù)雜的環(huán)境做出響應(yīng)，依據(jù)策略執(zhí)行動(dòng)作，并得到在該環(huán)境下的反饋，利用該反饋進(jìn)行不斷學(xué)習(xí)，訓(xùn)練能夠?qū)?dòng)態(tài)環(huán)境做出最優(yōu)響應(yīng)的神經(jīng)網(wǎng)絡(luò)模型，從而提升對(duì)環(huán)境的適應(yīng)能力。

該算法主要包括以下3個(gè)要素：環(huán)境的狀態(tài)S、智能體的動(dòng)作A、環(huán)境對(duì)智能體的獎(jiǎng)勵(lì)R。本研究的環(huán)境狀態(tài)包括時(shí)間和能耗有關(guān)的屬性，時(shí)刻t的環(huán)境狀態(tài)St描述為：

St={Tp,NR,TR,TA,Tm,D,ω,EP,ER}。

(22)

當(dāng)智能體執(zhí)行動(dòng)作后，狀態(tài)由St變化到St+1，設(shè)定狀態(tài)變化的一步為最早的一個(gè)或一批工件加工完成，此時(shí)會(huì)進(jìn)入下一個(gè)狀態(tài)。

在t時(shí)刻，動(dòng)態(tài)調(diào)度系統(tǒng)所執(zhí)行的動(dòng)作At是下一步加工的工序集，動(dòng)作At是由動(dòng)作選擇策略產(chǎn)生的。該策略根據(jù)對(duì)環(huán)境的觀察，根據(jù)概率ε選擇獲得價(jià)值最大的動(dòng)作。

獎(jiǎng)勵(lì)函數(shù)R的選取要考慮整個(gè)調(diào)度系統(tǒng)的優(yōu)化目標(biāo)，同時(shí)確保強(qiáng)化學(xué)習(xí)模型能夠向著獎(jiǎng)勵(lì)最大化的方向擬合，本研究中對(duì)各個(gè)調(diào)度目標(biāo)采取加權(quán)方式求和，并將求解目標(biāo)的最小化轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)中的獎(jiǎng)勵(lì)最大化，獎(jiǎng)勵(lì)函數(shù)如下：

(23)

式中：η表示縮放因子，用以控制對(duì)獎(jiǎng)勵(lì)值的調(diào)整；α1、α2、α3分別表示對(duì)平均延期懲罰、能耗、偏差率的權(quán)值。

Le(θg)=Es,a～ρ(·)[(ye-Q(s,a;θg))2]，e=1,2,…,NA,g=1,2,…,MN。

(24)

式中：s表示當(dāng)前的環(huán)境狀態(tài);a表示采取的具體行動(dòng);e表示算法的迭代序號(hào);g表示神經(jīng)網(wǎng)絡(luò)的參數(shù)序號(hào);NA表示算法的迭代次數(shù);MN表示神經(jīng)網(wǎng)絡(luò)的參數(shù)個(gè)數(shù);ye是當(dāng)前環(huán)境下采取行動(dòng)得到的現(xiàn)實(shí)值，即訓(xùn)練數(shù)據(jù)的輸出值;θg表示神經(jīng)網(wǎng)絡(luò)模型的第g號(hào)參數(shù);Q(s,a;θg)是根據(jù)當(dāng)前評(píng)估神經(jīng)網(wǎng)絡(luò)求出的估計(jì)值；Es,a～ρ(·)表示神經(jīng)網(wǎng)絡(luò)估計(jì)值和現(xiàn)實(shí)值的誤差累積。

DQN算法關(guān)鍵的一步是對(duì)ye求解，ye是根據(jù)現(xiàn)實(shí)神經(jīng)網(wǎng)絡(luò)求出的現(xiàn)實(shí)值，現(xiàn)實(shí)神經(jīng)網(wǎng)絡(luò)是上一個(gè)迭代周期內(nèi)的評(píng)估神經(jīng)網(wǎng)絡(luò)。在算法中采用兩個(gè)神經(jīng)網(wǎng)絡(luò)的目的是減少算法的不穩(wěn)定性。ye的求解公式如下：

(25)

2.3 基于QGA和DQN的調(diào)度算法整體框架

本研究中改進(jìn)了一般的QGA算法，利用DQN算法學(xué)習(xí)出的Q價(jià)值神經(jīng)網(wǎng)絡(luò)模型作為調(diào)度模型的適應(yīng)度函數(shù)，提高了算法對(duì)動(dòng)態(tài)環(huán)境的學(xué)習(xí)性和適應(yīng)性，融合了動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角策略，增強(qiáng)了其收斂能力，并結(jié)合混沌搜索方法均勻遍歷解空間。算法流程見(jiàn)圖1,算法具體步驟如下。

步驟1 設(shè)定個(gè)體總數(shù)popsize、單個(gè)個(gè)體的基因總數(shù)w、變異概率Pv、交叉概率Pc、種群進(jìn)化代數(shù)MaxGen、重調(diào)度周期TL、動(dòng)態(tài)事件的概率參數(shù)、最大學(xué)習(xí)調(diào)度次數(shù)MaxL、學(xué)習(xí)周期GapL、更新周期GapUp等參數(shù)。

步驟2 初始化用來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的經(jīng)驗(yàn)池，初始化Q評(píng)估神經(jīng)網(wǎng)絡(luò)模型(Q-evaluation)和Q現(xiàn)實(shí)神經(jīng)網(wǎng)絡(luò)模型(Q-target)，初始化學(xué)習(xí)調(diào)度次數(shù)TLS為1，學(xué)習(xí)步數(shù)step為1。

步驟3 在初始調(diào)度時(shí)刻，對(duì)已到達(dá)工件進(jìn)行調(diào)度，記錄當(dāng)前初始系統(tǒng)狀態(tài)S0。

步驟4 按照均勻規(guī)則初始化種群G0，生成popsize條概率幅一致的染色體。

步驟5 對(duì)染色體解碼，得到下一步加工的工序集，記錄當(dāng)前系統(tǒng)狀態(tài)S，通過(guò)Q-evaluation價(jià)值函數(shù)得到適應(yīng)度，并以此來(lái)更新量子旋轉(zhuǎn)門(mén)，生成子代種群Gc。

步驟6 將父代Gp與子代Gc種群合并成種群Gh，并對(duì)其解碼，通過(guò)Q-evaluation價(jià)值函數(shù)測(cè)量出種群的適應(yīng)度。

步驟 7 按照適應(yīng)度大小挑選出下一代種群。

步驟8 對(duì)挑選出的種群以設(shè)定的概率執(zhí)行交叉操作，并根據(jù)一定規(guī)則取部分個(gè)體變異，生成種群Gb。

步驟9 采取精英保留策略，選擇Gh中適應(yīng)度高的個(gè)體與種群Gb合并，生成下一代種群G。

步驟10 返回步驟4循環(huán)，直到達(dá)到最大種群進(jìn)化次數(shù)。

步驟11 解碼種群中適應(yīng)度最高的染色體，得到下一步的加工工序集A，記錄當(dāng)前系統(tǒng)狀態(tài)S，計(jì)算出獎(jiǎng)勵(lì)值R，并由執(zhí)行動(dòng)作推導(dǎo)出下一個(gè)系統(tǒng)狀態(tài)S′，將{A,S,R,S′ }記錄到經(jīng)驗(yàn)池中，并更新step。

步驟12 通過(guò)step判斷是否達(dá)到一個(gè)Q-target更新周期，達(dá)到即用Q-evaluation神經(jīng)網(wǎng)絡(luò)更新Q-target神經(jīng)網(wǎng)絡(luò)，未達(dá)到則繼續(xù)下一步。

步驟13 通過(guò)step判斷是否達(dá)到一個(gè)學(xué)習(xí)周期，如果達(dá)到即開(kāi)始進(jìn)行Q-evaluation神經(jīng)網(wǎng)絡(luò)訓(xùn)練，隨機(jī)抽取經(jīng)驗(yàn)池中的一批數(shù)據(jù)作為網(wǎng)絡(luò)模型的輸入數(shù)據(jù)，對(duì)應(yīng)的輸出數(shù)據(jù)根據(jù)公式計(jì)算得出，以此來(lái)訓(xùn)練Q-evaluation神經(jīng)網(wǎng)絡(luò)，未達(dá)到則繼續(xù)下一步。

步驟14 判斷一次調(diào)度是否完成，未完成則返回步驟4，完成則更新學(xué)習(xí)調(diào)度次數(shù)TLS。

步驟15 判斷學(xué)習(xí)調(diào)度次數(shù)TLS是否達(dá)到最大學(xué)習(xí)調(diào)度次數(shù)MaxL，未達(dá)到則返回步驟3，達(dá)到則表明強(qiáng)化學(xué)習(xí)過(guò)程結(jié)束，適應(yīng)度函數(shù)模型學(xué)習(xí)完成。

步驟16 根據(jù)適應(yīng)度函數(shù)模型求解最優(yōu)解，執(zhí)行步驟4～9。

步驟17 對(duì)種群進(jìn)行混沌搜索，如果找到一個(gè)非支配解，則將該非支配解對(duì)應(yīng)的個(gè)體代替種群中前端序值低的個(gè)體。

步驟18 返回步驟16循環(huán)，直到達(dá)到最大迭代次數(shù)，此時(shí)求出最優(yōu)解。

2.4 算法具體設(shè)計(jì)

2.4.1 初始化

2.4.2 多層編碼方案

由柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度的問(wèn)題特性可知其編碼由兩部分組成，分別是工序排序向量(operation sequence vector，OV)和加工設(shè)備選擇向量 (machine assignment vector，MV)。

w=LP×H+LA×H，

(26)

式中H為所有工件的工序總數(shù)。

接下來(lái)需要對(duì)二進(jìn)制染色體進(jìn)行解碼。由于量子比特是通過(guò)概率幅對(duì)解的一種線(xiàn)性疊加態(tài)，首先將二進(jìn)制染色體轉(zhuǎn)換為十進(jìn)制染色體，再根據(jù)各自的解碼策略，將十進(jìn)制染色體轉(zhuǎn)換為最終解。針對(duì)種群某一個(gè)體的染色體的解碼方案如下。

1)對(duì)于w位的初始解Q，根據(jù)概率幅將雙行的初始解轉(zhuǎn)換為單行的二進(jìn)制代碼Q。設(shè)Q(t)為第t位的量子比特，系統(tǒng)產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)r，若|αt|2>r2，則令B(t)=1，否則令其為0 。由此得到w位的二進(jìn)制解B=(b1,b2,…,bt,…,bw)；

(27)

2)根據(jù)上面的編碼策略，按照OV和MV分別進(jìn)行十進(jìn)制解碼。對(duì)于OV，將每LP位的二進(jìn)制串解碼成十進(jìn)制串，由此得到長(zhǎng)度為H的十進(jìn)制串DP；對(duì)于MV，將每LA/M位的二進(jìn)制串轉(zhuǎn)換為十進(jìn)制串，由此得到長(zhǎng)度為M×H的十進(jìn)制串DA。最終得到的十進(jìn)制染色體DR如下：

DR=[DP|DA]。

(28)

3)對(duì)于十進(jìn)制染色體DR，同樣按照兩部分分別處理。

對(duì)于OV，將DP中的數(shù)按從小到大標(biāo)記序號(hào)，標(biāo)記序號(hào)最小的數(shù)所在的位置被替換為第一個(gè)加工的工件索引號(hào)，標(biāo)記序號(hào)次小的數(shù)所在的位置被替換為第二個(gè)工件索引號(hào)，依此類(lèi)推。如果在DP中出現(xiàn)相等的數(shù)字，則位置序號(hào)較小的數(shù)代表工序號(hào)較小的工件。由此得到所有工序的加工順序序列SP。SP中第n次出現(xiàn)的數(shù)i將表示工件i的第n道工序。

對(duì)于MV，每M位為一個(gè)單元，在一個(gè)單元內(nèi)有M位十進(jìn)制數(shù)，根據(jù)能夠加工該單元對(duì)應(yīng)的工序的最大設(shè)備數(shù)h，取前h位中的最小數(shù)，該最小數(shù)所在的位置序號(hào)即為加工該道工序所對(duì)應(yīng)的設(shè)備選擇索引號(hào)，如果最小數(shù)有相同的，則對(duì)大小相同的位置隨機(jī)選擇一個(gè)作為設(shè)備選擇序號(hào)。由此得到設(shè)備選擇序列SA。

最終得到工序調(diào)度染色體SR如下：

SR=[SP|SA]。

(29)

4)根據(jù)MV將OV中的每道工序分配到對(duì)應(yīng)設(shè)備中，完成調(diào)度，得到最終調(diào)度解。

解碼流程如圖2所示。

圖2 解碼流程圖Fig. 2 Decoding flowchart

2.4.3 動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角策略

量子旋轉(zhuǎn)角大小的選擇對(duì)量子遺傳算法的性能影響很大。如果旋轉(zhuǎn)角幅值太小，可能導(dǎo)致收斂速度比較慢，如果旋轉(zhuǎn)角太大，則可能導(dǎo)致在最優(yōu)解附近徘徊，無(wú)法收斂。一般情況下，量子旋轉(zhuǎn)角的大小是固定的，無(wú)法對(duì)進(jìn)化情況做出自適應(yīng)調(diào)整，導(dǎo)致收斂速度較慢或無(wú)法收斂。

本研究中提出一種動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角策略。當(dāng)種群中個(gè)體的適應(yīng)度與種群中最優(yōu)個(gè)體的適應(yīng)度的差距較大時(shí)，可適當(dāng)調(diào)大旋轉(zhuǎn)角的幅值，以達(dá)到快速收斂的目的；反之則可適當(dāng)減小旋轉(zhuǎn)角的幅值，對(duì)個(gè)體進(jìn)行微調(diào)，防止在最優(yōu)解周?chē)鷣?lái)回震蕩以致無(wú)法收斂。旋轉(zhuǎn)角幅值的調(diào)整函數(shù)如下：

(30)

式中：Δθ表示旋轉(zhuǎn)角幅值，θmax和θmin限定了旋轉(zhuǎn)角的極值，fmax和fmin表示種群的個(gè)體適應(yīng)度極值，fc表示個(gè)體的適應(yīng)度。該策略關(guān)聯(lián)了旋轉(zhuǎn)角與個(gè)體適應(yīng)度，可動(dòng)態(tài)自適應(yīng)調(diào)整旋轉(zhuǎn)角度，從而提升整體的收斂速率。

2.4.4 交叉操作

在本研究中使用了一種關(guān)聯(lián)所有染色體的交叉技術(shù)，即全干擾交叉方式。這種方法的特點(diǎn)是所有染色體均受影響。例如假設(shè)人口為4，基因數(shù)為5，其中每個(gè)數(shù)字代表染色體上的一個(gè)量子位(圖3)。交叉操作完成后，染色體的每一位都將重新排列并斜向連接以形成新的種群。該交叉操作可以最大化地利用整個(gè)種群的染色體信息，提高種群的多樣性，并有效地減少早熟現(xiàn)象的發(fā)生。

圖3 全干擾交叉演示Fig. 3 Demonstration of full interference crossover

2.4.5 變異操作

與經(jīng)典遺傳算法相比較，量子遺傳算法同樣位數(shù)的量子比特包含了更豐富的信息，種群多樣性更好，但僅靠量子態(tài)帶來(lái)的多樣性對(duì)搜索全局最優(yōu)解仍然不夠，還是可能出現(xiàn)過(guò)早地收斂于局部解的問(wèn)題，因此需要加入量子變異來(lái)提升算法的性能。變異操作可以有效地減少早熟現(xiàn)象的發(fā)生，提高算法的尋優(yōu)能力。

在QGA算法中通常使用量子非門(mén)來(lái)進(jìn)行變異操作，量子非門(mén)的表示形式如下:

(31)

對(duì)某位量子比特進(jìn)行量子非門(mén)轉(zhuǎn)換，可得到：

(32)

該操作交換了量子比特|0和|1〉的概率幅，從而互換了測(cè)量計(jì)算時(shí)的概率，以達(dá)到變異的目的。

2.4.6 混沌搜索

為了避免種群早熟，本研究中引入混沌搜索算法，可對(duì)解空間比較均勻地遍歷?；煦缱兞康牡捎没赥ent映射的混沌搜索方法[15]。Tent映射函數(shù)有良好的物理性能，可以得到比較均勻的解集，能提高對(duì)解空間的搜索能力，但容易產(chǎn)生不動(dòng)點(diǎn)情況，在算法中需要避開(kāi)它。混沌變量的迭代步驟如下：

1)初始化迭代次數(shù)e=1。

2)取某一染色體Qe，對(duì)該染色體的第一行進(jìn)行迭代，迭代公式如下：

(33)

(34)

在此基礎(chǔ)上將當(dāng)前代種群引入混沌變量進(jìn)行混沌搜索，在最大迭代次數(shù)內(nèi)，若迭代得到的解不受當(dāng)前所有種群支配，則結(jié)束迭代并記錄當(dāng)前非劣解;若始終沒(méi)有得到非劣解，則迭代至最大迭代次數(shù)后停止迭代。

3 算例驗(yàn)證

3.1 測(cè)試數(shù)據(jù)

通過(guò)測(cè)試案例來(lái)驗(yàn)證算法解決多目標(biāo)DFJSP的可行性。當(dāng)前并沒(méi)有標(biāo)準(zhǔn)測(cè)試算例來(lái)測(cè)試柔性作業(yè)車(chē)間調(diào)度問(wèn)題，本研究中參考Brandimarte[16]柔性作業(yè)車(chē)間調(diào)度問(wèn)題標(biāo)準(zhǔn)算例，生成一系列的測(cè)試算例。為簡(jiǎn)化問(wèn)題，設(shè)每個(gè)工件的工序數(shù)一致。測(cè)試算例的參數(shù)如表2所示。

表2 測(cè)試算例參數(shù)

具體生成步驟以算例MK01為例：工件總數(shù)目為6，單個(gè)工件的工序數(shù)為4，某道工序的可選加工設(shè)備以一定概率隨機(jī)選取，在[1,9]之間隨機(jī)生成不同機(jī)器上工序的生產(chǎn)時(shí)間，并且是整數(shù)；在加工設(shè)備上加工不同工序所用的能耗在[2,8]之間隨機(jī)選取，且為實(shí)數(shù)；各個(gè)工件的交貨期設(shè)為50乘以工件設(shè)備數(shù)之比。

3.2 評(píng)價(jià)指標(biāo)

采用迭代距離Ds指標(biāo)[17]來(lái)評(píng)價(jià)算法的收斂性能：Ds表示的是當(dāng)前算法的非劣解集I相對(duì)于真實(shí)Pareto解集I*的距離。該距離越小，表明當(dāng)前算法的非劣解集越接近真實(shí)Pareto解，算法求優(yōu)性能就越好。

(35)

式中：NI*表示該非劣解集的元素個(gè)數(shù)；σxy表示解I與I*中元素y在歸一化空間內(nèi)的距離。真實(shí)Pareto解集可由所有算法算得的非劣解集構(gòu)成的集合中的非劣解近似表示。

采用ΔMetric指標(biāo)[18]來(lái)衡量非劣解集的多樣性。通過(guò)非劣解集中相鄰解的歐式距離與平均距離的差值累加來(lái)反映解空間分布的均勻性。其數(shù)學(xué)表達(dá)式如下：

(36)

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

本次實(shí)驗(yàn)首先需要驗(yàn)證通過(guò)DQN強(qiáng)化學(xué)習(xí)得到的Q適應(yīng)度函數(shù)的有效性，將其與其他評(píng)估適應(yīng)度的方法對(duì)比。常用的求解多目標(biāo)解適應(yīng)度的方法有兩種，一種是將多目標(biāo)通過(guò)加權(quán)方式轉(zhuǎn)換為單目標(biāo)來(lái)進(jìn)行評(píng)價(jià)，另一種是構(gòu)造基于非支配排序等級(jí)的實(shí)值函數(shù)來(lái)評(píng)價(jià)多目標(biāo)解。在本次實(shí)驗(yàn)以MK04作為算例，設(shè)定種群迭代次數(shù)為80，種群個(gè)體數(shù)為40，單位延期懲罰系數(shù)為0.4，且當(dāng)前只考慮設(shè)備發(fā)生故障的情況，為了統(tǒng)一計(jì)量各個(gè)評(píng)價(jià)方法的優(yōu)劣，設(shè)定設(shè)備在時(shí)刻8出現(xiàn)故障，并在時(shí)刻20維修好。在量子遺傳算法的基礎(chǔ)上，分別調(diào)用這3種方法，各自重復(fù)運(yùn)行10次，選擇調(diào)度結(jié)果中較優(yōu)解(平均延期懲罰最小優(yōu)先)，運(yùn)行結(jié)果如圖4～6和表3所示。

圖4 采用Q適應(yīng)度函數(shù)的重調(diào)度甘特圖Fig. 4 Rescheduling Gantt chart using Q fitness function

圖5 采用加權(quán)適應(yīng)度函數(shù)的重調(diào)度甘特圖Fig. 5 Rescheduling Gantt chart using weighted fitness function

圖6 采用基于非支配排序等級(jí)的適應(yīng)度函數(shù)的重調(diào)度甘特圖Fig. 6 Rescheduling Gantt chart using fitness function based on non-dominated ranking

表3 采用各種適應(yīng)度函數(shù)的實(shí)驗(yàn)結(jié)果

表3列出所有Pareto解中的各項(xiàng)目標(biāo)的最小值及Pareto解個(gè)數(shù)，在所求解的各項(xiàng)目標(biāo)上，采用Q適應(yīng)度函數(shù)的算法算出的最小值均明顯優(yōu)于其他兩種方法算出的結(jié)果，表明Q適應(yīng)度函數(shù)對(duì)解空間的尋優(yōu)能力更強(qiáng)，能夠更好地評(píng)估染色體的適應(yīng)度。而且Q適應(yīng)度函數(shù)對(duì)動(dòng)態(tài)事件有很好的響應(yīng)，能夠根據(jù)當(dāng)前環(huán)境做出整體的最優(yōu)選擇，如圖4～6是采用各種適應(yīng)度函數(shù)得到的最小平均延期懲罰解對(duì)應(yīng)的重調(diào)度結(jié)果，當(dāng)機(jī)器故障修復(fù)后，采用Q適應(yīng)度函數(shù)的算法并不急于在機(jī)器3上安排工件4加工，而是選擇等待工件2的加工，而其他兩種算法都急于在機(jī)器3上安排工件4加工，不能達(dá)到整體最優(yōu)。

在DFJSP問(wèn)題上，為驗(yàn)證算法的有效性，將本文的深度強(qiáng)化學(xué)習(xí)-量子遺傳算法(DQN-QGA)與求解DFJSP的常用算法非支配遺傳排序算法(non-dominated sorting genetic algorithm，NSGA)進(jìn)行比較，同時(shí)為了驗(yàn)證該算法在環(huán)境適應(yīng)性上的提升，與一般非支配量子遺傳算法(non-dominated sorting quantum genetic algorithm，NSQGA)進(jìn)行比較，并在各個(gè)測(cè)試案例中進(jìn)行測(cè)試驗(yàn)證。為保證一致性，對(duì)各個(gè)算法設(shè)定同樣的參數(shù)，包括種群進(jìn)化代數(shù)為100，種群個(gè)體總數(shù)為80，動(dòng)態(tài)事件均服從伽馬分布，根據(jù)文獻(xiàn)[8]中對(duì)動(dòng)態(tài)事件的仿真策略，α取0.2，β取0.4。同時(shí)對(duì)各個(gè)算例重復(fù)運(yùn)行20次，取20次運(yùn)算結(jié)果的Pareto前沿解作為算法的運(yùn)算結(jié)果。實(shí)驗(yàn)結(jié)果見(jiàn)表4。

表4 各類(lèi)算法關(guān)于指標(biāo)Ds和Δ的計(jì)算結(jié)果

續(xù)表4

在收斂性指標(biāo)上，DQN-QGA算法明顯優(yōu)于其他算法。在16個(gè)算例中，DQN-QGA的Ds指標(biāo)均比NSQGA和NSGA小，表明其求出的非劣解接近實(shí)際Pareto解，與常規(guī)算法相比，極大地提高了算法收斂性。在多樣性指標(biāo)上，DQN-QGA算法在超過(guò)2/3的算例中，Δ指標(biāo)比其他算法小，由于編碼解碼復(fù)雜和智能算法自身的隨機(jī)性，在剩下的算例中，DQN-QGA的Δ指標(biāo)比其他算法大?？傮w說(shuō)來(lái)，與傳統(tǒng)的遺傳算法和量子遺傳算法相比，DQN-QGA算法在收斂性和多樣性上有明顯的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

研究了柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題及其求解。首先建立了考慮了平均延期懲罰、能耗、偏差度的DFJSP優(yōu)化模型，采用動(dòng)態(tài)重調(diào)度和周期性重調(diào)度相結(jié)合的動(dòng)態(tài)調(diào)度響應(yīng)策略；然后利用DQN算法學(xué)習(xí)環(huán)境-行為評(píng)價(jià)神經(jīng)網(wǎng)絡(luò)模型作為優(yōu)化模型的適應(yīng)度函數(shù)，基于該適應(yīng)度函數(shù)，通過(guò)改進(jìn)的量子遺傳算法對(duì)優(yōu)化模型求解，該算法設(shè)計(jì)了多層編碼解碼方案，對(duì)量子交叉和變異操作進(jìn)行了適當(dāng)改進(jìn)，并引入了混沌變量，對(duì)種群進(jìn)行基于Tent映射的混沌搜索以提升對(duì)解空間的均勻遍歷能力，避免早熟現(xiàn)象。最后通過(guò)測(cè)試算例，驗(yàn)證了環(huán)境-行為評(píng)價(jià)神經(jīng)網(wǎng)絡(luò)模型的有效性，能夠根據(jù)當(dāng)前環(huán)境做出較優(yōu)的選擇，提高了優(yōu)化算法的魯棒性和自適應(yīng)性。提出的基于Q學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)的改進(jìn)QGA算法，通過(guò)不斷地學(xué)習(xí)，可以適應(yīng)新環(huán)境下的動(dòng)態(tài)事件干擾，具有很強(qiáng)的魯棒性，相較于傳統(tǒng)的遺傳算法，該算法在收斂性、多樣性、穩(wěn)定性上有了較大的提升，可以作為求解DFJSP問(wèn)題的一個(gè)途徑。