應用禁忌粒子群算法的車間調度及其并行化實現

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

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

混流混合車間調度涉及作業車間調度和流水車間調度，生產過程包括零件加工、部件裝配、產品總裝配.由于作業車間和流水車間聯系緊密，對某一個車間進行單獨優化都可能導致大量庫存和生產周期延長.因此，混流混合車間調度需要考慮作業車間調度和流水車間調度.

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

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

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

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

1 問題的建模

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

1) 在流水車間，只對自制件進行加工，不考慮外購外協件；

2) 生產之前，車間內的設備和工位沒有制品且已經準備就緒；

3) 加工時間包括準備時間、搬運時間；

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

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

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

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

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

(1)

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

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

(2)

部門裝配車間和產品總裝配車間的工位約束為

(3)

部門裝配車間和產品總裝配車間的工序約束為

(4)

部門裝配車間和產品總裝配車間的時間約束為

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

(5)

2 粒子群算法

2.1 傳統粒子群算法

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

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

(6)

xnex=xcur+vnex.

(7)

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

2.2 禁忌粒子群算法

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

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

2.3 禁忌粒子算法流程

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

1) 設置PSO的相關參數，置空禁忌表；

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

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

4) 將粒子群中的每個粒子進行隨機交叉變異，計算變異后的粒子適應度；

5) 若新的適應度比群體最優解好，則更新禁忌表中，更新群體最優解，若不滿足，就轉到流程6)；

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

7) 若迭代次數大于所設定的最大迭代次數，則將這個最優解輸出，若不滿足，則轉到流程2)中.

2.4 禁忌粒子群車間調度算法

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

2.4.2 適應度函數 適應度函數(G)為

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

(8)

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

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

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

2.4.4 算法并行化實現 采用Java軟件編寫對應的Map函數和Reduce函數，并調用Hadoop集群環境，結合禁忌粒子群算法和Hadoop集群，解決混流混合車間調度的問題.禁忌粒子群算法在運行過程中，讀取相關的車間數據，設定啟動多個Map函數和Reduce函數進行處理.在Map函數階段，計算禁忌粒子群算法中每個粒子，即根據所設置的目標函數，計算相對應的適應度；在Reduce函數階段，輸出粒子群中最優的適應度.算法并行化思路，如圖3所示.

3 實例驗證

3.1 混流混合車間調度實例

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

表1 產品需求矩陣Tab.1 Product demand matrix

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

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

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

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

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

表4 產品總裝配時間Tab.4 Total assembly time of products

圖4 算法進化曲線Fig.4 Algorithm evolution curve

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

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

3.2 算法對比

在種群大小為20，迭代次數為50的情況下，分別用最優解(tb)、平均值(tvar)對比3種算法的性能.結果表明，TSPSO收斂性能好、收斂的速度快且不易陷入局部最優.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在產品批量大的情況下，在零件加工車間、產品總裝配車間車間所得出的效果都比GA和IA更優.因此，TSPSO在大批量的情況下可對總體的調度進行優化.

4 結束語

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