改進遺傳算法柔性作業車間調度

王 丹， 周連喆

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

改進遺傳算法柔性作業車間調度

王 丹， 周連喆*

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

提出一種新的遺傳算法(NGA)解決FJSP的完工時間最小化問題。采用新染色體表示和不同交叉操作和變異操作策略，依據基準數據集和測試數據驗證了NGA算法。

車間調度； 遺傳； 交叉操作； 變異操作

0 引 言

作業車間調度問題(JSP)是生產調度和組合優化問題的一個分支。在經典的JSP中，任意一個工序只能由指定的某臺設備加工，而在柔性作業車間調度(FJSP)中，則允許工序由一個機床集合中的任意一臺加工。

柔性作業車間調度工作涉及到以下問題：分配工序機器(路徑問題)和確定工序在機器上的加工順序(排序問題)，以使得完成所有工序的時間最小化。進而，兩決策相結合又呈現了額外的復雜性。因為FJSP被證明是NP-hard問題的JSP問題的擴展[1]，所以柔性作業車間調度問題是比JSP更復雜的NP-hard問題。

多年以來，為了解決FJSP，已經提出了許多算法，尤其是禁忌搜索、模擬退火、遺傳算法、粒子群優化[2-5]。

在本研究中，提出了一種新的遺傳算法(NGA)來解決FJSP的完工時間最小化問題。我們創建一個新的染色體表示方法，稱為“置換工作”。

這種方法使我們能夠找到一個新的個體工作的編碼方案，并且它能考慮到各種約束的柔性作業車間調度問題。在同一時間，我們采用不同的交叉和變異算子的策略,計算結果表明，該算法是有效的。

1 定義和形式化問題

1.1問題描述

專注于由以下要素組成的柔性作業車間調度問題：

1)作業集合。J={J1,J2,…,Jn}是一組N個被安排的作業。每個作業集由一組預定的操作組成。Oij是作業Ji包含的nj道工序。所有的工件在零時刻都能被加工。

2)機器集合。M={1,2，…,m}是一組M臺不同的機器。每臺機器一次只能加工一個工件，并且每個工序一經開始就不能中斷。所有機器在零時刻都可用。

3)靈活性。柔性作業車間調度問題分為兩種類型如下：

①總調度(T-FJSP)：每個操作可以在M個在車間加工中現有的機器中的任何一個上進行。

②部分調度(P-FJSP)：每個操作可以在M個在車間加工中現有的機器中的其中一個上進行。

4)約束。限制可能的操作作業規則，它們可以被分類為以下條件：

①每個操作一次只能由一個機器加工(析取約束)。

②從開始到運行完成的每個操作(非搶占條件)。

③每個工件在某一時刻只能在一臺機器上加工，不能中途中斷(容量約束)。

④雖然各種工作操作之間不存在優先約束，但每個工作預定的操作順序控制著下一個操作，每個工件的每道工序需要在前一道工序完成后才能進行加工(優先/連接約束)。

⑤機器的限制強調的是該操作僅可以被給定集合中的機器處理(資源約束)。

5)目的。一個時間表，找到完成所有作業的最小時間(最小完工時間)。

為了簡化算法的演示，文中設計了一個FJSP樣本實例。P-FJSP數據集包括兩個作業在5臺機器進行加工。每個格子中的數字表示在相應的機器上操作的處理時間見表1。

表1 一個P-FJSP實例的處理時間表

1.2問題制定

文中所需的變量如下：

Ω----所有機器集合；

n----總工件的數量；

m----總機器的數量；

i----第i個工件；

j----第j個工序；

Jio----工件i的總的工序數量；

Oij----工件i的第j道工序；

Ωij----工件i的第j道工序的可選加工機器數；

Pijk----工件i的第j道工序在第k個機器上的加工時間；

Sijk----工件i的第j道工序在第k個機器上加工的開始運作時間；

Eijk----第j種工件的第i道工序在第k個機器上加工的結束時間；

L----所有工件的總的工序數量；

H----非常大的正整數。

1.2.1 目標函數

設Ci是工件Ji的完工時間，則最大完工時間Cmax最小的目標函數為：

1.2.2 限制條件

?i,j

Cij-Cij+H(1-Yijijk)+H(1-Xijk)+

Cij-Cij+H(Yijijk)+H(1-Xijk)+

約束方程(2)規定完成時間和操作開始時間之間的差值等于其分配機器的處理時間。約束方程(3)及(4)確保不在同一臺機器上同時處理任何作業。這個析取約束方程(3)變為非活動狀態時和析取約束方程(4)變得不活躍時，約束方程(5)確保操作的開始時間總是積極的。約束方程(6)表示工序之間的先后關系的各種操作。約束方程(7)規定同一臺機器同一時刻只能加工一個工件[16]。Xijk：工件i的第j道工序在機器k上加工的判別條件，如果工件i的第j道工序在機器k上加工，則Xijk=1，否則Xijk=0。它表示工件i的第j道工序只能選擇在可選機器集中的一臺機器上加工。Yijijk：機器k加工工序的判別條件。它表示任一確定時刻，機器k不能同時加工任意兩個不同的工件，也不能同時加工任意兩道不同的工序。

2 一種新的柔性作業車間調度問題的遺傳算法

2.1基本遺傳算法

遺傳算法是基于自然選擇和遺傳學原理的搜索方法[16-17]。它是一類借鑒生物界的進化規律(適者生存，優勝劣汰遺傳機制)演化而來的隨機化搜索方法。遺傳算法使用主要操作，即交叉和變異，以找出全部最佳個體。交叉允許不同的解決方案(染色體)和突變增加的品種之間的交換信息。在選擇和評價的初始種群之后，染色體被選中，并應用交叉和變異算子。然后，新的個體形成,這個過程一直持續達到終止條件為止[19-20]。

2.2染色體表示

染色體表示有一個組成部分，也就是作業排列(JP)。用一個長度等于L的整數數組，每個整數的值等于相應作業的數組索引。染色體取決于以下兩個組成部分：

關于操作的順序部分，使用一個長度等于L的整數數組，每個整數的值等于相應的作業序列數組的索引。關于機器序列部分，還可以使用等于L的相同的長度。例如，因為在變化的機器集數組中這個值是1，所以M1選擇運行操作O21。因為操作O21可以在兩臺機器(M1和M3，并且有效值是1和3)上運行，所以數組中的值也等于1。

2.3遺傳算子

2.3.1 選擇算子

為繁殖選擇個體是選擇的任務[21]。選擇是從群體中選擇優良個體、淘汰劣質個體的操作。文中采用的選擇方法的詳細步驟如圖1所示。

圖1 選擇算子程序

2.3.2 交叉算子

交叉的目標是通過交換目前獲得的好的信息以獲得更好的染色體來改善結果。交叉操作是將種群中的兩個個體交換某些基因，產生新的基因組合。在這項研究中，使用了兩種交叉算子的染色體。

根據所采用的表示，在這項研究中使用的兩種交叉算子為均勻交叉和基于保序的交叉(POX)。均勻交叉操作描述如圖2所示。

圖2 交叉算子程序

2.3.3 變異算子

突變引入額外的變異性，以提高個體的多樣性。通常情況下，突變只是小概率的出現。大概率可能破壞良好的染色體。在本研究中提出了一種變異算子，它是染色體PJ值突變，值突變工作過程如圖3所示。

圖3 變異算子程序

所提出的算法描述如圖4所示。

圖4 新的遺傳算法操作流程

2.4算法的性能驗證

提出的新算法通過Brandimarte數據集(BR數據)來測試。該數據集包括10個問題，其中作業數量從10到20不等，機器數量從4到15不等，每個作業的操作數從5到15不等。

提出的新算法與下面的算法相比較見表2。

M&G：由Mastrolilli和Gambardella提出的方法。

GENACE：由Ho和Tay提出的方法。

Zhang:由張國輝和高玲提出的方法。

Chen:陳H和伊洛J提出的方法。

Pessella：Pezzelle和Morganti提出的方法。

HGTS：由J.J.Palacios和A.Gonzalez提出的方法。

針對FSJ問題提出的NGA算法在MATLAB編碼和運行在P4CPU，主屏2.3GHz，記住下列參數：popsize=100，PC=0.8，PM=0.05，選擇百分比=30%。

表2列出了問題的名稱、問題的維數(工作號×機器號)，最好的已知的解決方案(Cm)，通過文中的算法得到的解(NGA)和每個其他算法得到的解。計算結果表明，所提出的遺傳算法，到目前為止，是尋找速度最佳的解決方案。在10個測試問題中，Mk01能獲得在所有的方法中較好的解。通過使用NGA，Mk03和Mk08可以在第一代獲得最優解。Mk02，Mk04，Mk05和Mk09(4個問題)可能具有和M&G方法同樣良好的結果。對于一個問題，mk06可以得到和GENACE相同的結果，并且兩個問題(Mk07，MK10)可以獲得和Chenetal同樣的結果。

3 案例研究問題

文中考慮了現實世界的應用----一個藥物公司的調度問題。Saidal集團是Algeria領先的制藥企業之一。該公司生產各種藥物。每個產品都可以被視為一種工作。因此，在這個問題上考慮了10個工作。這個部分在機器中產生。這個機器設置尺寸為31。

參與工作的藥品見表3。

加工時間是一臺機器在不同階段加工所需的時間。每臺機器的處理時間是多次測量的，平均時間是在這項工作中采取的。在不同的機器上所有10個工作的處理時間(10-3s)見表4。

表4 3個車間和不同的機器上作業分配的例子

3.1結果

為了獲得有意義的結果，在同一個實例上運行文中算法5次。為了在一個可以接受的時間跨度得到滿意的解，NGA中使用的參數要實驗性地進行選擇。根據問題的復雜性，有效遺傳算法的種群規模從50到150不等。

最初，我們檢查了在圖5～圖7中方法的性能。然后得出平均最好的完工時間。

最小完工時間(company)如圖8所示。

圖5 最小完工時間減少(Weighingroom)

圖6 最小完工時間減少(Fabrication room)

圖7 最小完工時間(conditioner shop)

圖8 最小完工時間(company)

在圖8中，可以看出平均最好完工時間在減少。

最優解的甘特圖如圖9～圖11所示(本公司制造車間和空調車間)。

在SAIDAL和NGA之間最小完工時間比較如圖12所示。

圖9 甘特圖(weighingroom) 圖10 甘特圖(fabricationshop)

圖11 甘特圖(conditioner shop)

圖12 SAIDAL和NGA之間最小完工時間比較

最后，整個公司的甘特圖如圖13所示。

圖13 整個公司的甘特圖

3.2附加性能評價

進行了一系列的實驗來評估所提出的NGA算法的性能。設計的各因素水平和最佳的完工時間比較見表5。

表5 SAIDAL和NGA之間最小完工時間比較

根據研究結果，為提出的遺傳算法提供了最佳的計算時間的結果(文中方法和該公司的處理時間之間的差距圖形見圖12)。

4 結論與未來研究

提出了一個新的染色體表示方案和各種交叉和變異算子策略。此外，從參考文獻的實例來看，該算法已經過測試，我們用屬于藥品制造公司的真實的應用數據檢查了該算法。計算結果表明，文中提出的新的遺傳算法(NGA)有效地解決了FJSP問題。

在未來的研究中，我們打算在優化算法和解決方案的過程中考慮多個目標，如預定時間、平均流量時間的要求和如更換工具類似的其他約束。

[1] M R Garey, D S Johmson， R Sethi. The complexity of flow shop and job shop scheduling[J]. Mathematics of Operational Research,1976(1):117-129.

[2] P Brucker, R Schile. Job-shop scheduling with multipurpose machines[J]. Computing,1990,45(4):369-375.

[3] P Brandimarte. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research,1993,41:157-183.

[4] H Chen, J Ihlow, C A Lehmann. Genetic algorithm for flexible Job shop scheduling[J]. IEEE International Conferenceon Robotics and Automation Detroit,1999(2):1120-1128.

[5] I Kacem, S Hammadi, P Borne. Approche by localization and multiobjective evolutionary and optimization for flexible job shop scheduling problems[J]. IEEE Transations Man and Cybernetrics,2002,32(1)：1-13.

[6] N B Ho, J C Tay. GENACE: An efficient cultural algorithm for solving the flexible job shop problem[J]. Proceeding of IEEE Congress on Evolutionary Computation,2004(1):1759-1766.

[7] H P Zhang, M Gen. Multistage-based genetic algorithm for flexible job shop scheduling problem[J]. Journal of Complexity International,2005,48:409-425.

[8] P Fattahi, M S Mehrabad, F Joli. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J]. Journal of Inteligent Manufacturing,2007,18:331-342.

[9] B S Girish, N Jawahar. Scheduling job shops associated with multiple routings with genetic and ant colony heuristics[C]//[S.l.]:Thiagarajar College of Engineering,2008.

[10] F Pezzela, G Margenti, G Ciaschetti. A genetic algorithm for flexible job shop scheduling problem[J]. Computers and Operations Research,2007,35(10):3202-3212.

[11] W Sun, Y Pan, X Lu, et al. Research on flexible job shop scheduling problem based on a modified genetic algorithm[J]. Journal of Mechanical Science and Technology,2010,24(10):2115-2119.

[12] A Motaghedi, K Sabri Laghare, M Heydari. Solving flexible job shop scheduling problem with multi objectives[J]. International Journal of Industrial Engineering and Production Research,2010,21:197-209.

[13] G Zhang, L Gao, Y Shi. An effective genetic algorithm for the flexible job shop scheduling problem[J]. Expert System with Application,2011,38:3563-3573.

[14] Q Zhang, H Manier, A Manier. A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constants and bounded proceding times[J]. Computers and operations Research,2012,39:1713-1723.

[15] J C Chen, C C Wu, C W Chen. Flexible job shopwith parallel machines using genetic algorithm and grouping genetic algorithm[J]. Expert Systems with Application,2012,39:10016-10021.

[16] N Kim, H Kim, J Lee. Damage detection of truss structures using two stage optimization based on micro genetic algorithm[J]. Journal of Mechanical Science And Technology,2014,28(9):3687-3695.

[17] R N Yadar, V Yadar, G H Singh. Application of non dominated sorting genetic algorithm for multi objective optimization of electrical discharge diamond face grinding process[J]. Journal of Mechanical Science and Technology,2014,28(6):2299-2306.

[18] L N Xing, Y U Chen, K W Yang. Multi population interactive coevolutionnary algorithm for flexible job shop scheduling problems[C]//Comput. Optim. Appl., DOI 10.1007//S 10589-009-9244-7,2009.

[19] F N Defersha, M Chen. A coase-grain parallel genetic algorithm for flexible job shop scheduling with lot streaming[C]// In IEEE International Conference on Computational Science and Engineering,2009.

[20] Y K Park, J M Yang. Optimization of mixed casting processes considering discrete ingot sizes[J]. Journal of Mechanical Science and Technology,2009,23:1899-1910.

[21] S F Hwang, Y Hsu, Y Chen. A genetic algorithm for the optimization of fiber angles in composite laminates[J]. Journal of Mechanical Science and Technology,2014,28(8):3163-3169.

Flexiblejobshopschedulingbasedonimprovedgeneticalgorithm

WANG Dan, ZHOU Lianzhe*

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012, China)

A new genetic algorithm (NGA) is put forward to solve the minimized completion time for FJSP. We apply a new chromosome representation and adopt different crossover operations and mutation operation. The algorithm is verified based on both the benchmark and tested data sets.

FJSP； genetic algorithm； crossover operator； mutation operator.

TP 18

A

1674-1374(2017)04-0361-10

2017-04-15

王 丹(1989-)，女，漢族，河南信陽人，長春工業大學碩士研究生，主要從事人工智能應用方向研究,E-mail:wd1037407198@163.com. *通訊作者：周連喆(1971-)，女，漢族，吉林長春人，長春工業大學副教授，主要從事人工智能與數據挖掘方向研究,E-mail:zhoulianzhe@ccut.edu.cn.

10.15923/j.cnki.cn22-1382/t.2017.4.08