祁文博，郭順生，趙 國，許 磊

(武漢理工大學(xué) 機電工程學(xué)院，湖北 武漢 430070)

在經(jīng)典作業(yè)車間調(diào)度問題中，待加工工件通常包含多道工序，各道工序間的工藝加工順序是一定的，且只能在指定的一臺加工機器上進(jìn)行加工。然而在柔性作業(yè)車間調(diào)度問題中，待加工工件的各道工序可以在指定的多臺機器中的一臺上進(jìn)行加工，并且不同機器對應(yīng)的加工性能不同。相比兩種作業(yè)車間調(diào)度問題，后者減少了對加工工序的機器約束，擴大了調(diào)度問題的解空間，使得問題求解過程更加復(fù)雜。通常在實際生產(chǎn)過程中，柔性調(diào)度問題比經(jīng)典調(diào)度問題應(yīng)用范圍更廣，更符合實際生產(chǎn)情況。

通常，求解調(diào)度問題的方法分為兩類：精確求解法和近似求解法。精確方法主要包括數(shù)學(xué)規(guī)劃方法和分支定界法，精確求解法能得到唯一的全局最優(yōu)解，但其局限于小規(guī)模調(diào)度問題的求解，并且求解效率不高[1-2]。近似求解法主要包括優(yōu)先分派規(guī)則法、遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法[3-7]等，它能夠很快得到問題的解，但不能保證解是最優(yōu)的，適合大規(guī)模問題的求解，不過近似方法得到的解也能較好地滿足實際問題的需求。遺傳算法源自于生物遺傳學(xué)的基本規(guī)律，它通過模擬生物進(jìn)化的過程實現(xiàn)對實際問題的求解，具有較強的通用性和對問題解空間的并行搜索能力，得到了廣泛的應(yīng)用。筆者研究的是基于機器選擇柔性的作業(yè)車間調(diào)度問題，采用有效的編碼和解碼方式，提出了一種新的種群初始化方法，并設(shè)計了相應(yīng)的遺傳操作算子，改善了調(diào)度問題解的質(zhì)量和求解速度。

1 問題的描述

柔性作業(yè)車間的調(diào)度問題描述如下:n個工件在m臺機器上進(jìn)行加工，每個工件Ji(1≤i≤n)至少包含Li(Li≥1)道工序，每道工序的加工機器有多種不同選擇，調(diào)度問題的目標(biāo)是為所有待加工件的工序分配加工機器，并確定每臺機器上工序的加工順序，使目標(biāo)函數(shù)達(dá)到最優(yōu)，以滿足實際生產(chǎn)的需要。以一個3×5(3個工件在5臺機器上加工)的作業(yè)車間調(diào)度實例進(jìn)行分析，該實例工序加工時間表如表1所示。

表1 柔性作業(yè)車間工序加工時間表

注：“-”表示該工序不能選擇對應(yīng)的機器進(jìn)行加工。

求解柔性作業(yè)車間調(diào)度問題解的過程中，需要一定的評價指標(biāo)來對調(diào)度方案的優(yōu)劣進(jìn)行評價。筆者考慮兩種性能指標(biāo)：最大完工時間最小、最大機器負(fù)荷最小[8]。

(1)最大完工時間CM是指所有工件中，最后一道工序的完工時間。

minCM=min(max(Cji)) 1≤i≤n

(1)

式中：Cji為工件的完工時間；Ji為第i個工件。

(2)最大機器負(fù)荷WM是指每臺機器上加工時間最長的那臺機器。

minWM=min(max(Wk)) 1≤k≤m

(2)

式中：WK為機器k上最后一道工序的完工時間。

以上兩種性能指標(biāo)應(yīng)滿足如下假設(shè)條件：

(1)機器約束。同一臺機器在某一時刻只允許加工一個工件。

(2)工序約束。同一工件的工序間有先后順序之分；同一工序只允許被一臺機器加工且加工過程必須連續(xù)。

(3)其他約束。在加工過程中，機器的調(diào)整與設(shè)置時間和作業(yè)運輸時間獨立于工序順序且忽略不計，不考慮作業(yè)的取消、機器的崩潰和其他隨機性因素。

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

2.1 染色體編碼與解碼

結(jié)合機器柔性作業(yè)車間調(diào)度問題的特點，采用分層編碼方式對機器基因串和工序基因串進(jìn)行編碼，兩基因串的長度相等，都等于待加工工件的工序總數(shù)之和[9]。首先確定機器選擇基因串，將柔性調(diào)度問題轉(zhuǎn)化為經(jīng)典調(diào)度問題進(jìn)行求解。機器選擇基因串用來確定每道工序的加工機器，而工序選擇基因串用來確定每臺機器上工序的加工順序，從而確定出調(diào)度問題的解。

(1)對于機器選擇基因串，每一個基因位表示對應(yīng)工序可選機器集中的索引位置，如表1中工序O12可選機器集為{M2,M4}，若基因位為1，表示O12選擇機器M2，以此類推，如圖1所示。

圖1 工序基因串

(2)對于工序基因串，每個基因位表示工件號，基因串中相同工件號出現(xiàn)的次數(shù)表示該工件的工序總數(shù)。其中相同工件號在基因串中出現(xiàn)的位置順序表示該工件的工序間加工順序，不同工件號在基因串中出現(xiàn)的位置順序表示不同工件工序的加工順序。例如表1中工件號3第1次出現(xiàn)的位置表示工件3的第一道工序O31，以此類推，如圖2所示。

圖2 機器基因串

(3)解碼過程是將兩條基因串所包含的信息轉(zhuǎn)化為一個有序的工序表，然后對表中各工件的工序以最早開始加工時間逐一加工，得到加工系統(tǒng)的調(diào)度甘特圖。

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

適應(yīng)度函數(shù)是用來評價種群個體好壞的重要指標(biāo)，它決定了個體被遺傳到下一代種群的可能性大小。通過適應(yīng)度函數(shù)值的大小對個體進(jìn)行選擇，可以保證個體的優(yōu)良性狀被遺傳到下一代，從而使得種群的優(yōu)良基因得以延續(xù)[10]。適應(yīng)度函數(shù)具有單值、連續(xù)非負(fù)等特點，因此采用目標(biāo)函數(shù)的倒數(shù)作為評價個體好壞的適應(yīng)度函數(shù)，如式(3)所示。

(3)

式中：f1(x)、f2(x)分別為調(diào)度模型的目標(biāo)函數(shù)，因此式(3)可以表示成：

i=1,2,…,n;j=1,2,…,m。

(4)

式中：m為加工系統(tǒng)的機器數(shù)；n為工件數(shù)；α、β分別為最大完工時間Cmax、最大機器負(fù)荷Wmax性能指標(biāo)的權(quán)重比，且α+β=1。

2.3 生成初始種群

初始種群的生成方法是利用遺傳算法求解調(diào)度問題中的重要環(huán)節(jié)，它不僅決定了初始種群的質(zhì)量，還影響著算法的求解效率。目前，利用隨機法產(chǎn)生初始種群的情況較多，該方法產(chǎn)生初始種群的質(zhì)量一般不高，而且也沒有考慮加工機器的負(fù)荷平衡問題，致使獲得最優(yōu)解或近似最優(yōu)解的迭代次數(shù)增加[11]。筆者提出一種全局搜索和隨機生成相結(jié)合的方法產(chǎn)生問題初始解，該方法考慮了調(diào)度問題的最大完工時間和最大機器負(fù)荷兩個性能指標(biāo)，改進(jìn)了初始種群的質(zhì)量，平衡了加工機器的工作負(fù)荷。全局搜索方法和隨機生成法各占初始種群的50%比例。

(1)全局搜索法。新建一個數(shù)組，數(shù)組長度等于機器選擇基因串的長度，該數(shù)組用來存放對應(yīng)工件工序所選加工機器的加工時間。隨機選擇一個工件，從該工件的第一道工序開始，將可選加工機器的加工時間加到數(shù)組的對應(yīng)位置上，然后將加工時間最短的機器從數(shù)組中選擇出來并保留，再將數(shù)組的其它位置為零，依次類推直到該工件的所有工序選擇完畢為止。重復(fù)以上步驟，直到最后一個工件最后一道工序選擇完畢。而對于工序基因串一般采用隨機生成法，將所有加工工序?qū)?yīng)的工件號存入一個數(shù)組，然后每次隨機從數(shù)組中取出一個工件號，放入一個新的數(shù)組中，循環(huán)該操作直到生成工序基因串完畢為止。以表1數(shù)據(jù)為例，第一次隨機選擇的工件是J1，第二次隨機選擇到J2，則執(zhí)行過程如圖3所示。

圖3 全局搜索圖

(2)隨機生成法。以表1中的數(shù)據(jù)為例進(jìn)行說明，對工序基因串，首先為每個工件的每道工序隨機生成一個(0,1)之間的隨機數(shù)，然后將隨機數(shù)按照從小到大的順序進(jìn)行重新排序，按照工件號出現(xiàn)的次數(shù)得到相應(yīng)的工序加工順序，如圖4所示。

圖4 隨機法工序基因串

對機器基因串，為每個工件的每道工序隨機生成一個[0,1)之間的隨機數(shù)，如工序O21對應(yīng)的隨機數(shù)為0.629 5，它對應(yīng)的可加工機器為M1、M2、M3，由于0.629 5∈[1/3，2/3]，因此選擇機器M2進(jìn)行加工，如圖5所示。

圖5 隨機法生成機器基因串

2.4 選擇操作

選擇操作是按照一定的選擇概率從種群中將適應(yīng)度更高的個體選擇出來，使種群的優(yōu)良特性能夠遺傳到下一代，保證種群的質(zhì)量[12]。筆者采用錦標(biāo)賽選擇法和精英保留策略兩種方法選擇個體，錦標(biāo)賽選擇法首先要設(shè)定一個概率參數(shù)s(一般設(shè)為0.8)，然后從種群中隨機選擇兩個個體，同時產(chǎn)生一個0到1之間的一個隨機數(shù)r，如果這個隨機數(shù)小于概率參數(shù)，則選擇適應(yīng)度值高的個體，否則選擇較差個體。被選擇出來的個體需要放回到種群，重新參與選擇。精英保留策略是將種群中1%的最優(yōu)個體不經(jīng)過選擇操作直接進(jìn)入到下一代種群中。

2.5 交叉操作

交叉是將父代個體的部分遺傳信息進(jìn)行交換，以產(chǎn)生新的基因組合的子代。交叉操作使得子代有效繼承了父代中的優(yōu)良信息，也使子代產(chǎn)生了新的遺傳信息，是遺傳算法的重要操作。對機器選擇基因串和工序選擇基因串采用相同的交叉概率進(jìn)行操作，對機器選擇基因串采用均勻交叉，對工序選擇基因串采用POX交叉[13]。均勻交叉要求基因串的位置順序不變，隨機產(chǎn)生兩個交叉位，然后將父代染色體P1、P2的兩個交叉位基因遺傳到子代C1、C2中，最后將P1、P2染色體中的其余基因位復(fù)制到C2、C1染色體中。使用POX交叉方法，首先將全部工件隨機劃分為兩個工件集Js1和Js2，復(fù)制父代個體P1和P2中包含在工件集Js1和Js2中的工件到C1/C2，保持子代個體基因位的位置和順序與父代相同，然后將父代P1、P2中不包含在工件集Js1、Js2中的工件復(fù)制到C2/C1，保持它們的順序不變。

2.6 變異操作

變異操作是對基因串中某些基因位進(jìn)行改變，以增強種群基因的多樣性，改善算法的局部搜索能力[14]。筆者針對機器選擇部分和工序排序部分分別設(shè)計變異算子。對于可選機器集元素數(shù)目大于2的加工工序，隨機選擇一個不同的機器實現(xiàn)機器選擇基因串的變異。對于工序排序基因串，隨機選擇兩個基因位，然后交換兩個位置的基因?qū)崿F(xiàn)工序排序基因串的變異。

2.7 改進(jìn)遺傳算法流程

筆者重點研究了遺傳算法的初始化方法，結(jié)合該方法設(shè)計了改進(jìn)遺傳算法的流程，其具體步驟如下：

(1)確定模型參數(shù)，種群規(guī)模、概率參數(shù)、交叉概率、變異概率和最大迭代次數(shù)；

(2)利用筆者提出的復(fù)合式初始化方法產(chǎn)生初始種群；

(3)根據(jù)適應(yīng)度函數(shù)對種群個體進(jìn)行評價，利用錦標(biāo)賽選擇法和精英保留策略選擇子代種群；

(4)按照交叉概率對種群進(jìn)行交叉操作；

(5)按照變異概率對種群進(jìn)行變異操作，生成新一代種群；

(6)判斷新一代種群是否滿足終止條件，若滿足，則輸出調(diào)度解，若不滿足，則返回步驟(3)。

3 算法實例

為了評價算法的性能，選取了研究較普遍的Kacem[15]基準(zhǔn)問題，它包括兩個8×8和10×10的實例，通過對基準(zhǔn)實例的模擬，驗證了算法的有效性。改進(jìn)遺傳算法參數(shù)設(shè)置如下：種群規(guī)模P=200，初始種群全局搜索和局部搜索各占50%，概率參數(shù)設(shè)為0.8，交叉概率設(shè)為0.8，變異概率設(shè)為0.01，最大迭代次數(shù)設(shè)為100。

表2給出了柔性作業(yè)車間調(diào)度8×8實例問題和完全柔性作業(yè)車間調(diào)度10×10實例問題的兩個目標(biāo)值的計算結(jié)果。從表2可看出，相比于傳統(tǒng)的遺傳算法和Kacem方法，采用改進(jìn)初始化種群生成方法后，最大完工時間和最大機器負(fù)荷均得到了一定程度的改善，而且在實際測試中，同時采用隨機生成法和改進(jìn)的初始化方法進(jìn)行分別求解后，發(fā)現(xiàn)采用改進(jìn)的初始化方法的求解時間T2短于采用隨機初始化方法的求解時間T1，說明在同樣滿足需求的情況下，改進(jìn)初始化方法求解效率要高于采用隨機生成法的求解效率，更符合實際生產(chǎn)的需要。圖6和圖7給出了改進(jìn)后的遺傳算法得到的兩個實例的最優(yōu)調(diào)度甘特圖。

表2 Kacem實例的測試結(jié)果比較

圖6 8×8基準(zhǔn)實例最佳調(diào)度甘特圖

圖7 10×10基準(zhǔn)實例最佳調(diào)度甘特圖

4 結(jié)論

在基于機器選擇柔性的前提下，考慮了最大完工時間、最大機器負(fù)荷兩個性能指標(biāo)，基于機器選擇和工序排序的分層編碼方式進(jìn)行編碼，設(shè)計了一種基于全局搜索和隨機搜索生成初始種群的復(fù)合式方法去求解調(diào)度問題的解。筆者采用8×8和10×10標(biāo)準(zhǔn)實例數(shù)據(jù)進(jìn)行測試分析，相比于傳統(tǒng)的遺傳算法，采用復(fù)合式的種群初始化方法，不僅提高了初始種群的質(zhì)量，平衡了各加工機器的工作負(fù)荷，而且在求解速度上得到了較大的改善，驗證了所提出算法的可行性和有效性。

[1] Chu C,Portmann M C, Porth J M. A Splitting-up Approach to Simplify Job-shop Scheduling Problems[J]. International Journal of Production Research,1992,30(4):859-870.

[2] Mouzon G,Yildirim M B. Single-machine Sustainable Production Planning to Minimize Total Energy Consumption and Total Completion Time Using a Multiple Objective[J].IEEE Transactions on Engineering Management,2012,54(9):585-597.

[3] Ebrahimipour V, Najjarbashi A, Sheikhalishahi M. Multi-objective Modeling for Preventive Maintenance Scheduling in a Multiple Production line[J]. Journal of Intelligent Manufacturing, 2015,26(1):111-122.

[4] Qiu X, Lau H Y K. An AIS-based Hybrid Algorithm for Static Job Shop Scheduling Problem[J]. Journal of Intelligent Manufacturing, 2014,25(3):489-503.

[5] Kundakc1 N, Kulak O. Hybrid Genetic Algorithms for Minimizing Makespan in Dynamic Job Shop Scheduling Problem[J]. Computers & Industrial Engineering, 2016,96:31-51.

[6] Zandieh M, Mozaffari E, Gholami M. A Robust Genetic Algorithm for Scheduling Realistic Hybrid Flexible Flow Line Problems[J]. Journal of Intelligent Manufacturing, 2010,21(6):731-743.

[7] Zorin D A, Kostenko V A. Simulated Annealing Algorithm in Problems of Multiprocessor Scheduling[J]. Automation and Remote Control, 2014,75(10):1790-1801.

[8] Jen J C,Chao C L,Hung C W. A New MCTS-based Algorithm for Multi-objective Flexible Job Shop Scheduling Problem[C]∥IEEE Technologies and Applications of Artificial Intelligence.[S.l.]:[s.n.],2015:413-419.

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

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

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

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

[13] 張超勇，饒運清，李培根.基于pox交叉的遺傳算法求解Job-Shop調(diào)度問題[J].中國機械工程，2004,15(23)：2149-2153.

[14] Tang D B,Dai M. Energy-efficient Approach to Minimizing the Energy Consumption in an Extended Job-shop Scheduling Problem[J].Chinese Journal of Mechanical Engineering,2015,28(5):1-8.

[15] Kacem Imed，Hammadi Slim, Borne Pierre. Approach by Localization and Multi-objective Evolutionary Optimization for Flexible Job-shop Scheduling Problems[J].IEEE Transactions on Systems， Man，and Cybernetics，Part C，2002,32(1):1-13.