一種加工工藝柔性的作業(yè)車間調(diào)度問題求解

朱文凡,　葛茂根

(合肥工業(yè)大學(xué) 機(jī)械與汽車工程學(xué)院,安徽 合肥　230009)

?

一種加工工藝柔性的作業(yè)車間調(diào)度問題求解

朱文凡,葛茂根

(合肥工業(yè)大學(xué) 機(jī)械與汽車工程學(xué)院,安徽 合肥230009)

摘要:針對(duì)產(chǎn)品實(shí)際生產(chǎn)加工工序存在互換性與交叉性的特點(diǎn),以及柔性生產(chǎn)作業(yè)車間調(diào)度問題,文章構(gòu)建了一種面向產(chǎn)品加工工藝柔性的生產(chǎn)作業(yè)調(diào)度問題模型,應(yīng)用工序位置集與后續(xù)工序約束集設(shè)計(jì)了該模型的求解方法;在此基礎(chǔ)上提出了基于柔性工序和機(jī)器選擇的兩段編碼方式,并隨機(jī)構(gòu)建了初始種群,采用分步交叉的改進(jìn)遺傳算法設(shè)計(jì)了相應(yīng)的交叉、變異等策略,防止操作過程中不可行解的產(chǎn)生。通過仿真實(shí)例,證明了模型和算法的實(shí)用性和有效性。

關(guān)鍵詞:工藝柔性;作業(yè)車間調(diào)度;遺傳算法;交叉策略

0引言

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem, FJSP)是對(duì)經(jīng)典作業(yè)車間調(diào)度問題的擴(kuò)展。在柔性作業(yè)車間調(diào)度生產(chǎn)過程中,工件的工序順序是預(yù)先確定的,每道工序可在多臺(tái)不同性能的機(jī)器上加工,并且不同機(jī)器上的加工時(shí)間不同。

目前,對(duì)柔性作業(yè)車間調(diào)度問題的研究方法主要有粒子群法(PSO)[1]、禁忌搜索(TS)[2]、蟻群算法[3]和遺傳算法(GA)[4-6]等。如文獻(xiàn)[5]設(shè)計(jì)了新的遺傳算法的初始種群的生成方法,加快了算法的收斂速度;文獻(xiàn)[6]在遺傳算法的算法流程上進(jìn)行了改進(jìn),提高了算法的效率。

在產(chǎn)品實(shí)際生產(chǎn)加工過程中,某些工件的工序之間存在互換性與交叉性,即具有柔性的加工工藝。但文獻(xiàn)[1-6]都是關(guān)于柔性作業(yè)車間調(diào)度中機(jī)器選擇和工序排序的問題,而對(duì)加工工藝柔性的研究相對(duì)較少。

針對(duì)柔性作業(yè)車間調(diào)度的實(shí)際生產(chǎn)特點(diǎn),本文提出了一種更符合實(shí)際生產(chǎn)情況的的加工工藝柔性的作業(yè)車間調(diào)度問題模型,并在問題求解過程中,應(yīng)用工序位置集與后續(xù)工序集確定工序的位置關(guān)系。

1加工工藝柔性的作業(yè)車間調(diào)度問題

1.1　柔性工序位置關(guān)系的表示

工件Ji(0

定義1在柔性工件加工過程中,柔性工序Oij在工序集中所有可能的位置集合定義為該工序的工序位置集Hij。

hij為集合Hij中的一個(gè)元素,記為該工序的一個(gè)工序位置。若工序Oi3可以在工件Ji中第3個(gè)加工,也可以第4個(gè)加工,則Hi3={3,4},表示工序Oi3的可能加工位置為3或4。默認(rèn)非柔性工序Oik的工序位置集為Hik={k}。

定義2工序位置為h的工序Oij的后續(xù)所有可能的加工工序的工序號(hào),記為該工序的后續(xù)工序集Pijh。

當(dāng)工序Oi3第4個(gè)加工時(shí),其后續(xù)加工工序可為Oi5、Oi6,則Pi34={5,6}。默認(rèn)非柔性工件的工序Oik的后續(xù)工序集為Pikk={k+1}。

用工序位置和后續(xù)工序集可完整地表述工件的所有工序的加工順序關(guān)系。以某加工工藝為例,該工件J1有6道工序,其中工序1、2之間的加工順序可任意互換;工序5可任意插入到工序3、4之間或前后,則各工序位置關(guān)系見表1所列。

表1　工序位置關(guān)系

1.2　問題描述與調(diào)度模型

具有柔性加工工藝的作業(yè)車間調(diào)度問題描述如下:設(shè)在m臺(tái)機(jī)器上安排n個(gè)工件加工。每個(gè)工件有1道或多道工序,每個(gè)工件的加工工序順序是不確定的,每道工序可以在多臺(tái)不同的機(jī)器上加工,且工序的加工時(shí)間隨加工機(jī)器的不同而不同。假設(shè)工序在可加工的機(jī)器上的加工時(shí)間是可以確定的,且加工過程一旦開始就不能中途停止[7]。

根據(jù)以上問題描述,采用最大完工時(shí)間最小化作為系統(tǒng)的性能優(yōu)化指標(biāo),即目標(biāo)函數(shù)。

上述FJSP調(diào)度問題表述為:

(1)

加工過程中的約束條件為:

(2)

(3)

(4)

(5)

(6)

(7)

(2)式表示工序位置靠前的工序優(yōu)先加工;(3)式表示后續(xù)工序集內(nèi)的工序緊接著當(dāng)前工序加工;(4)式表示每個(gè)工件同時(shí)只能在1個(gè)機(jī)器上加工; (5)式表示每個(gè)機(jī)器同時(shí)只能處理1個(gè)工件; (6)式表示所有機(jī)器在t=0時(shí)刻都可以使用,所有工件在t=0 時(shí)刻都可被加工。

2改進(jìn)遺傳算法

與傳統(tǒng)的作業(yè)車間調(diào)度問題相比,柔性作業(yè)車間調(diào)度問題擴(kuò)展了可行解的搜索范圍,大大提高了調(diào)度的難度。而遺傳算法(GA)的穩(wěn)定性好、操作方便、計(jì)算性能優(yōu)良、不受約束條件的限制,且具有隱含并行性和全局搜索能力等特點(diǎn),在生產(chǎn)調(diào)度領(lǐng)域得到廣泛的應(yīng)用。本文運(yùn)用遺傳算法求解該問題,提出了一種新的染色體編碼方案, 并設(shè)計(jì)了對(duì)應(yīng)的遺傳算子。

2.1　染色體編碼

染色體編碼由2部分組成:① 基于柔性工序的編碼,確定單個(gè)柔性工件的工序排序;② 基于機(jī)器選擇調(diào)度的編碼,確定所有工序的排序和對(duì)應(yīng)的機(jī)器選擇。2部分組合在一起形成完整的調(diào)度方案。

2.1.1基于柔性工序的編碼

此編碼需確定單個(gè)柔性工件的工序排序，采用符號(hào)和十位進(jìn)制數(shù)的混合編碼方式,染色體結(jié)構(gòu)如下:

其中,k為具有柔性工序的工件數(shù);qk為工件Jk的工序數(shù);Nij為i工件工序位置為j的工序號(hào)。如表1所列的工件的一個(gè)柔性基因段編碼可表示為[Ji,2,1,3,5,4,6],該工件可以按此工序順序加工。由此可知染色體數(shù)字段的個(gè)數(shù)為所有柔性工件的工序數(shù)之和。

2.1.2基于機(jī)器選擇的編碼

此編碼需確定所有工序排序和各工序的機(jī)器的選擇。在此編碼過程中各工件按柔性工序編碼的順序加工。染色體編碼采用基于工序的表達(dá)法[8],每個(gè)染色體由N個(gè)兩位數(shù)組成,N為所有工件的工序總數(shù)。每個(gè)兩位數(shù)中第1位數(shù)是被加工的工件號(hào),第1位數(shù)在染色體中出現(xiàn)的次數(shù)k表示該工件要加工的第k道工序；每個(gè)兩位數(shù)中的第2位數(shù)表示該工序加工的機(jī)器號(hào)。

以一個(gè)3×3的JSP調(diào)度問題為例,現(xiàn)有染色體為P[21,33,23,11,12,33,32,13,21],該染色體中第1個(gè)元素“21”表示工件2的第1道工序在機(jī)器1上加工,第2個(gè)元素“33”表示第3個(gè)工件的第1道工序在機(jī)器3上加工,第3個(gè)元素“23”表示工件2的第2道工序在機(jī)器3上加工。

2.2　初始種群的構(gòu)建

為了保證初始種群的多樣性,采用隨機(jī)生成的方式產(chǎn)生初始染色體。柔性工序編碼的構(gòu)建方法如下:對(duì)某一柔性工件i,隨機(jī)選擇一個(gè)工序位置為“1”的工序作為起始工序Ni1;隨機(jī)選擇一個(gè)該起始工序?qū)?yīng)的后續(xù)工序作為第2道工序Ni2;任意選擇Ni2中工序位置為“2”的后續(xù)工序集中的工序Ni3,作為后續(xù)工序;以此類推。

機(jī)器選擇的編碼也采取隨機(jī)生成的方式,第1位工件號(hào)數(shù)出現(xiàn)的次數(shù)等于其工序的總數(shù),第2位加工機(jī)器數(shù)從可用機(jī)器集Mij中隨機(jī)生成。

2.3　選擇策略

種群中適應(yīng)度值最大的染色體直接復(fù)制到下一代種群中,其他個(gè)體根據(jù)其適應(yīng)度值采用輪盤賭選擇[9]的方法選擇。適應(yīng)度函數(shù)f(x)就取目標(biāo)函數(shù)值Z(x)。

2.4　交叉策略

在作業(yè)車間調(diào)度和旅行商問題的遺傳算法中,交叉策略是最重要的一種操作。為增加算法的收斂性,交叉概率Pc選用自適應(yīng)適應(yīng)度算法[10]的方式得到。同時(shí),考慮到后代不可行解的增加對(duì)算法的抑制作用,設(shè)計(jì)了針對(duì)該染色體的交叉方式,減少不可行解的產(chǎn)生。

2.4.1面向柔性工序的交叉方式

由于柔性工序較少,并為確保交叉的可行性,采用整段交叉的方式,即隨機(jī)選擇染色體的多個(gè)柔性工序段,將父代染色體中該段基因全部互換。在互換的同時(shí),需變更該工序段對(duì)應(yīng)的機(jī)器選擇編碼,以降低搜索過程中出現(xiàn)非可行解的可能性。

以Q[31,22,21,11,12,33,13,33,21]機(jī)器選擇編碼為例,若柔性工序段J1的柔性工序編碼為[J1,2,1,3],現(xiàn)將其替換為[J1,3,2,1]。首先,由Q首位數(shù)字為“1”的機(jī)器信息可知工序號(hào)2對(duì)應(yīng)機(jī)器M1、工序號(hào)1對(duì)應(yīng)M2、工序號(hào)3對(duì)應(yīng)M3。其次,新編碼中J1的開始工序?yàn)楣ば蛱?hào)3,已知工序號(hào)3的加工機(jī)器為M3,則修改“11”為“13”;第2工序?yàn)楣ば蛱?hào)2,則修改“12”為“11”;同理修改“13”為“12”。更改后的機(jī)器選擇編碼為Q'[31,22,21,13,11,33,12,33,21],如圖1所示。

圖1　變更機(jī)器選擇編碼示意圖

2.4.2面向機(jī)器選擇的交叉方式

機(jī)器選擇的編碼在編碼階段,柔性工件的工序順序已確定為柔性工序編碼的順序,非柔性工件的工序順序按工序號(hào)順序加工。若要交叉后既保證獲得工序?qū)?yīng)的加工機(jī)器號(hào),也保證各工序的順序排列信息,首先需確定單個(gè)工件工序的加工順序。

采取兩點(diǎn)交叉的方式,即隨機(jī)選擇染色體P中的某2點(diǎn), 兩點(diǎn)間的所有編碼為復(fù)制段,將該復(fù)制段復(fù)制到要交叉的染色體Q中。

例如,若P[21,33,23,11,12,33,32,13,21]與Q[31,12,22,21,11,13,32,33,23]交叉,且復(fù)制段為P中的[11,12,33]基因段,即將P中該段的信息通過交叉?zhèn)鬟f給Q。已知P的柔性工序編碼為[J1,3,2,1,J2,1,3,2],Q的柔性工序編碼為[J1,2,1,3,J3,2,1,3]。交叉方法如下所述。

(1) 綜合機(jī)器選擇染色體和對(duì)應(yīng)的柔性工序編碼,要交叉的2個(gè)染色體可顯性表示為:

(2) 第1次交叉。將機(jī)器選擇信息即復(fù)制段中第2位數(shù)字的排列順序[M1,M2,M3]，傳遞給Q1,其工序順序?yàn)镵[1—3,1—2,3—2]。在Q1中,找到工序序列為“1—3”的元素,修改原機(jī)器信息M2為M1;同理將Q1中工序序列為“1—2”的機(jī)器信息改為M2,工序序列為“3—2”的機(jī)器信息改為M3。新染色體顯性表示為:

(3) 第2次交叉。要將工序排列順序信息(復(fù)制段中的第1位數(shù)字排列順序K[1—3,1—2,3—2])傳遞給Q。步驟如下:

首先，去除P1中的機(jī)器信息記為p1,去除Q1中的機(jī)器信息記為q1。

p1[2—1,3—1,2—3,1—3,1—2,3—2,3—3,1—1,2—2];

q1[3—2,1—2,2—1,2—2,1—1,1—3,3—1,3—3,2—3]。

然后，將q1中元素與K內(nèi)相同的去掉,得f1[2—1,2—2,1—1,3—1,3—3,2—3]。

最后，確定K在p1中的位置,將K內(nèi)所有元素插入f1的相同位置和順序中,產(chǎn)生的結(jié)果為f2[2—1,2—2,1—1,1—3,1—2,3—2,3—1,3—3,2—3]。

(4) 綜合2次交叉得到的f2和Q2,將Q2中的加工機(jī)器信息代入f2中可得交叉結(jié)果為:

即經(jīng)過2次交叉后的新染色體為Q[22,21,11,11,12,33,32,33,23]。

2.5　變異策略

同樣采用自適應(yīng)適應(yīng)度算法獲取變異概率Pm。對(duì)于柔性工序編碼的基因段,采用單點(diǎn)變異的方式,在柔性工序Oij的工序順序集中隨機(jī)另選取一個(gè)工序位置hij,根據(jù)其后續(xù)工序集確定一個(gè)新的染色體。

對(duì)于機(jī)器選擇編碼的基因段,采用逆轉(zhuǎn)變異的方式,隨機(jī)選擇一個(gè)基因段,將基因段中的所有基因值逆向插入到原位置中,形成新的基因段。

2.6　改進(jìn)遺傳算法執(zhí)行流程

柔性作業(yè)車間調(diào)度問題需要為單個(gè)工件選擇合適的工序加工順序,同時(shí)為每道工序進(jìn)行排序,并在各工序的機(jī)器可選集中選擇1臺(tái)機(jī)器。由于在面向柔性工序的交叉時(shí),相對(duì)應(yīng)的機(jī)器選擇編碼的加工機(jī)器信息也相應(yīng)變動(dòng),結(jié)合該問題的這些特點(diǎn),提出了分步交叉的改進(jìn)遺傳算法。

分步交叉的步驟如下:① 交叉1次柔性工序編碼的一個(gè)柔性工序段;② 若所有機(jī)器選擇編碼改變的基因數(shù)為n,每次在n中隨機(jī)選擇2點(diǎn),采用兩點(diǎn)交叉的方式對(duì)機(jī)器選擇編碼進(jìn)行多次交叉;③ 在所有子代中選擇適應(yīng)度最大的2個(gè)個(gè)體進(jìn)入下代中。即柔性工序編碼交叉1次,機(jī)器選擇編碼交叉了多次,這樣更有利于從后代選擇最優(yōu)的染色體存入子代中。

改進(jìn)的遺傳算法的具體步驟如下:

(1) 初始種群的確定,隨機(jī)產(chǎn)生N個(gè)個(gè)體。

(2) 計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值。

(3) 判斷是否達(dá)到終止條件,若達(dá)到則輸出最優(yōu)調(diào)度方案,并終止運(yùn)算;否則轉(zhuǎn)步驟(4)。

(4) 運(yùn)用選擇策略選擇下一代種群。

(5) 獲取交叉概率Pc,采用分步交叉法對(duì)種群中個(gè)體按照交叉策略進(jìn)行交叉。

(6) 獲取變異概率Pm,對(duì)新種群進(jìn)行變異操作,得到新一代種群。

(7) 返回步驟(3)。

3仿真結(jié)果與分析

為驗(yàn)證算法的有效性,現(xiàn)以某減速器生產(chǎn)企業(yè)的某車間加工為例。其中具有柔性工序的工件為J1、J2、J4和J6,其柔性工序的各工序位置和對(duì)應(yīng)后續(xù)工序集見表2所列,各工件的工序數(shù)量、可用加工設(shè)備和對(duì)應(yīng)時(shí)間見表3所列。

表2　柔性工序的工序位置關(guān)系表

表3　工序可用加工機(jī)器和對(duì)應(yīng)時(shí)間表

注:M3(1)表示該工序可用機(jī)器M3加工,加工時(shí)間為1 min。

改進(jìn)遺傳算法的最佳調(diào)度方案和收斂曲線圖如圖2所示，工件的加工路線和機(jī)器選擇路線見表4所列。

(a)　最佳調(diào)度甘特圖

(b)　收斂曲線

工件編號(hào)加工路線機(jī)器選擇路線J1O1—O2—O3—O6—O4—O5—O7—O8M3—M1—M2—M4—M6—M5—M3—M2J2O2—O1—O3—O4—O5—O7—O6M2—M3—M5—M2—M1—M4—M6J3O1—O2—O3—O4—O5—O6—O7M3—M4—M6—M1—M6—M5—M2J4O1—O2—O4—O3—O5—O7—O6—O8M2—M1—M3—M4—M5—M6—M3—M4J5O1—O2—O3—O4—O5—O6M3—M2—M5—M6—M1—M4J6O1—O2—O3—O5—O4—O6M2—M4—M6—M3—M5—M1

運(yùn)用Cfree軟件、C語(yǔ)言編程語(yǔ)言實(shí)現(xiàn)改進(jìn)的遺傳算法,并對(duì)該車間FJSP問題求最優(yōu)解。設(shè)定初始種群規(guī)模N=100,最大迭代次數(shù)為

100,得到圖2的最佳調(diào)度方案甘特圖和收斂曲線。由圖2可知,最優(yōu)方案的最大完工時(shí)間為61 min,證明了在考慮工序的加工順序柔性和工序選擇機(jī)器柔性的調(diào)度問題時(shí),該改進(jìn)遺傳算法是可行的,具有理論和實(shí)際意義。

4結(jié)束語(yǔ)

本文建立了加工工藝柔性的作業(yè)車間調(diào)度問題模型,以縮短生產(chǎn)周期為目標(biāo),提出了求解該問題的改進(jìn)遺傳算法,并設(shè)計(jì)了相應(yīng)的染色體編碼方案、交叉策略、變異策略等來提高算法的效率。仿真實(shí)驗(yàn)證明,提出的模型和改進(jìn)的遺傳算法對(duì)該柔性作業(yè)車間調(diào)度問題是可行的,柔性工藝的調(diào)度方案提高了該車間的生產(chǎn)效率,更加符合車間的實(shí)際加工生產(chǎn)情況,具有較大的理論和實(shí)際意義。

[參考文獻(xiàn)]

[1]劉明周,張明偉,蔣增強(qiáng)，等.基于混合粒子群算法的多目標(biāo)柔性Job-Shop調(diào)度方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2008,39(5):122-127.

[2]Li J Q,Pan Q K,Suganthan P N,et al.A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2011,52(5/6/7/8):683-697.

[3]陳知美,顧幸生.改進(jìn)型蟻群算法在Job Shop問題中的應(yīng)用[J].華東理工大學(xué)學(xué)報(bào):自然科學(xué)版,2006,32(4):466-470.

[4]Gen M,Gao J,Lin L.Multistage-based genetic algorithm for flexible job-shop scheduling problem[J].Intelligent and Evolutionary Systems,2009,187:183-196.

[5]張國(guó)輝,高亮,李培根,等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機(jī)械工程學(xué)報(bào),2009,45(7):145-150.

[6]張超勇,饒運(yùn)清,李培根,等.柔性作業(yè)車間調(diào)度問題的兩級(jí)遺傳算法[J].機(jī)械工程學(xué)報(bào),2007,43(4):119-124.

[7]王?，?蔣增強(qiáng),葛茂根.基于規(guī)則組合的Job Shop多目標(biāo)柔性調(diào)度方法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2010,33(1):14-18.

[8]馮紅娟.基于遺傳算法的車間作業(yè)調(diào)度問題的研究[D].長(zhǎng)春:長(zhǎng)春理工大學(xué),2008.

[9]王萬(wàn)良,吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用[M].北京:科學(xué)出版社,2007:42-56.

[10]梁佳成.改進(jìn)遺傳算法求解VRP問題[J].科技創(chuàng)新導(dǎo)報(bào),2012(36):225.

(責(zé)任編輯胡亞敏)

葛茂根(1979-),男,安徽安慶人,博士，合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.

A solution of flexible processing technology problem based on flexible job-shop scheduling

ZHU Wen-fan,GE Mao-gen

(School of Machinery and Automobile Engineering, Hefei University of Technology, Hefei 230009, China)

Abstract:According to the characteristics of the interchangeability of the actual production processes, and in face of the flexible job-shop scheduling problem(FJSP), the problem model based on the flexible processing technology of FJSP is presented. The solution of the model is designed by using the process position and the follow-up process constraint set. On this basis, two segment encoding scheme based on machine selection and flexible process is proposed, and the original individual is constructed at random. An order crossover model of genetic algorithm is proposed, meanwhile the corresponding crossover strategy and mutation strategy are designed, preventing the generation of infeasible solution. The simulation results verify the feasibility and efficiency of the model and the algorithm proposed in this paper.

Key words:flexible process; job-shop scheduling; genetic algorithm; crossover strategy

中圖分類號(hào):TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-5060(2015)03-0309-06

doi:10.3969/j.issn.1003-5060.2015.03.005

作者簡(jiǎn)介：朱文凡(1990-),男,安徽巢湖人,合肥工業(yè)大學(xué)碩士生;

收稿日期：2014-02-22；修回日期：2014-04-10