羅家祥 羅樹浩 吳忻生

(華南理工大學(xué)自動化科學(xué)與工程學(xué)院，廣東廣州510640)

表面貼裝技術(shù)是一種無需在印制電路板(PCB)上鉆插裝孔，而直接將表面貼裝元器件貼到PCB上，然后用焊料使元器件與PCB構(gòu)成機械和電氣連接的電子組裝技術(shù)．在PCB的組裝過程中，元器件的貼裝是整條生產(chǎn)線生產(chǎn)效率的關(guān)鍵環(huán)節(jié)，是生產(chǎn)線上的“瓶頸”．

為減少將電子元器件貼裝到PCB上所耗費的時間，提高生產(chǎn)效率，表面貼裝技術(shù)的優(yōu)化受到越來越多的關(guān)注．單臺貼片機的貼裝優(yōu)化一般存在兩個相關(guān)但仍然有一定獨立性的子問題［1］:1)喂料器的位置分配問題，確定不同類型的元器件喂料器在喂料槽上的安放位置;2)元器件的貼裝順序優(yōu)化問題，確定元器件的拾取和貼裝順序．前者通常被認(rèn)為是一個二次分配問題(QAP)［2］，后者被認(rèn)為是非對稱的旅行商問題(TSP)，均屬于NP難的組合優(yōu)化問題．文中主要研究元器件的貼裝順序優(yōu)化問題，即在喂料器安放位置確定的情況下，對元器件的拾取順序與貼裝順序進行優(yōu)化，使得貼裝過程中貼裝頭移動的總路徑最短．對該問題求解方法的研究主要集中在遺傳算法和其它一些啟發(fā)式算法．文獻［3］中提出了具有獨特的染色體編碼解碼方式和交叉算子的遺傳算法，該算法能有效解決元器件的貼裝順序問題．文獻［4］中將一種二維符號編碼方法應(yīng)用到遺傳算法中，實現(xiàn)了轉(zhuǎn)塔式貼片機的元器件貼裝順序和喂料槽分配的同時優(yōu)化．文獻［5］中針對貼裝順序優(yōu)化問題建立了以貼裝總時間為最小的數(shù)學(xué)模型，使用改進混合蛙跳算法來求解，結(jié)果表明該算法比遺傳算法具有更好的收斂性．文獻［6］在文獻［5］的混合蛙跳算法的基礎(chǔ)上，把混合蛙跳算法與蟻群算法相融合，實現(xiàn)對貼片機的元件貼裝順序優(yōu)化問題的求解，測試結(jié)果表明混合算法取得了更小的目標(biāo)函數(shù)值．此外，元器件貼裝順序優(yōu)化問題的求解方法還有傘布搜索算法［7］等．

雖然遺傳算法已被廣泛用于求解元器件貼裝順序優(yōu)化及其它復(fù)雜工業(yè)問題的優(yōu)化［8］，但遺傳算法具有過早收斂等局限性．為尋求更好的優(yōu)化結(jié)果，文中采用基于禁忌搜索的優(yōu)化算法對該問題進行求解．

首先，針對該優(yōu)化問題建立數(shù)學(xué)規(guī)劃模型，該模型考慮了貼裝過程中貼裝頭的移動路徑長度受貼裝頭間距的影響，并提出根據(jù)元器件的拾取路徑求取對應(yīng)最小貼裝路徑的方法．然后，分析了解序列的常見鄰域變換方法對貼裝頭運動路徑的影響，并據(jù)此選擇了交換鄰域結(jié)構(gòu);設(shè)計了包括禁忌移動和禁忌歷史局部最優(yōu)解的雙禁忌表，避免迭代過程中相同解序列的重復(fù)更新，增強算法避免迂回搜索的能力;引入了基于取貼循環(huán)插入移動的RLS策略，參照某個參考序列來搜索以取貼循環(huán)為單位的改進的插入移動．最后，通過實驗驗證所提算法的有效性．

1 問題描述及數(shù)學(xué)模型

1．1 問題描述

文中研究的拱架式貼片機組成包括機架、喂料槽、喂料器、拱架、貼裝頭、吸嘴和視覺識別攝像機等，如圖1所示．

圖1 拱架式貼片機結(jié)構(gòu)示意圖Fig．1 Schematic diagram of surface mounting machine with overhead－gantry

同一類型的元器件一般放在相同的喂料槽上．貼片機貼裝元器件的流程如下:

(1)傳送帶將PCB送到工作位置并夾緊固定;

(2)貼裝頭移動到喂料槽位置，同時或依次拾取指定的H(貼裝頭個數(shù))個元器件;

(3)帶著元器件的貼裝頭經(jīng)過視覺檢測區(qū)后，移動到工作臺上，將元器件按指定順序貼裝到PCB上的待貼裝位置;

(4)返回步驟(2)，直至PCB上的元器件貼裝完畢．

從貼裝元器件的流程可知，不同元器件的貼裝順序?qū)?yīng)不同長度的貼裝路徑．在視覺檢測時，貼裝頭的移動距離基本固定．因此元器件的取貼順序是影響貼裝效率的主要因素，是提高貼裝效率的要點．步驟(2)和(3)實現(xiàn)了拾取和貼裝H個元器件的過程，稱為一個取貼循環(huán)．一個取貼循環(huán)包括拾取H個元器件、貼裝H個元器件和返回下一個循環(huán)第一個元器件的拾取位置，如圖2所示．

圖2 一個取貼循環(huán)Fig．2 A picking and mounting cycle

文中擬將待貼裝的元器件組成取貼循環(huán)，確定取貼循環(huán)順序和每個循環(huán)內(nèi)的元器件拾取及貼裝順序，最小化貼裝頭在貼裝過程中移動的總路徑．

1．2 數(shù)學(xué)模型

貼裝頭在貼裝過程中移動的總路徑由多個取貼循環(huán)組成，每個取貼循環(huán)中又包括了拾取、貼裝元器件等多個階段．貼裝過程中的視覺檢測不是貼裝效率的主要影響因素，所以在優(yōu)化時不給予考慮．在已知喂料器位置的前提下，元器件的拾取位置和待貼裝位置均為已知條件．不失一般性，設(shè)待貼裝元器件個數(shù)n為貼裝頭個數(shù)H的整數(shù)倍．最大限度利用貼裝頭時，取貼循環(huán)個數(shù)為N=n/H．設(shè)J為待貼裝的元器件集合，J={1，2，…，n};S為元器件拾取順序，S=(S1，S2，…，Sk，…，SN)，Sk為第 k(k=1，2，…，N)個取貼循環(huán)中的元器件拾取順序，Sk=(sk，1，sk，2，…，sk，H)，該循環(huán)內(nèi)貼裝順序為 Πk=(πk，1，πk，2，…，πk，H);所有貼裝順序為 Π =(Π1，Π2，…，Πk，…，ΠN); 集 合 {sk，1，sk，2，…，sk，H} ={ πk，1，πk，2，…，πk，H}，即兩個集合包含的元器件相同;二維向量Ai、Bi分別為元器件i所在喂料器位置及其在PCB上的貼裝位置在直角坐標(biāo)系中的坐標(biāo);Δd為相鄰貼裝頭的間距;dkj為第k個取貼循環(huán)中貼裝頭拾取第j與第 j+1(j=1，2，…，H －1)個元器件所移動的距離;gk為第k個取貼循環(huán)中貼裝頭拾取第H個元器件后移動到貼裝PCB上本循環(huán)的第一個元器件所移動的距離;Dkj為第k個取貼循環(huán)中貼裝頭貼裝第j(j=1，2，…，H－1)與第j+1個元器件所移動的距離;bk為貼裝頭在第k個取貼循環(huán)中貼裝第H個元器件后至拾取第k+1個循環(huán)的第1個元器件所移動的距離;mk，j為第k個取貼循環(huán)中第j個貼裝元器件所在的貼裝頭．則建立的數(shù)學(xué)模型如下:

其中，· 為距離函數(shù)．目標(biāo)函數(shù)(1)包括拾取元器件路徑、從喂料槽到達PCB的路徑、貼裝元器件的路徑和從PCB回到喂料槽的路徑．約束(2)－(5)分別為 dkj、gk、Dkj、bk的計算式．上述模型考慮了貼裝頭的間距，更接近于實際貼裝生產(chǎn)．在計算貼裝頭移動距離時，對每次移動的起始位置坐標(biāo)進行補償，而不是將相鄰拾取或貼裝的兩個元器件之間的坐標(biāo)距離作為移動距離，如圖3所示．

圖3 考慮貼裝頭間距時的移動距離Fig．3 Moving distance considering the space between heads

上述模型所描述的元器件拾取與貼裝過程可看成一個特殊的TSP問題，因此所研究的優(yōu)化問題為NP難問題．

2 求解方法

禁忌搜索(TS)算法首先由 Glover［9］提出，通過引入一個存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，保證了多樣的有效搜索，已成功地解決了各類經(jīng)典的優(yōu)化問題．文中從TS算法的組成要素入手，結(jié)合貼片機貼裝順序優(yōu)化問題的特點，提出了一種基于參考解的局部搜索(RLS)的改進TS算法，設(shè)計了包括傳統(tǒng)禁忌表與歷史解禁忌表的雙禁忌表來避免迂回搜索，以提高搜索的多樣性．同時設(shè)計了基于取貼循環(huán)插入移動的RLS局部搜索策略，以提高算法的搜索性能．

2．1 解的表達形式及特點

一個取貼循環(huán)主要包括拾取和貼裝兩個過程，顯然元器件的拾取順序與貼裝順序是不一定相同的．在模型描述中，已用 S=(S1，S2，…，Sk，…，SN)和 Π =(Π1，Π2，…，Πk，…，ΠN)表示取貼循環(huán)中的元器件拾取序列和貼裝序列，兩者可進一步分別用長序列 S=(s1，s2，…，sH，…，sH(k－1)+1，…，sHk，…，sn)和 Π =(π1，π2，…，πH，…，πH(k－1)+1，…，πHk，…，πn)表示，并滿足{sH(k－1)+1，…，sHk}={πH(k－1)+1，…，πHk}的條件，表示第k個取貼循環(huán)內(nèi)拾取的元器件與貼裝的元器件相同．

對于第k個取貼循環(huán)中貼裝順序Πk的改變，只影響本循環(huán)的路徑總長度，不影響其它循環(huán)．因此，可以在不影響其它循環(huán)的前提下，尋找一個循環(huán)內(nèi)的最優(yōu)貼裝順序，使得本循環(huán)的貼裝總路徑長度最小．在Sk確定的條件下，最優(yōu)的Πk為:以本循環(huán)拾取的最后一個元器件sHk為起點、下一循環(huán)拾取的第一個元器件sHk+1為終點共H+2個城市的小規(guī)模TSP問題的解，如圖4所示．

圖4 單循環(huán)內(nèi)最優(yōu)貼裝順序Fig．4 Optimal mounting sequence in a single cycle

因此，求解所研究的優(yōu)化問題可集中在拾取序列S，而S對應(yīng)的貼裝順序可通過若干個小規(guī)模的TSP問題的求解獲得．貼裝順序的求解可在計算對應(yīng)拾取序列的目標(biāo)值時進行．

2．2 初始解的產(chǎn)生

文中基于最近鄰的啟發(fā)式方法［10］來獲取拾取順序的初始解．按最近鄰原則，分3個階段逐步確定當(dāng)前取貼循環(huán)內(nèi)的元器件拾取順序、當(dāng)前循環(huán)內(nèi)的元器件貼裝順序、下一循環(huán)拾取的第一個元器件．設(shè)Ω=J={1，2，…，n}，為待拾取的元器件集合，第 k個循環(huán)內(nèi)的元器件拾取順序為 Sk=(sH(k－1)+1，sH(k－1)+2，…，sHk)，貼裝順序為 Πk=(πH(k－1)+1，πH(k－1)+2，…，πHk)，c1，i，j為貼裝頭從拾取元器件 i移動到拾取元器件 j所經(jīng)過的距離．c2，i，j為貼裝頭在PCB上從貼裝元器件i移動到貼裝元器件j所經(jīng)過的距離;c3，i，j為貼裝頭從拾取元器件 i移動到貼裝元器件j所經(jīng)過的距離;c4，i，j為貼裝頭從貼裝元器件 i移動到拾取元器件 j所經(jīng)過的距離．c1，i，j、c2，i，j、c3，i，j、c4，i，j(i，j=1，2，…，n)可通過已知喂料器和貼裝點的坐標(biāo)計算得到．產(chǎn)生初始解的具體步驟描述如下:

(1)令 k:=1，在 Ω 中任意選擇元器件 i，sH(k－1)+1:=i，Ω:= Ω /{i};

(2)對所有 h(h=2，3，…，H)，在 Ω 中選擇 i=

(4)對所有 h(h=2，3，…，H)，在 Ψ 中選擇 i=

2．3 鄰域

交換、插入、2－opt和 3－opt是常見的鄰域結(jié)構(gòu)，常應(yīng)用于搜索算法中．當(dāng)對解序列中的1個或2個元器件移動時，插入、2－opt和3－opt移動會使得多個取貼循環(huán)發(fā)生改變，導(dǎo)致當(dāng)前解結(jié)構(gòu)產(chǎn)生較大變化，搜索的隨機性太強．因此，文中算法采用交換鄰域．在解序列中選擇兩點，然后交換在解序列中的位置，得到一個新的鄰解，如圖5所示．對解序列中任意兩點進行交換，得到的所有解構(gòu)成交換鄰域．

圖5 交換移動示例Fig．5 An example of exchange move

與其它移動相比，交換移動只改變交換的兩個點所在的取貼循環(huán)內(nèi)元器件的拾取順序，對其余的循環(huán)沒有影響．此外，由于同一循環(huán)內(nèi)元器件的拾取按一個方向進行，可避免貼裝頭在喂料槽上來回移動，使得該循環(huán)的拾取總路徑最小，因此解序列中同一循環(huán)內(nèi)的兩個元器件交換意義不大．由此可知，對于取貼循環(huán)總數(shù)N和循環(huán)內(nèi)貼裝元器件總數(shù)H，有效的交換鄰域大小為

2．4 禁忌表

文中提出的TS算法采用雙禁忌表TL1和TL2，禁忌表TL1記錄交換移動，禁忌表TL2記錄歷史解．

2．4．1 禁忌表 TL1

在TS算法中，為避免迂回搜索，一旦一個移動被接受，它的反移動就會被記錄到表中，在此后固定迭代步長內(nèi)該反移動會被禁忌．對于交換鄰域結(jié)構(gòu)，禁忌表TL1中的禁忌對象為交換的兩個點，而禁忌表長度根據(jù)問題的規(guī)模而定．

2．4．2 禁忌表 TL2

雖然禁忌表TL1在一定程度上可避免迂回搜索，但對于統(tǒng)治性較強的局部最優(yōu)解，算法可能會在若干次迭代后再次陷入該解，所以TL1不能保證完全杜絕迂回搜索現(xiàn)象．若盲目地增大禁忌表的長度，不僅會削弱禁忌表的作用，而且會導(dǎo)致TS算法的性能因禁忌太多而變差．

由序優(yōu)化理論［11］可知，在解空間中均勻抽取v個不同的解，設(shè)好解在所有解中占的比率為u，則v個解存在好解的概率為1－(1－u)v．這說明若能保證搜索到足夠多的不同的解，那么能搜索到足夠好解的概率接近1．

基于該思想，文中設(shè)計禁忌表TL2來禁忌迭代搜索過程中出現(xiàn)過的歷史局部最優(yōu)解，使得當(dāng)前解盡量不陷入被禁忌的局部最優(yōu)解，以避免重復(fù)搜索．

禁忌表TL2包括禁忌的解序列S和對應(yīng)的目標(biāo)函數(shù)值f(S)，TL2的規(guī)模會隨著搜索的進行而增大．在判斷某個解是否被TL2禁忌時，考慮到直接將解序列與TL2中所有存放的解相比較計算復(fù)雜，為了提高算法的效率，首先對解的目標(biāo)值進行判斷．若目標(biāo)值未被禁忌，則解序列一定不同;若目標(biāo)值相同，再完整比較解序列是否一致．經(jīng)判斷后，若解被TL2禁忌，則將其舍棄，在余下鄰域中繼續(xù)搜索．

2．5 RLS

文中引入一種基于插入鄰域的RLS搜索策略，當(dāng)?shù)阉飨萑刖植孔顑?yōu)時，以一定概率P對解實行變換，使得搜索盡量逃離局部最優(yōu)．RLS是一種重復(fù)插入的局部搜索方法［12］，對解為序列或集合的優(yōu)化問題較為有效．由于單個元器件的插入移動會改變一系列取貼循環(huán)的組成，對解的整體結(jié)構(gòu)造成較大的改變．因此文中將解分成N部分，每部分是一個取貼循環(huán)的拾取序列．RLS直接對每個取貼循環(huán)進行重復(fù)插入，而不是對每個元器件實施變換，如圖6所示．

圖6 基于取貼循環(huán)插入的RLSFig．6 RLS based on inserting mounting circles

設(shè)當(dāng)前解序列 Sc=(S1，S2，…，SN)，對應(yīng)目標(biāo)函數(shù)值為fc，對Sc應(yīng)用RLS搜索策略進行以取貼循環(huán)為單位的變換，步驟如下:

1)對當(dāng)前解進行擾動

(1)隨機選擇r個取貼循環(huán)，并按照取貼循環(huán)在解序列中的位置進行升序排序，得到(J1，J2，…，Jr)，對應(yīng)在序列中的位置為(p［1］，p［2］，…，p［r］)，令 h:=1．

(2)從當(dāng)前序列中取出Jh并插入到p［h］所在位置之前的所有位置，得到p［h］個新序列，選取具有最小目標(biāo)函數(shù)值fnew的新解Snew．

(3)若 fnew＜ fc，則 fc:=fnew，Sc:=Snew．h:=h+1．若h≤r，則返回步驟(1);否則輸出擾動后的解Sc．

2)基于參考解的搜索

(1)隨機生成拾取序列并作為參考序列R，令h:=1，k:=1．

(2)h:=h%N(%為取余運算)，將 R［h］從序列 Sc中移出，分別插入到位置 0，1，…，h，得到解集對應(yīng)的序列為Snew．

(3)若 fnew＜fc，則更新 fc:=fnew，Sc:=Snew，k:=1;否則 k:=k+1．

(4)h:=h+1，若 k≤N，則返回步驟(2);否則基于參考解的搜索結(jié)束，輸出Sc．

通過插入移動，RLS將參考解的特性融入到當(dāng)前解中．參考解的分散性強時，有助于提高算法的分散搜索能力．拾取序列對應(yīng)的貼裝序列則在計算目標(biāo)值時，通過全枚舉小規(guī)模TSP問題的解獲得．

2．6 算法步驟

基于RLS的改進TS算法步驟如下:

1)運用2．2節(jié)中所描述的方法產(chǎn)生初始解，并設(shè)為當(dāng)前解Sc和當(dāng)前最好解Sbest，對應(yīng)目標(biāo)函數(shù)值為fc和fbest．設(shè)置最大迭代步數(shù)itermax、最大未改進迭代步數(shù) Un_itermax、禁忌表TL1的長度L、進行 RLS變換的概率P，循環(huán)次數(shù)iter=0，未改進迭代次數(shù)Un_iter=0．

2)搜索當(dāng)前解的交換鄰域，記錄最好的鄰解Snei和未被TL1和TL2禁忌的鄰解Sl．

3)判斷藐視準(zhǔn)則是否成立，若f(Snei)＜fbest，則fbest:=f(Snei)，Sbest:=Snei，Sc:=Snei;否則 Sc:=Sl．

4)生成隨機數(shù) r'～［0，1］，若 r'＜ P，則按 2．5節(jié)中的RLS方法對解Sc進行變換．

5)若Sbest在本次迭代中更新，則Un_iter:=0，否則Un_iter:=Un_iter+1．將禁忌表TL1中非0元素減1，并將新禁忌的兩個點的禁忌長度設(shè)定為L，將Sc及其fc寫入禁忌表TL2中，令iter:=iter+1．

6)若Un_iter＞Un_itermax(達到最大未改進最好解的迭代次數(shù))或 iter＞itermax(達到最大迭代次數(shù))，則算法終止，輸出結(jié)果Sbest和f(Sbest);否則轉(zhuǎn)步驟2)．

3 實驗及算法性能分析

文中算法使用VC++6．0軟件編程，并在內(nèi)存為4096MB的FUJITSU計算機上運行．測試實例是20塊PCB的實際貼裝數(shù)據(jù)，對每個數(shù)據(jù)均測試10次取結(jié)果的平均值．實驗對象為四貼裝頭的拱架式貼片機，貼裝頭間距為16mm，兩側(cè)分別有50個槽位，喂料器分配給定，禁忌表TL1長度L=12，最大迭代步數(shù)itermax=200，最大未改進迭代步數(shù)Un_itermax=20，RLS變換的概率P=0．2．為驗證文中算法的有效性，將算法計算結(jié)果與使用蟻群 －混合蛙跳算法［6］、參數(shù)相同情況下不帶RLS搜索策略的改進TS算法的結(jié)果進行了比較，如表1所示，算例運行時間見表2．

表1表明，使用文中算法求解貼裝順序優(yōu)化問題得到的結(jié)果優(yōu)于蟻群－混合蛙跳算法［6］的求解結(jié)果，20塊PCB的解平均值提高了16．17%．文獻［6］算法將元器件的貼裝順序作為解序列，而元器件的拾取順序取與貼裝順序相同的序列，該處理方法可能導(dǎo)致取貼循環(huán)內(nèi)貼裝頭在喂料槽上來回移動的次數(shù)增加，從而使總路徑增加．文中算法對這兩個序列同時優(yōu)化，求解方法更為有效．根據(jù)表1，對于元器件數(shù)量超過100的后12組數(shù)據(jù)，RLS搜索策略能帶來平均1．14%的改進，證明了文中算法的性能更優(yōu)，在解決規(guī)模較大的問題上效果更突出．

表1 幾種算法的實驗結(jié)果比較Table 1 Comparison of the experimental results obtained by several algorithms

根據(jù)表2，盡管文中算法的運行時間會隨著問題規(guī)模的增大而增加，但當(dāng)元器件數(shù)量為378時求取一個解所用的時間約為43．043 s，因此算法的計算時間在實際應(yīng)用中是可以接受的．

表2 每個實例的運行時間Table 2 Running time for each instance

4 結(jié)語

文中針對拱架式貼片機貼裝順序優(yōu)化問題，建立了數(shù)學(xué)規(guī)劃模型，提出了一種基于RLS的改進TS算法．在該算法中，應(yīng)用了最近鄰算法生成初始解，采用了交換鄰域結(jié)構(gòu)，設(shè)計了雙禁忌表來避免迂回搜索，并引入以取貼循環(huán)為單位的RLS變換策略來提高算法突破局部最優(yōu)的能力．通過對實際生產(chǎn)的20塊PCB數(shù)據(jù)進行仿真計算，并將結(jié)果與文獻計算結(jié)果作比較，結(jié)果表明文中提出的改進TS算法能更有效地解決貼片機貼裝順序優(yōu)化問題．

［1］ Michael O B，Michael J M．Sequencing of insertions in printed circuit board assembly ［J］．Operations Research in Manufacturing，1988，36(2):192－201．

［2］ Leip?l?T，Nevalainen O．Optimization of the movements of a component placement machine［J］．European Journal of Operational Research，1989，38(2):167－177．

［3］ 曾又姣，金燁．基于遺傳算法的貼片機貼裝順序優(yōu)化［J］．計算機集成制造系統(tǒng)，2004，10(2):205－208．Zeng You－jiao，Jin Ye．Component placement sequence optimization for surface mounting machine based on genetic algorithm ［J］．Computer Integrated Manufacturing Systems，2004，10(2):205－208．

［4］ 杜軒，李宗斌，高新勤，等．基于遺傳算法的轉(zhuǎn)塔式貼片機貼裝過程優(yōu)化［J］．西安交通大學(xué)學(xué)報，2008，42(3):295－299．Du Xuan，Li Zong－bin，Gao Xin－qin，et al．Component placement process optimization for chip shooter machine based on genetic algorithm［J］．Journal of Xi’an Jiaotong University，2008，42(3):295－299．

［5］ 朱光宇，林蔚清．基于改進混合蛙跳算法的貼片機貼裝順序優(yōu)化 ［J］．中國工程機械報，2008，6(4):428－432．Zhu Guang－yu，Lin Wei－qing．Mounting sequential optimization on surface mounting machine using improved hybrid frog－jumping algorithm ［J］．Chinese Journal of Construction Machinery，2008，6(4):428－432．

［6］ 陳鐵梅，羅家祥，胡躍明．基于蟻群－混合蛙跳算法的貼片機貼裝順序優(yōu)化［J］．控制理論與應(yīng)用，2011，28(12):1813－1820．Chen Tie－mei，Luo Jia－xiang，Hu Yue－ming．Mounting sequence optimization on surface mounting machine using ant－colony algorithm and shuffled frog－leaping algorithm［J］．Journal of Control Theory ＆ Applications，2011，28(12):1813－1820．

［7］ 袁鵬，劉海明，胡躍明．基于傘布搜索法的貼片機貼裝順序優(yōu)化算法［J］．電子工藝技術(shù)，2007，28(6):316－320．Yuan Peng，Liu Hai－ming，Hu Yue－ming．Scatter searching algorithm for multi－h(huán)eaded surface mounter ［J］．Electronics Process Technology，2007，28(6):316－320．

［8］ 俞國燕，鄭時雄，劉桂雄，等．復(fù)雜工程問題全局優(yōu)化算法研究［J］．華南理工大學(xué)學(xué)報:自然科學(xué)版，2000，28(8):104－110．Yu Guo－yan，Zheng Shi－xiong，Liu Gui－xiong，et al．Study on global optimization algorithms for complex engineering problem ［J］．Journal of South China University of Technology:Natural Science Edition，2000，28(8):104－110．

［9］ Glover F．Future paths for integer programming and links to artificial intelligence［J］．Computers and Operations Research，1986，13(5):533－549．

［10］ Glover F，Gutin G，Yeo A，et al．Construction heuristics for the asymmetric TSP ［J］．European Journal of Operational Research，2001，129(3):555－568．

［11］ Edward Lau T W，Ho Y C．Universal alignment probabilities and subset selection for ordinal optimization ［J］．Journal of Optimization Theory and Applications，1997，93(3):455－489．

［12］ Tasgetiren F，Pan Q K，Liang Y C．A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times［J］．Computers and Operations Research，2009，36(6):1900－1915．