基于混合粒子群算法的企業訂單分配優化研究

陳 頻，吳鴻輝，江小云

（1.廈門理工學院 管理學院，廈門 361024；2.臺灣中華大學 企業管理學系，臺灣 300012）

0 引言

發光二極管（Light-Emitting Diode,LED）產業由于具有節能環保特性在我國處于快速成長階段，產業鏈包括原材料、上游的磊晶片制造、中游的芯片制造和下游的產品封裝。一般的LED芯片廠商將上游和中游整合制造，成為LED產業很重要的一環。LED芯片廠的生廠過程分為兩部分，包括前端和后端。前端主要生產磊晶片，后端將晶片加工成芯片，并經由點測、切割、分類和包裝，最后入庫或出貨。一片磊晶片可產出成千上萬顆結構、大小、電性功能不等的芯片。芯片中電性功能（分亮度和波長）的分布與前端的磊晶片的制造過程相關[1～3]，由于生產過程的不穩定特性，滿足投產工單的電性需求規格的芯片數量占的比例（即合工單率，Hit Target）普遍不高，導致產生很高的副產品庫存。然而，這些副產品庫存并不是殘次品，它們可以滿足其他的訂單。因此如何合理地分配訂單，有效地安排生產，最大幅度地降低庫存水平，是LED芯片廠所必須面對的問題。

1 LED芯片廠的訂單分配問題

LED芯片廠一般將芯片按其不同的電性功能以不同的區段（BIN）來分類。表1所示為一家LED廠的黃光芯片不同電性組合的BIN存貨表，共9種BIN，括號中所注為BIN的編號。電性功能主要分為波長和亮度。黃光LED 的波長為584nm～588nm，分三種波段，亮度為0mcd～300mcd，分三個等級。客戶下單時的訂單規格，是以各電性范圍來表示，例如客戶A的訂單要求規格為波長587nm～594nm,亮度為100mcd～300mcd，數量為800K。如表1的灰色部份所示，有4種BIN滿足需求，即｛（2,2），（2,3），（3,2），（3,3）｝。由于分配給客戶的BIN若越集中，則表示品質越好，價格應更高，因此出貨時最好滿足需求的BIN都出一些，不要為零或太低，否則會造成升級的問題（例如客戶下次要求一樣的品質）。要滿足一張訂單的規格和數量，有無限種BIN芯片數量的組合可滿足，應如何選取最佳的BIN出貨組合？也就是如何能讓更多的訂單可出貨[4～7]。例如上述客戶A的訂單，如果出貨時滿足訂單規格的4個BIN出貨量各為200K，則出貨后4個BIN的存貨數量分別為（263,212,201,179）。如果還有另一客戶B，訂單要求規格為波長584nm～591nm，亮度為200mcd～300mcd，數量為600K，則因滿足規格的2個BIN，即{（3,1），（3,2）}的存貨總計只有543K，無法滿足這張訂單的需求，生管只能下工單安排生產。但是如果客戶A的訂單BIN（3,2）少出貨100K，而讓其他3個BIN多出貨100K，則剩余的存貨即可滿足客戶B的訂單需求。因此，選擇最佳的BIN訂單分配組合，不但有助于存貨的有效利用，而且能大幅提高客戶的滿意度。

表1 LED芯片廠的黃光芯片各BIN期初庫存

2 訂單分配優化模型

假設LED芯片的亮度等級有J個等級，波長分為K種波段，總共有J ×K 個BIN，各BIN編號用(j,k)表示，j=1,…,J,k=1,…,K。 bjk表示BIN編號為(j,k)的初始庫存。有I張訂單須分配，訂單i(i=1,…,I)的需求數量為qi，需求波長波段等級范圍k為wil～wui，亮度等級范圍j為 lil～lui，則LED芯片廠的訂單分配優化模型可以描述如下。

決策變量 dijk為分配給訂單i的亮度等級編號為j，波長波段編號為k的BIN的出貨量。式（1）為目標函數，表示出貨量需最大。希望通過各決策變量 dijk的優化，找到最佳BIN出貨組合，讓盡可能多的訂單出貨需求得到滿足。式（2）為第一類約束條件，共J ×K 個不等式，表示對于每一個亮度等級編號為j，波長波段編號為k的BIN，I張訂單的總出貨量不能大于其庫存量。式（3）為第二類約束條件，共I個不等式，表示對于每一張訂單，其出貨量不能超過需求量。式（4）為決策變量的取值范圍下界約束,即為避免問題升級，出貨時每個BIN都要出的最少數量。式（5）表示各決策變量、各BIN庫存量和各訂單需求量須為正整數。

上述模型的決策變量值需為整數，屬于整數規劃模型，具有NP性質[8]。對于小規模整數規劃問題，可以通過使用隱枚舉法、動態規劃方法、分支定界法等傳統方法來求解[9]，而對于中等規模甚至大規模問題，計算量會出現組合爆炸的現象，很難在合理的時間內求得模型最優解[10]。上述模型由于變量和約束非常多，且隨著問題規模的變大會急劇增加，再加上決策變量屬三維結構，增加了模型求解的難度，不適合使用傳統方法求解。智能優化算法較常應用于中大規模的整數規劃求解[11,12]，因此針對該模型的特點，本文提出了基于轉換矩陣的一種編碼方法，將三維決策變量轉換為二維矩陣，而后形成一維決策變量，使用混合粒子群算法進行求解，不僅降低了算法計算過程的復雜度，而且提高了求解效率。

3 求解訂單分配優化模型的混合粒子群算法

使用標準粒子群算法求解時，隨著迭代次數的增加，在種群快速收斂集中的同時，各粒子越來越來相似，算法很難跳出這個局部最優范圍，即早熟收斂[13,14]。混合粒子群算法引用了遺傳算法中的交叉和變異操作，不僅增大了種群的多樣性，也有利于算法的全局搜索[15]。因此，本文提出了使用混合粒子群算法求解該訂單分配優化模型，具體步驟如下：

步驟1：生成轉換矩陣。決策變量 dijk屬于三維結構，本文引入一個二維矩陣S(如式（6）所示)將三維變量轉換為二維矩陣，最后形成一維決策變量求解。

其中矩陣中i表示訂單號，每一行代表一張訂單，共I張訂單。m表示BIN的序號，m與BIN的編號(j,k)對應關系如式（7）所示。矩陣元素 sim值1表示m所對應的BIN的波長和亮度符合訂單i的需求，0表示不符合。

步驟2：個體編碼。粒子個體采用整數編碼，每個粒子表示所有訂單的各BIN出貨組合。假設LED廠有I張訂單須滿足，J個亮度等級和K種波段等級，則每個粒子的長度為I×J×K（即式(6)中轉換矩陣的元素個數）。由于編碼太長，不僅浪費大量的存儲空間，而且降低運行效率。分析式(6)的轉換矩陣，屬稀疏矩陣。為了解除其稀疏特性，本文僅對矩陣中值為1的元素進行編碼，不僅有效減少個體長度，降低了算法計算過程的復雜度，在一定程度上也提高了算法性能。

步驟3：確定參數值。根據數據規模和分布特征確定混合粒子群算法的控制參數，如種群個體數目N、最大進化代數G和變異概率P。由于該模型決策變量和限制條件都較多，為保證求解效果，因此種群個體數目N和最大進化代數G須設得較大。

步驟4：粒子初始化。產生初始種群時，通過在變量范圍內隨機生成正整數方式。各變量最小值根據式（4）定為β×iq，最大值根據式（3）定為qi。

步驟6：適應度值計算。粒子適應度值表示訂單分配量。在本文中由于引入轉換矩陣S將三維決策變量轉換為二維，適應度函數因此表示為：

根據式（8）計算適應度值，得到個體最優粒子及群體最優粒子。

步驟7：交叉操作。交叉操作分為個體最優交叉和群體最優交叉。隨機選定兩個交叉位置，將個體分別和個體最優粒子及群體最優粒子進行交叉。

步驟8：變異操作。按變異概率P執行變異操作，生成新的個體。

步驟9：判斷算法是否結束。判斷是否達到最大進化代數G，如果未達到，則轉步驟5，否則執行以下步驟。

步驟10：群體最優粒子即為最佳解。

4 算例

為了驗證本研究提出的方法的有效性和優越性，本文針對具體的一家LED芯片廠的訂單分配進行優化，求解各BIN的最佳出貨組合。假設該LED廠將芯片按波長分為3種波段，按亮度分為3個等級，各BIN期初存貨如表1所示。已知8張訂單需要分配，各需求量與規格如表2所示。設定β 值為2%，也就是每個符合產品規格的BIN最小出貨量為其訂單需求的2%，小數點部份無條件進位。具體優化步驟如下。

表2 各訂單需求規格范圍及數量

首先根據已知條件生成轉換矩陣S，共8行9列，如式（9）所示。

接著構建用于優化的適應度函數如式（10）～式（13）所示。

最后使用本文提出的混合粒子群算法進行求解，經400次進化后，得到群體最優粒子為[1769138795617515238415718237413515610746163156166546]，轉換為二維矩陣D（共8行9列），如式（14）所示。算法進化過程如圖1所示。由式（10）得到此時的訂單分配總量為2052，即所有的訂單需求均得到滿足。式（14）中每一行的和即為各訂單的分配量（也就是330,276,194,272,291,153,319,217），每一列的和即為該列號所對應的BIN的總出庫量（也就是323,294,314,23,218,389,0,175,316），各BIN期末庫存如表3所示。從式（14）和表3可以看出，符合訂單1的BIN有4個，分別對應表3中的編號為(1,2)，(1,3)，(2,2)，(2,3)的BIN，其出貨量分別為176,9,138,7。滿足訂單2的BIN有3個，分別對應表3中的編號為(1,2)，(2,2)，(3,2)的BIN，其出貨量分別為95，6，175，依此類推。

圖1 混合粒子群算法的進化過程

5 結論

LED芯片廠為LED產業很重要的一環。LED廠一般將芯片按亮度和波長用不同的BIN來分類。客戶下單時的產品需求規格以亮度等級范圍和波長波段范圍表示，因此合乎規格的BIN有多種。要滿足一張訂單，有無限種BIN出貨數量組合可滿足。為了讓盡量多的訂單可出貨，如何優化各訂單的BIN庫存分配組合，是一個必須解決的重要問題。本研究提出一種混合粒子群算法來決定各訂單的最佳BIN庫存分配組合，以實現出貨數量最大的目標。實證結果充分證明了該方法的有效性。本研究提出的方法在現實的LED廠中具有良好的經濟效益和廣闊的應用前景，不僅最大限度地滿足了訂單需求，提高了客戶的滿意度，而且有效降低總體庫存水平，減少生產資金占用，提高企業的經濟效益和市場競爭能力。

表3 三種波段和三種亮度等級的LED芯片廠各BIN期末庫存

[1]Wu HH,Li MF,Hsu TF.An order fulfillment model for the LED chip manufacturing plant[J].Adv Mater Res,2013,694-697：3446-3452.

[2]Wu HH,Li MF.A study of the order fulfillment and production model for the LED die manufacturer[A].In：Proceeding of Chinese Institute of Industrial Engineers Confrence[C].Hsinchu,Taiwan,2011,55-61.

[3]Chang MH,Das D,Varde PV,Pecht M.Light emmiting diodes reliability review[J].Microelectron Reliab,2012,52(5)：762-782.

[4]Scholand MJ,Dillon HE.Life-Cycle assessment of energy and environmental impacts of LED lighting products -Part 2：LED manufacturing and performance[J].Pacific Northwest National Laboratory and the U.S.Department of Energy,2012.

[5]Wu HH,Li MF,Yeh CH.A study of the material reissued models for an insufficient output of the LED chip manufacturing plant[J].Adv Mater Res,2013,694-697：3434-3440.

[6]Wu HH,Wu HH,Li MF.A study of the shifting MO model for an insufficient output of the LED die manufacturing plant[A].In：Global Business &International Management Conference at NYIT-Vancouver Campus[C].Canada,2013,6(2)：46-55.

[7]Wu HH,Yeh CS.A study of the bin inventory allocation model for LED-CM plants[J].In：2nd International Conference on Materials and Manufacturing Research,Dalian,China,2014,85-89.

[8]Ayough A,Zandieh M,Farsijani H..GA and ICA approaches to job rotation scheduling problem：considering employee's boredom[J].Int J Adv Manuf Technol,2012,60：651-666.

[9]Yeniay O.Penalty function methods for constrained optimization with genetic algorithms[J].Math Comput Appl,2005,10(1)：45-56.

[10]Chen WC,Liu KP,Liu BH,Lai TT.Optimization of optical design for developing a LED lens module[J].Neural Comput &Applic,2013,22(3)：811-823.

[11]蔣大奎,李波,潭佳音.一類求解訂單分配和排序問題的集成優化算法[J].控制與決策,2013,28(2)：217-222.

[12]Lin YC,Wang KS,WANG FS.A mixed-coding scheme of evolutionary algorithms to solve mixed-integer nonlinear programming problems[J].Comput Math Appl,2004,47(8-9)：1295-1307.

[13]顏俊華,張敏,王永軍.基于遺傳算法的智能粒子群優化方法[J].西南大學學報(自然科學版),2010,32(11)：135-139.

[14]Chuang SP,Hsu TS,Yang CL.Parallel work center scheduling with release dates,due dates,and resourcedependent processing times[J].Int J Adv Manuf Technol,2009,40：193-202.

[15]Jiang XY,Wu HH.Optimization of setup frequency for TOC supply chain replenishment system with capacity constraints[J].Neural Comput &Applic,2013,23(6)：1831-1838.