潘 穎，周柏城

（大連海洋大學(xué)機(jī)械與動(dòng)力工程學(xué)院，大連116023）

?

基于改進(jìn)遺傳算法的多目標(biāo)柔性車間調(diào)度問題研究

潘 穎，周柏城

（大連海洋大學(xué)機(jī)械與動(dòng)力工程學(xué)院，大連116023）

摘要：通過對車間生產(chǎn)調(diào)度的特點(diǎn)和算法的研究，建立了離散車間多目標(biāo)動(dòng)態(tài)調(diào)度的數(shù)學(xué)模型及設(shè)計(jì)了改進(jìn)的遺傳算法。以最大完工時(shí)間最短、總延期時(shí)間最小和設(shè)備總負(fù)荷最小這3個(gè)目標(biāo)作為車間生產(chǎn)優(yōu)化目標(biāo)調(diào)度模型。利用改進(jìn)的遺傳算法確定車間調(diào)度的最優(yōu)解。最后通過實(shí)例分析，驗(yàn)證了算法的可行性。

關(guān)鍵詞：車間調(diào)度；多目標(biāo)；遺傳算法

在當(dāng)今激烈的市場競爭中，為了增強(qiáng)企業(yè)的核心競爭力，企業(yè)就要對現(xiàn)有的生產(chǎn)管理方式進(jìn)行改善，而車間的生產(chǎn)調(diào)度更是生產(chǎn)管理的核心技術(shù)［1］。隨著專家學(xué)者對各類經(jīng)典車間調(diào)度問題的不斷的深入研究，相繼出現(xiàn)了許多經(jīng)典車間調(diào)度問題的新的理論與方法［2-6］，這些理論與方法對制造業(yè)生產(chǎn)車間調(diào)度的研究具有重要的研究意義，能夠提高制造業(yè)的生產(chǎn)效率，同時(shí)也能帶來經(jīng)濟(jì)利益。

本文建立了3個(gè)優(yōu)化目標(biāo)的車間生產(chǎn)調(diào)度模型，分別是最大完工時(shí)間最短、總延期時(shí)間最小和設(shè)備總負(fù)荷最小，通過改進(jìn)遺傳算法尋求車間調(diào)度的最優(yōu)解。最后通過車間調(diào)度案例，證實(shí)改進(jìn)的遺傳算法比傳統(tǒng)算法更可行。

1　柔性車間調(diào)度的模型建立

1.1柔性作業(yè)車間問題參數(shù)描述

多目標(biāo)柔性作業(yè)車間調(diào)度是指生產(chǎn)車間中在m臺(tái)設(shè)備上加工n個(gè)工件，每個(gè)工件包含ni個(gè)事先確定加工順序的工序，每個(gè)工序可以在多臺(tái)設(shè)備上加工。其建模應(yīng)用符號(hào)參數(shù)如下：

tijs：加工工件ji的第j步工序在s上設(shè)備的加工所需時(shí)間；

ETi：加工工件ji完成最后一步工序所需時(shí)間；

ETijs：加工工件ji的第j步工序在s設(shè)備上完成加工的時(shí)間；

DTi：工件ji的交貨時(shí)間；

Ttijs：工件ji的第j步工序在設(shè)備上的調(diào)整時(shí)間；

qs：設(shè)備s的故障率；

Xijs為0，1變量，如果工件ji的第j道工序在設(shè)備s上加工取值為1，否則為0；

其中，針對上述建模并做如下假設(shè)：

（1）所有設(shè)備一開始均處于正常狀態(tài)，沒有設(shè)備故障。

（2）工件完成上一道加工工序后，立即開始下一道加工工序，之前的設(shè)備處于空閑。

（3）加工一旦開始，就不能中斷，機(jī)器出現(xiàn)故障除外。

（4）已知不同工序在每臺(tái)設(shè)備上的調(diào)整時(shí)間

（5）工件在加工設(shè)備上的加工與裝卸時(shí)間都能確定，計(jì)入加工時(shí)間。

1.2目標(biāo)函數(shù)模型的建立

1.2.1目標(biāo)函數(shù)：

（1）最大完工時(shí)間最短：

minf1=min（maxETi）（1）

（2）總延期最小：

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

2.1染色體編碼

染色體編碼利用整數(shù)編碼方式，并對染色體進(jìn)行兩層編碼，分別是基于其加工工序編碼方式和加工設(shè)備的編碼方式，彌補(bǔ)了傳統(tǒng)遺傳算法采用單層編碼的基因多樣性和完整性不足的缺點(diǎn)。獲得到每條染色體長度是為工件數(shù)量，ni為第i個(gè)工件的工序數(shù)。染色體被分成前后兩個(gè)部分，前部分染色體對應(yīng)工件加工工序，后部分染色體對應(yīng)相應(yīng)的加工設(shè)備。

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

采用線性尺度轉(zhuǎn)換方法，其適應(yīng)度函數(shù)，轉(zhuǎn)換公式為：

2.3選擇

在Matlab的遺傳算法工具箱中，選擇里面的錦標(biāo)賽方法進(jìn)行函數(shù)選擇，選取最優(yōu)個(gè)體。首先經(jīng)過計(jì)算得出個(gè)體的序值，然后選擇序值相對較小的個(gè)體進(jìn)行遺傳傳給下一代。兩條個(gè)體的序值相同時(shí)，需要計(jì)算其擁擠距離，優(yōu)先選擇擁擠距離相對較大的個(gè)體進(jìn)行遺傳，以便保持種群個(gè)體基因的多樣性。

2.4交叉

交叉方法采用單點(diǎn)交叉，在種群中隨機(jī)選擇兩條染色體，通過前面染色體編碼相同的思路，獲取到前半部分的染色體，得知染色體長度是然后隨機(jī)設(shè)定一處交叉點(diǎn)進(jìn)行交叉。

2.5變異

2.6解碼

解碼方法采用方法是染色體全自動(dòng)動(dòng)解碼方法，在染色體的前半部分基因中，在子目標(biāo)中按照最大綜合權(quán)重大小對應(yīng)其工序排列，從而確定加工設(shè)備順序。根據(jù)染色體上各基因的排列順序，可以確定總體加工時(shí)間，并通過繪制甘特圖將完成的車間調(diào)度結(jié)果顯示出來。i和j，其數(shù)值在

3　實(shí)例應(yīng)用與分析

為了證明算法的可行性，本文對10×10算例進(jìn)行了分析。參數(shù)為：種群中個(gè)體數(shù)目m=500，種群進(jìn)化代數(shù)T=500，種群代溝G=0.8，交叉概率Pc=0.85，變異概Pm=0.1.表1所示。

表1　發(fā)動(dòng)機(jī)各零部件的工序可選擇的加工設(shè)備列表

改進(jìn)的算法比改進(jìn)前的算法加工時(shí)間提前。實(shí)例測試結(jié)果如圖1所示。

圖1　傳統(tǒng)遺傳算法發(fā)動(dòng)機(jī)零部件加工甘特圖

圖2　改進(jìn)遺傳算法發(fā)動(dòng)機(jī)零部件加工甘特圖

4　結(jié)束語

本文描述了離散車間多目標(biāo)動(dòng)態(tài)調(diào)度問題研究現(xiàn)狀并運(yùn)用遺傳算法來求解此類問題。通過基于遺傳算法的多目標(biāo)優(yōu)化算法實(shí)現(xiàn)了對離散車間多目標(biāo)組合最優(yōu)的選擇。染色體編碼采用基于工件加工工序和工件加工設(shè)備的兩層編碼方法，并通過實(shí)例分析，驗(yàn)證了本文算法的可行性，解決了離散車間多目標(biāo)調(diào)度問題。

參考文獻(xiàn)：

［1］曾強(qiáng)，沈玲，楊育，等.多目標(biāo)等量分批柔性作業(yè)車間調(diào)度集成優(yōu)化方法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（16）: 237-243.

［2］劉烽，游海，丁一鈞，等.基于NSGA2算法的混合流水車間多目標(biāo)調(diào)度問題研究［J］.人工智能及識(shí)別技術(shù)，2012，24（2）:86-87.

［3］謝皓，應(yīng)保勝，袁波.基于遺傳算法的路徑柔性作業(yè)車間調(diào)度優(yōu)化［J］.2012，12（2）:465-468.

［4］楊開兵，劉曉冰.流水車間成組工件調(diào)度問題的多目標(biāo)優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2012，12（12）:3343-3346.

［5］王碩，顧幸生.基于改進(jìn)蟻群算法的作業(yè)車間調(diào)度.青島科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，10（5）:489-494.

［6］曹巖，雷蕾，房亞東.蟻群算法在離散型車間派工中的應(yīng)用.西安工業(yè)大學(xué)學(xué)報(bào)（社科版），2011，12（7）:611-615.

Research on Multi-objective Flexible Job Shop Scheduling based on the Improved Genetic Algorithm

PAN Ying，ZHOU Bai-cheng
（Machanical Engineering Institute，Dalian Ocean University，Dalian 116023，China）

Abstract：Through the study of the characteristics and the workshop production scheduling algorithms，and a mathematical model of discrete shop scheduling and dynamic multi-objective design improved genetic algorithm.In the shortest makespan，the total delay time and the minimum total equipment load the smallest of these three goals as the workshop production scheduling model optimization goal.Improved genetic algorithm to determine the optimal shop scheduling.Finally，an example analysis to verify the feasibility of the algorithm.

Key words：job shop scheduling；multi-objective；genetic algorithm

中圖分類號(hào)：TH16

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-545X（2016）03-0266-02

收稿日期：2015-12-03

基金項(xiàng)目：大連海洋大學(xué)博士啟動(dòng)基金（SYBS2a01205）；國家科技支撐計(jì)劃“大連市制造業(yè)信息化科技示范工程”（2013BAF02B03-2）

作者簡介：潘穎（1977-），女，黑龍江雙鴨山人，博士，講師，研究方向?yàn)檐囬g調(diào)度，精益生產(chǎn)。