基于改進(jìn)粒子群優(yōu)化算法的電子產(chǎn)品排產(chǎn)研究

祝 勇 潘曉弘

浙江大學(xué)，杭州，310027

基于改進(jìn)粒子群優(yōu)化算法的電子產(chǎn)品排產(chǎn)研究

祝 勇 潘曉弘

浙江大學(xué)，杭州，310027

針對以獲得最大效益為目標(biāo)的電子制造企業(yè)的訂單生產(chǎn)安排問題，提出一種基于改進(jìn)粒子群優(yōu)化算法的電子產(chǎn)品排產(chǎn)方法，建立了模糊生產(chǎn)能力約束條件下的電子產(chǎn)品訂單排產(chǎn)模型。在模糊生產(chǎn)能力約束條件下，該模型以由裝配生產(chǎn)費(fèi)用和拖期生產(chǎn)產(chǎn)生的懲罰費(fèi)用所構(gòu)成的總費(fèi)用最小化為目標(biāo)函數(shù)。為求解該排產(chǎn)模型，提出了一種動態(tài)改變慣性權(quán)重的粒子群算法，引入粒子群多樣性和進(jìn)化速度兩個參數(shù)，并以此構(gòu)造了動態(tài)改變慣性權(quán)重的計算式，從而可以更好地搜索問題解空間，避免了因粒子群多樣性降低導(dǎo)致的粒子陷入局部極值的困擾。應(yīng)用實(shí)例的計算分析表明了所提出方法的有效性。

電子產(chǎn)品排產(chǎn)；模糊約束整數(shù)規(guī)劃；粒子群優(yōu)化算法；自適應(yīng)慣性權(quán)重

0 引言

近年來許多學(xué)者對訂單排程的各種問題進(jìn)行了大量的研究［1－5］，對多種生產(chǎn)情況下的基于優(yōu)先級調(diào)度規(guī)則的生產(chǎn)調(diào)度與排程分別進(jìn)行了論述。Leung等［1－2］研究了在滿足訂單交貨期約束下，多產(chǎn)品在多機(jī)器上的生產(chǎn)調(diào)度。Lin等［4］、Wang等［5］都采用啟發(fā)式方法來解決在一定約束條件下使訂單總的加工或完成時間最短的問題。目前研究人員在生產(chǎn)調(diào)度方面做了很多相關(guān)工作［6－7］，但大多都只是從訂單的完成日期或交貨日期出發(fā)進(jìn)行生產(chǎn)安排，或者只考慮成本，沒有將兩者綜合考慮。

在實(shí)際生產(chǎn)過程中，很多時候不能作出精確決策，這時需要用模糊數(shù)來表示，例如產(chǎn)能在一定范圍內(nèi)浮動，可用三角模糊數(shù)來表示。在模糊產(chǎn)能約束條件下，考慮采用加工費(fèi)用與拖期生產(chǎn)的懲罰費(fèi)用之和為優(yōu)化目標(biāo)，建立模糊約束整數(shù)規(guī)劃模型，該模型是一個多維復(fù)雜約束優(yōu)化問題。為求解該問題本文提出一種新的自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法（particle swarm optimization algorithm with dynamically changing weight，DCWPSO），基于粒子群多樣性和進(jìn)化速度動態(tài)改變慣性權(quán)重，最后通過一個實(shí)例驗證了采用DCWPSO求解該訂單排產(chǎn)模型是有效的。

1 問題描述與模型建立

1.1 參數(shù)描述

某電子制造企業(yè)有M條裝配線，用Bi（i＝1，2，…，M）表示，生產(chǎn)N 種產(chǎn)品，用Pj（j＝1，2，…，N）表示。用矩陣A的元素~aij表示裝配線Bi單位時間裝配產(chǎn)品Pj的數(shù)量；用矩陣F的元素fij表示裝配線Bi裝配單位產(chǎn)品Pj所需的費(fèi)用；用矩陣G的元素~gij表示單位產(chǎn)品Pj消耗裝配線Bi的工時。~Hit表示裝配線Bi在第t天時的模糊空閑時間（每天的空閑時間在一定范圍內(nèi)波動，因此用模糊變量表示）。生產(chǎn)的最小批量為b，并且假設(shè)零部件和原材料供應(yīng)充足。

企業(yè)在計劃期［0，T］（T為自然數(shù)）內(nèi)接到L個客戶訂單，用Ok（k＝1，2，…，L）表示。訂單Ok對產(chǎn)品Pj的需求量為Dkj，交貨期用dk表示。

1.2 模糊約束整數(shù)規(guī)劃排產(chǎn)模型

電子產(chǎn)品訂單生產(chǎn)主要是面向裝配，電子產(chǎn)品的利潤較低，加工成本越低，企業(yè)能獲得的利潤越高。由于同一產(chǎn)品在不同裝配線上的裝配能力與費(fèi)用是不同的，故不同的安排生產(chǎn)的方法所產(chǎn)生的加工費(fèi)用不同。設(shè)第i條裝配線Bi在第t天時加工第j個產(chǎn)品Pj的數(shù)量為xijt，則加工費(fèi)用Cm為

由于需求與可用裝配生產(chǎn)能力不能完全匹配，企業(yè)經(jīng)常會出現(xiàn)拖期生產(chǎn)，而拖期生產(chǎn)需要向客戶支付懲罰費(fèi)用，設(shè)Pj拖期生產(chǎn)的單位懲罰系數(shù)為vj。

設(shè)αkt為訂單Ok在第t天時是否要交貨函數(shù)，若是，則αkt為1，否則為0，即

優(yōu)化目標(biāo)是最小化加工費(fèi)用與拖期懲罰費(fèi)用之和，決策變量為第i個裝配線Bi在第t天時加工第j個產(chǎn)品Pj的數(shù)量xijt，從而建立如下模糊約束整數(shù)規(guī)劃模型：

1.3 模糊生產(chǎn)能力約束的處理

對于式（6），由于生產(chǎn)能力的模糊性導(dǎo)致了約束的模糊。模糊生產(chǎn)能力~Hit采用三角模糊數(shù)（H（1）it，H（2）it，H（3）it）表示。

設(shè)裝配線Bi在第t天時的負(fù)荷為

設(shè)ξ、η是兩個模糊變量，則根據(jù)模糊變量的期望值比較原理［8］，有

根據(jù)式（10），當(dāng)E（Git）≤E（~Hit）時，式（6）的約束條件滿足。

2 改進(jìn)粒子群優(yōu)化算法求解

2.1 整數(shù)粒子群優(yōu)化算法

對于式（8），由于模糊生產(chǎn)能力約束的存在，傳統(tǒng)的數(shù)學(xué)規(guī)劃方法不能求解，粒子群優(yōu)化（particle swarm optimization，PSO）算法是由Kennedy等［9］和Eberhart等［10］提出的源于群智能的一種智能優(yōu)化算法，它用無質(zhì)量無體積的粒子作為個體，并為每個粒子規(guī)定簡單的行為規(guī)則，從而使整個粒子群表現(xiàn)出復(fù)雜的特性，可用來求解復(fù)雜的優(yōu)化問題。PSO算法有著個體數(shù)目少、計算簡單、魯棒性好等優(yōu)點(diǎn)，在函數(shù)優(yōu)化、模糊系統(tǒng)控制、組合優(yōu)化、約束優(yōu)化等領(lǐng)域均取得了非常好的應(yīng)用效果［10］。

在標(biāo)準(zhǔn)PSO算法中，粒子通過下式更新自己的速度和位置：

標(biāo)準(zhǔn)PSO算法在求解復(fù)雜多維約束優(yōu)化問題（如訂單排產(chǎn)模型）時存在早熟收斂現(xiàn)象并且容易陷入局部最優(yōu)。

2.2 慣性權(quán)重的動態(tài)改變

在PSO算法的參數(shù)中，慣性權(quán)重是最重要的參數(shù)，較大的慣性權(quán)重有利于全局探索，而較小的慣性權(quán)重有利于算法的局部搜索，加速算法的收斂。本文在前人研究成果的基礎(chǔ)上，提出了一種新的基于粒子群多樣性和進(jìn)化速度的自適應(yīng)慣性權(quán)重調(diào)整方法，當(dāng)進(jìn)化速度快時，需提高全局搜尋能力，當(dāng)粒子群多樣性差時，此時粒子群的全局搜索能力較差，要使粒子盡快地進(jìn)入全局搜索，此時需要增大慣性權(quán)重，反之減小慣性權(quán)重。

文獻(xiàn)［9］采用下式改變慣性權(quán)重w：

慣性權(quán)重線性遞減PSO算法（LDWPSO）在搜索后期由于多樣性降低，粒子容易陷入局部最優(yōu)。為了避免因粒子群多樣性降低導(dǎo)致粒子陷入局部極值，引入粒子群多樣性和進(jìn)化速度兩個參數(shù)。

粒子群多樣性Dt為所有裝配線在某時加工各產(chǎn)品數(shù)量的差異程度，可表示為平均聚集距離與最大聚集距離之比：

當(dāng)粒子都處于同一點(diǎn)時，Dt定義為0，粒子群多樣性最差。隨著粒子的擴(kuò)散，Dt增大，粒子群多樣性變好。

搜索開始時，Et較小，進(jìn)化速度較快，需擴(kuò)大搜索空間，也即要w較大；隨著搜索的進(jìn)行，Et增大，進(jìn)化減慢，這時要加強(qiáng)局部搜索能力，即要w較小。當(dāng)Dt較小時，粒子群多樣性較差，需要使其有擴(kuò)展搜索空間的能力，即要w較大，相反，當(dāng)Dt較大時，粒子群多樣性較好，需要能更好地搜索局部最優(yōu)解，即要w較小。從而基于Dt和Et，根據(jù)下式動態(tài)改變慣性權(quán)重w：

2.3 編碼與約束處理機(jī)制

由于目標(biāo)函數(shù)是最小化加工費(fèi)用與拖期懲罰費(fèi)用之和，所以可以直接采用目標(biāo)函數(shù)作為適應(yīng)值。訂單排產(chǎn)模型中決策變量是正整數(shù)，編碼可以采用解的自然表達(dá)，每個粒子表示的是各裝配線在某個時間段上產(chǎn)品的生產(chǎn)情況，分量表示一條裝配線上在某時生產(chǎn)一種產(chǎn)品的數(shù)量。從而一個粒子可以表示為：X ＝ ｛x111，x112，…，x11T；x121，x122，…，x12T；…；xMN1，xMN2，…，xMNT｝。

由于式（6）約束條件的存在，在粒子群進(jìn)化搜索過程中，可能會產(chǎn)生無效解，需要對其進(jìn)行修正，以保證粒子表示的是可行解。一個解xi的不可行度IF（xi）可表示為

于是，當(dāng)IF（xi）＞0時，式（6）不滿足，否則滿足。定義數(shù)組ISIF（m）記錄粒子在迭代過程中是否滿足生產(chǎn)能力約束（式（6）），若滿足，則置為1，不滿足，則置為0。

為了保證模糊生產(chǎn)能力約束能夠被滿足，在粒子生成和更新過程中的修復(fù)方程為

2.4 DCWPSO算法

DCWPSO算法隨著搜索的進(jìn)行，根據(jù)粒子群多樣性Dt和進(jìn)化速度Et動態(tài)改變慣性權(quán)重w，其具體步驟如下：

（1）設(shè)定粒子群的規(guī)模為m，維數(shù)為n，n＝MNT，最大迭代次數(shù)為tmax。

（2）初始化粒子的位置x為最小批量b和速度v。將粒子的個體最優(yōu)值pi設(shè)為當(dāng)前位置，pg設(shè)為初始化群體中最佳粒子的位置，置ISIF（m）＝1。

（3）計算粒子的適應(yīng)度f（x）、個體最優(yōu)值pi、全局最優(yōu)值pg。

（4）判斷算法收斂準(zhǔn)則是否滿足，如果滿足，轉(zhuǎn)步驟（8），否則執(zhí)行步驟（5）。

（5）對粒子群中的所有粒子執(zhí)行以下操作：①根據(jù)式（15）～式（17）計算粒子群多樣性Dt、進(jìn)化速度Et以及慣性權(quán)重w；②根據(jù)式（12）和式（13）更新粒子i的位置xi和速度vi；③ 根據(jù)式（18）計算xi的不可行度IF（xi），若IF（xi）＞0則置ISIF（xi）＝0。

（6）若ISIF（xi）＝0，則根據(jù)式（19）修正xi。

（7）迭代次數(shù)t加1，轉(zhuǎn)步驟（3）。

（8）輸出全局最優(yōu)值pg，算法運(yùn)行結(jié)束。

3 應(yīng)用案例

某電子制造企業(yè)有4條裝配線，生產(chǎn)6種產(chǎn)品。裝配線的能力矩陣A和費(fèi)用矩陣F分別為

計劃周期［0，T］為［0，30］，各裝配線的時間能力約束如表1所示，B1在第3、4、9、10、11、17、18天被占用；B2在第1、4、5、6、13、14、19、20天被占用；B3在第3、7、8、9、15、22、23天被占用；B4在第2、3、6、12、13、16、17、20、21天被占用。最小生產(chǎn)批量b＝100。

訂單如表2所示，其中各訂單Ok中對應(yīng)產(chǎn)品Pj的需求量為Dkj，dk為訂單Ok的交貨期，vj＝｛1.5，1.2，1.4，1.3，1，1.2｝。

為了與慣性權(quán)重線性遞減PSO算法［9］和文獻(xiàn)［12］中的改進(jìn)PSO算法（ACWPSO）相比較，本文算法（DCWPSO）與之采用同樣的參數(shù)：粒子群規(guī)模為30，維數(shù)為4×6×30＝720，最大進(jìn)化代數(shù)為500，c1＝c2＝2.0，winit＝1.2，wend＝0.4。仿真環(huán)境為 MATLAB 7.5，CPU Intel Pentium Ⅳ2.0G，內(nèi)存2G，經(jīng)過MATLAB仿真計算，DCWPSO耗時322s，LDWPSO 耗時406s，ACWPSO耗時354s，訂單完成日期和費(fèi)用如表3所示，仿真結(jié)果如圖1所示。

表1 各裝配線的時間能力約束 d

表2 計劃期內(nèi)客戶訂單需求

表3 三種算法下的訂單完成日期、費(fèi)用和耗時

圖1 DCWPSO、LDWPSO、ACWPSO排產(chǎn)結(jié)果比較

DCWPSO排產(chǎn)的最少加工費(fèi)用與拖期懲罰費(fèi)用之和為260 118元，其中加工費(fèi)用Cm為221 362元，拖期生產(chǎn)懲罰費(fèi)用Cl為38 756元，此時排產(chǎn)結(jié)果如表4所示。而采用LDWPSO排產(chǎn)時的總費(fèi)用為285 627元，比采用DCWPSO排產(chǎn)時的總費(fèi)用高了約9.8%，采用ACWPSO排產(chǎn)時的總費(fèi)用為267 081元，比采用DCWPSO排產(chǎn)時的總費(fèi)用高了約2.7%。DCWPSO收斂最快，耗時最少，為322s，LDWPSO耗時比DCWPSO增加了約26%，ACWPSO耗時比DCWPSO增加了約10%。由此可見，DCWPSO的最優(yōu)解要優(yōu)于LDWPSO和ACWPSO，其引起的總費(fèi)用最少，但收斂速度更快，耗時更少，這在求解大規(guī)模問題時體現(xiàn)更明顯。

表4 各裝配線的產(chǎn)品生產(chǎn)安排結(jié)果

4 結(jié)束語

本文提出了基于改進(jìn)PSO算法的電子產(chǎn)品訂單排產(chǎn)方法，建立了模糊約束整數(shù)規(guī)劃的訂單排產(chǎn)模型，通過改進(jìn)PSO算法求解?；诹Ｗ尤憾鄻有院瓦M(jìn)化速度動態(tài)改變慣性權(quán)重，以更好地搜索解空間，避免了因粒子群多樣性降低而導(dǎo)致的粒子陷入局部極值的困擾，并且對于違反約束的粒子采用了修復(fù)技術(shù)，以防止不可行解的產(chǎn)生。仿真結(jié)果表明，對于復(fù)雜約束排產(chǎn)優(yōu)化問題，DCWPSO算法尋優(yōu)性能優(yōu)良，為企業(yè)快速排產(chǎn)提供了一種新方法。不過此算法的收斂性理論分析還有待進(jìn)一步研究。

［1］ Leung J Y T，Li H，Pinedo M.Scheduling Orders for Multiple Product Types with Due Date Related Objectives［J］.European Journal of Operational Research，2006，168（2）：370－389.

［2］ Leung J Y T，Li H，Pinedo M.Scheduling Orders for Multiple Product Types to Minimize Total Weighted Completion Time［J］.Discrete Applied Mathematics，2007，155（8）：945－970.

［3］ Li K，Ganesan V K，Sivakumar A I.Scheduling of Single Stage Assembly with Air Transportation in a Consumer Electronic Supply Chain［J］.Computers＆Industrial Engineering，2006，51（2）：264－278.

［4］ Lin B M T，Kononov A V.Customer Order Scheduling to Minimize the Number of Late Jobs［J］.European Journal of Operational Research，2007，183（2）：944－948.

［5］ Wang G，Cheng T C E.Customer Order Scheduling to Minimize Total Weighted Completion Time［J］.Omega－International Journal of Management Science，2007，35（5）：623－626.

［6］ 金鋒，吳澄.大規(guī)模生產(chǎn)調(diào)度問題的研究現(xiàn)狀與展望［J］.計算機(jī)集成制造系統(tǒng)－CIMS，2006，12（2）：161－168.

［7］ 徐俊剛，戴國忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述［J］.計算機(jī)研究與發(fā)展，2004，41（2）：257－267.

［8］ Liu B，Liu Y K.Expected Value of Fuzzy Variable and Fuzzy Expected Value Models［J］.IEEE Trans.on Fuzzy Systems，2002，10（4）：445－450.

［9］ Kennedy J，Eberhart R C.Particle Swarm Optimization［C］／／Proc.of 1995IEEE Int.Conf.on Neural Network，Ⅳ.Piscataway：IEEE Service Center，1995：1942－1948.

［10］ Eberhart R C，Shi Y.Particle Swarm Optimization：Developments，Applications and Resources［C］／／Proc.of 2001IEEE Int.Conf.on Evolutionary Computation.Piscataway：IEEE Service Center，2001：81－86.

［11］ Eberhart R C，Shi Y.A Modified Particle Swarm Optimizer［C］／／Proc.of 1998IEEE Int.Conf.on Evolutionary Computation.Piscataway：IEEE Service Center，1998：69－73.

［12］ 王啟付，王戰(zhàn)江，王書亭.一種動態(tài)改變慣性權(quán)重的粒子群優(yōu)化算法［J］.中國機(jī)械工程，2005，16（11）：945－948.

Scheduling Electronic Products Based on a Modified Particle Swarm Optimization

Zhu Yong Pan Xiaohong
Zhejiang University，Hangzhou，310027

Order－oriented production was satisfied to maximizing the profit，and to the due date of customer order.In such a circumstances，scheduling orders had been an important decision in modern enterprises.A method of scheduling electronic products based on a modified PSO was proposed.A cost model of scheduling orders for electronic products with fuzzy capacity constraints was established.The total cost was constituted of two costs，they were production costs from the assembly and penalty cost arising from tardiness production.A new adaptive particle swarm optimization algorithm with dynamically changing inertia weight（DCWPSO）was proposed to solve the problem.The DCWPSO changed inertia weight based on population diversity and evolution speed in order to balance the trade－off between exploration and exploitation.The application demonstrates the efficiency of the proposed model and DCWPSO algorithm，which is significantly superior to the linearly decreasing weight PSO （LDWPSO）in convergence speed and accuracy.

scheduling electronic product；integer programming with fuzzy constraint；particle swarm optimization（PSO）algorithm；adaptive inertia weight

F273；TP391

1004—132X（2011）01—0049—06

2010—01—28

國家高技術(shù)研究發(fā)展計劃（863計劃）資助項目（2009AA04Z151，2007AA040607）

（編輯 王艷麗）

祝 勇，男，1979年生。浙江大學(xué)現(xiàn)代制造工程研究所博士研究生。主要研究方向為生產(chǎn)管理、供應(yīng)鏈管理、制造業(yè)信息化等。發(fā)表論文6篇。潘曉弘，男，1954年生。浙江大學(xué)機(jī)械工程學(xué)系教授、博士研究生導(dǎo)師。