鄭天華，王佳斌，蔡宇翔，彭凱

(華僑大學(xué) 工學(xué)院，福建 泉州 362021)

混流混合車間調(diào)度涉及作業(yè)車間調(diào)度和流水車間調(diào)度，生產(chǎn)過程包括零件加工、部件裝配、產(chǎn)品總裝配.由于作業(yè)車間和流水車間聯(lián)系緊密，對某一個車間進(jìn)行單獨優(yōu)化都可能導(dǎo)致大量庫存和生產(chǎn)周期延長.因此，混流混合車間調(diào)度需要考慮作業(yè)車間調(diào)度和流水車間調(diào)度.

目前，對車間調(diào)度的研究處于快速的發(fā)展階段.一些學(xué)者采用精確算法對車間調(diào)度問題進(jìn)行研究，如拉格朗日松弛算法[1-3]和分支定界算法[4-6].隨著車間調(diào)度規(guī)模擴(kuò)大，精確算法效率降低，而智能算法得到更廣泛的應(yīng)用.Figielska[7]采用禁忌搜索算法研究兩個階段混合流水車間問題.Marichelvam等[8]采用離散螢火蟲算法求解雙目標(biāo)混合流水車間問題.Naderi等[9]采用帝國主義競爭算法求解帶有子模塊和準(zhǔn)備書簡窗的車間調(diào)度問題.此外，混合人工蜂群算法[10]、混合果蠅優(yōu)化算法[11]、混合松鼠搜索算法[12]等也都應(yīng)用于車間調(diào)度問題中.

李修琳等[13]采用混合遺傳算法，以最小化緩存區(qū)庫存為目標(biāo)，研究混流混合車間集成調(diào)度問題.魯建廈等[14]采用博弈粒子群算法，以最小化部件車間齊套性和庫存為目標(biāo)，研究混流混合車間調(diào)度.王猛[15]提出免疫遺傳算法，以最小化最大完工時間為目標(biāo)，研究多級車間集成調(diào)度問題.Lou等[16]采用免疫克隆算法解決混合車間調(diào)度優(yōu)化問題，并取得有效的解決方案.

Hadoop集群是目前廣泛使用的大數(shù)據(jù)處理主流技術(shù)和系統(tǒng)平臺，在大規(guī)模分布式的存儲和批處理上有強(qiáng)大能力.劉佳耀等[17]針對大數(shù)據(jù)時代下Slope One算法推薦效率不高的問題，改進(jìn)算法并將其在大數(shù)據(jù)平臺上實現(xiàn)并行化.蔡春曉等[18]結(jié)合車牌識別算法和Hadoop集群，實現(xiàn)算法的并行化，有效地改進(jìn)算法的運行效率.王誠等[19]結(jié)合孤立森林算法和大數(shù)據(jù)平臺，實現(xiàn)算法的并行化，提高了算法運行的效率.

三段式[13-14]編碼的算法可以有效解決混流混合車間內(nèi)小批量的調(diào)度問題.面對大批量問題時，采用現(xiàn)有的智能算法易陷入局部最優(yōu)的問題，無法得出最佳的調(diào)度的方案.基于此，本文研究禁忌粒子群車間調(diào)度算法及其并行化實現(xiàn).

1 問題的建模

混流混合車間，如圖1所示.為研究混流混合車間調(diào)度問題，給出以下5個假設(shè)[13]：

1) 在流水車間，只對自制件進(jìn)行加工，不考慮外購?fù)鈪f(xié)件；

2) 生產(chǎn)之前，車間內(nèi)的設(shè)備和工位沒有制品且已經(jīng)準(zhǔn)備就緒；

3) 加工時間包括準(zhǔn)備時間、搬運時間；

4) 車間內(nèi)相同的零件之間有工序的約束，不同的零件不存在工序的約束；

5) 零件加工車間為部件裝配車間、產(chǎn)品總裝配車間加工一批零件，部件裝配車間為產(chǎn)品總裝配車間加工一批部件，裝配工將不滿足裝配工位的零件或部件放在緩沖區(qū)中，配送的時間假定為零.

圖1 混流混合車間Fig.1 Mixed flow mixing workshop

在加工過程中，零件加工車間要滿足工序約束和設(shè)備約束.零件在對應(yīng)的設(shè)備機(jī)器上按照工序進(jìn)行加工；部件裝配車間和產(chǎn)品總裝配車間在裝配過程中，要滿足工序約束和工位約束，零件在對應(yīng)的工位上操作，前置工序操作完成才能進(jìn)行下一步的工序操作.零件加工車間的設(shè)備約束為

Ei，j-ti，j+r×ci，h，j≥Ei，h，

(1)

零件加工車間的工序約束為

Eg，i-ti，g+r×di，g，j≥tg，i，

(2)

部門裝配車間和產(chǎn)品總裝配車間的工位約束為

(3)

部門裝配車間和產(chǎn)品總裝配車間的工序約束為

(4)

部門裝配車間和產(chǎn)品總裝配車間的時間約束為

Ex，k=tx，k+max(Ex-1，k，Ex，k-1).

(5)

2 粒子群算法

2.1 傳統(tǒng)粒子群算法

傳統(tǒng)粒子群算法(PSO)模擬鳥群覓食過程.在這個過程中，每個粒子的解對應(yīng)粒子相對應(yīng)的位置.傳統(tǒng)粒子群算法對應(yīng)的速度(vnex)[20]為

vnex=wvcur+c1r1(p*-xcur)+c2r2(g*-xcur)，

(6)

xnex=xcur+vnex.

(7)

式(6)，(7)中：w，c1，c2分別為慣性系數(shù)，個體認(rèn)知系數(shù)和社會認(rèn)知系數(shù)；vcur和xcur為當(dāng)前的速度和位移；vnex和xnex為下一步的速度和位移；p*為個體經(jīng)歷過最好的位置；g*為全局最優(yōu)位置；r1，r2為一組(0，1)內(nèi)的隨機(jī)數(shù).

2.2 禁忌粒子群算法

傳統(tǒng)粒子群算法搜索速度快、收斂效率好，但容易陷入局部最優(yōu)的情況.針對傳統(tǒng)粒子群算法中存在的問題，對粒子群算法進(jìn)行改進(jìn).在傳統(tǒng)粒子群算法尋優(yōu)的過程中，加入禁忌算法，對粒子種群進(jìn)行隨機(jī)交換組合，加強(qiáng)算法尋優(yōu)的能力，防止算法陷入局部最優(yōu)的可能.

圖2 禁忌粒子群算法流程Fig.2 Forbidden particle swarm algorithm flow

2.3 禁忌粒子算法流程

禁忌粒子群算法流程，如圖2所示.禁忌粒子群算法(TSPSO)算法有如下7個流程：

1) 設(shè)置PSO的相關(guān)參數(shù)，置空禁忌表；

2) 對PSO中的每個粒子計算適應(yīng)度值，更新個體的最優(yōu)解及群體的最優(yōu)解；

3) 更新粒子群中的位置及速度；

4) 將粒子群中的每個粒子進(jìn)行隨機(jī)交叉變異，計算變異后的粒子適應(yīng)度；

5) 若新的適應(yīng)度比群體最優(yōu)解好，則更新禁忌表中，更新群體最優(yōu)解，若不滿足，就轉(zhuǎn)到流程6)；

6) 若新的解比變換前的粒子對應(yīng)的解更好，則將這個粒子及對應(yīng)的解放入禁忌表，即更新禁忌表；

7) 若迭代次數(shù)大于所設(shè)定的最大迭代次數(shù)，則將這個最優(yōu)解輸出，若不滿足，則轉(zhuǎn)到流程2)中.

2.4 禁忌粒子群車間調(diào)度算法

2.4.1 編碼 對3個車間的零件和部件及產(chǎn)品進(jìn)行編碼，編碼完成后，對車間進(jìn)行統(tǒng)一優(yōu)化調(diào)度.首先，確定產(chǎn)品總裝配車間、部件裝配車間及零件加工車間產(chǎn)品數(shù)量最小比例，對其進(jìn)行統(tǒng)一編碼.其次，用字母代表產(chǎn)品、部件和零件，相同字母代表同樣的產(chǎn)品、部件和零件.如零件加工車間所生產(chǎn)的零件為A，B，C；部件裝配車間的部件為D，E；產(chǎn)品總裝車間的產(chǎn)品為F，G，H，那么，算法編碼為(A，B，C，D，E，F(xiàn)，G，H).

2.4.2 適應(yīng)度函數(shù) 適應(yīng)度函數(shù)(G)為

G=min(Ei，j+Ex，k+Ey，s).

(8)

式(8)中:Ey，s代表產(chǎn)品總裝配車間所有產(chǎn)品y在設(shè)備s完成裝配的最大完工時間約束.

2.4.3 粒子更新 采用式(6)，(7)對粒子種群進(jìn)行更新.將禁忌算法加入傳統(tǒng)粒子群算法中，對粒子群進(jìn)行隨機(jī)的交換組合，增強(qiáng)算法尋優(yōu)的能力，防止算法進(jìn)入局部最優(yōu)的可能.

圖3 算法并行化思路Fig.3 Idea of algorithm parallelization

2.4.4 算法并行化實現(xiàn) 采用Java軟件編寫對應(yīng)的Map函數(shù)和Reduce函數(shù)，并調(diào)用Hadoop集群環(huán)境，結(jié)合禁忌粒子群算法和Hadoop集群，解決混流混合車間調(diào)度的問題.禁忌粒子群算法在運行過程中，讀取相關(guān)的車間數(shù)據(jù)，設(shè)定啟動多個Map函數(shù)和Reduce函數(shù)進(jìn)行處理.在Map函數(shù)階段，計算禁忌粒子群算法中每個粒子，即根據(jù)所設(shè)置的目標(biāo)函數(shù)，計算相對應(yīng)的適應(yīng)度；在Reduce函數(shù)階段，輸出粒子群中最優(yōu)的適應(yīng)度.算法并行化思路，如圖3所示.

3 實例驗證

3.1 混流混合車間調(diào)度實例

以裝載機(jī)制造車間為例[15]，對算法進(jìn)行驗證.裝載機(jī)制造車間是由零件加工車間、部件裝配車間、產(chǎn)品總裝配車間組成的.產(chǎn)品需求矩陣，如表1所示.表1中：Q1，Q2，Q3，Q4為生產(chǎn)的產(chǎn)品.A～H為零件；X，Y為部件；-表示產(chǎn)品和需求的部件沒有關(guān)系；1表示產(chǎn)品和需求的部件有對應(yīng)關(guān)系.

表1 產(chǎn)品需求矩陣Tab.1 Product demand matrix

零件按A，B，C，D，E，F(xiàn)，G，H的順序進(jìn)行加工，零件加工時間(tp)，如表2所示.表2中：M1～M10分別表示設(shè)備.

表2 零件加工時間和工序Tab.2 Part processing time and processing sequences

部件裝配車間主要負(fù)責(zé)的是部件X，Y的裝配，部件裝配時間(tc)，如表3所示.

產(chǎn)品總裝配車間流水線共有33個裝配工位，工序按工位的順序進(jìn)行排序，產(chǎn)品總裝配時間(tt)如表4所示.

表3 部件裝配時間Tab.3 Assembly time of components

表4 產(chǎn)品總裝配時間Tab.4 Total assembly time of products

圖4 算法進(jìn)化曲線Fig.4 Algorithm evolution curve

生產(chǎn)計劃期內(nèi)產(chǎn)品Q1，Q2，Q3，Q4的任務(wù)分別為320，160，320，320 臺，最小生產(chǎn)循環(huán)為2∶1∶2∶2.根據(jù)已知條件，部件X，Y分為480，640個，最小的生產(chǎn)循環(huán)為3∶4；零件A～H分別為480，640，480，640，480，640，480，640個，最小生產(chǎn)循環(huán)為3∶4∶3∶4∶3∶4∶3∶4.

Hadoop集群由4臺機(jī)器組成，選取其中一臺機(jī)器作為Master節(jié)點，其他3臺作為Slave節(jié)點.設(shè)置禁忌粒子群算法的有關(guān)參數(shù)如下：種群的大小為20；迭代次數(shù)為300次；w為0.1；c1，c2都為1.TSPSO運行的最優(yōu)解為15 583 s；遺傳算法(GA)的最優(yōu)解為15 700 s；免疫遺傳算法(IA)[15]的最優(yōu)解為15 679 s.實驗結(jié)果表明，禁忌粒子群算法(TSPSO)可有效避免局部最優(yōu)的可能.算法進(jìn)化曲線，如圖4所示.圖4中：tb為最優(yōu)解；k為迭代次數(shù).

3.2 算法對比

在種群大小為20，迭代次數(shù)為50的情況下，分別用最優(yōu)解(tb)、平均值(tvar)對比3種算法的性能.結(jié)果表明，TSPSO收斂性能好、收斂的速度快且不易陷入局部最優(yōu).3種算法性能對比，如表5所示.

禁忌粒子群算法和遺傳算法及免疫遺傳算法的每個車間運行時間(tr)對比，如表6所示.表6中：δ為對比差比例.

表5 3種算法性能對比Tab.5 Performance comparison of three algorithms

表6 3種算法的每個車間運行時間對比Tab.6 Running time comparison of each workshop of three algorithms

由表6可知：TSPSO在產(chǎn)品批量大的情況下，在零件加工車間、產(chǎn)品總裝配車間車間所得出的效果都比GA和IA更優(yōu).因此，TSPSO在大批量的情況下可對總體的調(diào)度進(jìn)行優(yōu)化.

4 結(jié)束語

并行化的禁忌粒子群算法，在面對產(chǎn)品批量較大的情況下，可以有效地避免陷入局部最優(yōu)的問題，解決了批量大的情況下車間調(diào)度的問題.未來考慮對3個車間進(jìn)行獨立編碼，進(jìn)一步對車間調(diào)度進(jìn)行優(yōu)化，得到更好的調(diào)度的方案；對粒子群算法進(jìn)一步改進(jìn)，結(jié)合大數(shù)據(jù)平臺提高算法的效率.