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

(南京工程學(xué)院 a.自動(dòng)化學(xué)院;b.先進(jìn)數(shù)控技術(shù)江蘇省高校重點(diǎn)建設(shè)實(shí)驗(yàn)室,南京 211167)

0 引言

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

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

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

1 HFSP的編碼

構(gòu)造混合流水車間調(diào)度問題遺傳算法的關(guān)鍵是如何進(jìn)行遺傳算法的編碼和尋找基于特定問題的遺傳算子,使得不管在初期還是在進(jìn)化過程中所產(chǎn)生的染色體都是可行的調(diào)度,這也是所有遺傳算法應(yīng)用中的難點(diǎn)。

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

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

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

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

2 基于自適應(yīng)遺傳算法 HFSP的求解

2.1 初始群體的設(shè)定

(1)初始種群的產(chǎn)生

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

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

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

2.2 適應(yīng)度函數(shù)(fitness function)的設(shè)計(jì)

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

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

令 ti,j,k表示工件的加工時(shí)間,ci,j,k表示工件的完工時(shí)間,lasti,j表示各工序各機(jī)床上工件開始加工的時(shí)間。其中 i表示工序號(hào),j表示機(jī)床號(hào),k表示工件編號(hào)。

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

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

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

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

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

第二道工序：

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

工件 k開始加工的時(shí)間為 max{last2,j,c1,a1,k100,k},last2,j表示在第二道工序中第 j臺(tái)并行機(jī)床上在加工工件 k之前的前一個(gè)工件的完工時(shí)間,c1,a1,k100,k表示工件k在第一道工序中的完工時(shí)間,其中 a1,k100表示工件k在第一道工序中加工的機(jī)床號(hào)。

則最大流程時(shí)間為：

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

2.3 選擇

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

其中 i為個(gè)體排序號(hào);q為一個(gè)常數(shù)。

然后再采用輪盤賭選擇法來確定哪些個(gè)體被選擇進(jìn)行交叉和變異。

2.4 交叉

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

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

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

在 SACGA中,Pc按 照以下公式進(jìn)行調(diào)整：

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

2.5 變異

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

例如,在車間調(diào)度實(shí)例 A2×10中,第一道工序有 2臺(tái)并行機(jī)床,第二道工序有 3臺(tái)并行機(jī)床,則在兩道工序中 aij的取值范圍為[100,299]和[100,399],即：

此操作既保證了變異的充分隨機(jī)性,又保證了變異后產(chǎn)生新個(gè)體的合法性。

3 南汽轉(zhuǎn)向器某車間調(diào)度實(shí)例

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

圖 1 各工件在各機(jī)床上加工時(shí)間

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

SGA得到最好的染色體是[258,173,175,261,162,280,288,296,121,262,262,365,158,301,317,118,327,288,116,262],相應(yīng)的甘特圖如圖 3所示。甘特圖中包括工件在各級(jí)機(jī)床上的加工排序,加工開始、完成時(shí)間,以及所有工件的完工時(shí)間,即最大流程時(shí)間是 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],相應(yīng)的甘特圖如圖 4所示,最大流程時(shí)間是 80分鐘,加工效率更高。同時(shí),各并行機(jī)床的加工任務(wù)均勻,且各機(jī)床加工時(shí)間連續(xù),機(jī)床的加工時(shí)間都相應(yīng)縮短,減少了機(jī)床損耗,并節(jié)約了生產(chǎn)成本。當(dāng)然,利用遺傳算法得到的結(jié)果往往是近優(yōu)值,而非最優(yōu)值。但相對(duì)于人工經(jīng)驗(yàn)調(diào)度來說,利用智能算法所得到的結(jié)果,一方面準(zhǔn)確度得到了改進(jìn),另一方面也大大提高了排序效率。

根據(jù)南汽轉(zhuǎn)向器某閥體生產(chǎn)車間的實(shí)際情況,運(yùn)用 VB對(duì)實(shí)際加工情況進(jìn)行虛擬仿真,如圖 5所示,可以很直觀地觀察各工件的加工情況,運(yùn)行效果良好。

圖5 混合Flow-shop界面運(yùn)行仿真

4 結(jié)束語

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

[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]何龍敏,孫世杰,羅潤(rùn)梓.帶成組加工的二階段柔性流水作業(yè)問題[J].工程數(shù)學(xué)學(xué)報(bào),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]王萬良,吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用[M].北京：科學(xué)出版社,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.