改進遺傳算法柔性作業(yè)車間調(diào)度

王 丹， 周連喆

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

改進遺傳算法柔性作業(yè)車間調(diào)度

王 丹， 周連喆*

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

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

車間調(diào)度； 遺傳； 交叉操作； 變異操作

0 引 言

作業(yè)車間調(diào)度問題(JSP)是生產(chǎn)調(diào)度和組合優(yōu)化問題的一個分支。在經(jīng)典的JSP中，任意一個工序只能由指定的某臺設(shè)備加工，而在柔性作業(yè)車間調(diào)度(FJSP)中，則允許工序由一個機床集合中的任意一臺加工。

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

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

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

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

1 定義和形式化問題

1.1問題描述

專注于由以下要素組成的柔性作業(yè)車間調(diào)度問題：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2問題制定

文中所需的變量如下：

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

n----總工件的數(shù)量；

m----總機器的數(shù)量；

i----第i個工件；

j----第j個工序；

Jio----工件i的總的工序數(shù)量；

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

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

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

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

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

L----所有工件的總的工序數(shù)量；

H----非常大的正整數(shù)。

1.2.1 目標函數(shù)

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

1.2.2 限制條件

?i,j

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

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

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

2 一種新的柔性作業(yè)車間調(diào)度問題的遺傳算法

2.1基本遺傳算法

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

2.2染色體表示

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

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

2.3遺傳算子

2.3.1 選擇算子

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

圖1 選擇算子程序

2.3.2 交叉算子

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

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

圖2 交叉算子程序

2.3.3 變異算子

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

圖3 變異算子程序

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

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

2.4算法的性能驗證

提出的新算法通過Brandimarte數(shù)據(jù)集(BR數(shù)據(jù))來測試。該數(shù)據(jù)集包括10個問題，其中作業(yè)數(shù)量從10到20不等，機器數(shù)量從4到15不等，每個作業(yè)的操作數(shù)從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，記住下列參數(shù)：popsize=100，PC=0.8，PM=0.05，選擇百分比=30%。

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

3 案例研究問題

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

參與工作的藥品見表3。

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

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

3.1結(jié)果

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

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

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

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

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

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

圖8 最小完工時間(company)

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

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

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

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

圖11 甘特圖(conditioner shop)

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

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

圖13 整個公司的甘特圖

3.2附加性能評價

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

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

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

4 結(jié)論與未來研究

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

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

[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-)，女，漢族，河南信陽人，長春工業(yè)大學碩士研究生，主要從事人工智能應(yīng)用方向研究,E-mail:wd1037407198@163.com. *通訊作者：周連喆(1971-)，女，漢族，吉林長春人，長春工業(yè)大學副教授，主要從事人工智能與數(shù)據(jù)挖掘方向研究,E-mail:zhoulianzhe@ccut.edu.cn.

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