基于改進(jìn)遺傳算法的多目標(biāo)優(yōu)化生產(chǎn)調(diào)度模型

郭　梅，李西興

(1.山西北方晉東化工有限公司，山西 陽(yáng)泉 045000；2.湖北工業(yè)大學(xué) 機(jī)械工程學(xué)院，湖北 武漢 430068)

隨著計(jì)算機(jī)科學(xué)和信息技術(shù)的不斷發(fā)展，制造物聯(lián)網(wǎng)、云計(jì)算、大數(shù)據(jù)和智能制造等先進(jìn)制造技術(shù)和管理思想不斷被提出和應(yīng)用，特別是中國(guó)制造2025戰(zhàn)略為中國(guó)制造企業(yè)指明了發(fā)展方向。作為訂單任務(wù)制造執(zhí)行過(guò)程管理和控制的關(guān)鍵問(wèn)題——生產(chǎn)調(diào)度問(wèn)題(production scheduling problem，PSP)一直是機(jī)械制造企業(yè)中管理者最為關(guān)心的，它屬于NP(nondeterminism polynomial)問(wèn)題[1]。目前，隨著管理科學(xué)、計(jì)算機(jī)科學(xué)和信息科學(xué)等相關(guān)學(xué)科的不斷發(fā)展，眾多專家學(xué)者從不同的方面對(duì)生產(chǎn)調(diào)度問(wèn)題開(kāi)展了針對(duì)性的研究[2-3]，主要包括生產(chǎn)調(diào)度模型的構(gòu)建與優(yōu)化、生產(chǎn)調(diào)度目標(biāo)的求解(包括一般算法和優(yōu)化算法)、生產(chǎn)調(diào)度平臺(tái)的設(shè)計(jì)開(kāi)發(fā)和應(yīng)用[4-6]。筆者在已有研究的基礎(chǔ)上，以機(jī)械制造企業(yè)作為研究背景，

首先分析了企業(yè)內(nèi)部在生產(chǎn)制造執(zhí)行過(guò)程中存在的生產(chǎn)調(diào)度問(wèn)題，其次構(gòu)建了基于成本、平均完工時(shí)間和延遲概率的多目標(biāo)生產(chǎn)調(diào)度優(yōu)化模型，并對(duì)傳統(tǒng)遺傳算法加以改進(jìn)作為模型的求解算法，最后通過(guò)實(shí)例驗(yàn)證模型和算法的有效性。

1　機(jī)械制造企業(yè)關(guān)鍵零部件生產(chǎn)調(diào)度問(wèn)題分析

1.1　機(jī)械生產(chǎn)流程分析

當(dāng)前機(jī)械制造企業(yè)的生產(chǎn)模式主要是按訂單制造(make-to-order，MTO)，企業(yè)根據(jù)內(nèi)部以及外部現(xiàn)有生產(chǎn)資源制定生產(chǎn)計(jì)劃，安排生產(chǎn)加工，在制作過(guò)程中會(huì)遇到機(jī)器故障、人員調(diào)整等突發(fā)事件，此時(shí)生產(chǎn)調(diào)度將決定下一步工作任務(wù)的完成方式與路線，具體的生產(chǎn)流程如圖1所示。

圖1　機(jī)械制造企業(yè)生產(chǎn)流程

1.2　生產(chǎn)調(diào)度問(wèn)題分析

在生產(chǎn)管理中首先要根據(jù)現(xiàn)有資源來(lái)合理調(diào)度主要零部件的生產(chǎn)加工任務(wù)，目前主要存在的調(diào)度問(wèn)題有以下幾個(gè)方面：

(1)調(diào)度信息不及時(shí)，傳遞不準(zhǔn)確；

(2)調(diào)度次數(shù)多，周期有效性短；

(3)調(diào)度柔性不足；

(4)調(diào)度標(biāo)準(zhǔn)不統(tǒng)一。

當(dāng)前市場(chǎng)競(jìng)爭(zhēng)環(huán)境變得越來(lái)越激烈和復(fù)雜，客戶的個(gè)性化需求也越來(lái)越突出，這對(duì)企業(yè)整體的生產(chǎn)管控結(jié)構(gòu)帶來(lái)重要影響，傳統(tǒng)的管控方法不再適合。面對(duì)這種情況，機(jī)械制造企業(yè)對(duì)于生產(chǎn)管控的變更將更依賴于訂單產(chǎn)品的準(zhǔn)時(shí)交貨率和訂單產(chǎn)品的利潤(rùn)率，二者之間是相輔相成的。因此針對(duì)上述問(wèn)題筆者將從以下兩個(gè)方面開(kāi)展研究：

(1)構(gòu)建面向機(jī)械制造企業(yè)的基于生產(chǎn)成本、平均完工時(shí)間和延遲概率的多目標(biāo)生產(chǎn)調(diào)度優(yōu)化模型；

(2)引入一種基于聚類(lèi)輪盤(pán)賭選擇方法的雙階段遺傳因子改進(jìn)遺傳算法(improved genetic algorithm，IGA)來(lái)求解該生產(chǎn)調(diào)度優(yōu)化模型。

2　生產(chǎn)調(diào)度優(yōu)化模型的構(gòu)建

2.1　模型假設(shè)條件

針對(duì)上面提到的問(wèn)題，筆者提出基于生產(chǎn)成本、平均完工時(shí)間和延遲概率的多目標(biāo)生產(chǎn)調(diào)度優(yōu)化模型，在構(gòu)建優(yōu)化模型前作出如下假設(shè)：

(1)訂單任務(wù)信息、加工設(shè)備信息、人員信息和其他基本信息在制定生產(chǎn)調(diào)度時(shí)(假設(shè)為0時(shí)刻)都是已知的；

(2)每一個(gè)加工設(shè)備一次最多只能加工一個(gè)零部件，且一旦開(kāi)始加工某一零部件必須完成加工后才能繼續(xù)加工該零部件的下道工序或者是其他零部件的某道工序；

(3)每一個(gè)零部件一次最多只能被一個(gè)加工設(shè)備加工；

(4)每一個(gè)零部件包含若干道加工工序，且工藝路線一旦確定就不得更改；

(5)零部件在各個(gè)設(shè)備之間運(yùn)輸、裝夾、卸載時(shí)零部件的大小不做考慮，只考慮對(duì)應(yīng)時(shí)間；

(6)不同零部件之間沒(méi)有加工優(yōu)先級(jí)之分；

(7)加工設(shè)備的損耗成本(即折舊成本)在該優(yōu)化模型中不作考慮。

2.2　優(yōu)化模型的建立

筆者構(gòu)建基于總生產(chǎn)成本TC、平均完工時(shí)間ACT和延遲概率DP的多目標(biāo)優(yōu)化模型F，這樣既滿足客戶交貨期的需求，又符合企業(yè)的自身利益。根據(jù)構(gòu)建模型時(shí)的假設(shè)條件，構(gòu)建數(shù)學(xué)模型如下:

F=Wtc×TC+Wact×ACT+Wdp×DP

(1)

式中：Wtc、Wact和Wdp分別為T(mén)C、ACT和DP的權(quán)重值，并滿足Wtc+Wact+Wdp=1。

(1)將總生產(chǎn)成本劃分為工序成本PC、運(yùn)輸成本TrC、延期成本DC。

TC=PC+TrC+DC

(2)

其中，工序成本PC主要是針對(duì)機(jī)械零部件在機(jī)加工的過(guò)程中常用到的工序備、車(chē)、銑、磨、鏜、鉆、煮黑、噴丸、油漆等工序中產(chǎn)生的成本。在計(jì)算工序成本時(shí)常采用基于工時(shí)的計(jì)算方式，即以技術(shù)部給定的加工工時(shí)乘以企業(yè)內(nèi)部規(guī)定的單元工時(shí)價(jià)格。因此工序成本的計(jì)算公式如下：

(3)

pijk=λ×pjk

(4)

式中：n為零件數(shù)；m為工序數(shù)；pijk為零部件i的第j道工序在加工設(shè)備k上的加工成本；pjk為零部件i的第j道工序在加工設(shè)備k上的單位加工成本。

運(yùn)輸成本TrC主要包括兩方面：一方面是零部件在不同加工設(shè)備間加工時(shí)會(huì)造成零部件的轉(zhuǎn)運(yùn)，從而引起轉(zhuǎn)運(yùn)成本，規(guī)定單位轉(zhuǎn)運(yùn)成本是固定不變的，在進(jìn)行轉(zhuǎn)運(yùn)工作時(shí)不考慮零部件的大小，只考慮轉(zhuǎn)運(yùn)距離；另一方面是零部件的裝夾和卸載成本，規(guī)定零部件的裝夾和卸載的單位成本是固定不變的，在進(jìn)行裝夾和卸載工作時(shí)不考慮零部件的大小，只考慮裝夾和卸載的總時(shí)間。運(yùn)輸成本的計(jì)算公式如下：

(5)

(6)

Lijk=Timeijk×Unit_L

(7)

由于在實(shí)際的生產(chǎn)加工過(guò)程中會(huì)出現(xiàn)臨時(shí)訂單、機(jī)器故障、人員調(diào)整等情況，從而造成原加工任務(wù)中部分任務(wù)的延期完工，延期完工將給企業(yè)帶來(lái)延期成本，延期成本的計(jì)算公式如下：

(8)

Delayi=ceil((CTi-OTi)/8)

(9)

s.t. 如果Delayi<0,則Delayi=0；否則Delayi值不變。

式中：Delayi為零部件i的延期時(shí)間；“8”為企業(yè)規(guī)定的每天8小時(shí)工作時(shí)間長(zhǎng)度(由于企業(yè)中在計(jì)算延期成本時(shí)通常是以天作為延期單位，而零部件的完工時(shí)間是以小時(shí)為單位，因此為了將完工時(shí)間小時(shí)轉(zhuǎn)換為天，采用公式(9))；CTi為零部件i的實(shí)際完工時(shí)間，OTi為零部件i的規(guī)定完工時(shí)間；Unit_Di為零部件i的單位延期成本；ceil(x)為取整函數(shù)，輸出結(jié)果為比x大的最小整數(shù)。

平均完工時(shí)間是所有加工任務(wù)的整體加工時(shí)間之和除以加工任務(wù)的數(shù)量，具體如下：

(10)

延遲概率是指延遲總加工任務(wù)數(shù)除以加工任務(wù)的數(shù)量，具體如下：

(11)

s.t.如果Delayi=0,則qi=0，否則qi=1。

3　基于聚類(lèi)輪盤(pán)賭選擇方法的雙階段遺傳因子改進(jìn)遺傳算法

遺傳算法是根據(jù)自然界的“優(yōu)勝劣汰”的規(guī)則首次由J.Holland教授提出，基本思想是將每一代較優(yōu)的個(gè)體保存到下一代中，這樣在規(guī)定的求解代數(shù)后將獲得近似最優(yōu)解。筆者提出利用聚類(lèi)輪盤(pán)賭選擇方法來(lái)求解初始化種群，保證了初始化種群的多樣性，同時(shí)針對(duì)過(guò)早收斂和容易陷入局部最優(yōu)解的問(wèn)題，筆者提出分段遺傳算子，即在實(shí)際的計(jì)算過(guò)程中若連續(xù)Ncontinuous代沒(méi)有產(chǎn)生新個(gè)體時(shí)，將分別改變遺傳算子的值，從而進(jìn)一步提高種群的多樣性，降低優(yōu)良基因丟失的可能性。具體的改進(jìn)遺傳算法流程如圖2所示。

3.1　基于聚類(lèi)輪盤(pán)賭選擇方法的種群初始化方法

傳統(tǒng)的輪盤(pán)賭選擇方法是一類(lèi)基本的隨機(jī)選擇法，它容易引起算法的過(guò)早收斂和陷入最優(yōu)解，聚類(lèi)輪盤(pán)賭的思想，即將個(gè)體按照其適應(yīng)度值的大小進(jìn)行分組，然后按照傳統(tǒng)輪盤(pán)賭的基本思想進(jìn)行選擇，降低某一類(lèi)超級(jí)個(gè)體的數(shù)量，保證初始種群的多樣性，初始種群數(shù)定義為Initial_Pop。

(1)依據(jù)個(gè)體適應(yīng)度值的大小對(duì)初始化種群進(jìn)行分組，分組的個(gè)數(shù)即聚類(lèi)數(shù)H，滿足公式gen=CF1∪CF2∪…∪CFH，同時(shí)以隨機(jī)率參數(shù)rH設(shè)定對(duì)應(yīng)的初始聚類(lèi)中心(f1,f2,…,fH)；

(2)對(duì)于群體中的每一個(gè)體按照個(gè)體與聚類(lèi)中心之間相鄰距離最近的原則分別對(duì)每一個(gè)個(gè)體進(jìn)行聚類(lèi)，如果fi-fh=min|fi-fh|,fh∈(f1,f2,…,fH)，則i∈CFh；

(4)如果新的聚類(lèi)中心與上一個(gè)聚類(lèi)中心相同，則輸出H個(gè)聚類(lèi)，否則轉(zhuǎn)步驟(2)。

3.2　編碼和解碼

根據(jù)優(yōu)化模型的需求，采用基于待加工任務(wù)編號(hào)、加工工序編號(hào)、加工設(shè)備編號(hào)的混合十進(jìn)制編碼方法，具體編碼和解碼規(guī)則說(shuō)明如表1所示。編碼和解碼示例如表2所示。

表2中給出了3個(gè)零部件相應(yīng)的加工工序、工藝線路以及滿足條件的加工設(shè)備和對(duì)應(yīng)加工時(shí)間的編碼樣式。

表1　編碼和解碼規(guī)則說(shuō)明

表2　編碼和解碼示例說(shuō)明

在解碼時(shí)，根據(jù)染色體編碼時(shí)的規(guī)則解讀相應(yīng)的數(shù)據(jù)信息，如一個(gè)染色體G1124表示零部件1的第1道工序在加工設(shè)備2上進(jìn)行加工，需要消耗的加工時(shí)間為4 min。

3.3　適應(yīng)度函數(shù)

適應(yīng)度函數(shù)主要是為了評(píng)估個(gè)體的優(yōu)劣性而設(shè)定的，通常它是根據(jù)目標(biāo)函數(shù)演化而來(lái)，在本文中由于目標(biāo)函數(shù)F是最小化多目標(biāo)優(yōu)化問(wèn)題，且各目標(biāo)單位不同，因此在設(shè)定適應(yīng)度函數(shù)時(shí)要對(duì)其進(jìn)行標(biāo)準(zhǔn)統(tǒng)一化，如式(12)所示。

f(x)=F=Wtc×TC(x)′+

Wact×ACT(x)′+Wdp×DP(x)′

(12)

(13)

式中：TCm、ACTm和DPm為同一代中所有樣本染色體的均值；TCs、ACTs和DPs為同一代中所有樣本染色體的標(biāo)準(zhǔn)差。

3.4　遺傳算子

遺傳算子主要包含選擇算子(selection operator，SO)、交叉算子(crossover operator，CO)和變異算子(mutation operator，MO)，主要作用是保證個(gè)體的多樣性，降低算法陷入局部搜索的概率。

選擇算子SO采用聚類(lèi)輪盤(pán)賭的方法對(duì)個(gè)體進(jìn)行選擇操作，其中選擇概率定義為ps。

交叉算子CO對(duì)不同染色體的單個(gè)或多個(gè)相同基因位進(jìn)行交叉重組，生成新的染色體，其中交叉概率定義為pc，筆者采用優(yōu)先級(jí)交叉操作方法完成父代個(gè)體(Parent)交叉生成新的子代個(gè)體(Offspring)，具體過(guò)程如圖3所示。

圖3　交叉算子

變異算子MO對(duì)于染色體的基因位進(jìn)行變異重組生產(chǎn)新個(gè)體，但變異的范圍必須在染色體原有基因范圍內(nèi)，其中變異概率定義為pm，且pm的值通常小于pc，筆者采用翻轉(zhuǎn)變異方法實(shí)現(xiàn)染色體的變異操作，如圖4所示。

圖4　變異算子

3.5　終止條件

由于多目標(biāo)優(yōu)化求解過(guò)程中很難獲得最優(yōu)解，通常都是以近似最優(yōu)解作為最終輸出，因此為了防止避免算法求解過(guò)程中的不斷循環(huán)，常設(shè)定算法最大迭代次數(shù)max_Iterations，當(dāng)算法的實(shí)時(shí)迭代次數(shù)gen大于max_Iterations時(shí)算法跳出循環(huán)，算法終止并輸出近似最優(yōu)解。即終止條件為：

gen>max_Iterations

(14)

4　算法實(shí)例

為了驗(yàn)證模型和算法的有效性，首先搭建基于Matlab2013a的仿真模型，同時(shí)根據(jù)某機(jī)械制造企業(yè)的實(shí)際生產(chǎn)調(diào)度情況進(jìn)行實(shí)例驗(yàn)證。在機(jī)械制造中，關(guān)鍵零部件的生產(chǎn)加工對(duì)于整機(jī)的裝配完工和發(fā)貨有著重要影響，文中表3、表4和表5分別對(duì)應(yīng)著工序基礎(chǔ)信息、零部件基礎(chǔ)信息和算法參數(shù)。由于同種類(lèi)型加工設(shè)備(和工序類(lèi)別一致)通常放置在相同加工車(chē)間中，因此它們之間的距離可以忽略不計(jì)，即不考慮同種類(lèi)型加工設(shè)備之間的運(yùn)輸成本。表6中的距離表示不同類(lèi)型加工設(shè)備之間的距離，同時(shí)對(duì)于單位轉(zhuǎn)運(yùn)成本Unit_T和單位裝卸成本Unit_L分別設(shè)定為0.05元/m和0.1元/min。

表3　加工工序基礎(chǔ)信息

表4　零部件基礎(chǔ)信息

表5　算法參數(shù)設(shè)定

表6　加工設(shè)備之間距離　m

為了盡可能的獲取到最優(yōu)解，對(duì)算法進(jìn)行了20次測(cè)試，得出最優(yōu)適應(yīng)度值為1.462，平均求解耗時(shí)為7.74 s，具體的收斂曲線如圖5所示，圖6列出了對(duì)應(yīng)的Gantt圖。筆者在傳統(tǒng)遺傳算法的基礎(chǔ)上分別引入聚類(lèi)輪盤(pán)賭方法和分段遺傳因子方法，表7列出了單一聚類(lèi)遺傳算法(Cluster-GA)和傳統(tǒng)遺傳算法(Traditional-GA)的對(duì)比結(jié)果，同時(shí)與粒子群算法(PSO)進(jìn)行對(duì)比，各自對(duì)應(yīng)的進(jìn)化曲線如圖5所示。首先聚類(lèi)輪盤(pán)賭選擇方法比傳統(tǒng)的隨機(jī)初始化方法和單一輪盤(pán)賭選擇方法提供了更優(yōu)的初始化種群個(gè)體，在保證初始種群多樣性的同時(shí)確保相對(duì)最優(yōu)種群個(gè)體的數(shù)量；其次利用分段遺傳算子方法可以降低算法迭代過(guò)程中陷入局部最優(yōu)解的可能性，并且最大限度地避免全局近似最優(yōu)解的丟失，使得IGA在求解的速度和有效性方面更好。為了更好的與以上3種算法作比較，應(yīng)用方差分析法的理論來(lái)驗(yàn)證各個(gè)算法對(duì)應(yīng)的可靠性，通過(guò)置信水平值為5% 的LSD(least-significant difference，最小顯著性差異法)來(lái)分析各個(gè)方法的差異，結(jié)果如圖7所示，IGA方法的可靠性優(yōu)于其他3種方法。

圖5　收斂曲線對(duì)比分析

圖6　近似最優(yōu)解Gant圖

算法最優(yōu)解計(jì)算時(shí)間/s獲取最優(yōu)解代數(shù)最優(yōu)解比例/%Traditional-GA[7]1.26110.436040Cluster-GA[8]1.4138.636470IGA1.4627.748480PSO[9]1.4337.987770

圖7　置信度評(píng)估

5　結(jié)論

由于機(jī)械制造企業(yè)的生產(chǎn)模式發(fā)生了變化，為了快速響應(yīng)市場(chǎng)變化更好地滿足客戶個(gè)性化需求，首先分析了當(dāng)前企業(yè)的生產(chǎn)流程及生產(chǎn)調(diào)度中存在的問(wèn)題，其次構(gòu)建了基于生產(chǎn)成本、平均加工時(shí)間和延遲概率的多目標(biāo)優(yōu)化調(diào)度模型，提出基于聚類(lèi)輪盤(pán)賭的雙遺傳因子的改進(jìn)遺傳算法，并對(duì)模型進(jìn)行求解，最后通過(guò)實(shí)例數(shù)據(jù)測(cè)試和對(duì)比分析，證明了該方法的有效性和可行性。該理論模型和算法的特點(diǎn)和優(yōu)勢(shì)包括以下兩個(gè)方面：

(1)客戶滿意度和生產(chǎn)成本是當(dāng)前機(jī)械制造企業(yè)關(guān)注的重點(diǎn)，因此該模型以訂單任務(wù)中關(guān)鍵零部件的平均加工時(shí)間、生產(chǎn)成本和延遲概率作為優(yōu)化目標(biāo)，滿足企業(yè)的實(shí)際要求；

(2)傳統(tǒng)遺傳算法存在容易過(guò)早收斂和陷入局部最優(yōu)解的缺點(diǎn)，筆者分別通過(guò)應(yīng)用分段遺傳算子和聚類(lèi)輪盤(pán)賭的種群初始化方法來(lái)解決上述問(wèn)題，從而獲取了更好的近似最優(yōu)解。

參考文獻(xiàn)：

[1]Liang Gao, Guohui Zhang, Liping Zhang, et al. An Efficient Memetic Algorithm for Solving the Job Shop Scheduling Problem[J]. Computers & Industrial Engineering, 2011,60:699-705.

[2]劉瓊,張超勇,饒運(yùn)清，等.改進(jìn)遺傳算法解決柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].工業(yè)工程與管理，2009,14(2):59-65.

[3]巴黎,李言,曹源,等.考慮批量裝配的柔性作業(yè)車(chē)間調(diào)度問(wèn)題研究[J].中國(guó)機(jī)械工程，2015,26(23):3200-3207.

[4]楊曉梅，曾建潮.遺傳算法求解柔性Job-Shop調(diào)度問(wèn)題[J].控制與決策，2004,19(10):1197-1200.

[5]張鐵男,韓兵,于渤.生產(chǎn)能力約束條件下的柔性作業(yè)車(chē)間調(diào)度優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐,2011,31(3):505-509.

[6]張國(guó)輝,黨世杰.遺傳算法求解低碳柔性作業(yè)車(chē)間生產(chǎn)調(diào)度問(wèn)題[J].組合機(jī)床與自動(dòng)化加工技術(shù),2016(11):141-143.

[7]Alebachew D Yimer, Kudret Demirli. A Genetic Approach to Two-phase Optimization of Dynamic Supply Chain Scheduling[J]. Computers & Industrial Engineering, 2010,58:411-422.

[8]杜百崗,郭順生,彭兆,等.集團(tuán)制造多主體外協(xié)訂單任務(wù)制造資源配置[J].計(jì)算機(jī)集成制造系統(tǒng),2015,21(2):455-466.

[9]祁文博,郭順生,趙國(guó)，等.改進(jìn)初始化方法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].數(shù)字制造科學(xué)，2017，15(4)：192-196.