王 丹， 周連喆

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

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

王 丹， 周連喆*

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

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

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

0 引 言

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

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

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

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

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

1 定義和形式化問題

1.1問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 一個(gè)P-FJSP實(shí)例的處理時(shí)間表

1.2問題制定

文中所需的變量如下：

Ω----所有機(jī)器集合；

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

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

i----第i個(gè)工件；

j----第j個(gè)工序；

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

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

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

Pijk----工件i的第j道工序在第k個(gè)機(jī)器上的加工時(shí)間；

Sijk----工件i的第j道工序在第k個(gè)機(jī)器上加工的開始運(yùn)作時(shí)間；

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

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

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

1.2.1 目標(biāo)函數(shù)

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

1.2.2 限制條件

?i,j

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

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

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

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

2.1基本遺傳算法

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

2.2染色體表示

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

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

2.3遺傳算子

2.3.1 選擇算子

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

圖1 選擇算子程序

2.3.2 交叉算子

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

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

圖2 交叉算子程序

2.3.3 變異算子

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

圖3 變異算子程序

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

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

2.4算法的性能驗(yàn)證

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

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

3 案例研究問題

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

參與工作的藥品見表3。

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

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

3.1結(jié)果

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

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

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

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

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

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

圖8 最小完工時(shí)間(company)

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

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

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

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

圖11 甘特圖(conditioner shop)

圖12 SAIDAL和NGA之間最小完工時(shí)間比較

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

圖13 整個(gè)公司的甘特圖

3.2附加性能評價(jià)

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

表5 SAIDAL和NGA之間最小完工時(shí)間比較

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

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

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

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

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

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