基于混合粒子群算法的企業(yè)訂單分配優(yōu)化研究

陳 頻，吳鴻輝，江小云

（1.廈門理工學(xué)院 管理學(xué)院，廈門 361024；2.臺(tái)灣中華大學(xué) 企業(yè)管理學(xué)系，臺(tái)灣 300012）

0 引言

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

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

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

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

2 訂單分配優(yōu)化模型

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

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

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

3 求解訂單分配優(yōu)化模型的混合粒子群算法

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

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

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

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

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

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

步驟6：適應(yīng)度值計(jì)算。粒子適應(yīng)度值表示訂單分配量。在本文中由于引入轉(zhuǎn)換矩陣S將三維決策變量轉(zhuǎn)換為二維，適應(yīng)度函數(shù)因此表示為：

根據(jù)式（8）計(jì)算適應(yīng)度值，得到個(gè)體最優(yōu)粒子及群體最優(yōu)粒子。

步驟7：交叉操作。交叉操作分為個(gè)體最優(yōu)交叉和群體最優(yōu)交叉。隨機(jī)選定兩個(gè)交叉位置，將個(gè)體分別和個(gè)體最優(yōu)粒子及群體最優(yōu)粒子進(jìn)行交叉。

步驟8：變異操作。按變異概率P執(zhí)行變異操作，生成新的個(gè)體。

步驟9：判斷算法是否結(jié)束。判斷是否達(dá)到最大進(jìn)化代數(shù)G，如果未達(dá)到，則轉(zhuǎn)步驟5，否則執(zhí)行以下步驟。

步驟10：群體最優(yōu)粒子即為最佳解。

4 算例

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

表2 各訂單需求規(guī)格范圍及數(shù)量

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

接著構(gòu)建用于優(yōu)化的適應(yīng)度函數(shù)如式（10）～式（13）所示。

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

圖1 混合粒子群算法的進(jìn)化過程

5 結(jié)論

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

表3 三種波段和三種亮度等級(jí)的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]蔣大奎,李波,潭佳音.一類求解訂單分配和排序問題的集成優(yōu)化算法[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]顏俊華,張敏,王永軍.基于遺傳算法的智能粒子群優(yōu)化方法[J].西南大學(xué)學(xué)報(bào)(自然科學(xué)版),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.