吳亮，周學(xué)良，冷杰武，吳瑤

（1.湖北汽車工業(yè)學(xué)院機(jī)械工程學(xué)院，湖北十堰 442002；2.廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東廣州 510006）

柔性作業(yè)車間調(diào)度問題是傳統(tǒng)作業(yè)車間調(diào)度問題的擴(kuò)展。當(dāng)前生產(chǎn)調(diào)度研究大多基于單件調(diào)度［1］，但實(shí)際生產(chǎn)中產(chǎn)品加工往往是成批生產(chǎn)。產(chǎn)品生產(chǎn)采用批量分割的方式能提高生產(chǎn)效率，降低機(jī)床負(fù)荷。批量分割主要包含等量分批、一致分批和可變分批，等量分批是將工件劃分為數(shù)量相同的若干子批［2］。針對柔性車間等量分批調(diào)度問題，國內(nèi)外眾多學(xué)者進(jìn)行了深入研究，并取得一定成果。在建立批量數(shù)學(xué)模型方面，Alyn等［3］以批量和調(diào)度作為2 個(gè)階段，提出MIP 啟發(fā)式算法，并結(jié)合混合整數(shù)線性規(guī)劃解決實(shí)際大規(guī)模轉(zhuǎn)運(yùn)問題；Zhou［4］等建立了批量混合生產(chǎn)數(shù)學(xué)模型，并在案例分析中討論批量和非批量方案，提出了基于批次的排產(chǎn)方法；李聰波等［5］針對柔性車間多工藝批量生產(chǎn)，提出了面向能耗的分批優(yōu)化模型。在設(shè)計(jì)算法求解方面，周亞勤［6］基于機(jī)床的負(fù)荷和工件批量約束，提出了雙層嵌套式遺傳算法，設(shè)計(jì)設(shè)備優(yōu)先的解碼算子來確定子批工件工藝路徑；黃夏寶等［7］針對不同生產(chǎn)類型的批量調(diào)度問題，設(shè)計(jì)了遺傳模擬退火算法，在批量生產(chǎn)下確定最優(yōu)分批數(shù)；Xu［8］等針對工件批次調(diào)度和劃分成指數(shù)增長問題，提出了批次定向和搜索空間可預(yù)測的啟發(fā)式方法，使生產(chǎn)周期變短；孫志駿等［9］針對作業(yè)車間多工藝路線批量作業(yè)計(jì)劃優(yōu)化，提出了新的染色體編碼方式，優(yōu)化子批數(shù)量和獲取較優(yōu)的子批加工排序，縮短了產(chǎn)品加工的時(shí)間；張奎［10］針對柔性作業(yè)車間分批調(diào)度問題，提出FR 分批，縮短了產(chǎn)品的生產(chǎn)周期，但算法尋優(yōu)上存在優(yōu)化空間。上述學(xué)者通過設(shè)計(jì)高效的算法進(jìn)行求解，但對于批量調(diào)度研究仍存在求解精度不足的問題。文中針對柔性制造車間等量分批調(diào)度問題，在標(biāo)準(zhǔn)遺傳算法（genetic algorithm,GA）的基礎(chǔ)上，改進(jìn)適應(yīng)度函數(shù)，增加個(gè)體區(qū)分度，使用保留親代交叉機(jī)床基因策略，采用混合變異的方法選擇加工機(jī)床。通過自適應(yīng)交叉變異概率提高算法的尋優(yōu)和收斂速度。采用標(biāo)準(zhǔn)GA與改進(jìn)GA進(jìn)行算例測試對比，驗(yàn)證改進(jìn)GA的有效性。

1 等量分批的柔性車間調(diào)度

1.1 調(diào)度問題

有N種工件在M臺(tái)機(jī)床上加工，每種工件可以均分為1個(gè)或多個(gè)子批，每個(gè)子批都有確定的工藝次序。每類工件不同子批的每道工序可以根據(jù)自身工藝順序在若干個(gè)機(jī)床上加工，加工過程中子批具有柔性加工路徑。調(diào)度目標(biāo)是將每類工件的所有子批送入機(jī)床加工，確定最優(yōu)加工路線，使完工時(shí)間最小化，調(diào)度基本參數(shù)如表1所示。調(diào)度過程中必須滿足以下約束：1）任意批次的工件只屬于一類工件；2）將所有調(diào)度子批送入機(jī)床的概率相同；3）初始時(shí)刻，所有子批只要滿足工序機(jī)床選擇都可能被加工；4）任意子批只能在當(dāng)前工序加工完成之后才能加工下一道工序；5）不同子批之間沒有先后加工順序的約束；6）任意時(shí)刻，每臺(tái)機(jī)床上只能加工任意一種工件的工序；7）機(jī)床加工任意批次的工件，必須將該批次內(nèi)的工件全部加工完后才能加工下一個(gè)批次；8）不考慮機(jī)床準(zhǔn)備時(shí)間和換刀時(shí)間。

表1 調(diào)度問題參數(shù)

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

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

約束條件為

式（2）是對加工任務(wù)排隊(duì)時(shí)間的約束；式（3）是對加工任務(wù)工藝路線的相關(guān)約束；式（4）表示同時(shí)刻同1臺(tái)機(jī)床只能加工1道工序；式（5）是對批次零件數(shù)量和批次總數(shù)的定義；式（6）表示初始時(shí)刻上機(jī)概率相等；式（7）表示任意工件的子批工序只能在1臺(tái)機(jī)床上加工。

1.3 等量分批策略

實(shí)際生產(chǎn)中，工件總數(shù)存在不能完全等分的情況。工件i待加工數(shù)量為Qi，基準(zhǔn)批量為Bi，分割成s個(gè)子批，每個(gè)批次的批量為

2 改進(jìn)GA

GA 是運(yùn)用最廣泛的算法，對求解復(fù)雜柔性車間分批問題有較強(qiáng)的適用性，并能得到相對滿意的結(jié)果。染色編碼由兩部分組成，前半部分是每個(gè)子批的工序，后半部分是子批工序選擇的加工機(jī)床。改進(jìn)GA 流程如圖1 所示。利用改進(jìn)的適應(yīng)度函數(shù)，結(jié)合自適應(yīng)交叉變異概率，重新調(diào)整交叉和變異算子，使算法在廣域搜索范圍內(nèi)維持種群多樣性、局域搜索保持收斂性。

圖1 改進(jìn)GA流程圖

2.1 染色體的編碼與解碼

染色體前半部分選用基于工序編碼，后半部分是基于機(jī)床編碼，假設(shè)有2 類工件待加工，每類工件有2 道工序，工件數(shù)量均為8 個(gè)，均分為2 批，編碼如圖2 所示。圖2a 中前半部分表示子批的工序編碼，后半部分表示子批工序選擇機(jī)床的編碼。染色體編碼含義如表2所示。

圖2 染色體分段編碼

表2 染色體編碼數(shù)字說明

解碼是將染色體轉(zhuǎn)化成調(diào)度結(jié)果的過程。工件的批量均分使同一種工件不同批次工序之間相互獨(dú)立，不存在先后工序約束，整個(gè)加工過程可以并行運(yùn)行。解碼步驟如下：1）從左至右依次遍歷染色體中子批工序基因，取出工序基因分隔符0左邊的工件i和右邊的批次s，并由工件種類i和子批工序p重復(fù)出現(xiàn)的次數(shù)確定加工機(jī)床；2）比較當(dāng)前工序待加工機(jī)床累計(jì)時(shí)間與該工件工序加工累計(jì)時(shí)長，選出較大值作為當(dāng)前批次工序加工的開始時(shí)間，并利用數(shù)學(xué)模型中式（2）計(jì)算完工時(shí)間；3）遍歷染色體基因，將每個(gè)工序基因開始和完工時(shí)間放入1個(gè)矩陣數(shù)組中，利用數(shù)學(xué)模型中式（4）計(jì)算；4）遍歷步驟3）中完工時(shí)間矩陣數(shù)組，將完工時(shí)間最小染色體作為當(dāng)代種群中最優(yōu)染色體。

2.2 計(jì)算適應(yīng)度與選擇算子

完工時(shí)間越小，則染色體的基因越優(yōu)良。染色體適應(yīng)度用于評(píng)判染色體的優(yōu)劣，適應(yīng)度越大，被選擇的概率越大。采用改進(jìn)適應(yīng)度函數(shù)使染色體區(qū)分度更加明顯，也使劣質(zhì)基因有一定概率被選中。

假設(shè)當(dāng)前有5個(gè)批次的工件，每個(gè)批次的完工時(shí)間、傳統(tǒng)的適應(yīng)度函數(shù)（取最大完工時(shí)間倒數(shù)），改進(jìn)后的適應(yīng)度函數(shù)以及染色體被選中概率如表3所示。改進(jìn)的適應(yīng)度函數(shù)為

表3 不同批次工件參數(shù)變化

式中：λ1為s(i)的最小值；λ2為s(i)的最大值；c為任意較大常數(shù)，算法求解中取100，采用輪盤賭的方法選擇算子。

2.3 交叉操作

交叉操作是GA 的關(guān)鍵部分，是種群保持多樣性的途徑，交叉有利于產(chǎn)生優(yōu)秀的個(gè)體，從而獲得優(yōu)質(zhì)的調(diào)度解。染色體編碼由子批工序和機(jī)床選擇基因構(gòu)成，因此交叉包含批次工序基因交叉和機(jī)床選擇基因交叉。

針對子批工序基因交叉，采用部分映射交叉［11］，交叉步驟如圖3所示：1）從2到1/2染色體長度中隨機(jī)產(chǎn)生1個(gè)整數(shù)作為交叉點(diǎn)，假設(shè)產(chǎn)生的交叉點(diǎn)為4，取出交叉點(diǎn)后的染色體基因，P1 交叉部分為C1′，P2 部分為C2′，將C2′從右往左，C1′從左往右依次刪除相同部分基因位，得到新的C1 和C2，如圖3a 箭頭指向所示；2）處理P1 和P2 中多余和缺失的基因，遍歷P1未交叉部分的工序基因位，如圖3b中箭頭指向所示，P1基因位101與C2中的基因位101 相同，則用P1 中101 基因位由C1 中的基因201替換。P2中未交叉部分的處理方式和P1一致。子代S1和S2如圖3c所示。

圖3 染色體批次工序的交叉過程

機(jī)床選擇基因在交叉時(shí)，與工序交叉同等重要，決定算法在搜索過程中的全局收斂性。根據(jù)染色體在交叉過程中子代繼承父代優(yōu)良特征，針對機(jī)床基因采用新的交叉方式，即交叉部分保持父代中基因不變，未交叉部分重新選擇機(jī)床，機(jī)床基因交叉步驟如圖4所示：1）交換染色體P1、P2批次工序基因同時(shí)交換工序?qū)?yīng)的機(jī)床基因，機(jī)床基因未交叉部分暫時(shí)用0代替，得到S1和S2；2）遍歷S1中未交叉工序基因位和P1的工序基因，若S1中工序基因與P1中工序基因相同，則將P1工序基因?qū)?yīng)的機(jī)床基因復(fù)制到S1中工序基因位對應(yīng)機(jī)床基因位置處替換0；3）重復(fù)前2個(gè)步驟，將S2染色體中0位置用P2中機(jī)床基因進(jìn)行替換。

圖4 機(jī)床基因交叉過程

2.4 變異操作

變異操作有助于算法在收斂過程中跳出局部最優(yōu)，交叉之后通過變異操作獲得新的染色體，利用較小擾動(dòng)增加種群的多樣性。針對工件分批提出混合變異的方法，基于隨機(jī)和輪盤賭相結(jié)合的方式選擇機(jī)床基因，變異過程如圖5 所示：1）產(chǎn)生一個(gè)不大于工件種類總數(shù)N的隨機(jī)整數(shù)n1，取出第n1類工件子批工序基因和機(jī)床選擇基因，將子批工序基因逆序排列，獲得新的工序基因，子批工序?qū)?yīng)的機(jī)床基因設(shè)為0；2）從n1類工件子批集合｛s1,s2…si｝中隨機(jī)產(chǎn)生1 個(gè)s整數(shù)，遍歷第s子批的工序基因，根據(jù)工件種類n1和加工工序獲得所有可能的加工機(jī)床J1和所有可能的加工時(shí)間T1；3）根據(jù)工件可能加工時(shí)間T1，使用輪盤賭的方式選擇具體的加工時(shí)間t，從而為工件子批工序選擇相應(yīng)的加工機(jī)床；4）將n1類工件子批集合剩余子批使用隨機(jī)方式，選擇加工機(jī)床；5）將變異后產(chǎn)生的工件子批工序基因和機(jī)床選擇基因替換變異前染色體基因位。

圖5 染色體變異過程

2.5 自適應(yīng)交叉變異概率

算法求解前期，采用較小的交叉率，種群難以選出較優(yōu)的調(diào)度方案。伴隨算法的推進(jìn)，針對適應(yīng)度較高的個(gè)體采用大的交叉率和變異率，使優(yōu)質(zhì)染色體遭到破壞，算法陷入局部最優(yōu)。采用文獻(xiàn)［12］提出的自適應(yīng)交叉和變異概率，算法的收斂性和魯棒性都有所改善，交叉概率和變異概率為

式中：系數(shù)A為9.903；pcmax為交叉率上限；pcmin為交叉率下限；pmmax為變異率上限；pmmin為變異率下限；fmax、fmin、favg分別為種群中最大適應(yīng)度和最小適應(yīng)度以及平均適應(yīng)度；f′為參與交叉的2 個(gè)體中最大適應(yīng)度；f為變異個(gè)體適應(yīng)度。

3 實(shí)例測試對比分析

在Windows10 操作系統(tǒng)中利用MATLAB2019a進(jìn)行實(shí)驗(yàn)，利用文獻(xiàn)［9］的實(shí)例數(shù)據(jù)驗(yàn)證改進(jìn)GA的有效性。針對4類工件，每類工件8個(gè)，有6臺(tái)加工機(jī)床，每類工件有3 道工序，每道工序可以在多臺(tái)機(jī)床上加工。采用等量分批的方式，使用標(biāo)準(zhǔn)GA和改進(jìn)GA分別求解。

3.1 相同分批方案不同算法對比

將工件進(jìn)行均等分批調(diào)度，試驗(yàn)所得最佳分批結(jié)果為［3,3,3,3］，4類工件都均分為3批，每類子批的批量為［3,3,2］，即子批1批量為3個(gè)，子批2批量為3個(gè)，子批3批量為2個(gè)。算法初始參數(shù)見表4。

表4 算法初始化參數(shù)

調(diào)度甘特圖如圖6 所示，改進(jìn)GA 最佳調(diào)度時(shí)間為71 h，相比于標(biāo)準(zhǔn)GA 縮短29 h。圖7 為工件完工時(shí)間搜索過程，標(biāo)準(zhǔn)GA 在92 代左右收斂，最小完工時(shí)間為100 h，過早陷入局部最優(yōu)，改進(jìn)GA在76代左右收斂，最大完工時(shí)間為71 h，獲得較優(yōu)調(diào)度解，明顯改善算法全局部尋優(yōu)能力。文獻(xiàn)［9］中工件加工最大完工時(shí)間為87 h，最優(yōu)子批為13，相當(dāng)于文獻(xiàn)［9］使用更少的子批，使得生產(chǎn)管理簡化，體現(xiàn)改進(jìn)算法的優(yōu)越性。種群在每次迭代過程中當(dāng)代種群的最小完工時(shí)間和種群完工時(shí)間的平均值如表5所示。

圖6 調(diào)度甘特圖

圖7 算法搜索過程

表5 某代運(yùn)行結(jié)果對比h

3.2 算法穩(wěn)定性分析

為驗(yàn)證算法穩(wěn)定性，采用文獻(xiàn)［9］中實(shí)例數(shù)據(jù)在改進(jìn)GA 和標(biāo)準(zhǔn)GA 中分別單獨(dú)運(yùn)行30 次，仿真結(jié)果如圖8 所示。圖8 為比較試驗(yàn)，改進(jìn)GA 與標(biāo)準(zhǔn)GA使用相同參數(shù)以及相同分批方案，經(jīng)過獨(dú)立的30 次運(yùn)行測試。改進(jìn)GA 求出4 次最優(yōu)解71 h，優(yōu)于標(biāo)準(zhǔn)GA的1次最優(yōu)解91 h，且改進(jìn)GA穩(wěn)定在71～76 h，標(biāo)準(zhǔn)GA 在91～103 h 且波動(dòng)較大。改進(jìn)GA 平均最小完工時(shí)間為73.47 h，而GA 平均最小完工時(shí)間為97.27 h，驗(yàn)證了改進(jìn)GA對柔性制造車間等量分批調(diào)度問題求解的穩(wěn)定性。

圖8 算法獨(dú)立運(yùn)行對比

3.3 算法有效性分析

為檢測算法有效性，從30 組運(yùn)算結(jié)果中隨機(jī)抽選5組樣本進(jìn)行ANOVA檢驗(yàn)，假設(shè)改進(jìn)GA對調(diào)度解無顯著影響。隨機(jī)抽選的數(shù)據(jù)如表6所示。

表6 樣本數(shù)據(jù)

ANOVA 檢驗(yàn)之前，對樣本數(shù)據(jù)進(jìn)行方差齊次檢驗(yàn)，基于最小完工時(shí)間平均值顯著性為0.318，大于0.05，故ANOVA 分析有效。樣本數(shù)據(jù)ANOVA分析結(jié)果如表7 所示。表7 中F值遠(yuǎn)大于其臨界值，因此拒絕原假設(shè)，即改進(jìn)GA 對調(diào)度解顯著相關(guān)，關(guān)系強(qiáng)度為

表7 ANOVA分析

式中：SSA 為組間誤差平方和；SST 為總誤差平方和；R為關(guān)系強(qiáng)度統(tǒng)計(jì)量。由式（12）得R為0.97，大于0.8，因此改進(jìn)GA影響程度為重度相關(guān)。

3.4 改進(jìn)GA性能討論與分析

相比于標(biāo)準(zhǔn)GA，當(dāng)種群中染色體區(qū)分度較小時(shí)，改進(jìn)適應(yīng)度函數(shù)將目標(biāo)值進(jìn)行尺度變換，不僅使個(gè)體之間具有較高的區(qū)分度，并且使較差的個(gè)體仍有繁殖的機(jī)會(huì)，強(qiáng)化了算法的選擇功能。

在標(biāo)準(zhǔn)GA 交叉過程中，待交叉的工序任意選擇可加工機(jī)床。改進(jìn)GA交叉過程中，保留部分父代工序基因?qū)?yīng)的機(jī)床基因，使得染色體在尋優(yōu)過程中能較好地遺傳父代優(yōu)質(zhì)基因，避免工序隨機(jī)匹配加工機(jī)床，有效防止優(yōu)質(zhì)解流失，從而提高算法的全局尋優(yōu)能力。

標(biāo)準(zhǔn)GA通過交換工序中任意2個(gè)基因位及其對應(yīng)的機(jī)床基因位實(shí)現(xiàn)變異，可能導(dǎo)致待加工工序和可選加工機(jī)床集不對應(yīng)，從而產(chǎn)生不可行解，需要對解重新檢查并處理。改進(jìn)GA在變異操作中，針對某類工件所有子批工序進(jìn)行變異，在改變子批工序順序的同時(shí)，采用輪盤賭的方式選擇加工時(shí)間較短的機(jī)床，避免無效解的產(chǎn)生，同時(shí)使變異過程具有方向性和目的性，使算法期望搜索效率更高。

4 結(jié)論

文中研究了柔性車間分批調(diào)度問題，以最小完工時(shí)間作為優(yōu)化目標(biāo)，對個(gè)體的適應(yīng)度、染色體的交叉方式以及變異方式進(jìn)行了改進(jìn)，并利用自適應(yīng)交叉變異概率動(dòng)態(tài)調(diào)整交叉和變異過程。相比整批調(diào)度方式，等量分批能大幅度縮短車間加工時(shí)間，提高機(jī)床加工效率。在相同的分批方案下，改進(jìn)GA 求解能得到較好的收斂結(jié)果。文中未考慮機(jī)床換刀時(shí)間、機(jī)床負(fù)荷以及機(jī)床功耗等問題，這是后續(xù)研究的重點(diǎn)。