基于多種群混合遺傳算法的車間實(shí)時(shí)調(diào)度系統(tǒng)

成國(guó)煌,夏勝雄,王 宇,2,嚴(yán) 睿

(1.武昌船舶重工有限責(zé)任公司,湖北 武漢 430060;2.華中科技大學(xué),湖北 武漢 430074)

基于多種群混合遺傳算法的車間實(shí)時(shí)調(diào)度系統(tǒng)

成國(guó)煌1,夏勝雄1,王 宇1,2,嚴(yán) 睿1

(1.武昌船舶重工有限責(zé)任公司,湖北 武漢 430060;2.華中科技大學(xué),湖北 武漢 430074)

針對(duì)某船廠管子加工車間的實(shí)際情況,采用動(dòng)態(tài)柔性調(diào)度技術(shù),構(gòu)建實(shí)時(shí)反饋調(diào)度模型,建立基于多種群混合遺傳算法的車間實(shí)時(shí)調(diào)度系統(tǒng),把動(dòng)態(tài)連續(xù)的調(diào)度問(wèn)題變成分塊的靜態(tài)調(diào)度問(wèn)題,使動(dòng)態(tài)問(wèn)題靜態(tài)化。針對(duì)調(diào)度問(wèn)題的求解特點(diǎn),提出基于多種群粒子群的混合遺傳算法的任務(wù)調(diào)度算法。運(yùn)用上述理論和算法,通過(guò)仿真和實(shí)際應(yīng)用,結(jié)果表明該實(shí)時(shí)調(diào)度系統(tǒng)的有效性和合理性。

遺傳算法;粒子群優(yōu)化;車間調(diào)度;實(shí)時(shí)調(diào)度系統(tǒng)

0 引 言

目前,全球造船行業(yè)已經(jīng)由典型的資金密集型、勞動(dòng)密集型傳統(tǒng)行業(yè)轉(zhuǎn)變?yōu)橘Y金密集、勞動(dòng)密集和技術(shù)密集相互并重的高新行業(yè)。因此,加快造船企業(yè)信息空間工程建設(shè),利用信息技術(shù)構(gòu)造基礎(chǔ)軟件平臺(tái),建立智能化的并行協(xié)同生產(chǎn)模型,從而實(shí)現(xiàn)企業(yè)行為模式的變革,全面提升企業(yè)的競(jìng)爭(zhēng)力。而且,由于現(xiàn)代造船企業(yè)趨向于總裝廠方向發(fā)展,其主要任務(wù)將是船體制造和管子生產(chǎn)。而管子制造是一個(gè)多工種的復(fù)合工程,船用管子數(shù)量多,品種規(guī)格復(fù)雜,其材質(zhì)、形狀和尺寸等完全一樣的極少,單項(xiàng)加工技術(shù)的提高并不能很大程度地提高管子的生產(chǎn)效率,因此管子的生產(chǎn)往往會(huì)成為造船中的瓶頸,所以研究管子的生產(chǎn)調(diào)度技術(shù),提高管子生產(chǎn)效率是造船技術(shù)的一個(gè)重要問(wèn)題。

車間柔性調(diào)度問(wèn)題多是NP難題,現(xiàn)有的調(diào)度算法主要包括物理規(guī)劃和模擬退火(simulated annealing,SA)、禁忌搜索算法 (taboo search,TS)、蟻群算法(ant system,AS)、遺傳算法(genetic algorithm,GA)、粒子群優(yōu)化 (particle swarm optimization,PSO)和混合算法等,但各種算法都有自己的優(yōu)點(diǎn)和不足[1-3]。本文結(jié)合某船廠管子加工車間數(shù)字化生產(chǎn)的實(shí)際需要,按照車間現(xiàn)用的生產(chǎn)模式,通過(guò)采用多種群混合遺傳算法的周期調(diào)度策略,解決實(shí)時(shí)反饋調(diào)度中的重調(diào)度問(wèn)題,形成實(shí)時(shí)調(diào)度的柔性計(jì)劃調(diào)度技術(shù),使得車間具備處理突發(fā)事件的能力,提高船舶制造企業(yè)的生產(chǎn)效率。

1 實(shí)時(shí)優(yōu)化調(diào)度策略

傳統(tǒng)的對(duì)生產(chǎn)調(diào)度的研究是在以下假設(shè)條件下進(jìn)行的:①被調(diào)度的工件集合是確定的;②工件的加工時(shí)間是確定的,并且在安排計(jì)劃時(shí)全部工件都已到達(dá);③加工工件的機(jī)器是連續(xù)可用的。這類調(diào)度問(wèn)題是靜態(tài)調(diào)度問(wèn)題,但實(shí)際生產(chǎn)中的大量問(wèn)題是隨機(jī)發(fā)生的。如在該船廠的管子加工車間中,由于緊急任務(wù)的加工托盤插入、加工機(jī)器出現(xiàn)故障等隨機(jī)事件,使得預(yù)調(diào)度不能正常執(zhí)行,這就需要安排重調(diào)度。這類問(wèn)題是動(dòng)態(tài)環(huán)境下生產(chǎn)調(diào)度問(wèn)題。

針對(duì)管子加工車間實(shí)際的生產(chǎn)情況和要求,本文制定了在靜態(tài)調(diào)度的基礎(chǔ)上,在不確定性和突發(fā)性情況下運(yùn)用動(dòng)態(tài)調(diào)度技術(shù)對(duì)管子加工車間的生產(chǎn)進(jìn)行動(dòng)態(tài)調(diào)度,構(gòu)建實(shí)時(shí)反饋柔性調(diào)度模型,采用基于多種群混合遺傳算法的周期調(diào)度策略,把動(dòng)態(tài)連續(xù)的問(wèn)題變成分塊的靜態(tài)問(wèn)題,從而使復(fù)雜問(wèn)題簡(jiǎn)單化,動(dòng)態(tài)問(wèn)題靜態(tài)化,以保證生產(chǎn)的順利進(jìn)行。具體操作流程如圖1所示。

由圖1可知,實(shí)時(shí)反饋調(diào)度模型在得到資源重組技術(shù)對(duì)安裝托盤生成代加工管的制造托盤信息后,參考安裝托盤的開(kāi)始加工和交貨時(shí)間以及車間加工資源重組等的目標(biāo)信息,運(yùn)用基于混合遺傳算法的周期調(diào)度方案,得到制造托盤和車間生產(chǎn)計(jì)劃。此時(shí),系統(tǒng)判斷是否有突發(fā)事情發(fā)生,如有設(shè)備故障、負(fù)荷不均勻及訂單加入等突發(fā)事件發(fā)生時(shí)則使用調(diào)度規(guī)則算法優(yōu)化重調(diào)度,將各種加工設(shè)備和被加工資料的重組信息重新處理,生成新的調(diào)度計(jì)劃和任務(wù),保證生產(chǎn)的順利進(jìn)行。如果沒(méi)有突發(fā)事件的發(fā)生則按照原來(lái)的靜態(tài)調(diào)度的計(jì)劃進(jìn)行即可。

圖1 實(shí)時(shí)反饋柔性計(jì)劃調(diào)度操作流程Fig.1 The operation flow of real-time feedback flexible schedule

故該生產(chǎn)調(diào)度系統(tǒng)具有能在線產(chǎn)生實(shí)時(shí)調(diào)度、對(duì)隨機(jī)擾動(dòng)實(shí)現(xiàn)在線辨識(shí)以及快速進(jìn)行自動(dòng)重調(diào)度等特點(diǎn)。

2 靜態(tài)調(diào)度問(wèn)題描述

車間調(diào)度問(wèn)題是一個(gè)NP難題,單純使用某一種優(yōu)化算法來(lái)解決作業(yè)車間柔性調(diào)度問(wèn)題時(shí)都有一定的局限性。遺傳算法(GA)具有很強(qiáng)的全局尋優(yōu)能力,但求精確解效率低,局部有很強(qiáng)的全局尋優(yōu)能力,但求精確解效率低,局部搜索能力差。粒子群優(yōu)化算法(PSO)計(jì)算簡(jiǎn)單、精度高、局部搜索能力強(qiáng),收斂速度較快,但PSO的全局搜索能力不如GA。根據(jù)文獻(xiàn)[4-8],本文在研究了GA和PSO基本原理的基礎(chǔ)上,綜合GA的全局優(yōu)化能力和PSO的局部尋優(yōu)能力,提出一種多種群混合遺傳粒子群算法,實(shí)現(xiàn)在某船廠管子加工車間柔性生產(chǎn)實(shí)時(shí)調(diào)度。

本算法運(yùn)行時(shí),首先隨機(jī)產(chǎn)生多個(gè)初始解,建立遺傳算法初始種群,計(jì)算種群中所有個(gè)體的適應(yīng)度進(jìn)行個(gè)體評(píng)價(jià),然后進(jìn)行遺傳算子迭代:選擇、交叉、變異,利用GA算法進(jìn)行全局搜索。然后選擇遺傳算法中最好的PS個(gè)個(gè)體作為粒子群算法的初始粒子,并將這些初始粒子隨機(jī)組成PN個(gè)粒子群,通過(guò)設(shè)置不同級(jí)別的慣性因子,使各粒子群搜索或側(cè)重于整體搜索或側(cè)重于局部開(kāi)發(fā),利用粒子群算法計(jì)算簡(jiǎn)單、效率高的特點(diǎn),快速全面地搜尋出較優(yōu)良的個(gè)體。各粒子群之間亦實(shí)行個(gè)體遷移,以擴(kuò)大搜索領(lǐng)域。

結(jié)合管子加工車間生產(chǎn)的實(shí)際情況,對(duì)于實(shí)時(shí)反饋柔性調(diào)度系統(tǒng)在靜態(tài)或動(dòng)態(tài)條件下的優(yōu)化實(shí)時(shí)調(diào)度問(wèn)題描述如下:假設(shè)n種規(guī)格管子在m臺(tái)彎管機(jī)床上加工,每種規(guī)格的管子j由nj根管子組成。為使問(wèn)題簡(jiǎn)化,利用成組技術(shù),要求同規(guī)格管子之間有工藝上的先后約束,并假定每根管子可由多臺(tái)彎管機(jī)加工,不同規(guī)格管子在加工工藝上沒(méi)有先后約束,每臺(tái)彎管機(jī)在同一時(shí)刻只能加工1根管子,在0時(shí)刻所有的管子都可被加工,每根管子的加工時(shí)間是確定的,工件的裝卸時(shí)間計(jì)算在加工時(shí)間內(nèi)。

本文從管子加工車間的實(shí)際要求出發(fā),要求調(diào)度結(jié)果在滿足一定約束的條件下,確定與各設(shè)備上所有管子的加工開(kāi)始時(shí)間、完成時(shí)間和加工次序,使生產(chǎn)周期(T)、生產(chǎn)成本(C)、設(shè)備利用率 (L,B)等加工性能指標(biāo)達(dá)到最優(yōu)或次優(yōu)。

3 基于混合遺傳算法的優(yōu)化調(diào)度結(jié)構(gòu)

基于上述分析,具有粒子群搜索的多種群混合遺傳算法調(diào)度流程如圖2所示。

1)編碼。本文根據(jù)簡(jiǎn)單原則以每根管子作為調(diào)度編碼基本單元,這樣便于使每一個(gè)個(gè)體都對(duì)應(yīng)一個(gè)合法、可行的調(diào)度。

2)參數(shù)初始化,建立遺傳算法初始種群。確定種群規(guī)模、交叉概率、變異概率、進(jìn)化代數(shù)等。

3)個(gè)體解碼。

4)產(chǎn)生權(quán)重,計(jì)算適應(yīng)度。權(quán)重系數(shù)在一定范圍內(nèi)隨機(jī)產(chǎn)生。由于時(shí)間、成本、設(shè)備利用率等是不同量綱的參數(shù),可能使得適應(yīng)度函數(shù)變復(fù)雜,所以處理多目標(biāo)問(wèn)題時(shí),通常采用目標(biāo)加權(quán)法,構(gòu)建適應(yīng)度函數(shù),將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化成單目標(biāo)優(yōu)化問(wèn)題[9]。

適應(yīng)度函數(shù)如下:

圖2 混合算法流程Fig.2 The flow of combining algorithms

式中:Ch為第h類管子的完成時(shí)間;T′為該調(diào)度方案的最大完成時(shí)間;phijk為第h類管子中的第j根管子的第i個(gè)工序在第k個(gè)機(jī)器上加工需要的時(shí)間;Zhijk為決策變量,表示第h類管子中的第j根管子的第i個(gè)工序是否選擇在k機(jī)器上加工,Zhijk=1表示選中,Zhijk=0表示未選中為第k個(gè)機(jī)器實(shí)際加工時(shí)的機(jī)器損耗、人工和加工費(fèi)用為第k個(gè)機(jī)器的等待加工時(shí)的機(jī)器損耗和人工費(fèi)用;μ1,μ2,μ3,μ4分別為時(shí)間、成本、總負(fù)荷、最大負(fù)荷的量綱統(tǒng)一化系數(shù)[9];w1,w2,w3,w4為權(quán)系數(shù),且w1+w2+w3+w4=1。

5)判斷是否滿足條件。是,則轉(zhuǎn)7);否則轉(zhuǎn)5)。

6)遺傳進(jìn)化、個(gè)體遷移與替代。按照設(shè)定的選擇方式進(jìn)行選擇操作,從種群中選出P個(gè)染色體個(gè)體作為父代染色體個(gè)體Pop(t)←selection[G(t)];按交叉概率Pc對(duì)染色體個(gè)體進(jìn)行交叉操作(t)←crossover[Pop(t)];按變異概率Pm對(duì)染色體個(gè)體進(jìn)行變異操作(t)←mutation[(t)]。在此過(guò)程中采用小生境技術(shù)以維持種群的多樣性、精英選擇策略以保證算法的收斂性。

7)粒子群搜索、個(gè)體遷移與替代。在粒子群優(yōu)化算法中,每個(gè)優(yōu)化問(wèn)題的解稱之為“粒子”,在每一次迭代中,粒子通過(guò)跟蹤2個(gè)“極值”來(lái)更新自己,粒子本身所找到的最優(yōu)解,稱作個(gè)體極值pbest;整個(gè)種群當(dāng)前找到的最優(yōu)解稱作全局極值gbest。每個(gè)粒子根據(jù)如下的公式來(lái)更新自己的速度和位置:

其中:V(t)為粒子的速度;present(t)為當(dāng)前粒子的位置;c1和c2為正常數(shù),稱為加速因子;rand()為[0,1]之間的隨機(jī)數(shù);ε為慣性因子。

遺傳算法搜索完成后,從當(dāng)前群體中選取最好的PS個(gè)個(gè)體作為粒子群優(yōu)化的初始粒子,并組成PN個(gè)粒子群,取粒子群中的最優(yōu)個(gè)體作為全局極值gbest,并根據(jù)粒子群中各個(gè)粒子與全局極值的差異來(lái)確定各個(gè)粒子的初始速度。然后再利用粒子群算法進(jìn)行局部搜索,以加快算法后期的收斂速度。根據(jù)適應(yīng)度,各粒子群進(jìn)行粒子個(gè)體遷移與替代。

8)判斷是否滿足終止條件。如果滿足則輸出Pareto最優(yōu)解集;否則轉(zhuǎn)步驟7),繼續(xù)搜索。

4 仿真與應(yīng)用結(jié)果分析

4.1 仿真試驗(yàn)分析

根據(jù)文獻(xiàn)[10]中提出的具有15個(gè)工件、10臺(tái)機(jī)器、56道工序的大規(guī)模柔性調(diào)度問(wèn)題,對(duì)本文優(yōu)化算法與文獻(xiàn)[10]中運(yùn)用的AL+CGA及PSO+SA算法就生產(chǎn)周期、機(jī)器總負(fù)荷以及關(guān)鍵機(jī)器負(fù)荷三目標(biāo)優(yōu)化調(diào)度問(wèn)題進(jìn)行了仿真試驗(yàn),比較結(jié)果如表1所示,從而驗(yàn)證了本算法的有效與可行性。

表1 柔性調(diào)度15×10問(wèn)題結(jié)果比較Tab.1 Comparing with 15×10 flexible scheduling data

4.2 應(yīng)用結(jié)果分析

某船廠管子加工車間有6臺(tái)數(shù)控彎管機(jī),對(duì)5種規(guī)格的管子進(jìn)行生產(chǎn),每種規(guī)格的管子批量為4根,不同規(guī)格的管子加工工序不同。由于彎管機(jī)的加工范圍各不相同,所以每種規(guī)格的管子只能在其中的幾臺(tái)設(shè)備上加工。對(duì)該車間原始生產(chǎn)數(shù)據(jù)經(jīng)過(guò)處理,得到如表2所示不同種類管子在相關(guān)設(shè)備上的加工時(shí)間,該加工時(shí)間包括設(shè)備調(diào)整和工件安裝時(shí)間。

機(jī)床工時(shí)費(fèi)及工人小時(shí)工資費(fèi)如表3所示,對(duì)生產(chǎn)周期、生產(chǎn)成本、機(jī)器的總負(fù)荷和最大負(fù)荷4個(gè)性能指標(biāo)進(jìn)行優(yōu)化,循環(huán)10次,根據(jù)不同權(quán)系數(shù)得到多個(gè)Pareto最優(yōu)解,如表4所示為部分最優(yōu)解。限于篇幅,本文僅在圖3中輸出1例權(quán)系數(shù)(w1=0.069,w2=0.310,w3=0.071,w4=0.550)的調(diào)度甘特圖,甘特圖中方框內(nèi)的數(shù)字編號(hào)表示管子加工工序,如“312”表示第3類管子的第1根在進(jìn)行第2道工序加工。

表2 管子加工時(shí)間原始數(shù)據(jù)Tab.2 Original data of piping machining time min

表3 機(jī)床工時(shí)費(fèi)及工人小時(shí)工資費(fèi)Tab.3 Expense of machines and operators Yuan/h

表4 不同權(quán)系數(shù)下的部分最優(yōu)解Tab.4 Member of pareto data

圖3 權(quán)系數(shù)為(w1=0.069,w2=0.310,w3=0.071,w4=0.550)的調(diào)度甘特圖Fig.3 The gunter chart of real-time flexible scheduling

基于多種群混合遺傳算法的車間實(shí)時(shí)柔性優(yōu)化調(diào)度系統(tǒng)在某船廠管子加工車間的應(yīng)用取得了很好的效果,生產(chǎn)成本大幅降低,生產(chǎn)效率相比應(yīng)用本調(diào)度系統(tǒng)之前提高了近1.5倍。同時(shí)由于在本調(diào)度系統(tǒng)中組合實(shí)時(shí)反饋調(diào)度模型,使得車間具備處理突發(fā)事件的能力,車間生產(chǎn)線具有高度的柔性。

5 結(jié) 語(yǔ)

針對(duì)傳統(tǒng)車間調(diào)度問(wèn)題的局限性,本文結(jié)合生產(chǎn)實(shí)際情況,對(duì)生產(chǎn)中出現(xiàn)機(jī)器故障或緊急任務(wù)突然加入等突發(fā)事件的調(diào)度問(wèn)題展開(kāi)研究,并考慮現(xiàn)代生產(chǎn)敏捷制造的要求,建立了基于多種群混合遺傳粒子群算法的車間實(shí)時(shí)調(diào)度系統(tǒng)。該系統(tǒng)在靜態(tài)調(diào)度的基礎(chǔ)上,通過(guò)構(gòu)建實(shí)時(shí)反饋柔性調(diào)度模型,在不確定性或突發(fā)性事故出現(xiàn)的情況下運(yùn)用動(dòng)態(tài)調(diào)度技術(shù)對(duì)車間的生產(chǎn)進(jìn)行調(diào)度,把動(dòng)態(tài)連續(xù)的問(wèn)題變成分塊的靜態(tài)問(wèn)題,從而使動(dòng)態(tài)問(wèn)題靜態(tài)化,形成了實(shí)時(shí)調(diào)度的柔性計(jì)劃調(diào)度技術(shù)。

利用遺傳算法和粒子群算法的優(yōu)點(diǎn),通過(guò)多種群搜索將GA和PSO兩種算法結(jié)合到一起,可取長(zhǎng)補(bǔ)短。遺傳算法是從維護(hù)種群多樣性的角度來(lái)避免早熟收斂,粒子群算法則是從避免傳統(tǒng)遺傳算法變異算子的隨機(jī)性和盲目性的角度提高收斂效率,使優(yōu)化效果更加理想。仿真及實(shí)際生產(chǎn)應(yīng)用結(jié)果表明了該模型及算法的有效和合理性,具有一定的理論和實(shí)踐意義。

[1] 何霆,劉飛,等.車間生產(chǎn)調(diào)度問(wèn)題研究[J].機(jī)械工程學(xué)報(bào),2000,36(5):97-102.

HE Ting,LIU Fei,et al.Research on workshop producing scheduling problems[J].Chinese Journal of Mechanical Engineering,2000,36(5):97-102.

[2] HALL N G,SRISKANDARAJAH C.A Survey of machine scheduling problems with blocking and no-wait in process[J].Operations Research,2005,44(3):510-525.

[3] 唐立新.CIMS下生產(chǎn)批量計(jì)劃理論及其應(yīng)用[M].北京:科學(xué)出版社,1999.

TANG LI-xin.The theory and application ofbatch producing scheme base on CIMS[M].Beijing:China Science Press,1999.

[4] KONAK A,COIT D,SMITH A.Multi-objective optimization using genetic algorithm:a tutorial[J].Reliability Engineering and System Safety,2006,91(9):992-1007.

[5] CARLOS A,GREGORIO T,MAXIMINO S.Handing multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.

[6] SAKAWA M,KUBOTA R.Fuzzy programming for multiobjective job-shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm[J].European Journal of Operational Research,2000,12(2):393-407.

[7] TADAHIKO M,ISHIBUCHI H,HIDEO T.Multi-objective genetic algorithm and its application to flow shop scheduling[J].Computers and Engineering,1996,30(4):957-968.

[8] ALLAHVERDI A,ALDOWAISAN T.New heuristics formmachine no-wait flow shop to minimize total completion time[J].The International Journal of Management Science,2004,(32):345-352.

[9] 王凌.車間調(diào)度及其遺傳算法[M].北京:清華大學(xué)出版社,2003.

WANG Ling.Research on workshop scheduling problems and genetic algorithm[M].Beijing:Tsinghua University Press,2003.

[10]KACEM I,HAMMADIS,BORNE P.Pareto-optimality approach for flexible job scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation,2002,60(3-5):245-276.

Real-time flow-shop scheduling system based on multi-population hybridization of genetic algorithm and particle swarm optimization

CHENG Guo-huang1,XIA Shen-xiong1,WANG Yu1,2,YAN Rui1
(1.Wuchang Shipbuilding Industry Co.,Ltd,Wuhan 430060,China;2.Huazhong University of Science and Technology,Wuhan 430074,China)

Flexible flow-shop scheduling problem is a non-polynomial problem.To solve several problems of a pipe-curving workshop in this article such as underproduction,disordered production management and improved efficiency,the real-time feedback adjustment scheduling model and the real-time job-shop scheduling system based on multi-particle swarm optimization hybrid genetic algorithm are given by the dynamic flexible scheduling technology.Through the scheduling model and scheduling system,the dynamic sequential flow-shop scheduling problem is become a static blocking scheduling problem.The performance of the model and system are evaluated and compared with those of other representative approaches through simulations and practiced applications,and the results demonstrate the feasibility,rationalization and efficiency of the real-time scheduling system.

genetic algorithm(GA);particle swarm optimization(PSO);flow-shop scheduling;realtime scheduling system

TP18

A

1672-7649(2011)11-0126-05

10.3404/j.issn.1672-7649.2011.11.030

2010-12-06;

2011-02-22

湖北省科技廳科技攻關(guān)計(jì)劃資助項(xiàng)目(2007AA109A01);武漢市科技局科技成果推廣應(yīng)用計(jì)劃研究資助項(xiàng)目(200731414455)

成國(guó)煌(1976-),男,碩士,工程師,從事設(shè)計(jì)及系統(tǒng)開(kāi)發(fā)工作。