張國輝，朱寶英，楊洋洋，孫靖賀

(鄭州航空工業(yè)管理學(xué)院，鄭州 450015)

0 引言

隨著社會的發(fā)展人們對個性化的需求越來越高，車間加工方式越來越呈現(xiàn)多品種小批量的趨勢，車間管理的柔性化、精細(xì)化程度不斷提高[1-2]。傳統(tǒng)柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem, FJSP)進(jìn)行優(yōu)化時將調(diào)整時間、加工時間等時間作為整體或僅考慮加工時間。根據(jù)福特汽車公司的統(tǒng)計，在實際加工過程中，工件的安裝與定位、機(jī)器的調(diào)整、工作臺的清掃與清屑等時間占總加工時間的90%以上。輔助性的調(diào)整時間和加工時間需要作為獨(dú)立因素同時進(jìn)行考慮，以提高優(yōu)化后調(diào)度方案的有效性。

目前針對柔性作業(yè)車間調(diào)度問題的研究文獻(xiàn)很多，集中在以加工時間為對象的多目標(biāo)調(diào)度、動態(tài)調(diào)度等[3-4]，然而考慮到工件調(diào)整時間，并將其與加工時間作為獨(dú)立因素同時考慮的文獻(xiàn)極少。文獻(xiàn)[5]針對單機(jī)調(diào)度問題提出帶調(diào)整時間加權(quán)成套訂單數(shù)排序問題并采用遺傳算法進(jìn)行求解。文獻(xiàn)[6]將調(diào)度問題轉(zhuǎn)化為經(jīng)典的旅行商問題，并采用基于優(yōu)先級的比例選擇、實數(shù)兩點交叉及模式變異算子的改進(jìn)遺傳算法對含有調(diào)整時間的作業(yè)車間調(diào)度問題求解。文獻(xiàn)[7]提出通過改變工序調(diào)度次序前移存在調(diào)整時間綜合調(diào)度工序的算法，實現(xiàn)提高設(shè)備利用率，提前產(chǎn)品最終完工時間。文獻(xiàn)[8]提出了一種考慮調(diào)整時間的作業(yè)車間調(diào)度與預(yù)防性維修集成方法。文獻(xiàn)[9]以拖期最小為目標(biāo)優(yōu)化含調(diào)整時間的柔性作業(yè)車間調(diào)度問題。文獻(xiàn)[10]采用禁忌搜索算法求解帶有調(diào)整時間的柔性作業(yè)車間調(diào)度問題。

本文將調(diào)整時間與加工時間作為獨(dú)立影響因素進(jìn)行考慮，通過對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，在進(jìn)行解碼時提出考慮調(diào)整時間的活動調(diào)度解碼方案、自適應(yīng)函數(shù)進(jìn)行交叉和變異，實現(xiàn)對求解過程的快速尋優(yōu)。運(yùn)用Matlab編程對實驗數(shù)據(jù)進(jìn)行測試，實驗結(jié)果進(jìn)一步驗證了考慮工件調(diào)整時間的柔性作業(yè)車間調(diào)度模型更加符合實際生產(chǎn)情況。

1 帶調(diào)整時間的FJSP模型建立

帶調(diào)整時間的FJSP問題數(shù)學(xué)模型的描述及定義為：工件集J={J1,J2,J3,…,Jg,…Jn}，Jg是第g個工件(g=1,2,3,…,n)；機(jī)器集M={M1,M2,M3,…,Mi,…,Mm},Mi是第i臺機(jī)器(i=1,2,3,…,m)；Ojh是工件j的第h道工序，并定義Oj(h-1)為第Ojh的上一道工序，Oj’h’表示為Ojh所在機(jī)器的前一道工序；Pjh表示工件j的第h道工序加工完成時間；Tijh表示工件j的第h道工序在機(jī)器i上加工時所需要的時間；Sijh表示為工件j的第h道工序在機(jī)器i上的加工開始時間；Cijh表示為工件j的第h道工序在機(jī)器i上的加工結(jié)束時間；Installtimei表示在機(jī)器Mi安裝、定位等調(diào)整時間；Cj表示為工件j的完工時間；Cmax表示為最大完工時間。在建立數(shù)學(xué)模型時，假設(shè)以下條件：

(1)所有機(jī)器在零時刻均可用，所有工件在零時刻均可被加工。

(2)任意一道工序只能在一臺機(jī)器加工，且工序在加工過程中不允許被中斷。

(3)任意一臺機(jī)器在同一時間僅能加工同一工件的同一道工序。

(4)不同工件之間沒有加工順序約束，同一工件的不同工序間有先后加工順序約束。

以最大完工時間最小為優(yōu)化目標(biāo)，其目標(biāo)函數(shù)及約束條件分別為：

Cmax=min(max1≤j≤n(Cj))

(1)

Cijh=Sijh+Tijh

(2)

Cijh-Cij′h′≥Tijh+Adjustmenti

(3)

(4)

式(1)表示總目標(biāo)函數(shù)，即最大完工時間最小化；式(2)表示工序加工的完成時間等于工序開始時間與工序加工時間之和；式(3)表示機(jī)器的資源約束，同一機(jī)器在同一時刻只能允許加工一個工件；式(4)表示如果工序所在機(jī)器的開始加工時間(空隙開始時間)小于上一道工序的調(diào)整時間，則受調(diào)整時間約束；否則(空隙開始時間大于上道工序結(jié)束時間)，加工工序受當(dāng)前加工機(jī)器的資源約束。所以，若某一工件的相鄰工序在同一機(jī)器上加工時，僅受機(jī)器資源約束；對于同一工件內(nèi)的相鄰兩道工序而言，考慮了調(diào)整時間，替代了傳統(tǒng)加工模型中的工序順序約束。為了方便理解，給出具體的柔性作業(yè)車間調(diào)度問題實例，如表1所示。

表1 部分柔性作業(yè)車間調(diào)度問題實例

2 改進(jìn)遺傳算法求解帶有調(diào)整時間的FJSP

2.1 FJSP的染色體編碼和解碼

在使用遺傳算法求解目標(biāo)問題時，編碼與解碼是遺傳算法首先要解決的問題，如前文所述，F(xiàn)JSP包含兩個子問題：機(jī)器選擇與工序排序。機(jī)器選擇是用來解決每道加工工序在可選機(jī)器集中選擇哪臺機(jī)器進(jìn)行加工；工序排序是用來解決所有工件在選擇完加工機(jī)器后，工序排序和開工時間的問題。采用文獻(xiàn)[11]中的編碼方式進(jìn)行編碼，將兩個子問題編碼到一條染色體上，即表示FJSP的一個可行解,見圖1。

圖1 染色體編碼

(1)機(jī)器選擇部分：該部分染色體長度為總工序數(shù)L，每個基因位用整數(shù)表示，從左到右依次按加工工件的工序順序排列，每個整數(shù)表示加工工件的當(dāng)前工序在可選擇的機(jī)器集中的順序編號。以表1為例，如圖1左半部分所示，該基因串為4-2-3-1-3-2，表示工序O11在可選加工機(jī)器集中第4個機(jī)器上進(jìn)行加工，即實際加工機(jī)器為M4；工序O12在可選加工機(jī)器集中第2個機(jī)器上進(jìn)行加工，即實際加工機(jī)器為M3，以此類推。

(2)工序排序部分：該部分染色體長度為總工序數(shù)L，每個基因用工件號進(jìn)行編碼，工件號出現(xiàn)的次數(shù)就表示該工件的工序數(shù)。如圖1右半部分所示，該基因串為2-1-2-1-2-1，對應(yīng)的加工工序為O21-O11-O22-O12-O23-O13。

在解碼過程中，由于染色體包含兩部分，即機(jī)器選擇子問題和工序排序子問題。首先對機(jī)器選擇進(jìn)行解碼：從左到右依次讀取機(jī)器部分染色體，并轉(zhuǎn)換到機(jī)器順序矩陣中和時間順序矩陣中。其次對工序排序進(jìn)行解碼：從左到右依次讀取工序染色體部分，根據(jù)機(jī)器選擇部分解碼得到的機(jī)器矩陣、加工時間矩陣以及調(diào)整時間矩陣，依次得到每個工件的加工工序所對應(yīng)的加工機(jī)器、加工時間以及調(diào)整時間。

為了確保染色體解碼后產(chǎn)生活動調(diào)度，本文提出考慮調(diào)整時間的工序左移插入式解碼方法。解碼原則如下：

(1)如果工件j的工序Ojh在機(jī)器Mi上是第一道工序，則直接從它的前一道工序Oj(h-1)加工完畢后即可進(jìn)行調(diào)整并加工工件；

(2)如果工件j兩道工序即工序Ojh與Oj(h-1)在相同的機(jī)器上進(jìn)行加工，并且兩道工序緊鄰，即它們之間沒有其它工件進(jìn)行加工，此時僅考慮一次調(diào)整時間；否則，分別考慮各自的調(diào)整時間；

(3)如果工序Ojh是工件j的第一道工序，那么直接從所在機(jī)器的零時刻開始調(diào)整工件然后加工即可。否則，從所在機(jī)器左邊開始查找所有空閑時間段[TSi,TEi]，TSi表示空閑時間段的開始時間，TEi表示空閑時間段的結(jié)束時間?？紤]到工件調(diào)整時間，按照式(5)得到工序Ojh最早加工開始時間ta，能滿足工件加工工序的順序約束。

ta=max{Pj(h-1),TSi}

(5)

按照式(6)判斷空閑間隔時間段能否滿足插入條件，如果滿足則插入到當(dāng)前空閑時間段中；否則，按照式(7)的時間tb在機(jī)器Mi上進(jìn)行加工，其中TMi表示當(dāng)前機(jī)器Mi最后一道加工工序的結(jié)束時間。以此類推，依次讀取工序部分染色體，直至染色體結(jié)束。

ta+Adjustmenti+Tijh≤TEi

(6)

tb=max{Pj(h-1),TMi}

(7)

2.2 FJSP的初始化方法

在使用遺傳算法求解目標(biāo)問題時，初始解的優(yōu)劣直接影響到算法的求解質(zhì)量和解的收斂速度。由于FJSP不僅要解決機(jī)器選擇問題，而且還要解決加工工序排序問題。針對FJSP這些特點，機(jī)器選擇部分采用文獻(xiàn)[11]提出的GLR機(jī)器選擇方法。該方法包括：隨機(jī)選擇(Radom Selection, RS)、局部選擇(Local Selection, LS)和全局選擇(Global Selection, GS)。為了保證初始種群的多樣性，增加種群的選擇性，使其在計算過程中不至于提前結(jié)束，工序排序部分采用隨機(jī)選擇(Radom Selection, RS)的初始化方法。

2.3 FJSP的交叉和變異

2.3.1 自適應(yīng)交叉算子

交叉操作是根據(jù)自然界生物交配的原則，對種群中的染色體隨機(jī)配對，以一定的概率交換種群之間的基因片段。在交叉過程中，以一定的方式交換兩個配對染色體的部分基因，產(chǎn)生兩個新的染色體。交叉方法包括：單點交叉法、兩點交叉法，多點交叉法，均勻交叉法等。依據(jù)本文研究的帶有調(diào)整時間FJSP問題特點，并滿足交叉時的計算效率和產(chǎn)生的染色體對所求問題的解的可行性。

機(jī)器選擇部分：為保證交叉后產(chǎn)生的基因的先后順序不變，采用均勻交叉法。

(1)在區(qū)間[1，L]內(nèi)隨機(jī)的產(chǎn)生一個整數(shù)r。

(2)根據(jù)隨機(jī)數(shù)r，隨機(jī)生成r個不等的整數(shù)。

(3)根據(jù)(2)產(chǎn)生的隨機(jī)整數(shù)r將父代染色體中的P1/P2中包含的基因復(fù)制到子代C1/C2中，保持順序和位置不變。

(4)父代染色體中的P1/P2中余下的基因復(fù)制到子代C2/C1中，保持順序和位置不變。

工序排序部分：采用改進(jìn)的順序交叉法，對每個染色體的多個工件進(jìn)行操作。更好的繼承的父代染色體中的優(yōu)良基因。

(1)父代染色體P1/P2隨機(jī)產(chǎn)生工件集Job。

(2)將父代染色體中的P1/P2中包含有Job的基因復(fù)制到子代中，保持順序和位置不變

(3)將另一個父代染色體P2/P1中刪除Job所包含的基因，按照從左到右的原則填入子代染色體中的空白基因位。

在交叉過程中本文采用自適應(yīng)交叉概率以提高優(yōu)良個體信息的保留。隨著種群迭代次數(shù)的增加，為了減少對優(yōu)良解個體信息的破壞，交叉概率逐漸降低。自適應(yīng)交叉概率公式為：

(8)

Pc表示自適應(yīng)交叉概率，Pc_max表示最大交叉概率CurInterStep表示當(dāng)前迭代次數(shù)，MaxIterStep表示最大迭代次數(shù)。

2.3.2 自適應(yīng)變異算子

變異操作是根據(jù)自然界生物變異的過程，以一定的概率改變種群增加種群的多樣性。以很小的概率來改變?nèi)旧w中基因的遺傳片段。

對于機(jī)器選擇部分，為保留優(yōu)良個體的信息，保證機(jī)器順序不被破壞。在變異染色體中隨機(jī)選擇r個位置。然后依據(jù)選擇的每一個位置，對其位置上的機(jī)器設(shè)置為當(dāng)前機(jī)器集中加工的時間最短的機(jī)器。

對于工序排序部分，本文采用鄰域搜索變異操作，即在變異過程中在鄰域范圍內(nèi)搜索產(chǎn)生多個子代，選擇其中性能較好的子代為變異后的個體。具體步驟如下：

(1)在[0，1]內(nèi)產(chǎn)生一個隨機(jī)數(shù)r，若r小于變異概率Pm，轉(zhuǎn)到(2)，否則轉(zhuǎn)到(4)；

(2)隨機(jī)在父代工序排序染色體中產(chǎn)生3個基因位，對此基因進(jìn)行排序，將每一個排序的結(jié)果作為該位置上子代的基因，得到另外5個子染色體；

(3)計算當(dāng)前6個染色體的適應(yīng)值，選取其中最優(yōu)的子染色體作為變異結(jié)果；

(4)結(jié)束。

本文采用自適應(yīng)變異計算方法來改善進(jìn)化性能，已達(dá)到盡量的保留較優(yōu)的個體。自適應(yīng)變異公式為：

(9)

Pm表示自適應(yīng)交叉概率，Pm_max表示最大交叉概率CurInterStep表示當(dāng)前迭代次數(shù)，MaxIterStep表示最大迭代次數(shù)。

2.4 算法流程

如圖2所示，為采用自適應(yīng)交叉算子和變異算子的遺傳算法流程圖。

圖2 算法流程圖

3 實例仿真

某模具公司的CNC生產(chǎn)車間是典型的柔性作業(yè)車間調(diào)度問題，在實際加工過程中，工件在不同機(jī)床上進(jìn)行加工時都存在安裝、定位等調(diào)整時間，在滿足工件工藝的前提下盡可能的縮短生產(chǎn)周期，并盡可能的提高設(shè)備利用率。

依據(jù)上述改進(jìn)的遺傳算法，采用Matlab7.0編程，運(yùn)行環(huán)境為P4 CPU，主頻1.9GHz，內(nèi)存4G的個人計算機(jī)。設(shè)置遺傳算法的主要參數(shù)如下：種群規(guī)模40，交叉概率Pc_max0.8，變異概率Pm_max0.6，最大迭代代數(shù)為100代。

表2表示某加工車間7個工件在6臺機(jī)器上的FJSP實例，表中括號外的數(shù)字表示該工序在對應(yīng)機(jī)器上的加工時間，括號中的數(shù)字表示工序在當(dāng)前加工機(jī)器上的調(diào)整時間，“-”表示該工件的工序不能在相對應(yīng)的機(jī)器上加工。例如，表2中O11與M2對應(yīng)的數(shù)值6表示工件J1的第一道工序在M2上的加工時間為6，調(diào)整時間為1。

表2 工件在機(jī)器上的加工時間和調(diào)整時間

圖3、圖4分別是在Matlab仿真平臺中通過改進(jìn)的遺傳算法對未考慮調(diào)整時間和考慮調(diào)整時間的柔性作業(yè)車間調(diào)度問題進(jìn)行運(yùn)算的輸出結(jié)果的甘特圖。圖3中的完工時間為37，圖4中的完工時間為55，可以明顯看出調(diào)整時間在實際生產(chǎn)過程對調(diào)度方案存在較大影響。圖3中不同的顏色代表不同的工件。圖4中淺灰色部分代表對應(yīng)工序在機(jī)器上的調(diào)整時間，其它顏色和圖3中一樣代表各道工序在相應(yīng)機(jī)器上的加工時間。對比兩圖可看出帶有調(diào)整時間的調(diào)度更復(fù)雜，更加符合實際機(jī)件加工，使柔性作業(yè)車間調(diào)度問題更加滿足實際需求。

圖3 未考慮調(diào)整時間的調(diào)度甘特圖

圖4 考慮調(diào)整時間的調(diào)度甘特圖

圖5 考慮調(diào)整時間FJSP求解過程收斂曲線

圖5為改進(jìn)遺傳算法求解帶調(diào)整時間的表1和表2問題時的收斂曲線。實現(xiàn)為每代中最優(yōu)解的迭代過程，虛線為每代種群中個體目標(biāo)值的平均值收斂過程。每代最優(yōu)解的收斂曲線是不斷下降，逐漸收斂到最終結(jié)果；而種群均值前期是快速下降，后期呈現(xiàn)波浪式的上下跳動，并沒有明顯的下降趨勢。這個問題也是后期研究工作中需要從問題本身特征進(jìn)行分析，設(shè)計更加符合問題本身的算法，使其能夠更快速的進(jìn)行收斂。

4 結(jié)束語

實際生產(chǎn)過程中，工件在加工設(shè)備上進(jìn)行加工時存在調(diào)整時間，為了能夠更有效的指導(dǎo)實際生產(chǎn)。本文將調(diào)整時間和加工時間作為獨(dú)立因素進(jìn)行考慮，以最大完工時間最小為優(yōu)化目標(biāo)，建立了考慮調(diào)整時間的柔性作業(yè)車間調(diào)度問題模型。通過對遺傳算法進(jìn)行改進(jìn)對提出的模型進(jìn)行求解，設(shè)計了考慮調(diào)整時間的工序左移插入式解碼方法，解碼成活動調(diào)度，提高算法運(yùn)行效率。最后，在Matlab仿真環(huán)境中對實際案例進(jìn)行運(yùn)算，通過對未考慮調(diào)整時間和考慮調(diào)整時間的結(jié)果比較，驗證了考慮調(diào)整時間的問題模型更加符合實際生產(chǎn)，同時也驗證了建立的模型和改進(jìn)的算法是可行的和有效的，能夠更有效的指導(dǎo)實際生產(chǎn)。