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

成國煌,夏勝雄,王 宇,2,嚴 睿

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

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

成國煌1,夏勝雄1,王 宇1,2,嚴 睿1

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

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

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

0 引 言

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

車間柔性調(diào)度問題多是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)點和不足[1-3]。本文結合某船廠管子加工車間數(shù)字化生產(chǎn)的實際需要,按照車間現(xiàn)用的生產(chǎn)模式,通過采用多種群混合遺傳算法的周期調(diào)度策略,解決實時反饋調(diào)度中的重調(diào)度問題,形成實時調(diào)度的柔性計劃調(diào)度技術,使得車間具備處理突發(fā)事件的能力,提高船舶制造企業(yè)的生產(chǎn)效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3)個體解碼。

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

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

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

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

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

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

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

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

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

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

4 仿真與應用結果分析

4.1 仿真試驗分析

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

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

4.2 應用結果分析

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

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

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

表3 機床工時費及工人小時工資費Tab.3 Expense of machines and operators Yuan/h

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

圖3 權系數(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

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

5 結 語

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

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

[1] 何霆,劉飛,等.車間生產(chǎn)調(diào)度問題研究[J].機械工程學報,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)批量計劃理論及其應用[M].北京:科學出版社,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].北京:清華大學出版社,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

湖北省科技廳科技攻關計劃資助項目(2007AA109A01);武漢市科技局科技成果推廣應用計劃研究資助項目(200731414455)

成國煌(1976-),男,碩士,工程師,從事設計及系統(tǒng)開發(fā)工作。