基于混合果蠅-遺傳算法求解柔性作業(yè)車間調(diào)度問題

劉晶晶,劉業(yè)峰,黎 虹

(1.沈陽(yáng)工學(xué)院 基礎(chǔ)課部，遼寧 撫順 113122;2.遼寧省數(shù)控機(jī)床信息物理融合與智能制造重點(diǎn)實(shí)驗(yàn)室, 遼寧 撫順 113122;3.沈陽(yáng)工學(xué)院 機(jī)械工程與自動(dòng)化學(xué)院，遼寧 撫順 113122)

0 引言

近年來，智能制造技術(shù)迅速發(fā)展，柔性作業(yè)車間的調(diào)度問題具有重要的現(xiàn)實(shí)意義。 科學(xué)地調(diào)度其生產(chǎn)過程可提高企業(yè)生產(chǎn)效率，在一定程度上保障交貨時(shí)間，降低生產(chǎn)能耗。大量學(xué)者用不同的方法研究了自動(dòng)化車間的生產(chǎn)調(diào)度問題。采用的方法主要有傳統(tǒng)運(yùn)籌學(xué)方法(拉格朗日松弛方法[1]、分支定界法[2])等)和智能算法(群智能算法、人工智能算法、啟發(fā)式算法等)。 上述算法中，非智能算法的求解時(shí)間復(fù)雜度較高，并不適應(yīng)大規(guī)模生產(chǎn)調(diào)度問題，而智能優(yōu)化算法的計(jì)算效率較高，有時(shí)容易陷入局部極小，需要依據(jù)問題的不同特征予以改進(jìn)。

遺傳算法(GA)是求解并行調(diào)度問題的有效算法，目前已有大量研究。文獻(xiàn)[3]根據(jù)機(jī)床的加工匹配特性，列出3個(gè)不同維度的優(yōu)化目標(biāo)，使用多層編碼技術(shù)提出了基于遺傳算法的生產(chǎn)調(diào)度方法；文獻(xiàn)[4]提出了求解生產(chǎn)調(diào)度問題的變鄰域改進(jìn)遺傳算法；文獻(xiàn)[5]基于排列編碼技術(shù)提出了一種具有并行批處理和能力約束的混合車間調(diào)度遺傳算法;遺傳算法和其他智能優(yōu)化算法相結(jié)合也是研究調(diào)度問題的熱點(diǎn)方法[6]；文獻(xiàn)[7]提出多維矩陣編碼技術(shù)，使用遺傳算法解決了混合流水作業(yè)調(diào)度問題；文獻(xiàn)[8]將傳統(tǒng)方法與遺傳算法相結(jié)合提出了基于單純形格設(shè)計(jì)的多目標(biāo)遺傳算法求解車間調(diào)度問題。

其他啟發(fā)式算法或群智能算法也在解決生產(chǎn)調(diào)度問題中發(fā)揮著重要作用。文獻(xiàn)[9]提出了一種混合變鄰域搜索算法(HVNS)來求解混合流車間調(diào)度問題，給出了八種鄰域結(jié)構(gòu)并提出了動(dòng)態(tài)鄰域更新方法提取全局信息；文獻(xiàn)[10]基于生產(chǎn)車間調(diào)度，提出了兩階段啟發(fā)式算法，第一階段進(jìn)行作業(yè)排序，第二階段基于禁忌搜索和貪心算法的列生產(chǎn)算法進(jìn)行搶占式調(diào)度以最小化完工時(shí)間；除此之外，粒子群優(yōu)化算法[11]、人工蜂群算法[12-14]等也被廣泛應(yīng)用于生產(chǎn)調(diào)度問題中；部分調(diào)度問題將目標(biāo)轉(zhuǎn)向生產(chǎn)排產(chǎn)[15-20]，仍圍繞生產(chǎn)效率最大化的主題提出了一系列啟發(fā)式算法[21-22]。

2012年，由臺(tái)灣學(xué)者潘文濤提出了果蠅優(yōu)化算法(FOA)[23]，很快在優(yōu)化領(lǐng)域受到關(guān)注。果蠅優(yōu)化算法目前的研究進(jìn)展[24], 包括維持種群多樣性、知識(shí)驅(qū)動(dòng)策略與協(xié)同機(jī)制的設(shè)計(jì)等方面的改進(jìn)工作。該文獻(xiàn)也介紹了果蠅優(yōu)化算法在離散優(yōu)化、多目標(biāo)優(yōu)化、不確定優(yōu)化等方面的擴(kuò)展性研究工作；求解并行調(diào)度問題時(shí)，多數(shù)學(xué)者對(duì)果蠅算法作了相應(yīng)改進(jìn)，包括編碼方式和鄰域結(jié)構(gòu)生成方式的改進(jìn)[25]、如何提高群體多樣性以及搜索方式的改進(jìn)等[26-30]。2014年，文獻(xiàn)[31]將果蠅優(yōu)化算法應(yīng)用到煉鋼連鑄的離散生產(chǎn)調(diào)度問題中，取得了有效的結(jié)果；2018年，文獻(xiàn)[32]提出了一種多目標(biāo)果蠅優(yōu)化算法(MOFOA)來解決測(cè)試點(diǎn)的選擇問題； 2019年，文獻(xiàn)[33-34]也成功將果蠅優(yōu)化算法應(yīng)用到混合流水車間調(diào)度問題中。

綜上，柔性車間調(diào)度問題取得了一定的研究成果，但該調(diào)度問題屬于NP-Hard問題，現(xiàn)有的優(yōu)化算法還存在不足，目前將遺傳算法和其它群智能優(yōu)化算法結(jié)合使用或改進(jìn)果蠅優(yōu)化算法解決柔性作業(yè)車間調(diào)度問題的情況較多，將遺傳算法和果蠅優(yōu)化算法結(jié)合在一起使用較少，本文結(jié)合果蠅優(yōu)化算法和遺傳算法的特點(diǎn)，將二者結(jié)合使用，選取表達(dá)方式直接且解碼方便的多維矩陣編碼技術(shù)，引入尋優(yōu)變異算子和自適應(yīng)動(dòng)態(tài)轉(zhuǎn)移策略，在兩階段種群進(jìn)化的基礎(chǔ)上，以最小化完工時(shí)間為優(yōu)化目標(biāo)，建立了生產(chǎn)調(diào)度模型，得到了優(yōu)化調(diào)度方案[35]。

1 問題描述

柔性車間生產(chǎn)調(diào)度問題是指多個(gè)工件在有限臺(tái)設(shè)備上加工。在不同時(shí)刻，一臺(tái)設(shè)備可以用于多個(gè)工件多道工序的加工，同時(shí)設(shè)備具有可選性和靈活性。因此，可以將不同設(shè)備的按序組合作為一個(gè)工件的加工路徑，以達(dá)到加工用時(shí)最小化的目標(biāo)。

具體描述為：加工m個(gè)工件，每個(gè)工件各有n道工序，每道工序可以在任一臺(tái)機(jī)器上加工，連續(xù)兩道工序之間考慮運(yùn)輸和工序切換等待時(shí)間，各工件各道工序的加工時(shí)間均不相同。現(xiàn)共有s套設(shè)備，每套設(shè)備的工作效率不同，目標(biāo)為使得所有工件的總加工時(shí)間最短，如圖1所示。

圖1 柔性車間生產(chǎn)線運(yùn)行圖

2 數(shù)學(xué)建模

2.1 符號(hào)表示

tcij：第i個(gè)工件第j道工序的加工完成時(shí)間；

tpij:第i個(gè)工件第j道工序的加工時(shí)間；

tranj,j+1：AGV小車將工件物料由第j道工序到第j+1道工序之間的運(yùn)輸時(shí)間；

xijs[1]：0-1變量，當(dāng)且僅當(dāng)工件i的第j道工

序在機(jī)器號(hào)為s的機(jī)器上加工時(shí)為1，否則為0(i=1,2,,m)，(j=1,2,,n)，(s=1,2,3)；

yikj[1]：0-1變量，當(dāng)且僅當(dāng)工件i先于工件在第j道工序被加工時(shí)為1，否則為0(i,k=1,2,,m)，(j=1,2,,n)。

2.2 數(shù)學(xué)模型

將生產(chǎn)過程分解為“加工時(shí)間”和“工序間的運(yùn)輸時(shí)間”，通過優(yōu)化總加工時(shí)間來實(shí)現(xiàn)生產(chǎn)線的高效生產(chǎn)，現(xiàn)有m個(gè)工件在n道工序上加工。

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

(1)

2.2.2 約束條件

根據(jù)自動(dòng)化生產(chǎn)的實(shí)際調(diào)度需求，設(shè)定如下約束條件：

1)加工順序約束，即同一工件在前一道工序加工完畢送至下一道工序后開始加工。

tci,j+1-tci,j-tpi,j+1=tranj,j+1

(i=1,2,,mj=1,2,,n-1)

(2)

2)機(jī)器能力約束[1]，即同一臺(tái)機(jī)器不能同時(shí)加工多個(gè)工件。

tck,j-tci,j-tpk,j+(3-xijs-xkjs-yikj)U≥0

(k≠i,U為較大正數(shù))

(3)

3)連續(xù)加工，即一個(gè)工件加工結(jié)束后立刻加工下一個(gè)工件。

tci+1,n-tci,n-tpi+1,n=0,i=1,，m-1

(4)

4)各道工序加工機(jī)器唯一性約束。

(5)

5)工序之間的順序關(guān)系約束。

yijs+ykjs=1(k≠i)

(6)

6)變量約束。

xijs∈{0,1},yikj∈{0,1}

(i,k=1,2,,m;j=1,2,,n;s=1,2,3)

(7)

3 基于FOA-GA算法的求解策略

FOA算法是基于果蠅覓食行為的生物學(xué)原理提出的一種智能優(yōu)化算法。該算法分為兩個(gè)階段：嗅覺階段和視覺階段。通過兩個(gè)階段的不斷迭代實(shí)現(xiàn)覓食的優(yōu)化，得到問題的滿意解。 FOA算法具有易于實(shí)現(xiàn)、控制參數(shù)少、便于進(jìn)入問題特定的搜索環(huán)節(jié)等優(yōu)點(diǎn)。但是，該算法強(qiáng)調(diào)對(duì)個(gè)體鄰域的搜索，缺少種群多樣性的變更，因此全局搜索能力較弱，容易陷入局部極小。

GA算法是利用生物進(jìn)化中的自然選擇原理，依據(jù)適者生存的原則構(gòu)建的計(jì)算模型，通過染色體的選擇、交叉、變異方式，進(jìn)行種群的不斷迭代更新，從而找到最優(yōu)解或滿意解。 GA算法操作稍復(fù)雜，但具有極大的靈活性，對(duì)于各類特殊問題都可以按照特定方式進(jìn)行求解，可以較大程度地避免解集陷入局部極小。

本文結(jié)合柔性自動(dòng)化生產(chǎn)線的加工調(diào)度問題，對(duì)FOA算法和GA算法進(jìn)行改進(jìn)，提出混合FOA-GA啟發(fā)式算法，以工件最短加工時(shí)間為目標(biāo)函數(shù)，建立了局部搜索與全局搜索相結(jié)合的搜索方式，具體算法如下。

3.1 編碼方式

采用矩陣式編碼結(jié)構(gòu)[7]矩陣的行號(hào)代表工件編號(hào)，矩陣的列號(hào)代表工件的加工工序，矩陣中的元素值代表加工的機(jī)器號(hào)。對(duì)于加工工件的任意給定排序，預(yù)先為各工件的各道工序隨機(jī)分配加工機(jī)器。

macij表示第i個(gè)工件的第j道工序在macij號(hào)設(shè)備上加工。另已知各工件在各道工序上的加工時(shí)間表為矩陣ProT，其中元素可各不相同。

3.2 適應(yīng)度函數(shù)以及解碼方式

適應(yīng)度為工件加工總時(shí)間的倒數(shù)(即第一個(gè)工件開始加工至最后一個(gè)工件結(jié)束加工所用時(shí)間的倒數(shù))。在矩陣編碼機(jī)制下，采用啟發(fā)式算法解碼并計(jì)算適應(yīng)度：

1)按工序搜索。將第k道工序中需要在機(jī)器m上加工的所有工件編號(hào)進(jìn)行提取:

W={w1,w2,,wn}

(8)

式(8)中，w1,w2,,wn表示在第k(k=2,3,,n)道工序中第m號(hào)機(jī)器上加工的所有工件，取出上一道工序的完工時(shí)間集合:

(9)

2)排序選出在(8)中結(jié)束最早的工件，將其結(jié)束時(shí)間與第k道工序中第m號(hào)機(jī)器上正在加工工件的結(jié)束時(shí)刻作比較，二者取較大值，將其與運(yùn)輸時(shí)間之和記為第k道工序中下一個(gè)工件的開始加工時(shí)間，即:

(10)

3)適應(yīng)度為最后一個(gè)工件的加工完成時(shí)間與第一個(gè)工件開始加工時(shí)間之差的倒數(shù)。

(11)

3.3 算法流程

3.3.1 種群初始化

隨機(jī)產(chǎn)生初始種群，并計(jì)算當(dāng)前最佳適應(yīng)度值，記錄初步全局最優(yōu)解fcur。

3.3.2 嗅覺階段

考慮到問題結(jié)構(gòu)和解的離散性，采用多重交換(multi-swap)技術(shù)[31]產(chǎn)生每個(gè)個(gè)體的局部信息結(jié)構(gòu)進(jìn)行果蠅嗅覺階段的搜索，即在合適的范圍內(nèi)進(jìn)行工件加工機(jī)器安排的多重交換，在矩陣編碼方式下，其實(shí)際意義為工件加工路徑的局部尋優(yōu)。如圖2所示(假設(shè)每道工序有5臺(tái)機(jī)器)，若交換第1、2行基因段，則工件1每道工序?qū)?yīng)機(jī)器的加工路徑由1,5,2,3,3交換成2,4,3,2,5，這對(duì)于具有不同加工時(shí)長(zhǎng)的各個(gè)工件尋找局部最佳加工路徑具有重要作用。若當(dāng)前適應(yīng)度優(yōu)于交換前的適應(yīng)度，則進(jìn)行局部較優(yōu)解以及種群個(gè)體的替換，更新種群。

圖2 嗅覺階段通過多重交換技術(shù)進(jìn)行局部路徑搜索示意圖

3.3.3 交叉機(jī)制

為了豐富種群的多樣性，引入遺傳算法中的交叉機(jī)制。很多已有文獻(xiàn)中采用單點(diǎn)交叉或兩點(diǎn)交叉方式，本文采用單點(diǎn)交叉方式，父代兩兩交叉產(chǎn)生子代，采用精英策略保留優(yōu)勢(shì)個(gè)體，在父代和子代中采用錦標(biāo)賽的方式進(jìn)行優(yōu)勝劣汰。矩陣編碼形式下的交叉方式如圖3所示。

圖3 交叉操作示意圖

3.3.4 變異機(jī)制

1)基于實(shí)際生產(chǎn)情況(在每道工序3臺(tái)機(jī)器的情況下，1號(hào)、2號(hào)和3號(hào)機(jī)器生產(chǎn)效率依次降低)，選取一定比例的個(gè)體(本文選取80%)，設(shè)置尋優(yōu)變異算法：計(jì)算當(dāng)前個(gè)體中各工序中使用1號(hào)設(shè)備和3號(hào)設(shè)備的數(shù)量s1和s3，若s1>s3，變異時(shí)以β(本文β=0.8)為概率，將安排到3號(hào)機(jī)器生產(chǎn)的工件向效能較高的1號(hào)和2號(hào)機(jī)器調(diào)整，以提高生產(chǎn)效率，如圖4所示。

圖4 尋優(yōu)變異算法操作示意圖

2)為避免陷入局部最優(yōu)，選取20%比例的個(gè)體，按給定概率進(jìn)行變異(由于選取的個(gè)體較少，本文設(shè)定變異概率為0.3)。 計(jì)算新的適應(yīng)度并記錄當(dāng)前最佳適應(yīng)度和最佳個(gè)體。

3.3.5 視覺階段

二是相關(guān)課程的任課教師可以聯(lián)合團(tuán)委、學(xué)生會(huì)等，精心設(shè)計(jì)暑期“三下鄉(xiāng)”社會(huì)實(shí)踐主題，引導(dǎo)學(xué)生在社會(huì)實(shí)踐中認(rèn)識(shí)閩東、服務(wù)地方、提升能力，使學(xué)生對(duì)閩東特色文化的認(rèn)識(shí)從感性上升到理性，進(jìn)而增強(qiáng)實(shí)踐育人的實(shí)效性。比如：多渠道了解閩東革命老區(qū)的實(shí)際需求，結(jié)合學(xué)科專業(yè)特長(zhǎng)，組織學(xué)生開展志愿服務(wù)，幫助老區(qū)人民解決實(shí)際困難，鍛煉和提高學(xué)生們的綜合素質(zhì)能力；結(jié)合大學(xué)生創(chuàng)新創(chuàng)業(yè)教育，讓高校教師的科研成果、學(xué)生的創(chuàng)新思維在社會(huì)實(shí)踐中落地生根，實(shí)現(xiàn)成果轉(zhuǎn)換，惠及群眾。通過創(chuàng)新創(chuàng)業(yè)實(shí)踐，使學(xué)生逐步提高整合資源的能力、溝通協(xié)調(diào)的能力、統(tǒng)籌領(lǐng)導(dǎo)的能力等，從而為今后就業(yè)創(chuàng)業(yè)奠定良好的基礎(chǔ)。

整個(gè)種群向當(dāng)前最優(yōu)解的方向搜索。由于問題的解具有離散型，因此常規(guī)果蠅搜索方式并不適用于此。為了不改變種群的多樣性并使種群整體向好，采用如下方法：設(shè)置動(dòng)態(tài)自適應(yīng)轉(zhuǎn)移比例α(i)(i=1,2,,itermax)。

(12)

其中:N為種群規(guī)模。為了保持種群多樣性，在初始階段，α(i)取值較小，隨著迭代次數(shù)的增加，α(i)呈現(xiàn)增大趨勢(shì)(但有隨機(jī)擾動(dòng))，以加快收斂速度，將適應(yīng)度較差的個(gè)體以α(i)為比例向最優(yōu)個(gè)體調(diào)整，以加快種群的收斂速度。

具體流程如圖5所示。

圖5 FOA-GA算法流程圖

4 數(shù)值實(shí)驗(yàn)

以某實(shí)驗(yàn)室智能制造車間為原型：某生產(chǎn)線自動(dòng)化加工單元主要由三臺(tái)智能加工設(shè)備組成。做出如下假設(shè)：車間具有三套自動(dòng)化生產(chǎn)線，編號(hào)為1、2、3，按生產(chǎn)效率等級(jí)分別為高、中、低。2號(hào)設(shè)備比對(duì)應(yīng)的1號(hào)設(shè)備加工時(shí)間多5個(gè)單位，3號(hào)設(shè)備比對(duì)應(yīng)的2號(hào)設(shè)備加工時(shí)間多5個(gè)單位。需解決的問題是：m(一般為8的整數(shù)倍)個(gè)工件在生產(chǎn)線上按順序進(jìn)行n個(gè)工序的加工，工件可以由AGV小車運(yùn)輸調(diào)度，在對(duì)應(yīng)工序的任一臺(tái)設(shè)備上加工，不考慮第一道工序開始前的物料運(yùn)輸時(shí)間，如何使得總加工時(shí)間最短。

以16個(gè)工件、3道工序?yàn)槔O(shè)定各工件在各道工序加工所需時(shí)間如表1所示， AGV小車在各道工序之間的運(yùn)輸時(shí)間如表2～3所示。

例如，表2中4.4387表示工件由第一道工序的1號(hào)機(jī)器運(yùn)輸?shù)降诙拦ば虻?號(hào)機(jī)器所需時(shí)間。

表1 工件在各道工序的加工時(shí)間表(以1號(hào)機(jī)器為標(biāo)準(zhǔn))

實(shí)驗(yàn)參數(shù)設(shè)置如表4所示。

表4 參數(shù)設(shè)置表

為了排除實(shí)驗(yàn)結(jié)果的隨機(jī)性因素，現(xiàn)給出10次實(shí)驗(yàn)結(jié)果的平均值和最優(yōu)值，在相同參數(shù)設(shè)置下分別對(duì)比FOA-GA、GA和FOA算法的實(shí)驗(yàn)結(jié)果。使用MATLAB R2019a編寫程序，在8 G內(nèi)存、1.6 GHz的CPU上運(yùn)行，實(shí)驗(yàn)結(jié)果如表5所示。

表5 三種算法最優(yōu)加工時(shí)間平均值對(duì)比表(16個(gè)工件)

由表5可知，在加工16個(gè)工件時(shí)，F(xiàn)OA-GA算法、GA算法和FOA算法的最優(yōu)解(即最短加工時(shí)間)分別為398.995 3、410.817 5和412.007 9比較其平均值，F(xiàn)OA-GA算法得到的工件加工時(shí)間比GA算法平均節(jié)約10.302 4個(gè)單位，比FOA算法平均節(jié)約12.100 4個(gè)單位，證明了算法的有效性。

現(xiàn)給出在FOA-GA算法下取得最優(yōu)解時(shí)的調(diào)度方案。

圖6中，“1-1”代表第1個(gè)工件的第1道工序，機(jī)器編號(hào)1、4、7分別對(duì)應(yīng)第1道工序的1-3號(hào)機(jī)器，機(jī)器編號(hào)2、5、8分別對(duì)應(yīng)第2道工序的1-3號(hào)機(jī)器，機(jī)器編號(hào)3、6、9分別對(duì)應(yīng)第3道工序的1-3號(hào)機(jī)器。當(dāng)3套設(shè)備之間的生產(chǎn)效率差距較大時(shí)，尋優(yōu)算子的作用更加明顯，機(jī)器分配的合理性更加顯著。FOA-GA算法的收斂曲線如圖7～8所示。

圖6 加工16個(gè)工件的生產(chǎn)任務(wù)甘特圖(FOA-GA算法)

如圖7所示，使用FOA-GAG算法，經(jīng)過27次迭代后，曲線收斂，工件加工時(shí)間的最優(yōu)解為398.9953個(gè)時(shí)間單位。為了體現(xiàn)視覺階段動(dòng)態(tài)自適應(yīng)轉(zhuǎn)移算子的效果，圖8給出了在近乎相同最優(yōu)解下引入動(dòng)態(tài)自適應(yīng)轉(zhuǎn)移算子前后的實(shí)驗(yàn)結(jié)果對(duì)比，可見引入動(dòng)態(tài)自適應(yīng)算子后，最優(yōu)解曲線的收斂時(shí)間由第118次迭代步數(shù)加速至第27次迭代步數(shù)，效果顯著。

圖7 引入動(dòng)態(tài)自適應(yīng)轉(zhuǎn)移算子后的最優(yōu)解收斂曲線圖

圖8 未引入動(dòng)態(tài)自適應(yīng)轉(zhuǎn)移算子時(shí)的最優(yōu)解收斂曲線圖

采用GA算法和FOA算法取得最優(yōu)解時(shí)的收斂曲線如圖9～10所示。

圖9 最優(yōu)解收斂曲線圖(GA)

圖10 最優(yōu)解收斂曲線圖(FOA)

由圖9可知，GA算法在經(jīng)過74次迭代后取得最優(yōu)解為410.817 5，比FOA-GA算法多耗時(shí)11.822 2個(gè)時(shí)間單位。從圖10可以看出，F(xiàn)OA算法在迭代140次后取得最優(yōu)解412.007 9，比FOA-GA算法多耗時(shí)13.012 6個(gè)時(shí)間單位，且FOA算法收斂較慢。以上對(duì)比證明了FOA-GA算法的優(yōu)越性和有效性。

實(shí)際生產(chǎn)中，工件數(shù)量較大，現(xiàn)分別考慮加工40、80、120、200個(gè)工件時(shí)的情況，并將加工16個(gè)工件時(shí)的實(shí)驗(yàn)結(jié)果也記錄于表6中。在每次實(shí)驗(yàn)中，工件在各道工序的加工時(shí)間隨機(jī)生成在[36,50]之間，工序間的轉(zhuǎn)移運(yùn)輸時(shí)間隨機(jī)生成在[3,10]之間，比較10次實(shí)驗(yàn)的平均值。

表6 3種算法的加工時(shí)間對(duì)比表(3道工序、不同工件數(shù))

由表6可以看出，分別加工16、40、80、120、200個(gè)工件時(shí)，F(xiàn)OA-GA算法均表現(xiàn)出優(yōu)勢(shì)所在。 例如，當(dāng)加工80個(gè)工件時(shí)，F(xiàn)OA-GA算法所得的最優(yōu)解為1 584.3，工件的加工用時(shí)比GA算法平均節(jié)約37.5個(gè)單位，比FOA算法平均節(jié)約50.4個(gè)單位；當(dāng)加工200個(gè)工件時(shí)，F(xiàn)OA-GA算法的最優(yōu)解平均值為3 809.3，加工用時(shí)比GA算法平均節(jié)約28.7個(gè)單位，比FOA算法平均節(jié)約117.7個(gè)單位。

實(shí)際加工中，往往不只3道工序，現(xiàn)給出在加工16個(gè)工件、工序個(gè)數(shù)分別為3、4和5時(shí)3種算法在10次實(shí)驗(yàn)中平均值對(duì)比結(jié)果，如表7所示。

表7 3種算法的加工時(shí)間對(duì)比表(16個(gè)工件、不同工序數(shù))

表7給出了在工件數(shù)相同、工序數(shù)不同的情況下，3種算法的結(jié)果對(duì)比，可以看出FOA算法均占有優(yōu)勢(shì)，再一次驗(yàn)證了算法的有效性。

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

本文在結(jié)合果蠅優(yōu)化算法(FOA)和遺傳算法(GA)的基礎(chǔ)上，通過矩陣編碼機(jī)制，引入局部加工路徑搜索技術(shù)和以提高生產(chǎn)效率為原則的尋優(yōu)變異算子，解決了工件自動(dòng)化生產(chǎn)調(diào)度問題，再通過自適應(yīng)動(dòng)態(tài)轉(zhuǎn)移算子，加快了算法的收斂性。通過數(shù)值實(shí)驗(yàn)，橫向?qū)Ρ菺A算法和FOA算法，證明了FOA-GA算法的優(yōu)越性和有效性。將上述算法依據(jù)企業(yè)的智能車間進(jìn)行改進(jìn)，便可進(jìn)行實(shí)際應(yīng)用。