蔣 城，蔡晉輝

（1.杭州鴻雁智能科技有限公司，浙江 杭州 310007；2.中國計(jì)量大學(xué)，浙江 杭州 310018）

0 引言

隨著物聯(lián)制造車間的發(fā)展，智能排程算法受到重視，產(chǎn)生了很多新的算法，如：領(lǐng)域搜索技術(shù)[1]、模擬退火算法（SA）[2]、禁忌搜索算法[3]、遺傳算法[4]、神經(jīng)網(wǎng)絡(luò)技術(shù)[5]、蟻群算法[6]、粒子群算法[7]、蜂群算法[8]、螢火蟲算法[9]、蛙跳算法[10]等。

其中，遺傳算法（GA）以其全體搜索策略和群體中個(gè)體信息交換特點(diǎn)，被廣泛應(yīng)用于求解車間調(diào)度問題。國內(nèi)外學(xué)者對(duì)遺傳算法做了大量的研究，在Reeves[11]驗(yàn)證了遺傳算法的優(yōu)越性后，Murata[12]將局部搜索引入遺傳算法中，形成基于遺傳算法求解車間調(diào)度問題的框架。之后遺傳算法的調(diào)度優(yōu)化成為研究重點(diǎn)。例如，王金鵬[13]運(yùn)用最優(yōu)子群遺傳算法來求解柔性流水車間問題，王軍強(qiáng)[14]設(shè)計(jì)了多樣性判定增強(qiáng)算子，分析算子時(shí)間復(fù)雜度，對(duì)自適應(yīng)遺傳算法進(jìn)行優(yōu)化求解。王蕾等[15]以加工完成時(shí)間、機(jī)器損耗、員工操作舒適度為多目標(biāo)函數(shù)，改進(jìn)遺傳算法。

但遺傳算法存在局部搜索能力較差，易產(chǎn)生“早熟”收斂的問題，單純對(duì)遺傳算法進(jìn)行優(yōu)化很難解決這些問題，研究人員將遺傳算法與其他算法結(jié)合，以取得更好調(diào)度結(jié)果。程子安等[16]提出雙種群機(jī)制，分別負(fù)責(zé)全局搜索和局部搜索，并設(shè)計(jì)相關(guān)遺傳算法來彌補(bǔ)局部搜索能力不足的問題。趙詩奎[17]設(shè)計(jì)了一種兩級(jí)領(lǐng)域搜索混合算法，利用遺傳算法搜索全局變量，對(duì)兩級(jí)領(lǐng)域算法進(jìn)行改進(jìn)，實(shí)現(xiàn)局部搜索。但這些改進(jìn)算法存在設(shè)計(jì)復(fù)雜，耗時(shí)長(zhǎng)等問題，且多針對(duì)機(jī)械化調(diào)度排程，本文以電子企業(yè)裝配車間為研究對(duì)象，針對(duì)員工車間排程設(shè)計(jì)了改進(jìn)遺傳退火算法（GASA），在算法中加入了最優(yōu)解存儲(chǔ)器，能夠保證適應(yīng)度值一直往最優(yōu)化方向發(fā)展，克服遺傳算法易早熟，以及模擬退火算法波動(dòng)幅度大、搜索速度慢的缺點(diǎn)。

1 車間排程數(shù)學(xué)模型建立

本文智能排程的實(shí)質(zhì)是對(duì)電子企業(yè)車間裝配生產(chǎn)線員工的生產(chǎn)調(diào)度分配。假設(shè)生產(chǎn)線加工裝配過程共有m位員工，加工的產(chǎn)品共有n種，形成產(chǎn)品集合J，員工集合M，工序集合O。所有產(chǎn)品加工時(shí)間可以用時(shí)間矩陣T來表示，矩陣T每一行代表一種產(chǎn)品，每一列代表一道加工工序，未經(jīng)過的工序用0表示，矩陣T可以表示為：

上式中，產(chǎn)品1生產(chǎn)過程共需要n1道工序，每道工序的加工時(shí)間分別為T11、T12…T1n，產(chǎn)品i生產(chǎn)過程共需要ni道工序。因?yàn)楦鞯拦ば蛟诓煌瑔T工Mk加工時(shí)間不同，所以各加工時(shí)間值不固定，因此才有生產(chǎn)調(diào)度的必要，以期求出最優(yōu)解。

本文首先在滿足約束條件并且不考慮其他擾動(dòng)因素的情況下，建立裝配生產(chǎn)車間調(diào)度模型。為追求所有產(chǎn)品的最大完成時(shí)間最短，產(chǎn)品的總加工時(shí)長(zhǎng)可以用T1表示，表達(dá)式為：

其中，Ciek表示產(chǎn)品Ji在最后一道工序加工完成的時(shí)間，即該產(chǎn)品總加工時(shí)間。在實(shí)際應(yīng)用中，還需將滿足交貨期限的指標(biāo)放入模型中。客戶對(duì)產(chǎn)品交貨期的需求，可以用滿意度指標(biāo)E/T指標(biāo)T2表示，表達(dá)式為：

要使產(chǎn)品交貨期控制在客戶期望交貨區(qū)間內(nèi)，提前和延后都會(huì)使調(diào)度結(jié)果不能最優(yōu)化，所以設(shè)定產(chǎn)品i的提前懲罰系數(shù)αi和延后懲罰系數(shù)βi。T2值越小，表明產(chǎn)品交貨期越接近客戶期望交貨區(qū)間，客戶滿意度越高。生產(chǎn)調(diào)度的總目標(biāo)函數(shù)可以表示為： min[T1，T2]

2 改進(jìn)遺傳退火算法設(shè)計(jì)

傳統(tǒng)遺傳算法為保證基因的多樣性，引入變異操作以避免某些基因缺失。但實(shí)驗(yàn)證明遺傳退火算法在進(jìn)化后期，進(jìn)化會(huì)因變異操作而出現(xiàn)較大的波動(dòng)。而遺傳退火算法中模擬退火可以保證基因的多樣性，而不需引入變異操作。遺傳退火算法可以分為以下四個(gè)步驟：確定問題的編碼方案、確定適應(yīng)度函數(shù)、設(shè)計(jì)遺傳退火算子、設(shè)置算法參數(shù)。

2.1 染色體編碼和解碼設(shè)計(jì)

表1 3×3調(diào)度問題基礎(chǔ)數(shù)據(jù)表

假設(shè)給定染色體[2 3 1 3 2 2 1 3 1]，數(shù)字表示產(chǎn)品J1，每個(gè)數(shù)字產(chǎn)生幾次表明該產(chǎn)品有幾道工序。再根據(jù)表1基礎(chǔ)數(shù)據(jù)表的對(duì)應(yīng)關(guān)系，可得到其加工所需時(shí)間。以此類推，最終得到該染色體對(duì)應(yīng)的員工列表為[M2M1M3M3M1M3M1M2M2]和對(duì)應(yīng)的時(shí)間列表，最終得到染色體解碼操作表，如表2所示。

表2 染色體解碼操作表

根據(jù)該解碼操作表可得到可行調(diào)度方案如圖1所示。

圖1 基于工序編碼的可行調(diào)度

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

本文選用倒數(shù)選取法構(gòu)造適應(yīng)度函數(shù)。目標(biāo)函數(shù)為最小值問題的適應(yīng)度函數(shù)為：

式（1）中，T（t）為關(guān)于種群中第 i個(gè)優(yōu)化方式總加工時(shí)間的函數(shù)。

2.3 遺傳退火算子設(shè)計(jì)

遺傳退火算子的設(shè)計(jì)包括以下部分：

2.3.1 選擇算子

選擇操作是將優(yōu)良個(gè)體從父代種群中挑選出來，保留到子代，個(gè)體適應(yīng)度值是判斷個(gè)體優(yōu)良性的重要依據(jù)。本文采用賭輪法進(jìn)行選擇操作。

遺傳選擇算子公式為：

式（2）中，f（xi）為個(gè)體適應(yīng)度值，Pi為個(gè)體被選中概率。

退火選擇算子公式為：

式（3）中，t為退火溫度，favg為當(dāng)前種群平均適應(yīng)度值。

2.3.2 交叉算子

本文設(shè)計(jì)了一種以產(chǎn)品工序作為基因片段的交叉方式，具體步驟如下：

步驟一：首先隨機(jī)選擇兩個(gè)個(gè)體P1、P2，隨機(jī)選擇個(gè)體中兩個(gè)產(chǎn)品J1、J2將個(gè)體染色體中兩個(gè)產(chǎn)品所有基因按照原順序重新組成新基因片段A1、A2，在P1、P2中被提取的位置用0代替，如下所示：

步驟二：將新基因片段調(diào)換順序，依次替換掉對(duì)方個(gè)體中為0的基因片段，產(chǎn)生新的子代個(gè)體B1和 B2，如下所示：

步驟三：把子代B1、B2所有基因反序排列，得到最終個(gè)體C1、C2，以提高種群多樣性，避免遺傳算法早熟收斂，如下所示：

2.3.3 最優(yōu)解存儲(chǔ)器

最優(yōu)解存儲(chǔ)器用來記錄調(diào)度過程中遇到的最優(yōu)解，存儲(chǔ)器主要包括兩個(gè)部分p*和f*，p*用來存儲(chǔ)最優(yōu)解，f*用來存儲(chǔ)該最優(yōu)解的目標(biāo)函數(shù)值。在算法運(yùn)行過程中，產(chǎn)生的優(yōu)秀個(gè)體目標(biāo)函數(shù)值f與存儲(chǔ)器中已有最優(yōu)解目標(biāo)函數(shù)值f*比較，若f優(yōu)于f*，則p*=p，f*=f，以此保證優(yōu)化結(jié)果為最優(yōu)解。

2.4 算法參數(shù)設(shè)置

在調(diào)度算法開始運(yùn)行之前，需要對(duì)算法參數(shù)進(jìn)行設(shè)置，主要包括以下幾個(gè)方面：

（1）種群大小 N

（2）編碼串長(zhǎng)度 l

（3）交叉概率 pc

本文設(shè)計(jì)的交叉概率與適應(yīng)度值相關(guān)聯(lián)，當(dāng)個(gè)體適應(yīng)度值大于種群平均適應(yīng)度值時(shí)，應(yīng)盡量保留該優(yōu)秀個(gè)體，pc值應(yīng)較小，反之則應(yīng)較大，具體計(jì)算公式為：

式（4）中，fmax為種群最佳個(gè)體適應(yīng)度值，favg為種群平均適應(yīng)度值，f為兩個(gè)要交叉?zhèn)€體中較大的適應(yīng)度值，k1、k2為交叉概率調(diào)整系數(shù)，取k1=k2=1。

（4）終止條件

設(shè)定如果進(jìn)化達(dá)到最大代數(shù)N或者當(dāng)溫度降低到給定終止溫度Te時(shí)，算法終止，停止進(jìn)化，返回最優(yōu)解。

（5）初始溫度 T0

初始溫度影響全局搜索能力，溫度越高搜索能力越強(qiáng)，但所用時(shí)間也越長(zhǎng)。在實(shí)際車間調(diào)度問題中，T0的取值公式為：

式中，fmax、fmin分別為初始種群中個(gè)體適應(yīng)度值的最大值和最小值，r取10。

（6）退溫函數(shù)

退溫函數(shù)采用指數(shù)函數(shù)的方式進(jìn)行退溫，能夠保證后期緩慢降溫，退溫函數(shù)為：

式中，T0為初始溫度，降溫系數(shù)a取0.9，k為循環(huán)次數(shù)。

2.5 遺傳退火算法流程

遺傳退火算法的設(shè)計(jì)步驟如下：

步驟一：建立目標(biāo)函數(shù)，確定適應(yīng)度函數(shù)。

步驟二：初始化算法參數(shù)：種群大小N、交叉概率 pc、初始溫度 T0、降溫系數(shù) a。

步驟三：編碼產(chǎn)生初始種群P0，令i=0，k=0。

步驟四：采用賭輪法選擇個(gè)體，按照自適應(yīng)交叉概率pc執(zhí)行交叉操作，更新存儲(chǔ)器中的f*和p*，生成新的臨時(shí)種群S。

步驟五：新的臨時(shí)種群S作為模擬退火算法的初始種群，對(duì)種群中各個(gè)個(gè)體進(jìn)行模擬退火操作，計(jì)算種群中染色體適應(yīng)度，更新存儲(chǔ)器中的f*和p*。

步驟六：判斷是否滿足終止條件，如是，則輸出最優(yōu)解并結(jié)束算法；否則轉(zhuǎn)步驟四。

遺傳退火算法的流程如圖2所示。

圖2 遺傳退火算法流程

3 實(shí)驗(yàn)結(jié)果及分析

3.1 調(diào)度問題理想狀態(tài)甘特圖

為驗(yàn)證算法的有效性，采用Job-shop benchmark基準(zhǔn)問題做對(duì)比。本文采用FT06基準(zhǔn)問題數(shù)據(jù)來驗(yàn)證遺傳退火算法的有效性。算法初始運(yùn)行參數(shù)設(shè)置為：種群規(guī)模N=50，交叉概率pc=0.7，初始溫度T0=100℃，終止溫度Te=0.01℃，降溫系數(shù)a=0.9，最大迭代次數(shù)G=100。整理后得到6×6調(diào)度問題基礎(chǔ)數(shù)據(jù)，整理后數(shù)據(jù)如表3所示。

表3 6×6調(diào)度問題基礎(chǔ)數(shù)據(jù)表

根據(jù)本文設(shè)計(jì)的GASA算法運(yùn)行結(jié)果，得到其中一個(gè)最優(yōu)染色體為[5 6 1 2 6 3 4 1 6 4 3 5 1 4 5 6 4 1 5 2 6 5 1 3 2 4 5 6 1 2 3 2 3 4 2 3]。通過GASA算法得到的最優(yōu)染色體需要的加工時(shí)間為55秒，對(duì)于FT06問題，6×6規(guī)模的最優(yōu)目標(biāo)函數(shù)值f*=55，因此達(dá)到該問題最優(yōu)解，驗(yàn)證了算法的有效性。最優(yōu)解調(diào)度甘特圖如圖3所示。算法收斂曲線如圖4所示。

圖3 最優(yōu)解調(diào)度甘特圖

圖4 算法收斂曲線

從圖4中可以看出，經(jīng)過50次迭代后，遺傳退火算法最終收斂，得到的最優(yōu)適應(yīng)度值為55。表明改進(jìn)遺傳退火算法有較快的搜索速度和較高的搜索精度。為更直觀的比較GASA算法、GA算法和SA算法，分別對(duì)基準(zhǔn)問題進(jìn)行求解，得到它們的收斂曲線，如圖5所示。

圖5 三種算法收斂對(duì)比圖

從圖5可看出，SA算法和GASA算法都能達(dá)到最優(yōu)解，但分別在76代和50代時(shí)完成收斂找到最優(yōu)值，表明改進(jìn)模擬退火算法收斂速度更快，并且SA算法在迭代初期波動(dòng)幅度很大，而GASA算法由于在算法中加入了最優(yōu)解存儲(chǔ)器，能夠保證適應(yīng)度值一直往最優(yōu)化方向發(fā)展。對(duì)比GA算法和GASA算法，可以看出GA算法在19代時(shí)完成收斂，但并未達(dá)到全局最優(yōu)解，表明GA算法在進(jìn)化過程中容易陷入“早熟”，得到局部最優(yōu)解。綜上所述，遺傳退火算法在進(jìn)化過程中收斂平滑，收斂速度適中，全局最優(yōu)解搜索能力強(qiáng)，能夠克服遺傳算法易早熟的缺點(diǎn)，又能克服模擬退火算法波動(dòng)幅度大搜索速度慢的缺點(diǎn)，驗(yàn)證了算法的有效性和優(yōu)越性，符合本文設(shè)計(jì)目標(biāo)。

3.2 實(shí)際情況下調(diào)度甘特圖

上文給出的最優(yōu)解是在理想狀態(tài)下得到的，但在實(shí)際生產(chǎn)過程中經(jīng)常出現(xiàn)各種干擾因素，如電子企業(yè)經(jīng)常出現(xiàn)臨時(shí)插單的情況。為應(yīng)對(duì)該情況，本文將臨時(shí)訂單到來時(shí)刻作為再調(diào)度的初始時(shí)刻，將臨時(shí)插單數(shù)據(jù)輸入到初始時(shí)刻，對(duì)于在此刻加工的產(chǎn)品及工序不做打擾，對(duì)產(chǎn)品未完成的工序進(jìn)行再調(diào)度。例如，在圖3理想狀態(tài)調(diào)度甘特圖時(shí)刻為30min時(shí)，出現(xiàn)臨時(shí)訂單，需要優(yōu)先加工產(chǎn)品J7，要求該產(chǎn)品必須在30分鐘之內(nèi)加工完成，其基礎(chǔ)數(shù)據(jù)如表4所示。

表4 臨時(shí)插單產(chǎn)品基礎(chǔ)數(shù)據(jù)表

按照臨時(shí)插單調(diào)度優(yōu)先的規(guī)則，若不采取再調(diào)度，則每位員工在該產(chǎn)品經(jīng)過自己工序時(shí)，需要優(yōu)先加工該產(chǎn)品，此時(shí)的總加工時(shí)間為66min，產(chǎn)品J7加工完成時(shí)刻為56min，加工用時(shí)26分鐘，其甘特圖如圖6所示。采取臨時(shí)插單再調(diào)度后，產(chǎn)品總加工時(shí)間為63min，產(chǎn)品J7加工完成時(shí)刻為60min，加工用時(shí)30分鐘，在滿足30分鐘內(nèi)加工完成這一約束性目標(biāo)的前提下，使各產(chǎn)品總加工時(shí)間最小化，其甘特圖如圖7所示。

圖6 未采用臨時(shí)插單的調(diào)度甘特圖

圖7 采用臨時(shí)插單的調(diào)度甘特圖

理想狀態(tài)最優(yōu)調(diào)度甘特圖適用于客戶對(duì)交貨期不做更改的情況，但在實(shí)際生產(chǎn)過程中，部分客戶可能在加工階段對(duì)產(chǎn)品交貨期做出改變，此時(shí)需要在原調(diào)度方案的基礎(chǔ)上，改變員工加工產(chǎn)品的順序，以滿足產(chǎn)品交貨期更改需求。例如客戶在時(shí)刻為30min時(shí)對(duì)產(chǎn)品J3期望交貨期提出修改，將該產(chǎn)品交貨期提前至[45，50]之間，進(jìn)行再調(diào)度后，產(chǎn)品J3的加工完成時(shí)刻提前至46min，其調(diào)度甘特圖如圖8所示。

圖8 交貨期提前的調(diào)度甘特圖

4 總結(jié)

本文針對(duì)電子裝配車間自動(dòng)化水平低、生產(chǎn)以人工加工裝配為主的實(shí)際生產(chǎn)情況，適應(yīng)物聯(lián)制造建設(shè)需要，研適用于人工生產(chǎn)的智能排程方法。首先對(duì)車間生產(chǎn)調(diào)度問題進(jìn)行分析并建立多目標(biāo)調(diào)度模型。其次根據(jù)模型設(shè)計(jì)了改進(jìn)遺傳退火算法，研究了算法實(shí)現(xiàn)的過程以及各參數(shù)的設(shè)定，并給出了遺傳退火算法的具體流程。最后利用Job-shop benchmark FT06基準(zhǔn)問題作對(duì)比，驗(yàn)證了改進(jìn)算法的有效性，給出了最優(yōu)解調(diào)度結(jié)果及其甘特圖。同時(shí)針對(duì)實(shí)際生產(chǎn)過程中出現(xiàn)的臨時(shí)插單和交貨期提前事件，給出了再調(diào)度方法及其甘特圖。排程計(jì)劃最終通過生產(chǎn)任務(wù)的派工執(zhí)行實(shí)現(xiàn)電子裝配企業(yè)員工生產(chǎn)效率的提升。