求解作業(yè)車間調(diào)度問(wèn)題的改進(jìn)遺傳算法①

陳金廣,馬玲葉,馬麗麗

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,西安 710048)

1 引言

作業(yè)車間調(diào)度問(wèn)題的求解目標(biāo)是得到一個(gè)科學(xué)、合理的調(diào)度方案.一個(gè)科學(xué)、合理的調(diào)度方案能夠有效提高生產(chǎn)效率、降低加工成本.調(diào)度方案主要是確定各工件的加工次序和加工機(jī)器,這是典型的NPhard 問(wèn)題[1].現(xiàn)代企業(yè)間的競(jìng)爭(zhēng)日趨激烈,合理安排作業(yè)車間調(diào)度至關(guān)重要.此外,工業(yè)工程中車間生產(chǎn)規(guī)模逐漸擴(kuò)大,作業(yè)車間調(diào)度越來(lái)越復(fù)雜,作業(yè)車間調(diào)度的組合改進(jìn)問(wèn)題已成為當(dāng)今工業(yè)工程領(lǐng)域發(fā)展研究的熱點(diǎn)問(wèn)題之一[2].作業(yè)車間調(diào)度(JSP)都是憑借著工人的工作經(jīng)驗(yàn)來(lái)安排工件的加工順序,然而這種方法不僅對(duì)工人要求較高,且會(huì)出現(xiàn)安排不合理的情況.啟發(fā)式研究方法可以很好的解決這類問(wèn)題,常用的主流求解方法有粒子群優(yōu)化算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、禁忌搜索算法等[3-8].其中遺傳算法(Genetic Algorithm,GA)作為一種群智能算法,具有隱式并行性和全局搜索特性,是求解作業(yè)車間調(diào)度問(wèn)題的有力工具,因此遺傳算法被很多學(xué)者用來(lái)解決作業(yè)車間調(diào)度問(wèn)題,其在柔性作業(yè)車間(FJSP)的應(yīng)用最為廣泛.根據(jù)FJSP的特點(diǎn),劉瓊等[9]提出了一種改進(jìn)的交叉變異方法并設(shè)計(jì)了一種初始解產(chǎn)生機(jī)制.張國(guó)輝等[10]采用一種隨機(jī)和優(yōu)化相結(jié)合的初始化種群方法.趙詩(shī)奎等[11]運(yùn)用均勻設(shè)計(jì)原對(duì)遺傳算法中的初始種群及適應(yīng)度函數(shù)進(jìn)行設(shè)計(jì)并將其應(yīng)用到FJSP 中.對(duì)于上述3 篇文獻(xiàn),交叉和變異概率均是通過(guò)多次試驗(yàn)和前人經(jīng)驗(yàn)給定,沒(méi)有采用自適應(yīng)的方法確定.Kacem 等[12]和Zhang 等[13]分別提出了基于時(shí)間表和機(jī)器時(shí)間數(shù)組的機(jī)器指派法,取得了較好的成效,然而,這兩種方法都是基于單步優(yōu)化指派機(jī)器,最終的指派結(jié)果沒(méi)有定量的全局性衡量指標(biāo),不能保證最終機(jī)器指派結(jié)果的質(zhì)量.不同類型的作業(yè)車間所需的調(diào)度方法不同,對(duì)于JSP,何斌等研究了自適應(yīng)交叉與變異概率提高了算法的尋優(yōu)能力和收斂速度,但其染色體總數(shù)僅根據(jù)初始種群數(shù)決定,染色體多樣性低[14].李春廷等通過(guò)改變遺傳算法編碼研究以及遺傳算子的設(shè)計(jì)證明其算法的有效性,但其實(shí)驗(yàn)時(shí)交叉、變異概率難以確定[15].

綜上所述,對(duì)于作業(yè)車間調(diào)度問(wèn)題存在著染色體多樣性低,收斂速度慢,遺傳參數(shù)難以確定的問(wèn)題.對(duì)此本文提出了一種改進(jìn)后的遺傳算法來(lái)解決作業(yè)車間調(diào)度問(wèn)題.改進(jìn)后的遺傳算法在初始化時(shí)能夠適當(dāng)擴(kuò)大種群,在迭代過(guò)程中運(yùn)用更易區(qū)分染色體的適應(yīng)度函數(shù)計(jì)算染色體的適應(yīng)度值,并且運(yùn)用能夠自適應(yīng)改變交叉和變異概率的算子調(diào)整概率值.實(shí)驗(yàn)結(jié)果表明改進(jìn)后的遺傳算法更適用于作業(yè)車間調(diào)度.

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

在作業(yè)車間中有一批待加工工件,這批待加工工件中有n個(gè)不同的工件,每個(gè)工件均包含m道工序,需要在m臺(tái)機(jī)器上加工.加工這批工件需要同時(shí)滿足以下幾點(diǎn)約束條件:

1)所有工件的工序之間都有順序約束,即同一工件的各工序間有先后順序,需按照工序順序進(jìn)行加工;

2)不同工件的加工工序之間沒(méi)有順序約束;

3)每道工序只能在一臺(tái)機(jī)器上加工;

4)各工件工序的加工時(shí)間由對(duì)應(yīng)的加工機(jī)器確定;

5)在同一時(shí)刻車間中的同一機(jī)器只能加工一道工序;

6)一道工序同一時(shí)刻只能在一臺(tái)機(jī)器上加工,且不能中途中斷;

7)不同工件之間優(yōu)先級(jí)是相同的;

8)不考慮機(jī)器故障等隨機(jī)性因素.

本文求解目標(biāo)為確定每臺(tái)機(jī)器上工序的加工順序和每個(gè)工序的開(kāi)工時(shí)間,使得最大完工時(shí)間 最小.優(yōu)化目標(biāo)函數(shù)如式(1)所示:

式中,Cmax表示最大完成時(shí)間,Cik表示工件i在機(jī)器k上的完工時(shí)間.

3 改進(jìn)算法設(shè)計(jì)

3.1 染色體編碼

遺傳算法的基因編碼方式有很多種,如浮點(diǎn)數(shù)編碼、二進(jìn)制編碼、整數(shù)編碼、符號(hào)編碼、矩陣編碼等[16].基因編碼在算法中起著至關(guān)重要的作用,編碼的方式直接影響遺傳算法的運(yùn)行速度以及能否找到全局最優(yōu)解[17].對(duì)于作業(yè)車間問(wèn)題,本文采用基于工序的實(shí)數(shù)編碼來(lái)表示染色體[18],一個(gè)編碼后的染色體代表一個(gè)車間調(diào)度問(wèn)題的調(diào)度方案.

對(duì)于n個(gè)不同工件在m臺(tái)機(jī)器上加工的作業(yè)車間調(diào)度問(wèn)題,采用基于工序的編碼方式編碼后,每條染色體均含有n×m個(gè)基因,染色體的基因順序?qū)?yīng)所有工件工序的加工順序,即一條染色體代表一個(gè)車間調(diào)度問(wèn)題的調(diào)度方案.每條染色體的基因表示如下:每個(gè)工件號(hào)在染色體中只能出現(xiàn)m次;從染色體的第一個(gè)基因位到最后一個(gè)基因位依次遍歷,若同一工件號(hào)出現(xiàn)第k次則表示為此工件的第k道工序,如染色體[3 3 2 1 2 1],其中第一個(gè)3 代表3號(hào)工件的第一道工序,第二個(gè)3 代表3號(hào)工件的第二道工序,以此類推.

3.2 種群初始化

首先給定種群的初始值p;然后根據(jù)作業(yè)車間一道工序只在一臺(tái)機(jī)器上加工的特點(diǎn),生成一個(gè)有n×m個(gè)基因的染色體;最后調(diào)用randperm 函數(shù)處理生成的染色體,使其循環(huán)p次,得到一個(gè)初始種群.

3.3 染色體適應(yīng)度值

本文的優(yōu)化目標(biāo)是最小化最大完成時(shí)間,因此最大完成時(shí)間越小的染色體越優(yōu)良.染色體的適應(yīng)度值是用來(lái)區(qū)分染色體間的優(yōu)劣程度,染色體越優(yōu)良適應(yīng)度值越大,被選中的概率越大,染色體越差適應(yīng)度值越低,被選中的概率越低.為了更好的體現(xiàn)遺傳算法優(yōu)勝劣汰的準(zhǔn)則,本文采用新的計(jì)算染色體適應(yīng)度值的方法,使染色體間的區(qū)分度更加明顯,優(yōu)良染色體被選中的概率大.

假設(shè)現(xiàn)有4 個(gè)工件,其加工完成時(shí)間分別為[20,21,22,23],利用取最大完成時(shí)間倒數(shù)方法得到的適應(yīng)度值分別為[0.05,0.0476,0.0454,0.0425],改進(jìn)后的算法得到的適應(yīng)度值分別為[1,0.6308,0.2923,0].從這兩組適應(yīng)度值可看出,這樣設(shè)定適應(yīng)度值可以讓最大完成時(shí)間小的染色體被多次選擇,最大完成時(shí)間最大的染色體被少選擇或者不被選擇,拉開(kāi)了染色體間差距,保障了對(duì)優(yōu)良染色體的選擇,比前者獲得優(yōu)良染色體的概率更大.

適應(yīng)度函數(shù)如式(2)所示,最大完工時(shí)間的倒數(shù)如式(3)所示:

式(2)、式(3)中,i為初始種群中的任意一條染色體,Max表示h(i)的最大值,Min表示h(i)的最小值.

在確定好各染色體的適應(yīng)度值后在采用輪盤(pán)賭[19]的方法選擇初始種群中的染色體.

3.4 交叉與變異

交叉操作可以增加種群的多樣性,提高算法的搜索能力,有利于產(chǎn)生優(yōu)秀的染色體,即有利于產(chǎn)生優(yōu)秀的作業(yè)車間調(diào)度方案.鑒于優(yōu)先工序交叉法POX (Precedence Operation Crossover)能夠很好地繼承父代優(yōu)良特征并且子代總是可行的這一特點(diǎn),本文選擇POX 進(jìn)行交叉操作[20],具體步驟如下所述:

步驟1.按順序依次選擇種群中的一條染色體作為父代1 即Parent1,隨機(jī)選擇種群中的一條染色體作為父代2 即Parent2;

步驟2.將工件集{1,2,3,…,n}隨機(jī)劃分為兩個(gè)非空子集j1,j2;

步驟3.將Parent1和Parent2 中包含j1={2}工件號(hào)分別按其在染色體中的位置復(fù)制到子代1 即Children1和子代2 即Children2 中,將Parent1和Parent2 中包含j1={2}工件號(hào)分別按其在染色體中的順序復(fù)制到Children2和Children1 中;Children1和Children2 這兩條染色體即為交叉后的染色體.如Parent1={3,2,2,3,1,1},Parent2={1,1,3,2,2,3},對(duì)工件集{1,2,3}隨機(jī)劃分生成j1={2},j2={3,1},經(jīng)過(guò)POX 交叉后得到Children1={1,2,2,1,3,3},Children2={3,3,1,2,2,1}.

變異操作是小概率發(fā)生的,它能夠?qū)θ旧w產(chǎn)生較小的擾動(dòng)來(lái)增加種群的多樣性,從而產(chǎn)生更能滿足目標(biāo)函數(shù)要求的調(diào)度方案.交叉后的染色體在進(jìn)行小概率的變異操作,可得到新的染色體,保持種群多樣性.為了保證新得到的染色體編碼是可調(diào)度的,避免將不可行調(diào)度轉(zhuǎn)換成可行調(diào)度,減少代碼運(yùn)行時(shí)間,本文采用互換法(Reciprocal Exchange Mutation,REM)進(jìn)行變異操作[21].對(duì)一個(gè)染色體隨機(jī)選擇兩個(gè)基因號(hào),將兩個(gè)基因號(hào)上對(duì)應(yīng)的工件號(hào)進(jìn)行互換,循環(huán)i次后可得到變異后的染色體.

3.5 交叉與變異概率

交叉和變異概率影響著交叉操作和變異操作的發(fā)生,當(dāng)交叉和變異概率大于由rand 函數(shù)在(0,1)之間隨機(jī)產(chǎn)生的值時(shí),染色體發(fā)生交叉、變異.

標(biāo)準(zhǔn)遺傳算法的交叉和變異概率通常都是固定不變的值,一般根據(jù)前人經(jīng)驗(yàn)給定或者根據(jù)實(shí)驗(yàn)結(jié)果給定,當(dāng)給定的值較小時(shí)會(huì)使搜索范圍變小,不利于尋找更優(yōu)解;而當(dāng)給定值較大時(shí)則可能導(dǎo)致已有的優(yōu)良染色體在交叉和變異操作后變差;在實(shí)驗(yàn)中容易出現(xiàn)早熟問(wèn)題,即未成熟收斂.本文確定交叉和變異概率值時(shí)采用文獻(xiàn)[22]提出的自適應(yīng)改變交叉和變異概率的方法,該算法能夠在種群進(jìn)化初期提高進(jìn)化能力,降低陷入局部最優(yōu)的風(fēng)險(xiǎn),避免早熟問(wèn)題的出現(xiàn),解決了參數(shù)難以確定的問(wèn)題.自適應(yīng)交叉概率函數(shù)如式(4)所示,自適應(yīng)變異概率函數(shù)如式(5)所示:

式(4)、式(5)中,gmax表示當(dāng)前種群中所有染色體的最大適應(yīng)度值;gavg表示當(dāng)前種群中所有染色體的平均適應(yīng)度值;為兩個(gè)交叉染色體中適應(yīng)度值較大的值;g表示選中的變異染色體的適應(yīng)度值.算法中k1,k2,k3,k4的值在(0,1)范圍中選擇即可.

4 仿真實(shí)驗(yàn)

程序運(yùn)行平臺(tái)為MacOS10.13.6 操作系統(tǒng)上的Matlab_R2018a 軟件,用標(biāo)準(zhǔn)遺傳算法和改進(jìn)算法分別對(duì)測(cè)試用例庫(kù)中的FT06和LA01 這兩個(gè)用例進(jìn)行實(shí)驗(yàn).FT06是一個(gè)6×6的測(cè)試用例,即共有6 個(gè)工件,每個(gè)工件都有6 個(gè)加工工序,FT06的工件工序集J=[3,1,2,4,6,5;2,3,5,6,1,4;3,4,6,1,2,5;2,1,3,4,5,6;3,2,5,6,1,4;2,4,6,1,5,3];加工FT06 各個(gè)工序所需時(shí)間集T=[1,3,6,7,3,6;8,5,10,10,10,4;5,4,8,9,1,7;5,5,5,3,8,9;9,3,5,4,3,1;3,3,9,10,4,1];LA01是一個(gè)10×5的測(cè)試用例,即共有10 個(gè)工件,每個(gè)工件都有5 個(gè)加工工序,LA01的工件工序集J=[2,1,5,4,3;1,4,5,3,2;4,5,2,3,1;2,1,5,3,4;1,4,3,2,5;2,3,5,1,4;4,5,2,3,1;3,1,2,4,5;4,2,5,1,3;5,4,3,2,1];加工LA01 各個(gè)工序所需時(shí)間集T=[21,53,95,55,34;21,52,16,26,71;39,98,42,31,12;77,55,79,66,77;83,34,64,19,37;54,43,79,92,62;69,77,87,87,93;38,60,41,24,83;17,49,25,44,98;77,79,43,75,96].

此次實(shí)驗(yàn)涉及到標(biāo)準(zhǔn)遺傳算法和對(duì)標(biāo)準(zhǔn)遺傳算法的種群初始化,適應(yīng)度函數(shù),交叉、變異概率的確定進(jìn)行優(yōu)化后得到的遺傳算法.根據(jù)多次實(shí)驗(yàn)以及前人實(shí)驗(yàn)結(jié)果,標(biāo)準(zhǔn)遺傳算法的參數(shù)設(shè)置為:迭代次數(shù)為200,種群總大小為100,交叉概率為0.9,變異概率為0.05;改進(jìn)后的遺傳算法參數(shù)設(shè)置為:迭代次數(shù)為200,種群總大小為100,在初始化時(shí)將種群總大小擴(kuò)大為原來(lái)的2 倍,以增加染色體的多樣性,并且由于改進(jìn)算法中交叉和變異概率是自適應(yīng)調(diào)節(jié)的,無(wú)需直接指定,由式(4)和式(5)確定,優(yōu)化后的遺傳算法參數(shù)設(shè)置為迭代次數(shù)為200,種群總大小為100,k1=k2=0.9,k3=k4=0.1.運(yùn)行20 次后,圖1和圖2分別為使用標(biāo)準(zhǔn)遺傳算法與改進(jìn)后的遺傳算法求解FT06和LA01 得到的最優(yōu)解值.

從圖1和圖2中可知,在20 次實(shí)驗(yàn)中,改進(jìn)后的遺傳算法得到的最優(yōu)解都優(yōu)于標(biāo)準(zhǔn)遺傳算法得到的最優(yōu)解,證明改進(jìn)后的遺傳算法的尋優(yōu)能力強(qiáng)于標(biāo)準(zhǔn)遺傳算法.分析總結(jié)圖1、圖2中的數(shù)據(jù),結(jié)合每次實(shí)驗(yàn)得到的迭代過(guò)程圖,得到結(jié)果對(duì)比表如表1所示.

圖1 FT06 基準(zhǔn)案例最優(yōu)解

圖2 LA01 基準(zhǔn)案例最優(yōu)解

表1 基準(zhǔn)案例(FT06,LA01)結(jié)果對(duì)比表

從表1可看出,用FT06 基準(zhǔn)案例驗(yàn)證時(shí),標(biāo)準(zhǔn)算法求得的最優(yōu)解為59,20 次實(shí)驗(yàn)中有2 次求得59,所得解均值是61.5,當(dāng)求得最優(yōu)解為59 時(shí),最優(yōu)迭代次數(shù)為3,平均迭代次數(shù)為11.6;改進(jìn)算法求得的最優(yōu)解為55,20 次實(shí)驗(yàn)中有12 次求得55,所得解均值為56.2,當(dāng)求得最優(yōu)解為55 時(shí),最優(yōu)迭代次數(shù)為10,平均迭代次數(shù)為38.05;用LA01 基準(zhǔn)案例驗(yàn)證時(shí),標(biāo)準(zhǔn)算法求得的最優(yōu)解為740,20 次實(shí)驗(yàn)中有1 次求得740,所得解均值為774.35,當(dāng)求得最優(yōu)解為740 時(shí),最優(yōu)迭代次數(shù)為4,平均迭代次數(shù)為8.4;改進(jìn)算法求得的最優(yōu)解為666,20 次實(shí)驗(yàn)中有14 次求得最優(yōu)解,最優(yōu)解平均值為671.3,當(dāng)求得最優(yōu)解為666 時(shí),最優(yōu)迭代次數(shù)為18,平均迭代次數(shù)為76.6.

由此可以看出,改進(jìn)后的遺傳算法得到的最優(yōu)解優(yōu)于標(biāo)準(zhǔn)遺傳算法,解決了標(biāo)準(zhǔn)算法的早熟問(wèn)題;同時(shí)在進(jìn)行20 次實(shí)驗(yàn)后,改進(jìn)后的算法得到最優(yōu)解的次數(shù)分別為12和14 次大于標(biāo)準(zhǔn)算法得到最優(yōu)解的次數(shù),解決了標(biāo)準(zhǔn)算法的解的穩(wěn)定性差問(wèn)題.

運(yùn)用標(biāo)準(zhǔn)遺傳算法對(duì)不同基準(zhǔn)案例進(jìn)行驗(yàn)證時(shí),可能需要不同的交叉和變異參數(shù)來(lái)提高算法的收斂速度和搜索能力.而交叉和變異概率難以確定,一般由實(shí)驗(yàn)經(jīng)驗(yàn)或者參考前人的參數(shù)設(shè)計(jì)給出,給定后的值固定不變.對(duì)于標(biāo)準(zhǔn)遺傳算法只改進(jìn)適應(yīng)度函數(shù)后進(jìn)行實(shí)驗(yàn)驗(yàn)證,給定交叉概率為0.9,變異概率為0.05,實(shí)驗(yàn)結(jié)果如表2所示.

表2 改進(jìn)適應(yīng)度函數(shù)后的實(shí)驗(yàn)結(jié)果表

對(duì)比表1,表2可知,表2中迭代次數(shù)均大于表1中本文算法對(duì)應(yīng)的迭代次數(shù).由此可知,改進(jìn)算法中的自適應(yīng)交叉和變異概率提高算法的收斂速度.

由參考文獻(xiàn)[23]可知,FT06的最優(yōu)解為55,LA01的最優(yōu)解為666.結(jié)合結(jié)果分析可知,不論是FT06 基準(zhǔn)案例還是LA01 基準(zhǔn)案例,改進(jìn)算法均能得到與基準(zhǔn)案例最優(yōu)解相同的解,并且在20 次實(shí)驗(yàn)中,改進(jìn)算法得到最優(yōu)解的次數(shù)分別為12和14 次,均高于標(biāo)準(zhǔn)算法;改進(jìn)算法在得到最優(yōu)解時(shí),其迭代次數(shù)分別為10和18,相比于只改進(jìn)尋優(yōu)能力后得到的最優(yōu)解時(shí)的迭代次數(shù),改進(jìn)算法可以提高收斂速度.

用FT06和LA01 驗(yàn)證改進(jìn)后的遺傳算法,生成的遺傳代數(shù)圖和甘特圖分別如圖3～圖6所示.由圖4可知每臺(tái)機(jī)器上的工序順序,以及加工完所有工件花費(fèi)的最少加工時(shí)間55,由圖3可知得到此調(diào)度方案只迭代了10 次;由圖6可知每臺(tái)機(jī)器上的工序順序,以及加工完所有工件花費(fèi)的最少加工時(shí)間666,由圖5可知得到此調(diào)度方案只迭代了18 次.仿真結(jié)果表明改進(jìn)后的遺傳算法比標(biāo)準(zhǔn)遺傳算法收斂速度快,所得解更穩(wěn)定,遺傳參數(shù)較易確定.相較于文獻(xiàn)[14,15],優(yōu)化后的遺傳算法的收斂速度更優(yōu),交叉和變異概率采用自適應(yīng)交叉、變異函數(shù)確定,解決了參數(shù)難以確定的問(wèn)題,證實(shí)了改進(jìn)后遺傳算法的有效性和可靠性.

圖3 FT06 遺傳代數(shù)圖

圖4 FT06 甘特圖

圖5 LA01 遺傳代數(shù)圖

圖6 LA01 甘特圖

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

以最小化最大完成時(shí)間為優(yōu)化目標(biāo),對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn),以求解目標(biāo)問(wèn)題的最優(yōu)解.在初始化時(shí)擴(kuò)大種群數(shù)量以增加種群多樣性,采用的適應(yīng)度函數(shù)可以增加染色體區(qū)分度,使用POX 算法完成交叉操作,產(chǎn)生的子代可以很好地繼承父代優(yōu)良特征并且子代總是可行,交叉和變異概率采用自適應(yīng)交叉和變異概率,概率可根據(jù)染色體適應(yīng)度值自動(dòng)調(diào)整.通過(guò)對(duì)FT06和LA01 進(jìn)行仿真實(shí)驗(yàn),所得的實(shí)驗(yàn)結(jié)果表明改進(jìn)后的遺傳算法解決了標(biāo)準(zhǔn)遺傳算法中參數(shù)難以確定,早熟收斂,所得解不穩(wěn)定的問(wèn)題,提高算法的尋優(yōu)能力和收斂速度,比標(biāo)準(zhǔn)遺傳算法更適用于作業(yè)車間生產(chǎn).對(duì)于柔性作業(yè)車間調(diào)度問(wèn)題,其每道工序可以在多臺(tái)機(jī)床上加工,并且在不同的機(jī)床上加工所需時(shí)間不同,因此本文算法不適用于柔性作業(yè)車間的調(diào)度問(wèn)題,下一步將研究能夠處理柔性作業(yè)車間的調(diào)度問(wèn)題.