考慮調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題研究*

張國(guó)輝，朱寶英，楊洋洋，孫靖賀

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 FJSP的染色體編碼和解碼

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

圖1 染色體編碼

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

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

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

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

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

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

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

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

(5)

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

ta+Adjustmenti+Tijh≤TEi

(6)

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

(7)

2.2 FJSP的初始化方法

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

2.3 FJSP的交叉和變異

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

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

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

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

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

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

(4)結(jié)束。

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

(9)

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

2.4 算法流程

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

圖2 算法流程圖

3 實(shí)例仿真

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

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

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

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

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

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

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

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

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

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

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