祝 勇 潘曉弘

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

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

祝 勇 潘曉弘

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

針對(duì)以獲得最大效益為目標(biāo)的電子制造企業(yè)的訂單生產(chǎn)安排問(wè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)模型，提出了一種動(dòng)態(tài)改變慣性權(quán)重的粒子群算法，引入粒子群多樣性和進(jìn)化速度兩個(gè)參數(shù)，并以此構(gòu)造了動(dòng)態(tài)改變慣性權(quán)重的計(jì)算式，從而可以更好地搜索問(wèn)題解空間，避免了因粒子群多樣性降低導(dǎo)致的粒子陷入局部極值的困擾。應(yīng)用實(shí)例的計(jì)算分析表明了所提出方法的有效性。

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

0 引言

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

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

1 問(wèn)題描述與模型建立

1.1 參數(shù)描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 DCWPSO算法

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

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

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

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

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

（5）對(duì)粒子群中的所有粒子執(zhí)行以下操作：①根據(jù)式（15）～式（17）計(jì)算粒子群多樣性Dt、進(jìn)化速度Et以及慣性權(quán)重w；②根據(jù)式（12）和式（13）更新粒子i的位置xi和速度vi；③ 根據(jù)式（18）計(jì)算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條裝配線(xiàn)，生產(chǎn)6種產(chǎn)品。裝配線(xiàn)的能力矩陣A和費(fèi)用矩陣F分別為

計(jì)劃周期［0，T］為［0，30］，各裝配線(xiàn)的時(shí)間能力約束如表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中對(duì)應(yīng)產(chǎn)品Pj的需求量為Dkj，dk為訂單Ok的交貨期，vj＝｛1.5，1.2，1.4，1.3，1，1.2｝。

為了與慣性權(quán)重線(xià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)過(guò)MATLAB仿真計(jì)算，DCWPSO耗時(shí)322s，LDWPSO 耗時(shí)406s，ACWPSO耗時(shí)354s，訂單完成日期和費(fèi)用如表3所示，仿真結(jié)果如圖1所示。

表1 各裝配線(xiàn)的時(shí)間能力約束 d

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

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

圖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元，此時(shí)排產(chǎn)結(jié)果如表4所示。而采用LDWPSO排產(chǎn)時(shí)的總費(fèi)用為285 627元，比采用DCWPSO排產(chǎn)時(shí)的總費(fèi)用高了約9.8%，采用ACWPSO排產(chǎn)時(shí)的總費(fèi)用為267 081元，比采用DCWPSO排產(chǎn)時(shí)的總費(fèi)用高了約2.7%。DCWPSO收斂最快，耗時(shí)最少，為322s，LDWPSO耗時(shí)比DCWPSO增加了約26%，ACWPSO耗時(shí)比DCWPSO增加了約10%。由此可見(jiàn)，DCWPSO的最優(yōu)解要優(yōu)于LDWPSO和ACWPSO，其引起的總費(fèi)用最少，但收斂速度更快，耗時(shí)更少，這在求解大規(guī)模問(wèn)題時(shí)體現(xiàn)更明顯。

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

4 結(jié)束語(yǔ)

本文提出了基于改進(jìn)PSO算法的電子產(chǎn)品訂單排產(chǎn)方法，建立了模糊約束整數(shù)規(guī)劃的訂單排產(chǎn)模型，通過(guò)改進(jìn)PSO算法求解?；诹Ｗ尤憾鄻有院瓦M(jìn)化速度動(dòng)態(tài)改變慣性權(quán)重，以更好地搜索解空間，避免了因粒子群多樣性降低而導(dǎo)致的粒子陷入局部極值的困擾，并且對(duì)于違反約束的粒子采用了修復(fù)技術(shù)，以防止不可行解的產(chǎn)生。仿真結(jié)果表明，對(duì)于復(fù)雜約束排產(chǎn)優(yōu)化問(wèn)題，DCWPSO算法尋優(yōu)性能優(yōu)良，為企業(yè)快速排產(chǎn)提供了一種新方法。不過(guò)此算法的收斂性理論分析還有待進(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)度問(wèn)題的研究現(xiàn)狀與展望［J］.計(jì)算機(jī)集成制造系統(tǒng)－CIMS，2006，12（2）：161－168.

［7］ 徐俊剛，戴國(guó)忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述［J］.計(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)江，王書(shū)亭.一種動(dòng)態(tài)改變慣性權(quán)重的粒子群優(yōu)化算法［J］.中國(guó)機(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

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

（編輯 王艷麗）

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