基于改進(jìn)遺傳算法的車間調(diào)度原型系統(tǒng)

郭 岳， 朱 斌， 車志忠， 戴 博， 張富強(qiáng)， 惠記莊

(長(zhǎng)安大學(xué)公路養(yǎng)護(hù)裝備國(guó)家工程實(shí)驗(yàn)室，西安 710064)

當(dāng)前，制造業(yè)進(jìn)入以智能制造為代表的工業(yè)4.0時(shí)代，隨著用戶對(duì)于產(chǎn)品制造要求不斷提升，以制造執(zhí)行系統(tǒng)(manufacturing execution system，MES)為核心的先進(jìn)制造技術(shù)已成為研究的熱點(diǎn)[1]。車間調(diào)度作為MES系統(tǒng)中的關(guān)鍵業(yè)務(wù)，也是提高制造業(yè)生產(chǎn)效率的關(guān)鍵因素[2]。車間調(diào)度問(wèn)題(job-shop scheduling problem,JSP)和柔性車間調(diào)度問(wèn)題(flexible job-shop scheduling problem,FJSP)都是經(jīng)典離散組合優(yōu)化問(wèn)題[3]，數(shù)學(xué)上屬于NP難題[4]。

中外學(xué)者采用不同的求解算法對(duì)車間調(diào)度問(wèn)題進(jìn)行了深入研究，其中遺傳算法作為一種魯棒性強(qiáng)、通用性好的智能優(yōu)化算法，在車間調(diào)度問(wèn)題中得到了廣泛應(yīng)用[5]。但傳統(tǒng)遺傳算法存在全局搜索能力和局部搜索能力較差，并容易早熟收斂等問(wèn)題。對(duì)于遺傳算法的改進(jìn)已經(jīng)有眾多的研究成果。Gao等[6]針對(duì)柔性車間調(diào)度問(wèn)題提出一種經(jīng)典的混合遺傳算法。陸曈曈等[7]針對(duì)柔性車間調(diào)度問(wèn)題提出一種改進(jìn)元胞遺傳算法。石小秋等[8]為解決車間調(diào)度問(wèn)題，提出了一種自適應(yīng)變級(jí)遺傳雜草算法，分析了求解參數(shù)對(duì)算法性能的影響。王秋芬等[9]基于集合論數(shù)學(xué)模型，研究了兩層編碼在解決車間調(diào)度問(wèn)題的應(yīng)用。Wang等[10]針對(duì)逆向作業(yè)車間調(diào)度問(wèn)題，提出了一種基于十進(jìn)制機(jī)制的分組編碼方案，該方案可以同時(shí)優(yōu)化過(guò)程和參數(shù)。何斌等[11]針對(duì)車間調(diào)度問(wèn)題,提出通過(guò)動(dòng)態(tài)改變交叉與變異概率提高算法的尋優(yōu)能力。趙詩(shī)奎等[12-13]為提高遺傳算法求解車間調(diào)度問(wèn)題初始種群的質(zhì)量,提出了啟發(fā)式方法與基于短用時(shí)和設(shè)備均衡策略的機(jī)器鏈優(yōu)化方法。宋存利[14]提出了改進(jìn)貪婪遺傳算法，采用了正序解碼和逆序解碼加再調(diào)度并用的解碼策略。

這些研究主要集中在種群初始化、遺傳操作、解碼、以及其他算法融合等方面。可以看出，目前在構(gòu)造遺傳算法初始種群方面方法過(guò)于復(fù)雜，沒(méi)有解決初始種群大小難以確定(一般通過(guò)經(jīng)驗(yàn)或測(cè)試)、初始解穩(wěn)定性差、初始化種群多樣性難以保證[12-13]和不利于遺傳操作過(guò)程的問(wèn)題，且整個(gè)算法在實(shí)際車間調(diào)度系統(tǒng)實(shí)現(xiàn)上還存在一定的困難。為此在遺傳算法求解車間調(diào)度問(wèn)題的基礎(chǔ)上引入幻方變換編碼機(jī)制，產(chǎn)生自適應(yīng)問(wèn)題規(guī)模的初始種群，直接對(duì)幻方變換產(chǎn)生的互換編碼種群進(jìn)行遺傳操作，簡(jiǎn)化了遺傳操作的復(fù)雜度；針對(duì)車間調(diào)度問(wèn)題和柔性車間調(diào)度問(wèn)題進(jìn)行綜合考慮，不再將JSP問(wèn)題當(dāng)作FJSP問(wèn)題處理，充分分析了兩者差異，并融入到遺傳算法中；最后在此基礎(chǔ)上對(duì)這兩類問(wèn)題和上期工序遺留問(wèn)題進(jìn)行了原型系統(tǒng)開(kāi)發(fā)，并對(duì)改進(jìn)遺傳算法的有效性進(jìn)行了驗(yàn)證。

1 車間調(diào)度問(wèn)題描述

車間調(diào)度問(wèn)題作為一類特殊的排序問(wèn)題，其目的是在給定的機(jī)器資源約束下，在不破壞事務(wù)技術(shù)順序的前提下，完成多個(gè)事務(wù)的合理資源分配[15]。其數(shù)學(xué)上可以描述為n項(xiàng)事務(wù)在m種資源下按照給定約束有序進(jìn)行，其數(shù)學(xué)模型如下：

(1)機(jī)器資源集M={me1,me2,…,mem}，mej表示第j種資源，j=1,2,…，m。

(2)事務(wù)集J={jo1,jo2,…,jon}，joi表示第i個(gè)事務(wù)，i=1,2,…，n。

(3)事務(wù)順序集JM={jm1,jm2,…，jmn}，jmi={jmi1,jmi2,…，jmil}表示事務(wù)i的技術(shù)順序。

(4)可選機(jī)器集OPM={jmi1,jmi2,…，jmil}，jmil={jmil1,jmil2,…，jmils}表示事務(wù)的技術(shù)步l可以選擇的機(jī)器資源。

(5)機(jī)器處理事務(wù)時(shí)間矩陣T，til∈T，表示第i個(gè)事務(wù)在機(jī)器l上的加工時(shí)間。

2 改進(jìn)遺傳算法

基于以上數(shù)學(xué)模型，改進(jìn)遺傳算法流程如圖1所示，根據(jù)求解問(wèn)題類型的不同，JSP問(wèn)題采用單層編碼，F(xiàn)JSP問(wèn)題采用多層編碼，并利用幻方變換法初始化種群，進(jìn)行遺傳操作，直到達(dá)到最大遺傳代數(shù)，再將最優(yōu)染色體按求解問(wèn)題類型和解碼規(guī)則生成調(diào)度方案。

圖1 改進(jìn)遺傳算法流程Fig.1 Flow chart of improved genetic algorithm

2.1 初始化種群

為了保證遺傳算法種群的多樣性，同時(shí)提高初始解的質(zhì)量，目前車間調(diào)度問(wèn)題多采用互換編碼、隨機(jī)編碼、NEH啟發(fā)式編碼[16]和量子比特編碼[17]等，這些編碼方式都存在遺傳操作過(guò)程過(guò)于復(fù)雜的問(wèn)題，為此，提出基于規(guī)則的幻方變換互換編碼。互換編碼主要用于解決一維排序問(wèn)題，如旅行商問(wèn)題，車間調(diào)度問(wèn)題可以看成是帶約束的多旅行商問(wèn)題(multiple traveling salesman problem, MTSP)[18]，即多個(gè)工件在機(jī)器上的流轉(zhuǎn)，只是需要添加技術(shù)約束條件(工件在機(jī)器上的加工次序)。車間調(diào)度問(wèn)題編碼可以看成一維旅行商問(wèn)題，即對(duì)所有工件工序進(jìn)行互換編碼，并對(duì)互換編碼進(jìn)行切片以產(chǎn)生滿足車間調(diào)度問(wèn)題的工序編碼。對(duì)于JSP問(wèn)題工件工序和加工機(jī)器是一一對(duì)應(yīng)的。采用基于工序的單層編碼就足以解決；而對(duì)于FJSP問(wèn)題，則需要根據(jù)工序可選機(jī)器集生成機(jī)器碼層，然而機(jī)器碼層可以看作工序編碼層的子層，只要跟隨工序碼層做相同的遺傳操作，就能求解FJSP問(wèn)題，因此下文只對(duì)單層編碼過(guò)程進(jìn)行介紹。

2.1.1 互換編碼與工序編碼的關(guān)系

設(shè)一條染色體X={x1,x2,…,xJn}，x為1～Jn的整數(shù)隨機(jī)排列，對(duì)其進(jìn)行切片映射即可產(chǎn)生工序編碼的染色體X′={x′1,x′2,…,x′Jn}，其中x′k=i(1≤i≤n,1≤k≤Jn)，若x′k為染色體X′中x′1到x′k的第j個(gè)i，則x′k表示工件i的第j道工序。圖2所示為4個(gè)工件，各工件工序數(shù)為3、3、4、2的互換編碼到工序編碼的切片映射生成過(guò)程。至此問(wèn)題轉(zhuǎn)化為基于工序的互換編碼問(wèn)題。下面開(kāi)始構(gòu)造互換編碼。

圖2 互換編碼與工序編碼映射關(guān)系Fig.2 Interchange coding and process coding mapping

2.1.2 幻方種群構(gòu)造方法

幻方是起源于我國(guó)的神秘的數(shù)學(xué)問(wèn)題，其在人工智能、對(duì)策論、實(shí)驗(yàn)設(shè)計(jì)、工藝美術(shù)、電子回路原理、位置解析學(xué)等方面有著廣泛的應(yīng)用，并逐步成為組合數(shù)學(xué)研究的重要課題[19]。

下面結(jié)合幻方矩陣構(gòu)造工件工序總數(shù)為12的初始種群，具體步驟如下：

(2)幻方變換，對(duì)幻方矩陣依次逆時(shí)針旋轉(zhuǎn)c×90°<360°，其中c=1、2、4，c為初始種群規(guī)模因子，控制種群大小。圖3所示為4階幻方旋轉(zhuǎn)變換過(guò)程。

圖3 4階幻方旋轉(zhuǎn)變換Fig.3 4th-order magic square rotation transformation

(3)取步驟(2)中幻方矩陣記為A，對(duì)A矩陣作初等行變換E(i,j)A，其中i,j∈[i,L]，且i≠j，E(i,j)為初等矩陣。圖4所示為步驟(2)旋轉(zhuǎn)變換后的幻方進(jìn)行行變換過(guò)程，每一個(gè)4階幻方被變換為一個(gè)數(shù)據(jù)立方體。

圖4 4階幻方行變換Fig.4 4th magic square row transformation

(4)對(duì)幻方變換數(shù)據(jù)立方體進(jìn)行拉直，去除大于Jn的數(shù)據(jù)，產(chǎn)生初始種群。圖5所示為4階幻方變換數(shù)據(jù)立方體經(jīng)過(guò)拉直調(diào)整生成初始種群的過(guò)程。

圖5 4階幻方種群生成過(guò)程Fig.5 4th-order magic square population generation process

2.1.3 種群規(guī)模

在遺傳算法初始化時(shí)，種群規(guī)模設(shè)置過(guò)大會(huì)導(dǎo)致算法計(jì)算量增加、效率降低。經(jīng)驗(yàn)得知，種群規(guī)模通常取[10,200]，具體大小可根據(jù)染色體基因位數(shù)估算確定。現(xiàn)提出的構(gòu)造初始種群機(jī)制，產(chǎn)生的種群個(gè)體為幻方階數(shù)的函數(shù)，而幻方階數(shù)又可以通過(guò)基因位數(shù)得到，所以可近似認(rèn)為種群數(shù)與基因位數(shù)存在某種模糊關(guān)系，式(1)為其種群規(guī)模與幻方階數(shù)L的關(guān)系。

(1)

式(1)中:Nind為種群中個(gè)體數(shù)量；參數(shù)p與種群規(guī)模因子c有關(guān)，滿足表1的關(guān)系。

表1 參數(shù)p與因子c的關(guān)系

可以驗(yàn)證在工件總工序數(shù)Jn與L2相差不大時(shí)，所產(chǎn)生初始種群的個(gè)體具有多樣性。

2.2 選擇操作

對(duì)于車間調(diào)度問(wèn)題常采用所有機(jī)器中最大加工時(shí)間作為適應(yīng)度函數(shù)。那么適應(yīng)度為

(2)

式(2)中：Eval為種群中適應(yīng)度值；m為機(jī)器數(shù)。

陶俊波等[20]提出通過(guò)個(gè)體好壞的排序(并非原始適應(yīng)值)確定個(gè)體選擇概率，可以防止優(yōu)秀個(gè)體過(guò)度繁殖，進(jìn)而避免算法過(guò)早收斂。基于排序的適應(yīng)度分配選擇步驟如下：

(1)由于種群中個(gè)體適應(yīng)度越小，調(diào)度方案越優(yōu)，所以對(duì)種群中個(gè)體按照適應(yīng)度大小進(jìn)行從小到大線性排序。

(2)種群中排序?yàn)閕的個(gè)體分配適應(yīng)度為

(3)

式(3)中：sp為選擇壓差，決定偏移和選擇強(qiáng)度。

(3)按照種群中個(gè)體分配適應(yīng)度值進(jìn)行“比例選擇”，即所謂的“輪盤(pán)賭”。

2.3 交叉操作

種群通過(guò)交叉操作可繼承父代的優(yōu)秀基因片段，從而推動(dòng)整個(gè)群體的進(jìn)化歷程。對(duì)于車間調(diào)度問(wèn)題，為了盡可能多的繼承父代優(yōu)秀基因片段，這里采用單點(diǎn)交叉，即交換父代兩個(gè)染色體中交叉點(diǎn)之后(或之前)的基因片段，產(chǎn)生子代個(gè)體，具體操作步驟如下：

(1)根據(jù)交叉概率選擇兩條交叉染色體，并隨機(jī)產(chǎn)生交叉位置Pos。

(2)將父代個(gè)體交叉點(diǎn)之后的基因片段進(jìn)行交換，并找出在非交叉位置的不合法基因位。

(3)依次交換不合法基因位產(chǎn)生子代個(gè)體。

圖6所示為種群中隨機(jī)選擇的兩條染色體進(jìn)行單點(diǎn)交叉操作過(guò)程，圖6(a)隨機(jī)生成交叉位置Pos，圖6(b)交換Pos位置之后的基因片段，并且標(biāo)記交叉點(diǎn)之前重復(fù)基因位，圖6(c)交換交叉點(diǎn)之前基因位所產(chǎn)生的兩條子代染色體。

圖6 單點(diǎn)交叉操作過(guò)程Fig.6 Single point cross operation process

2.4 變異操作

變異算子采用的是兩點(diǎn)換位法，首先根據(jù)變異率選取染色體X={x1,x2,…,xJn}，在染色體X上隨機(jī)選取兩點(diǎn)i、j，將這兩個(gè)點(diǎn)上的基因位進(jìn)行互換，生成新的子代染色體X*={x1,…,xj,…,xi,…,xJn}。

2.5 解碼

由于JSP問(wèn)題和FJSP問(wèn)題編碼方式的不同，編碼位含義不同，那么解碼也就存在一定的差異。雖然兩種問(wèn)題解碼具體過(guò)程存在差異，但解碼的過(guò)程可以統(tǒng)一，即實(shí)現(xiàn)染色體到加工描述矩陣的映射。

為描述某一工件某道工序的加工過(guò)程，需要4個(gè)參數(shù)，分別為工件號(hào)、工序號(hào)、機(jī)器號(hào)和加工時(shí)間，這一事件記作D=(X,XP,XM,XT)，其中D為加工描述矩陣，D中各元素分別表示工件編碼序列、以工件編碼序列所對(duì)應(yīng)工序序列、機(jī)器序列和加工時(shí)間序列。

對(duì)于染色體X={x1,x2,…,xJn}，解碼步驟如下：

(1)染色體切片，將互換編碼通過(guò)切片轉(zhuǎn)化為工序編碼的染色體X′={x′1,x′2,…,x′Jn},其中x′k=i(1≤i≤n,1≤k≤Jn)。

(2)按照染色體X′工件加工順序，對(duì)照工件工序集產(chǎn)生染色體X′的對(duì)應(yīng)加工工序序列集XP、加工機(jī)器序列集XM和對(duì)照XP和XM產(chǎn)生染色體X′對(duì)應(yīng)的加工機(jī)器時(shí)間序列集XT。

(3)定義機(jī)器上工件開(kāi)始加工時(shí)間矩陣、機(jī)器當(dāng)前時(shí)間數(shù)組和機(jī)器上工件結(jié)束加工時(shí)間矩陣，判斷問(wèn)題類型有無(wú)上期遺留未加工工序，如果存在工序遺留，那么機(jī)器當(dāng)前時(shí)間數(shù)組應(yīng)該為上期未加工工序各機(jī)器遺留時(shí)間。

(4)解碼過(guò)程需做如下邏輯判斷，如果某工件首次加工或待加工工件機(jī)器當(dāng)前時(shí)間大于該工件上道工序加工完成機(jī)器時(shí)間則直接開(kāi)始當(dāng)前工件加工，否則機(jī)器等待工件上道工序加工完成，才能進(jìn)行當(dāng)前工序加工。

3 調(diào)度原型系統(tǒng)

作業(yè)車間調(diào)度作為MES生產(chǎn)計(jì)劃的一個(gè)主要功能模塊，其需要提供MES生產(chǎn)計(jì)劃數(shù)據(jù)接口，完成對(duì)車間作業(yè)計(jì)劃工藝和設(shè)備等信息的采集和處理，通過(guò)自身的排程功能，生成資源分配計(jì)劃，傳回MES系統(tǒng)，以便進(jìn)行后續(xù)的動(dòng)態(tài)調(diào)整和生產(chǎn)執(zhí)行。

3.1 原型系統(tǒng)設(shè)計(jì)

作業(yè)車間調(diào)度系統(tǒng)(圖7)中包含對(duì)工件、機(jī)器、工藝和排程的管理。工件管理完成調(diào)度工件的添加和移除；機(jī)器管理包括對(duì)機(jī)器號(hào)和機(jī)器狀態(tài)的設(shè)定；工藝管理包括加工狀態(tài)修改；排程管理包括問(wèn)題類型、排程參數(shù)的確認(rèn)、求解參數(shù)設(shè)定、查看求解過(guò)程和排程結(jié)果展示。

3.2 排程展示和功能驗(yàn)證

采用文獻(xiàn)[21]提供的某鋼橋算例來(lái)展示排程管理結(jié)果，實(shí)驗(yàn)數(shù)據(jù)如圖8所示，程序?yàn)槊嫦驅(qū)ο蟮摹⑦\(yùn)行于.NET Framework和.NET Core之上的高級(jí)程序設(shè)計(jì)語(yǔ)言C#開(kāi)發(fā)，參數(shù)設(shè)置如下：迭代次數(shù)為50，交叉概率為0.8，變異概率為0.1，種群規(guī)模c取1，對(duì)應(yīng)的種群大小為88，上期各機(jī)器遺留任務(wù)所需時(shí)間均為10。圖8和圖9所示為其排程參數(shù)設(shè)置和排程結(jié)果，圖10所示為每代求解結(jié)果和平均求解結(jié)果的變化情況。

為了驗(yàn)證本文提出的改進(jìn)遺傳算法的有效性，采用文獻(xiàn)[9,11,21]中相同數(shù)據(jù)集進(jìn)行測(cè)試。算例1為Ft06基準(zhǔn)算例，算例2為8×6算例，算例3為工程測(cè)試案例。文獻(xiàn)[9]采用兩層編碼并對(duì)適應(yīng)度度量和遺傳算子進(jìn)行優(yōu)化的改進(jìn)遺傳算法；文獻(xiàn)[11]采用動(dòng)態(tài)交叉和變異算子的改進(jìn)遺傳算法；文獻(xiàn)[21]采用標(biāo)準(zhǔn)遺傳算法進(jìn)行求解。為了對(duì)本文提出的種群初始化方法的有效性進(jìn)行驗(yàn)證，可對(duì)測(cè)試算例的10次實(shí)驗(yàn)結(jié)果的第一代最優(yōu)值及第一代所有個(gè)體適應(yīng)度平均值進(jìn)行對(duì)比[12-13]。表2列出了3個(gè)算例的第一代求解結(jié)果和最終求解結(jié)果，將求解結(jié)果與相關(guān)文獻(xiàn)求解結(jié)果進(jìn)行比較可以看出，提出的種群構(gòu)造方法在第一代就能得到相對(duì)優(yōu)秀的個(gè)體，優(yōu)于其他文獻(xiàn)中的初始種群構(gòu)造方法，采用自適應(yīng)種群為工程測(cè)試案例大小，當(dāng)種群規(guī)模較小時(shí)，仍然能夠得到較優(yōu)的結(jié)果，表明該算法構(gòu)造種群具有良好的多樣性。算法最終求解結(jié)果等于或優(yōu)于文獻(xiàn)結(jié)果，驗(yàn)證了該求解算法的有效性。

圖7 車間調(diào)度系統(tǒng)組成Fig.7 Composition of the shop scheduling system

圖8 排程參數(shù)設(shè)置界面Fig.8 Scheduling parameter setting interface

圖9 排程結(jié)果展示界面Fig.9 Scheduling results display interface

圖10 改進(jìn)遺傳算法求解過(guò)程Fig.10 Improved genetic algorithm solution process

表2 改進(jìn)遺傳算法求解結(jié)果對(duì)比

4 結(jié)論

對(duì)車間調(diào)度問(wèn)題的研究得到以下結(jié)論：

(1)遺傳算法進(jìn)行基于幻方變換的互換編碼和基于規(guī)則的解碼設(shè)計(jì)，減小了種群染色體的空間復(fù)雜度，簡(jiǎn)化了遺傳算法求解車間調(diào)度問(wèn)題的編碼過(guò)程，提高了遺傳算法的求解能力。

(2)采用互換編碼進(jìn)行遺傳操作有效簡(jiǎn)化了交叉和變異過(guò)程，為實(shí)際調(diào)度問(wèn)題的解決提供理論支持。

(3)在微軟.NET平臺(tái)采用C#語(yǔ)言構(gòu)建了用于同時(shí)求解JSP、FJSP和上期工序遺留問(wèn)題的調(diào)度原型系統(tǒng)，為搭建更加符合生產(chǎn)實(shí)際的車間調(diào)度系統(tǒng)提供了參考。