基于擴(kuò)展雙資源約束型航空構(gòu)件制造車間調(diào)度方法

婁航宇，張吉善，趙云博

(東北大學(xué) 工商管理學(xué)院，遼寧 沈陽(yáng) 110819)

0 引言

近年來(lái)隨著國(guó)家科研水平整體提升，高端制造業(yè)蓬勃發(fā)展。航空構(gòu)件作為航天設(shè)備的重要組成部分，其制造過(guò)程是航天工業(yè)的關(guān)鍵環(huán)節(jié)。航空構(gòu)件屬于典型的單件小批量、多品種的生產(chǎn)方式，不同品種甚至同種品種不同型號(hào)的構(gòu)件間工藝路線相差巨大[1-2]。實(shí)際航空構(gòu)件制造中有如下特征：

(1)制造工藝復(fù)雜，加工精度要求高。不同構(gòu)件間工藝順序不同，加工時(shí)間存在較大差異。

(2)雙資源約束。航空構(gòu)件因其特殊性，在制造過(guò)程中需嚴(yán)格把關(guān)，關(guān)鍵構(gòu)件需高精度設(shè)備與高技能員工協(xié)同完成。

(3)按設(shè)備組加工，數(shù)控設(shè)備居多。航空構(gòu)件制造車間常按機(jī)群方式布置，不同設(shè)備組配備不同員工且其能力均具有柔性，數(shù)控設(shè)備除上下料外無(wú)需人員輔助。

綜上述所述，本文考慮將其抽象為擴(kuò)展雙資源約束柔性作業(yè)車間調(diào)度問題(Extend Dual Resource Constraints, EDRC)。

雙資源約束柔性作業(yè)車間調(diào)度(Dual Resource Constraints, DRC)問題在柔性作業(yè)車間調(diào)度(Flexible Job shop Scheduling Problem, FJSP)的基礎(chǔ)上增加了設(shè)備與人員資源約束，是一種更復(fù)雜的NP-Hard問題[3]。鑒于此類問題的隨機(jī)性與復(fù)雜性，受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。Nelson[4]首次關(guān)注設(shè)備與人員資源問題，并將問題定義為雙資源約束問題。Li等[5]采用改進(jìn)分支種群算法求解DRC問題，使得完工時(shí)間及成本最小化。Cao等[6]針對(duì)DRC問題采用基于工序的二段式編碼方式，設(shè)計(jì)一種包含能動(dòng)解碼方式及有效交叉算子的改進(jìn)免疫遺傳算法求解以提高算法的搜索能力，在實(shí)例仿真階段假設(shè)所有工序均為機(jī)加工序且由普通機(jī)床加工。陳呈頻等[7]設(shè)計(jì)了一種改進(jìn)智能水滴算法求解雙資源約束問題以使成本最小化，假設(shè)員工可操縱任一臺(tái)設(shè)備即具備全部柔性，但在實(shí)際生產(chǎn)中員工較難滿足全部柔性。多數(shù)已有文獻(xiàn)在模型構(gòu)建上普遍理想化，例如，假定工件工序均為普通機(jī)加工序，工序加工全程需員工參與；員工具備全部柔性；忽略數(shù)控設(shè)備參與工件加工等，上述假設(shè)條件很難運(yùn)用于實(shí)際生產(chǎn)環(huán)境。近年來(lái)，動(dòng)態(tài)環(huán)境及準(zhǔn)備時(shí)間等影響因素受到重視。黃媛等[8]針對(duì)動(dòng)態(tài)條件下的DRC問題設(shè)計(jì)了三層調(diào)度系統(tǒng)及染色體還原機(jī)制，降低了隨機(jī)擾動(dòng)對(duì)調(diào)度的影響。Wu等[9]利用混合遺傳算法求解考慮員工具有學(xué)習(xí)遺忘效應(yīng)的DRC問題。

近十幾年來(lái)，越來(lái)越多基于模擬自然現(xiàn)象及生物進(jìn)化的元啟發(fā)式算法應(yīng)用于DRC問題，如遺傳算法(Genetic Algorithm, GA)[10]、粒子群算法(Particle Swarm Optimization, PSO)[11]、變鄰域搜索算法(Variable Neighborhood Search, VNS)[12]、模擬退火算法(Simulated Annealing, SA)[13]及果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm, FOA)[14]等。教與學(xué)優(yōu)化(Teaching-Learning-Based Optimization, TLBO)算法是由Rao等[15]于2010年提出的一種新型基于群體智能的進(jìn)化算法，并廣泛應(yīng)用于各類組合優(yōu)化問題。Zheng等[16]研究多技能資源約束項(xiàng)目調(diào)度問題并利用TLBO算法求解，在教和學(xué)兩階段均采用交叉操作進(jìn)行學(xué)習(xí)。Tuncel等[17]利用TLBO算法優(yōu)化工業(yè)裝配系統(tǒng)中的雙邊線平衡問題，以提高產(chǎn)線效率。Xu等[18]率先采用TLBO算法求解具有模糊作業(yè)時(shí)間的柔性作業(yè)車間調(diào)度問題，以完工時(shí)間為優(yōu)化目標(biāo)并獲得較優(yōu)調(diào)度方案。

本文結(jié)合航空構(gòu)件在制造過(guò)程中的實(shí)際情況，在DRC問題基礎(chǔ)上考慮數(shù)控設(shè)備參與加工、裝夾準(zhǔn)備時(shí)間、構(gòu)件工藝上存在機(jī)加/非機(jī)加工序交替和重要工序需特定設(shè)備與人員資源要求，提出一種擴(kuò)展雙資源約束柔性作業(yè)車間調(diào)度問題(EDRC)并構(gòu)建調(diào)度模型。目前，采用TLBO算法求解DRC問題的相關(guān)文獻(xiàn)較少，本文首次采用并設(shè)計(jì)了多小組協(xié)同教與學(xué)優(yōu)化算法(Multi-group TLBO, MTLBO)求解EDRC問題，以確定工序維、設(shè)備維和人員維的選擇排序問題。最后，在避免設(shè)備及人員使用沖突的情況下，使得完工時(shí)間、總拖期、能耗和成本最優(yōu)。

1 擴(kuò)展雙資源約束柔性作業(yè)車間調(diào)度模型

1.1 問題描述

通過(guò)為各工序選擇最合適的“設(shè)備—工人”組合，優(yōu)化各設(shè)備上機(jī)加工序執(zhí)行次序，使得完工時(shí)間，總拖期，能源消耗及加工成本最小。其他假設(shè)條件如下：

(1)設(shè)備、工件及員工在零時(shí)刻均空閑可用;

(2)每臺(tái)設(shè)備在同一時(shí)刻最多加工一個(gè)工件，每個(gè)工件在同一時(shí)刻最多被一臺(tái)設(shè)備加工;

(3)工件加工時(shí)間包含運(yùn)輸時(shí)間、卡具及刀具更換等輔助時(shí)間;

(4)員工能力具有柔性且效率一致;

(5)設(shè)備加工期間不允許中斷、搶占。

1.2 模型構(gòu)建

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

(1)完工時(shí)間最小 產(chǎn)品制造周期是衡量企業(yè)生產(chǎn)效率的重要指標(biāo)。本文將其定義為所有工件中的最大完成時(shí)間。

min(f1)=min(maxCi),?i。

(1)

(2)總拖期最小 交貨期直接影響企業(yè)信譽(yù)及客戶滿意度，按期交貨有助于企業(yè)的資金周轉(zhuǎn)。本文定義總拖期為所有工件的拖期之和。

(2)

(3)總能耗最小 隨著能耗成本的攀升與節(jié)能思想的深入，企業(yè)愈發(fā)重視能耗指標(biāo)。加工過(guò)程中能耗可視為由設(shè)備空轉(zhuǎn)能耗(Ew)與設(shè)備加工能耗(Ed)兩部分組成。為更貼近實(shí)際生產(chǎn)，設(shè)備完成本機(jī)全部加工任務(wù)后即可停止。

(3)

(4)生產(chǎn)成本最小 生產(chǎn)成本是直接影響企業(yè)利潤(rùn)的重要因素，本文視生產(chǎn)成本由機(jī)床使用費(fèi)用(Fm)、員工費(fèi)用(Fw)、原材料成本(Fs)及電力成本(Fe)四部分構(gòu)成。

min(f4)=Fm+Fw+Fs+Fe

(4)

結(jié)合企業(yè)對(duì)不同目標(biāo)的期望差異及不同目標(biāo)間的重要性，采用式(5)對(duì)上述目標(biāo)加權(quán)整合。

min(F)=ω1f1+ω2f2+ω3f3+ω4f4。

(5)

1.2.2 約束條件

(6)

(7)

(8)

XijkXijr(ETijk-STijr)×(STijk-ETijr)≥0；

(9)

XijklXfpkl(ETijkl-STfprl)×(ETfprl-STijkl)>0,

mk或mr為非數(shù)控設(shè)備；

(10)

(11)

mk或mr為數(shù)控設(shè)備。

(12)

其中：式(6)表示工序的加工時(shí)間由基本加工時(shí)間、上料時(shí)間和下料時(shí)間組成；式(7)表示工序需滿足工藝路線要求；式(8)表示每臺(tái)設(shè)備在同一時(shí)刻至多加工一個(gè)工件；式(9)表示每個(gè)工件在同一時(shí)刻至多能被一臺(tái)設(shè)備加工；式(10)表示工人操縱非數(shù)控設(shè)備時(shí)，需參與工序的整個(gè)加工過(guò)程；式(11)和式(12)表示工人只參與數(shù)控設(shè)備與上料與下料環(huán)節(jié)，其他時(shí)間可參與其他設(shè)備加工過(guò)程。

2 多小組協(xié)同“教”與“學(xué)”優(yōu)化算法

TLBO算法是一種群體智能進(jìn)化算法，教師與學(xué)生組成的班級(jí)相當(dāng)于進(jìn)化算法中的種群。該算法通過(guò)模擬教師授課與學(xué)生自學(xué)兩個(gè)階段來(lái)實(shí)現(xiàn)群體在優(yōu)化目標(biāo)上的整體提升。標(biāo)準(zhǔn)TLBO算法對(duì)教師與學(xué)生單一分組，在求解過(guò)程中速度慢且易陷入局部最優(yōu)[19]。

本文設(shè)計(jì)了一種求解EDRC問題的MTLBO算法對(duì)學(xué)生群體進(jìn)行分組教學(xué)。針對(duì)求解離散型問題，對(duì)標(biāo)準(zhǔn)TLBO的兩階段連續(xù)更新公式進(jìn)行離散化，在維持核心框架不變的基礎(chǔ)上引入多種學(xué)習(xí)算子，以增強(qiáng)離散解空間內(nèi)的全局搜索能力。在教階段，各組設(shè)置一名組長(zhǎng)對(duì)所在小組教學(xué)；在學(xué)階段，根據(jù)適應(yīng)度值優(yōu)劣將學(xué)生分為優(yōu)生與差生，分別執(zhí)行所設(shè)計(jì)的縱向局部搜索學(xué)習(xí)和橫向?qū)W習(xí)策略。最后，當(dāng)某小組連續(xù)L代平均適應(yīng)度值未提升時(shí)，執(zhí)行基于最優(yōu)小組的組間交流操作，實(shí)現(xiàn)對(duì)組內(nèi)成員的擾動(dòng)。算法各階段具體操作在下文詳細(xì)闡述，算法流程圖如圖1所示。

2.1 編碼機(jī)制

與其他優(yōu)化算法類似，在求解優(yōu)化過(guò)程中需建立個(gè)體與實(shí)際調(diào)度的映射關(guān)系?？紤]到EDRC問題特性，本文設(shè)計(jì)了三層編碼機(jī)制隨機(jī)初始化每名學(xué)生。第一層為工序維OS,采用基于工序編碼方式，長(zhǎng)度等于總工序數(shù)m×n，每個(gè)工件的各個(gè)工序在OS中由該工件號(hào)表示，工件號(hào)的第i次出現(xiàn)即表示該工件的第i道工序；第二維為設(shè)備維MS，根據(jù)工件數(shù)分成n個(gè)子片段，第i片段第j個(gè)數(shù)字對(duì)應(yīng)加工數(shù)分成n個(gè)子片段，第i片段第j個(gè)數(shù)字對(duì)應(yīng)加工Oij的設(shè)備在候選設(shè)備集Mij中的位置；第三層為員工維WS，編碼方式與MS類似，第i片段第j個(gè)數(shù)字代表參與Oij加工的員工序號(hào)，編碼示意圖如圖2所示。

該編碼表達(dá)3個(gè)工件由5名工人在6臺(tái)設(shè)備上加工的調(diào)度，其中工件1、工件2和工件3各包含2道工序、3道工序和2道工序。由解碼工序維OS可知，工件的加工順序?yàn)镺31→O21→O11→O12→O32→O22→O23。針對(duì)O31結(jié)合MS與WS可知，O31由工人W4在M1上完成，其余工序以此類推。

2.2 解碼機(jī)制

不同解碼方法會(huì)對(duì)調(diào)度結(jié)果產(chǎn)生影響，貪婪插入解碼[20]及全主動(dòng)解碼[21]兩種解碼方法可以有效縮短完工時(shí)間。本文在貪婪插入解碼基礎(chǔ)上，綜合考慮人員柔性與數(shù)控設(shè)備屬性，設(shè)計(jì)一種適用于EDRC問題的主動(dòng)解碼方法，具體步驟如下：

步驟1自左向右讀取OS向量中的工序Oij，從MS與WS向量中提取其對(duì)應(yīng)設(shè)備mk及人員wl。

步驟2獲取工序Oij加工時(shí)間Pijk，尋找設(shè)備mk上所有可用空閑時(shí)間[TSmk,TEmk]，員工wl所有可用空閑時(shí)間[TSwl,TEwl]。TS，TE分別對(duì)應(yīng)空閑開始時(shí)間與結(jié)束時(shí)間。

步驟3按式(13)計(jì)算Oij最早開始加工時(shí)間ta：

ta=max(Ci,(j-1),TSmk,TSwl)。

(13)

步驟4判斷工序是否滿足插入條件。非數(shù)控設(shè)備按式(14)，數(shù)控設(shè)備按式(15)判斷Oij是否滿足插入規(guī)則，若不滿足，則安排在mk及wl最后一道工序結(jié)束后進(jìn)行加工，開工時(shí)間tb由式(16)計(jì)算，主動(dòng)解碼示意圖如圖3所示。

ta+t0+Pjkl+t1≤min(TEmk,TEwl)，

(14)

ta=min{[(ta+t0+Pijl+t1)≤TEmk]∧

[(ta+t0)∈[TSwl,TEwl]]∧

[(ta+t0+Pijl+t1)∈[TSwl,TEwl]]}，

(15)

tb=max(LMk,LWl)。

(16)

其中：LMk表示設(shè)備k上最后工序完工時(shí)間，LWl表示工人l執(zhí)行完最后工序的時(shí)間。

步驟5重復(fù)步驟1～步驟4，直至所有工序均安排完畢。

2.3 “教師”階段

教師階段，利用教師與學(xué)生之間的差異性向?qū)W生傳授知識(shí)，以提高班級(jí)整體學(xué)習(xí)水平。針對(duì)本文所提算法，選出每組中適應(yīng)度值最優(yōu)個(gè)體作為該組教師，負(fù)責(zé)本組的教學(xué)任務(wù)。教學(xué)過(guò)程如下：

首先由式(17)計(jì)算每名學(xué)生與教師間的差距D_Mi。

D_Mi=ri×(Mteacher-TF×Mmean)。

(17)

式中：ri=rand(0,1)表示學(xué)習(xí)步長(zhǎng)；TF=[1+rand(0,1)]表示教學(xué)因子；Mteacher，Mmean分別表示教師成績(jī)和當(dāng)代成績(jī)平均水平。

其次，每名學(xué)生根據(jù)D_Mi按式(18)向教師靠攏。

(18)

對(duì)于離散型優(yōu)化問題，混合采用多種交叉變異算子可提高算法的搜索能力及收斂性能[22]，故針對(duì)問題編碼特性設(shè)計(jì)3種離散教學(xué)算子，如圖4所示，以避免陷入局部最優(yōu)。根據(jù)式(17)計(jì)算個(gè)體間離散差，教學(xué)過(guò)程中OS維隨機(jī)執(zhí)行優(yōu)先操作交叉POX(precedence operation crossover)或基于工件交叉JBX(job-based crossover)，MS，WS維執(zhí)行兩點(diǎn)交叉TPX(the two-point crossover)[23]，維持群體多樣性同時(shí)擴(kuò)大搜索范圍。若教學(xué)后成績(jī)提高則接受教學(xué)后個(gè)體，否則維持原個(gè)體不變。

2.4 “學(xué)生”階段

學(xué)生階段模擬學(xué)生互相學(xué)習(xí)的過(guò)程，取長(zhǎng)補(bǔ)短共同進(jìn)步。標(biāo)準(zhǔn)教與學(xué)算法中單一形式的相互學(xué)習(xí)不便于區(qū)分學(xué)生學(xué)習(xí)能力，難以做到因材施教。本文針對(duì)優(yōu)生與差生的學(xué)習(xí)能力差異，設(shè)計(jì)了兩階段差異性學(xué)習(xí)策略，即優(yōu)生執(zhí)行縱向?qū)W習(xí)策略，差生執(zhí)行橫向?qū)W習(xí)策略，便于學(xué)生充分拓展與發(fā)掘知識(shí)提高個(gè)人成績(jī)。第i次迭代中，學(xué)生p向q學(xué)習(xí)的過(guò)程按式(19)和式(20)進(jìn)行：

(19)

(20)

式中F(Xi,p)表示第i代個(gè)體p的適應(yīng)度值，當(dāng)F(Xi,p)優(yōu)于F(Xi,q)時(shí)接受新個(gè)體，否則維持舊個(gè)體不變。

與教師階段相似，學(xué)生階段在維持學(xué)習(xí)框架不變的基礎(chǔ)上，引入3種自學(xué)算子以適應(yīng)離散型問題，如圖5所示。OS維隨機(jī)執(zhí)行3點(diǎn)鄰域全排列變異或互換變異算子。MS，WS維執(zhí)行多點(diǎn)變異算子，隨機(jī)選擇3個(gè)位置并替換為其他合法值。

該階段對(duì)小組中全部個(gè)體進(jìn)行適應(yīng)度值評(píng)估，排名前1/2的學(xué)生定義為優(yōu)生，其余學(xué)生認(rèn)定為差生。

2.4.1 “優(yōu)生”縱向自學(xué)習(xí)策略

優(yōu)生相比差生普遍具有更強(qiáng)的自學(xué)能力，通過(guò)對(duì)自身擅長(zhǎng)領(lǐng)域進(jìn)行深入挖掘，提高自身成績(jī)。針對(duì)不同優(yōu)生Xi的成績(jī)，賦予不同的探索次數(shù)N(i)。文獻(xiàn)[24]研究發(fā)現(xiàn)，賦予自學(xué)能力強(qiáng)的優(yōu)生更多探索次數(shù)一方面有利于個(gè)體到達(dá)更遠(yuǎn)的鄰域，另一方面有利于對(duì)個(gè)體的鄰域進(jìn)行更加細(xì)致的搜索以提升算法局部搜索能力，探索次數(shù)N(i)由式(21)確定：

(21)

式中：Fi表示該小組內(nèi)第i個(gè)個(gè)體的成績(jī)；Fmax、Fmin為小組內(nèi)最優(yōu)和最差的成績(jī)；UL為設(shè)定的探索次數(shù)上限；LL為探索次數(shù)下限?？紤]到算法執(zhí)行效率并參考文獻(xiàn)[25]，設(shè)定UL=15，LL=1。

若經(jīng)過(guò)縱向自學(xué)習(xí)后的當(dāng)前個(gè)體Xq優(yōu)于原個(gè)體Xp，則接受當(dāng)前個(gè)體，否則維持原個(gè)體不變，縱向自學(xué)習(xí)步驟如圖6所示。

2.4.2 “差生”橫向互學(xué)習(xí)策略

鑒于差生自學(xué)習(xí)能力薄弱的特征，采用組間互學(xué)方式向其他學(xué)生學(xué)習(xí)。通過(guò)向更優(yōu)個(gè)體學(xué)習(xí)，有機(jī)會(huì)搜尋差生擅長(zhǎng)的學(xué)習(xí)領(lǐng)域而成為優(yōu)生，從而進(jìn)行縱向自學(xué)習(xí)，提升整體的學(xué)習(xí)成績(jī)。具體學(xué)習(xí)方式為：根據(jù)成績(jī)排名，個(gè)體Xp隨機(jī)選取比其排名更優(yōu)的個(gè)體Xq學(xué)習(xí)，橫向?qū)W習(xí)過(guò)程按式(19)及式(20)進(jìn)行。

2.5 基于最優(yōu)小組協(xié)同交流階段

為全面提高各小組的學(xué)習(xí)效果，當(dāng)某小組的學(xué)習(xí)成績(jī)得不到進(jìn)一步提升時(shí)，執(zhí)行組間交流操作與其他小組交流學(xué)習(xí)心得。本文設(shè)定當(dāng)某小組的最好成績(jī)連續(xù)L代未提升時(shí)，采用輪盤賭方式在最優(yōu)小組(平均成績(jī)最佳)中選擇H名學(xué)生，替換當(dāng)前小組中最差的H名學(xué)生，最優(yōu)小組中每名學(xué)生的選中概率

(22)

算法迭代初期，為充分發(fā)揮個(gè)體創(chuàng)造力，執(zhí)行協(xié)同交流操作時(shí)參與交流的學(xué)生數(shù)H應(yīng)較小。隨著迭代次數(shù)增加，個(gè)體的成績(jī)與能力成績(jī)趨于穩(wěn)定，應(yīng)適當(dāng)增加交流人數(shù)以增強(qiáng)協(xié)同交流強(qiáng)度，小組中參與交流的學(xué)生數(shù)

H=Gen/C。

(23)

式中：Gen表示當(dāng)前迭代次數(shù)，C為常數(shù)。組間交流操作可視為對(duì)陷入局部最優(yōu)的小組進(jìn)行擾動(dòng)，有利于維持子代種群多樣性，并提升算法的全局搜索能力。

3 實(shí)例仿真與分析

實(shí)例分析通過(guò)兩方面展開：①在FJSP問題基準(zhǔn)算例的基礎(chǔ)上生成EDRC測(cè)試算例，通過(guò)與其他算法求解結(jié)果進(jìn)行比較驗(yàn)證本文算法的有效性；②從實(shí)例應(yīng)用角度，對(duì)某航空設(shè)備制造企業(yè)的加工數(shù)據(jù)進(jìn)行整理，綜合車間內(nèi)部設(shè)備與員工能力，通過(guò)MTLBO算法得出調(diào)度方案，驗(yàn)證算法對(duì)解決EDRC問題的有效性及模型的正確性。算法在CPU-i5，3.4 GHz，內(nèi)存8.00 G的PC機(jī)上利用Python 3.6編程實(shí)現(xiàn)，算法針對(duì)各算例獨(dú)立運(yùn)行20次。

3.1 測(cè)試算例仿真與分析

本文研究EDRC問題且考慮4個(gè)優(yōu)化目標(biāo)，在FJSP問題的基準(zhǔn)算例MK01-MK10[26]基礎(chǔ)上還需增加員工數(shù)量等加工信息進(jìn)行擴(kuò)充，以證提出算法的有效性，具體加工變量取值如表1所示。

表1 加工變量信息表

基于算例MK01～MK10與表1中加工變量信息隨機(jī)生成10組測(cè)試算例IMK01～I(xiàn)MK10，對(duì)算法的有效性進(jìn)行測(cè)試與驗(yàn)證。對(duì)規(guī)模適中的IMK04算例采用Taguchi[27]正交試驗(yàn)法并參照文獻(xiàn)[25]，確定參數(shù)設(shè)置為：小組個(gè)數(shù)為4，每組學(xué)生規(guī)模為100，L=20，C=50，MaxGen=200，ω1=0.6，ω2=0.1，ω3=0.2，ω4=0.1。生成算例通過(guò)MTLBO及另外兩種算法TLBO[28]，混合遺傳算法(Hybird Genetic Algorithm, HGA)[29]求解，其中TLBO，HGA參數(shù)設(shè)置與其原文獻(xiàn)保持一致算例，運(yùn)行結(jié)果比較如表2所示。

表2 算例運(yùn)行結(jié)果比較

由表2中運(yùn)算結(jié)果可知，利用本文提出的MTLBO算法求解算例時(shí)，在10個(gè)測(cè)試算例中相比于其他兩種算法均明顯占優(yōu)，表明所設(shè)計(jì)的兩階段自學(xué)策略及分組教學(xué)方式可有效提高算法的魯棒性及搜索能力。因此，MTLBO算法可有效求解EDRC問題并具有較強(qiáng)的競(jìng)爭(zhēng)力。

由表2運(yùn)算結(jié)果可知，利用本文提出的MTLBO算法求解算例時(shí)，在10個(gè)測(cè)試算例中相比于其他兩種算法均明顯占優(yōu)，表明所設(shè)計(jì)的兩階段自學(xué)策略及分組教學(xué)方式可有效地提高算法的魯棒性及搜索能力。因此，MTLBO算法可有效求解EDRC問題并具有較強(qiáng)的競(jìng)爭(zhēng)力。

3.2 實(shí)例應(yīng)用仿真與分析

通過(guò)整理分析某航空設(shè)備制造企業(yè)生產(chǎn)車間的數(shù)據(jù)，給出7個(gè)工件的工藝流程及約束，每道工序可至少在一臺(tái)設(shè)備上加工，但加工效率與能耗存在差異。表3中給出各工序操作內(nèi)容及在可選設(shè)備上的運(yùn)行能耗與加工時(shí)間。依照工藝將工序劃分為機(jī)加工序(車、銑、鏜等操作)及非機(jī)加工序(熱處理、鉗、檢驗(yàn)操作)。車間現(xiàn)有員工6人，設(shè)備8臺(tái)分為4組：普車組、數(shù)車組、數(shù)銑組及鏜床組。每組中設(shè)備數(shù)量、性能及對(duì)應(yīng)員工均不同，表4列出各工序操作對(duì)應(yīng)的設(shè)備組及可選人員。設(shè)備M1～M8的空轉(zhuǎn)單位能耗分別為：0.56，0.45，0.48，0.96，1.05，0.30，0.42，0.40。員工單位工時(shí)費(fèi)用為15，平均工業(yè)電價(jià)e=0.77。

表3 工件工序加工信息

續(xù)表3

表4 工序可選設(shè)備與員工信息

3.2.1 考慮雙資源(DRC)約束下的實(shí)例測(cè)試

首先，考慮雙資源約束情況，即忽略數(shù)控設(shè)備對(duì)調(diào)度方案的影響，此時(shí)假設(shè)設(shè)備均為非數(shù)控。因某些重要工序需要高精度設(shè)備及高能力級(jí)別的員工協(xié)同加工，故存在設(shè)備約束及人員資源約束。采用MTLBO算法進(jìn)行求解(參數(shù)與測(cè)試實(shí)驗(yàn)中保持一致)。在最佳的調(diào)度方案下，案例的各目標(biāo)值分別為f1=74，f2=19，f3=256.9，f4=6 618.1。在此調(diào)度方案下關(guān)鍵設(shè)備(M6，M7)的稼動(dòng)率為89.5%及77.6%。調(diào)度方案Gantt圖如圖7所示，圖中M1上第一個(gè)“2-1-4”表示工序O21由員工4在設(shè)備1上完成。

3.2.2 考慮擴(kuò)展雙資源(EDRC)約束下的實(shí)例測(cè)試

考慮數(shù)控設(shè)備對(duì)調(diào)度方案的影響，數(shù)控設(shè)備切削過(guò)程中按程序運(yùn)行，不需員工參與，釋放了人員資源約束。采用本文提出的多小組協(xié)同教與學(xué)優(yōu)化算法進(jìn)行求解，得到的最佳調(diào)度方案Gantt圖如圖8所示。例如針對(duì)圖中方框O47和O15均需員工1加工時(shí)，其執(zhí)行過(guò)程為員工1在M6上裝夾完J4后數(shù)控設(shè)備M6開始自動(dòng)切削，員工1～M7上裝夾J1，M7開始自動(dòng)加工，員工1返回M6，下料操作同理，故調(diào)度方案避免了人員使用沖突。此外，如O72及O75之間為非機(jī)加(鉗、檢驗(yàn))工序預(yù)留出處理時(shí)間，相比于只考慮機(jī)加工序及普通機(jī)床調(diào)度的傳統(tǒng)雙資源問題更貼近實(shí)際生產(chǎn)。圖8中調(diào)度方案對(duì)應(yīng)的目標(biāo)分別為f1=67，f2=6，f3=198.8，f4=6 463.0，關(guān)鍵設(shè)備稼動(dòng)率為90.9%和90.5%。相較于不考慮數(shù)控設(shè)備的情況四個(gè)目標(biāo)值分別下降了9.46%、68.42%、22.62%和2.34%，關(guān)鍵設(shè)備稼動(dòng)率分別提升了1.61%和16.67%。兩種情況下的人員利用率如圖9所示。

由圖8和圖9可知，在考慮數(shù)控設(shè)備的擴(kuò)展雙資源約束情況下，員工工作負(fù)荷減輕、空閑時(shí)間增多。最優(yōu)調(diào)度方案預(yù)留出設(shè)備5，且員工存在較多空閑時(shí)間，有利于下批工件加工及應(yīng)對(duì)員工病假等其他突發(fā)情況。

3.2.3 實(shí)例求解算法對(duì)比分析

為進(jìn)一步驗(yàn)證本文提出的MTLBO算法對(duì)求解實(shí)際復(fù)雜車間調(diào)度問題的有效性，針對(duì)航空構(gòu)件制造車間調(diào)度實(shí)例分別采用TLBO算法及HGA算法進(jìn)行求解，并與本文算法進(jìn)行比較。3種算法針對(duì)實(shí)例問題的兩種情況，即DRC約束及EDRC約束下的求解結(jié)果見表5，在EDRC情況下的迭代收斂圖如10所示。

表5 不同算法求解實(shí)例結(jié)果對(duì)比

續(xù)表5

由表5可知，MTLBO算法在實(shí)例問題的求解結(jié)果上均優(yōu)于其他兩種算法。從圖10中可以得出，迭代過(guò)程中MTLBO算法的收斂速度和求解質(zhì)量明顯優(yōu)于TLBO算法及HGA算法，TLBO算法因陷入局部最優(yōu)求解結(jié)果并不理想。由此驗(yàn)證了本文提出的MTLBO算法的可行性和有效性，并可有效地運(yùn)用于航空構(gòu)件的實(shí)際生產(chǎn)中，對(duì)企業(yè)制定生產(chǎn)計(jì)劃大綱具有指導(dǎo)作用。

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

本文研究了一類復(fù)雜的擴(kuò)展雙資源約束柔性作組協(xié)同教與學(xué)算法(MTLBO算法)，這是首次運(yùn)用MTLBO算法求解此類問題。在算法核心框架不變的基礎(chǔ)上，針對(duì)求解EDRC離散型問題設(shè)計(jì)多種學(xué)習(xí)算子，保證了算法的全局搜索能力。自學(xué)階段優(yōu)生采取縱向自學(xué)策略以對(duì)優(yōu)質(zhì)區(qū)域細(xì)致搜索，平衡算法全局開發(fā)與局部搜索能力。此外，獨(dú)特的組間交流策略有利于維持種群多樣性，避免算法陷入局部最優(yōu)。通過(guò)求解測(cè)試算例驗(yàn)證了算法的可行性及有效性，并應(yīng)用于實(shí)際航空構(gòu)件生產(chǎn)車間，結(jié)果表明算法可有效求解出最佳調(diào)度方案并避免設(shè)備人員使用沖突，具備一定的工程應(yīng)用前景。

本文未考慮到動(dòng)態(tài)因素對(duì)車間調(diào)度的影響，如員工休息、設(shè)備故障及新工件到達(dá)等，這些問題將在下一步進(jìn)行研究。