趙建峰,朱曉春,汪木蘭,卞磊,吳春英

(南京工程學院 a.自動化學院;b.先進數(shù)控技術江蘇省高校重點建設實驗室,南京 211167)

0 引言

近幾十年來,隨著 CAD/CAM/CAPP/CNC、FMS、CIM等先進制造技術的發(fā)展,生產調度問題越來越受到許多學者的關注。這是因為在生產過程中存在著大量幾何形狀類似、加工工序相同的工件,因此許多生產過程就不是簡單的平行設備或者流水線作業(yè),而是多級多機的混合流水車間(Hybrid Flow-shop,HFS)生產?；旌狭魉囬g作業(yè)調度也稱為柔性流水線作業(yè)調度,是一類復雜的車間作業(yè)排序問題,相當普遍地存在于現(xiàn)代制造工業(yè)中[1-3]。

混合流水車間調度問題(Hybrid Flow-shop Scheduling prob lem,HFSP)可描述為：假設有 N個獨立的工件J={i=1,2,…,n},需依次通過 k道工序加工,在每道工序上有 mi≥1(i=1,2,…,k)臺獨立的并行機可履行該階段任務,而每個工件的每道工序只需在一臺機床上加工,任意兩道工序間有無限的存儲能力(即被加工工件在兩道工序間可以等待任意時間)。記該問題為Fk(m1,m2,…,mk)‖Cmax,其中 k為工序數(shù),mi(i=1,2,…,k)是每道工序上的并行機床數(shù)量,最大完工時間Cmax是目標函數(shù)。問題的解是確定并行機床的分配情況以及同一臺機床上工件的加工排序,使最大完工時間 Cmax最小化。

HFSP本質上是大規(guī)模組合優(yōu)化問題,是 NP-hard完全問題,傳統(tǒng)的數(shù)學規(guī)劃方法難以求解[4-5]。早期對于混合 Flow-shop的調度主要有分枝定界算法[6]、啟發(fā)式算法[7]、混合整數(shù)規(guī)劃等,但這些算法只能解決規(guī)模較小的調度問題,對于大規(guī)模甚至中等規(guī)模問題的求解仍然不很理想。近年來,神經網絡、模糊邏輯、遺傳算法等已被用來求解這種大規(guī)模調度問題[1-3,8-10],其中遺傳算法具有效率高、全局尋優(yōu)等功能而得到廣泛應用。本文采用順序自適應交叉遺傳算法求解混合調度問題,該算法能夠在優(yōu)化過程中自動選擇比較合適的交叉概率,從而提高了搜索范圍和搜索效率,仿真結果表明了此算法對于求解混合調度問題的優(yōu)越性。

1 HFSP的編碼

構造混合流水車間調度問題遺傳算法的關鍵是如何進行遺傳算法的編碼和尋找基于特定問題的遺傳算子,使得不管在初期還是在進化過程中所產生的染色體都是可行的調度,這也是所有遺傳算法應用中的難點。

假設要加工 N個工件,每個工件都要依次經過 k道工序加工,所有工序中至少有一個工序存在并行機。下面構造一個 K×N維的 HFSP的編碼矩陣 AK×N為：

編碼矩陣中的元素 aij(i=1,2…K;j=1,2…N)為整數(shù)區(qū)間[100,999]上的一個三位數(shù),其中第一位數(shù)字表示第 j個工件在第 i道工序中在第 Intj(ai×j/100)臺并行機床上加工,后兩位數(shù)字的大小表示在該機床上的加工順序,數(shù)字小的則優(yōu)先加工。例如,隨機產生矩陣 A2×10為 ：

矩陣 A2×10的下標 2×10表示 10個工件需經過 2道工序的加工。第一行的十個基因元素(103,209,221,197,134,229,187,145,185,298)表示第一道工序中 10個工件的加工編碼,其中首位數(shù)字為 1的表示工件在第一臺機床上加工,即工件 1(103)、工件4(197)、工件 5(134)、工件 7(187)、工件 8(145)、工件 9(185)在機床 1上加工,首位數(shù)字為 2的工件即工件 2(209)、工件 3(221)、工件 6(229)、工件 10(298)在機床 2上加工。后兩位數(shù)字表示加工順序,數(shù)字小的優(yōu)先加工,在 1號機床的 6個工件中,因為 03＜34＜45＜85＜87＜97,所以機床 1上各工件的加工順序為 1→5→8→9→7→4;同理機床 2上各工件的加工順序為 2→3→6→10。如果該兩位數(shù)字相等,則以排在前面的優(yōu)先加工。

第二行十個基因元素(208,335,383,197,330,276,110,100,298,200)表示在第二道工序中工件的加工編碼,編碼方式與第一行十個基因相同,則工件 4(197)、工件 7(110)、工件 8(100)在第二道工序的第 1臺機床上加工;工件 1(208)、工件 6(276)、工件 9(298)、工件 10(200)在第 2臺機床上加工,工件 2(335)、工件 3(383)、工件 5(330)在第 2臺機床上加工。同理由于 00＜10＜97,00＜08＜76＜98,30＜35＜83,所以第二道工序中 3臺機床上工件的加工順序為別為(8→7→4),(10→1→6→9)和(5→2→3)。

2 基于自適應遺傳算法 HFSP的求解

2.1 初始群體的設定

(1)初始種群的產生

隨機生成 n個編碼矩陣 AK×N,組成 n條染色體,每條染色體由 K個小段組成,每個小段包括 N個基因,即由編碼矩陣的每一行組成一個小段,則每條染色體含有 K×N個基因,每個基因的取值范圍為[100,(mi+1)×100),其中 mi為單個工序中最大并行機床數(shù)。例如根據上述的編碼矩陣 A2×10可以得到對應的 20個基因的染色體為：

(2)種群規(guī)模的確定

考慮到種群 n如果取的太大則會增加計算量,影響算法效率,n太小則會陷入局部解過早收斂,這里 n的取值根據編碼矩陣 K和 N的大小決定。例如對于A2×10的編碼矩陣,一般 n的取值為[20,30]。

2.2 適應度函數(shù)(fitness function)的設計

HFSP遺傳算法求解的重點是獲得目標函數(shù)即最大完工時間 Cmax,并取最大流程時間的倒數(shù)作為適應度函數(shù)。

本文以 10個工件在 2道工序上加工的車間調度為例進行說明,其中第一道工序有 2臺并行機床,第二道工序有 3臺并行機床,即該問題為 Fk(2,3)‖Cmax,編碼矩陣為 A2×10。

令 ti,j,k表示工件的加工時間,ci,j,k表示工件的完工時間,lasti,j表示各工序各機床上工件開始加工的時間。其中 i表示工序號,j表示機床號,k表示工件編號。

首先將編碼矩陣 A2×10中第一行的 10個數(shù)按大小賦給 B1,1,k和 B1,2,k(百位是 1的賦給 B1,1,k,百位是 2的賦給 B1,2,k),然后再將編碼矩陣中第二行的 10個數(shù)按大小賦給 B2,1,k,B2,2,k和 B2,3,k(百位是 1的賦給 B2,1,k,百位是 2的賦給 B2,2,k百位是 3的賦給 B2,3,k)。例如：

依次取上式 B中的每一個數(shù) bi,j,k,如果該數(shù)不等于 0,則表示工件 k的第 i道工序在第 j臺并行機床上加工,其加工所需時間是 ti,j,k(即每個不為 0的 bi,j,k對應于一個 ti,j,k),再通過比較 bi,j,k后兩位數(shù)字的大小決定工件 k在機床上的加工順序,然后將每個不為 0的bi,j,k對應的 ti,j,k賦給 Ti,j,k,n,其中 n為工件 k在第 i道工序第 j臺并行機床上的加工順序。例如第一道工序第一臺機床上 k個工件的編碼 B1,1,k所對應的加工時間矩陣 T1,1,,k,n為 ：

其中行表示工件號 k,列表示加工順序 n。第一道工序：

其中 j=1,2;k=1,2,…10;n=1,2,…10。

last1,j表示在第一道工序中第 j臺并行機床上工件k之前工件的完工時間,這里即表示工件 k開始加工的時間,Ti,j,k,n表示加工工件 k所需要的時間,c1,j,k表示工件 k的完工時間,然后再將 C1,j,k賦給 last1,j,此時的last1,j對于第 k+1個加工的工件來說就是第 k個工件的完工時間,即第 k+1個工件開始加工的時間。

第二道工序：

式中 j=1,2,3;k=1,2,…10;n=1,2,…10。

工件 k開始加工的時間為 max{last2,j,c1,a1,k100,k},last2,j表示在第二道工序中第 j臺并行機床上在加工工件 k之前的前一個工件的完工時間,c1,a1,k100,k表示工件k在第一道工序中的完工時間,其中 a1,k100表示工件k在第一道工序中加工的機床號。

則最大流程時間為：

適應度函數(shù)取為：

2.3 選擇

為防止過早收斂,本文采用非線性排序來確定個體被選擇(復制)的概率,首先將種群中各染色體按適應度值從好到壞進行排序,使得排在前面的適應度值較好的個體分配到的概率 pi也較大[9]。

其中 i為個體排序號;q為一個常數(shù)。

然后再采用輪盤賭選擇法來確定哪些個體被選擇進行交叉和變異。

2.4 交叉

交叉操作又稱為基因重組。染色體之間是否進行交叉一般是通過生成[0,1]的隨機實數(shù) Rc來決定,如果 Rc小于設定的交叉概率 Pc,則第 i條染色體和第 i+1條染色體進行交叉操作,該方法稱為基本遺傳算法(simple genetic algorithm,SGA)。

在基本遺傳算法中交叉概率 Pc是固定值,如果 Pc越大,新個體產生的速度就越快,但 Pc過大時適應度值高的優(yōu)良個體也容易被破壞;而 Pc過小,則又會使搜索過程緩慢,以致停滯不前[9-10]。

為了解決該問題,本文設計了一種新的交叉方法,使得 Pc能夠隨著目標函數(shù)適應度值的變化而自動調整,即使目標函數(shù)適應度值高的個體取較低的 Pc,目標函數(shù)適應度值低的個體取較高的 Pc,從而使適應度值高的優(yōu)良個體得到保存,而適應度值低的個體被淘汰,且每次的操作都是由第 i條染色體和第 i+1條染色體交叉完成,故稱之為順序自適應交叉遺傳算法(sequence adaptive crossgenetic algorithm,SACGA)。

在 SACGA中,Pc按 照以下公式進行調整：

由于染色體編碼由 2段組成,為了確保后代的合法性,這里采用分段交叉法。首先隨機生成[1,K×N]的隨機整數(shù) Z,然后將兩個相鄰的編碼矩陣 AK×N中第Z個至該段最后一個基因全部互換,完成一次交叉操作。即當 Z∈[1,10]時,第一段發(fā)生交叉;當 Z∈[11,20]時,第二段發(fā)生交叉。假設在 Z=6,發(fā)生交叉時,則：

2.5 變異

現(xiàn)將 A2×10中的每個基因元素 aij對應生成[0,1]的隨機實數(shù) Rm,如果 Rm小于設定的變異概率 Pm,則 aij發(fā)生變異操作。每個基因變異的取值范圍是[100,(mi+1)×100)。

例如,在車間調度實例 A2×10中,第一道工序有 2臺并行機床,第二道工序有 3臺并行機床,則在兩道工序中 aij的取值范圍為[100,299]和[100,399],即：

此操作既保證了變異的充分隨機性,又保證了變異后產生新個體的合法性。

3 南汽轉向器某車間調度實例

現(xiàn)以南汽轉向器某閥體生產車間為例,該車間主要生產 IVECO、MG3和 MG7等 10個品種的閥體工件。為了提高加工效率,該車間的加工工藝由原來的車→銑→磨優(yōu)化為數(shù)控車→高速銑加工,以銑代磨,因此該車間共有 2臺數(shù)控車床和 3臺高速銑削加工中心。由于各機床加工能力的不同以及機床操作工人技能的差異等原因,各加工時間也不盡相同,由設計軟件隨機生成的加工時間如圖 1所示。

圖 1 各工件在各機床上加工時間

該閥體生產車間采用基本遺傳算法(SGA)和順序自適應交叉遺傳算法(SACGA)進行生產調度安排,兩種遺傳算法的參數(shù)為：初始化種群大小 pop_size=20,選擇參數(shù) q=0.4,交叉概率 Pc=0.6,變異概率 Pm=0.01。經過 80代進化后目標函數(shù)的最小值和平均值變化曲線如圖 2所示。由圖 2可以看出,SACGA最小值變化曲線收斂得更快,求解質量和尋優(yōu)效率均優(yōu)于基本遺傳算法,更有利于產生最優(yōu)解。

SGA得到最好的染色體是[258,173,175,261,162,280,288,296,121,262,262,365,158,301,317,118,327,288,116,262],相應的甘特圖如圖 3所示。甘特圖中包括工件在各級機床上的加工排序,加工開始、完成時間,以及所有工件的完工時間,即最大流程時間是 83分鐘。

圖 2 混合 Flow-shop遺傳算法曲線

SACGA得到的最好的染色體是[136,269,294,299,299,128,298,288,168,131,361,254,194,364,386,183,280,355,197,271],相應的甘特圖如圖 4所示,最大流程時間是 80分鐘,加工效率更高。同時,各并行機床的加工任務均勻,且各機床加工時間連續(xù),機床的加工時間都相應縮短,減少了機床損耗,并節(jié)約了生產成本。當然,利用遺傳算法得到的結果往往是近優(yōu)值,而非最優(yōu)值。但相對于人工經驗調度來說,利用智能算法所得到的結果,一方面準確度得到了改進,另一方面也大大提高了排序效率。

根據南汽轉向器某閥體生產車間的實際情況,運用 VB對實際加工情況進行虛擬仿真,如圖 5所示,可以很直觀地觀察各工件的加工情況,運行效果良好。

圖5 混合Flow-shop界面運行仿真

4 結束語

本文所提出的順序自適應交叉遺傳算法是在 Srinvivas和 Patnaik等在 1994年提出的自適應遺傳算法的基礎上發(fā)展起來的一種新的算法,該算法既有利于優(yōu)良個體的保留,提高整個算法的收斂性;同時又提高了算法的尋優(yōu)速度。實例分析及虛擬仿真結果表明,混合 Flow-shop順序自適應交叉遺傳算法所計算出的調度結果較基本遺傳算法更為優(yōu)越,具有較廣的應用價值。本文主要研究了 10個工件在 5臺機床上地生產調度,對于大規(guī)模的組合優(yōu)化問題,是下一步研究的主要目標。

[1]Johnson SM.Op timal two-and three-stage production schedules with setup times included[J].NavalResearch Logistics-Quarterly,1954(1)：61-68.

[2]Gup ta JND.Two-stage hybrid Flow shop scheduling p roblem[J].Operational Research Society,1988,39(4)：359-364.

[3]Yang Jianbo.GA-based discrete dynam ic programming app roach for schedu ling in FMS environments[J].Sy-stems,Man and Cybernetics,Part B,IEEE Transactions,2001,31(5)：824-835.

[4]Hoogeveen JA,Lenstra JK.Preem ptive Scheduling in a Twostage Multiprocessor Flow Shop is NP-hard[J].European Journal of Operational Research,1996,89(1)：172-175.

[5]何龍敏,孫世杰,羅潤梓.帶成組加工的二階段柔性流水作業(yè)問題[J].工程數(shù)學學報,2008,25(5)：829-842.

[6]O Moursli,Y A Pochet,Branch and bound algorithm for the hybrid flow shop[J],Int.J.Prod.Econ.2000,64：113-125.

[7]Guinet A.Scheduling hybrid flow shop to m inimize maximum tardiness or maximum completion t ime[J].I-nt JProRes,1996,34：1643-1654.

[8]Iyer SK,Saxenab B.Imp roved genetic algorithm for the permutation flow shop scheduling p roblem[J].Comput Oper Res,2004,31：593-606.

[9]王萬良,吳啟迪.生產調度智能算法及其應用[M].北京：科學出版社,2007.

[10]Srinvas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Trans Systems Man and Cybernetics,1994,24(4)：656-667.