基于多種群混合遺傳算法的車間實時調度系統

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

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

基于多種群混合遺傳算法的車間實時調度系統

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

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

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

遺傳算法;粒子群優化;車間調度;實時調度系統

0 引 言

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

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

1 實時優化調度策略

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

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

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

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

故該生產調度系統具有能在線產生實時調度、對隨機擾動實現在線辨識以及快速進行自動重調度等特點。

2 靜態調度問題描述

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

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

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

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

3 基于混合遺傳算法的優化調度結構

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

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

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

3)個體解碼。

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

適應度函數如下:

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

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

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

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

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

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

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

8)判斷是否滿足終止條件。如果滿足則輸出Pareto最優解集;否則轉步驟7),繼續搜索。

4 仿真與應用結果分析

4.1 仿真試驗分析

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

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

4.2 應用結果分析

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

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

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

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

表4 不同權系數下的部分最優解Tab.4 Member of pareto data

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

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

5 結 語

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

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

[1] 何霆,劉飛,等.車間生產調度問題研究[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下生產批量計劃理論及其應用[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] 王凌.車間調度及其遺傳算法[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-),男,碩士,工程師,從事設計及系統開發工作。