黃夏寶，楊立熙，傅光炎

（1.福建江夏學(xué)院 工商管理學(xué)院，福州 350108；2.福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院，福州 350108）

0 引言

近年來(lái)，電子產(chǎn)品不斷朝著多元化、定制化方向演進(jìn)，印刷電路板組裝（Print Circuit Board Assembly，PCBA）的多品種、變批量生產(chǎn)模式成為主流，因此在快速性和靈活性方面對(duì)電子制造企業(yè)提出了更高的要求，PCBA車(chē)間的生產(chǎn)調(diào)度優(yōu)化成為亟需解決的問(wèn)題[1,2]。

PCBA車(chē)間調(diào)度問(wèn)題主要集中在表面貼裝技術(shù)（Surface Mounted Technology，SMT）子車(chē)間的調(diào)度研究，包括SMT車(chē)間中多品種PCB貼裝生產(chǎn)排程優(yōu)化[3]、生產(chǎn)線的負(fù)荷均衡化問(wèn)題[4]、產(chǎn)線分配和組間排序問(wèn)題[5]、多條生產(chǎn)線的調(diào)度問(wèn)題[6,7]。PCBA車(chē)間生產(chǎn)調(diào)度問(wèn)題是一個(gè)集批量規(guī)劃和生產(chǎn)排程的綜合性問(wèn)題[8]。在多品種、小批量的PCBA分批調(diào)度問(wèn)題中，有通過(guò)反應(yīng)式禁忌搜索算法確定PCB組內(nèi)和組間的序列[9]；隨機(jī)的方式生成子批大小與個(gè)數(shù)[10]；訂單批次與批量可變的柔性分批調(diào)度方法[11,12]；分批具有方向性的試探法[13]；將訂單中每個(gè)工件都作為一個(gè)批次的訂單批量的大小與排序動(dòng)態(tài)結(jié)合的方法[14]。

PCBA車(chē)間的主板加工主要包含SMT、自動(dòng)插件（Automatic Insertion，AI）、手工插件（Manual Insertion，MI）三道流程，現(xiàn)階段大部分文獻(xiàn)集中于SMT子車(chē)間生產(chǎn)調(diào)度的研究，而對(duì)PCBA全局的研究較少。在實(shí)際排程過(guò)程中，三個(gè)子車(chē)間的排程相互獨(dú)立，排程人員僅負(fù)責(zé)各自車(chē)間的排程任務(wù)，且采用手工Excel排程的方法，缺乏協(xié)調(diào)性與高效性；排程人員僅對(duì)超大訂單進(jìn)行分批，未考慮其它批量生產(chǎn)類(lèi)型的分批。因此，設(shè)計(jì)自動(dòng)排程的程序?qū)CBA車(chē)間全局生產(chǎn)在多種批量生產(chǎn)類(lèi)型下分批調(diào)度的研究很有必要。文獻(xiàn)中不少分批策略需要不斷嘗試不同批量劃分的解，搜索效率低，多用于解決較小批量的生產(chǎn)調(diào)度，而本文為解決PCBA車(chē)間存在的不少中、大批量的問(wèn)題，采用等量分批調(diào)度策略。

本文面向PCBA車(chē)間生產(chǎn)全流程，構(gòu)建了柔性作業(yè)車(chē)間等量分批調(diào)度模型。針對(duì)遺傳算法（Genetic Algorithm，GA）存在的過(guò)早收斂、容易陷入局部最優(yōu)的缺點(diǎn)，設(shè)計(jì)了改進(jìn)的遺傳模擬退火算法（Genetic Simulated Annealing Algorithms，GASA）來(lái)求解該問(wèn)題。

1 PCBA柔性作業(yè)車(chē)間分批調(diào)度模型

1.1 問(wèn)題描述

PCBA車(chē)間中每道流程都有多條可選擇的生產(chǎn)線，且加工效率各不相同。排程任務(wù)有多個(gè)訂單，受產(chǎn)能約束的影響，完工時(shí)間越短越好。在加工的過(guò)程需要考慮加工順序與設(shè)備資源等約束，本文假設(shè)：1）同一時(shí)刻，每條生產(chǎn)線上最多有一個(gè)訂單批次被加工；2）同一時(shí)刻，每個(gè)訂單批次的同道工序只允許在同一條生產(chǎn)線上加工；3）每個(gè)訂單的批次加工過(guò)程不允許間斷；4）訂單在生產(chǎn)線間的運(yùn)輸時(shí)間記為零；5）每個(gè)訂單批次都可在t=0時(shí)被加工。

1.2 模型的建立

PCBA柔性作業(yè)車(chē)間分批調(diào)度模型可描述為：PCBA車(chē)間有I個(gè)訂單，每個(gè)訂單有Qi個(gè)相同的產(chǎn)品、hi道工序，分批數(shù)為N。每個(gè)子批在k條可選擇的生產(chǎn)線上加工，同一工序在不同生產(chǎn)線上的加工時(shí)間各不相同。Oijr為訂單i第j批次的第r道工序；Mijr為工序Oijr的可選擇生產(chǎn)線數(shù)；Pijrk為工序Oijr在生產(chǎn)線k上的加工時(shí)間；Sijr、Cijr分別為工序Oijr的開(kāi)始、完成時(shí)間；T為切換時(shí)間。本文以最小化最大完工時(shí)間為模型的目標(biāo)函數(shù)：

針對(duì)分批調(diào)度問(wèn)題，約束如下：

其中：訂單序號(hào)i，u=1，2，…，I，批次序號(hào)j，v=1，2，…，N，r=1，2，…，hi，w=1，2，…，hh，k=1，2，…，M；

上述公式中，xkijr、ykijruvw、zkijruvw為決策變量，式(2)、式(3)表示同一訂單批次的工序間加工順序約束；式(4)表示加工為非搶占式；式(5)表示每個(gè)訂單同一批次的完工時(shí)間約束；式(6)、式(7)表示同一時(shí)刻同一生產(chǎn)線只能加工一道工序。

2 分批調(diào)度混合算法

本文將整個(gè)求解過(guò)程分為訂單批量分批、子批排程兩個(gè)階段，如圖1所示。其中批量分批包括批量生產(chǎn)類(lèi)型劃分和等量分批兩個(gè)子問(wèn)題，子批排程又包括子批排序和生產(chǎn)線選擇兩個(gè)子問(wèn)題。

圖1 訂單分批排程流程圖

2.1 批量分批

批量的劃分標(biāo)準(zhǔn)并非以量作為唯一衡量標(biāo)準(zhǔn)，而是需要與產(chǎn)品的價(jià)值量、加工難度等因素綜合考慮。依據(jù)技術(shù)經(jīng)濟(jì)原則，確立了一種批量劃分的經(jīng)驗(yàn)方法，該種劃分方法與切換時(shí)間密切相關(guān)[15]。需要給定一個(gè)生產(chǎn)線的損失系數(shù)閾值，引用文獻(xiàn)[15]中式(8)與表1閾值系數(shù)。

式中：δ為生產(chǎn)線損失系數(shù)閾值；tαd為某訂單總切換時(shí)間；t某訂單單個(gè)產(chǎn)品總的加工時(shí)間；Qmin批量數(shù)量界限。

PCBA加工的四道工序總切換時(shí)間tαd=7200s。根據(jù)PCBA車(chē)間各生產(chǎn)線加工時(shí)間，求得單件產(chǎn)品總加權(quán)時(shí)間t=145s，再依據(jù)中件的劃分確定各生產(chǎn)類(lèi)型的批量范圍。

表1 閾值系數(shù)與生產(chǎn)類(lèi)型批量范圍表

通常，批量的大小與生產(chǎn)周期呈現(xiàn)“U”型的關(guān)系，批量過(guò)大或過(guò)小都會(huì)影響生產(chǎn)的效率。等量分批過(guò)程中可能遇到無(wú)法均勻分配的問(wèn)題，此時(shí)需對(duì)算法進(jìn)行優(yōu)化，如某一大批量訂單批量為1550，若分3批，（批量/分批數(shù)）后的值取整作為前2批批量，余下作為第3個(gè)子批批量，結(jié)果為[516，516，518]。

2.2 子批排程算法

2.2.1 GASA算法流程

本文采用GASA算法來(lái)解決子批排程問(wèn)題，具體流程如圖2所示。

圖2 遺傳-模擬退火算法流程圖

2.2.2 編碼與解碼

分段編碼有易于操作和表達(dá)的特性，因此本文運(yùn)用分段編碼與OSMS的整數(shù)編碼[16]相結(jié)合的方式，將編碼分為工序排序和生產(chǎn)線選擇兩部分，如圖3所示。

1）子批工序排序部分

基因位表示訂單號(hào)&批次號(hào)組合。訂單&批次號(hào)出現(xiàn)的次序表示該訂單批次的工序間的加工先后次序，第h次出現(xiàn)的訂單&批次號(hào)表示該訂單批次的第h道工序，如工序O121表示訂單1的第2批次的第1道工序。由于即使在訂單批次工序數(shù)不確定、調(diào)度模式變化的情況下該種編碼方式依然適用，表現(xiàn)出較高的柔性而被廣泛使用。

2）生產(chǎn)線選擇部分

前部分工序排序的染色體和后部分生產(chǎn)線選擇的染色體是一一對(duì)應(yīng)的。生產(chǎn)線編碼上染色體的數(shù)字代表對(duì)應(yīng)工序的可選擇加工生產(chǎn)線的序號(hào)。這種生產(chǎn)線編碼方式能夠保證后續(xù)進(jìn)行算法的各項(xiàng)操作依舊能獲得可行解。

圖3 分段編碼

解碼也需要分別對(duì)工序排序部分和生產(chǎn)線選擇兩個(gè)部分進(jìn)行操作，算法如下：染色體上從左到右依次讀取工序排序部分中的基因值，將每個(gè)值轉(zhuǎn)化為對(duì)應(yīng)的各道工序Oijr；相應(yīng)的，可以算出Oijr在生產(chǎn)線Mk上的加工時(shí)間Pijrk；假設(shè)生產(chǎn)線Mk上兩個(gè)相鄰訂單批次工序Ouvw、Oijr，若其訂單號(hào)（u，i）、工序號(hào)（w，r）相同，批次不同，則不需要換批時(shí)間；否則需要添加換批時(shí)間T。

2.2.3 交叉與變異操作

本文采用洗牌交叉與單點(diǎn)交叉結(jié)合的方式對(duì)工序排序部分進(jìn)行交叉。洗牌交叉：隨機(jī)打亂種群中各個(gè)個(gè)體的排序，以避免每次迭代后，依舊選擇相同次序的兩個(gè)父代個(gè)體進(jìn)行交叉操作；單點(diǎn)交叉：在基因串長(zhǎng)度的范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)變異位置點(diǎn)Pos，交換兩父代染色體的前1～Pos位基因，用父代染色體多余基因修補(bǔ)子代缺失基因，將兩個(gè)個(gè)體基因串的后位的生產(chǎn)線選擇部分也做相同的交叉操作，保持原有工序排序的各個(gè)基因?qū)?yīng)的生產(chǎn)線選擇不變。

變異操作主要針對(duì)生產(chǎn)線選擇部分，通過(guò)隨機(jī)選擇變異位置，在需要變異的位置上以更高的概率選擇加工時(shí)間最少的生產(chǎn)線，從而達(dá)到局部?jī)?yōu)化的目的。

2.2.4 模擬退火操作

本文將模擬退火算法的Metropolis準(zhǔn)則與遺傳算法串聯(lián)使用，擴(kuò)展到遺傳算法的交叉、變異操作后的新個(gè)體接受準(zhǔn)則中，先采用SWAP操作產(chǎn)生新個(gè)體，若新個(gè)體結(jié)果優(yōu)于原有個(gè)體，則接受新個(gè)體；若新個(gè)體結(jié)果劣于原有個(gè)體，則以一定概率接受新個(gè)體。在這里引入了初始溫度t0以及狀態(tài)接受函數(shù)k，式(11)為退溫函數(shù)。

式中FitnV（i）為種群中個(gè)體i的適應(yīng)度值，df為原個(gè)體與新個(gè)體的適應(yīng)度值差值，pr為初始接受概率，λ為溫度衰減系數(shù)，通過(guò)多次實(shí)驗(yàn)驗(yàn)證，本文pr取0.8，λ取0.95。

3 實(shí)例分析

某PCBA車(chē)間由SMT車(chē)間、AI車(chē)間和MI車(chē)間構(gòu)成，共有生產(chǎn)線9條，其中SMT車(chē)間4條、AI車(chē)間3條、MI車(chē)間2條，每個(gè)子車(chē)間內(nèi)的生產(chǎn)線都具有相同的功能，但由于生產(chǎn)線設(shè)備組成型號(hào)與新舊程度不一，加工效率也有所不同。某一周的預(yù)先排程如表2所示，共有10個(gè)訂單需要在PCBA車(chē)間加工，加工流程為：SMT B面加工→SMT T面加工→AI加工→MI加工，子批之間的換批時(shí)間為30min。PCBA車(chē)間各生產(chǎn)線加工時(shí)間如表3所示。

實(shí)例分析有兩個(gè)目的：一是比較本文提出的算法與遺傳算法在求解實(shí)際調(diào)度問(wèn)題方面的表現(xiàn)；二是研究不同生產(chǎn)類(lèi)型下批量與分批數(shù)之間的關(guān)系。算法采用MATLAB編程實(shí)現(xiàn)。

表2 各訂單的批量及其加工點(diǎn)數(shù)

3.1 GA與GASA算法比較

算法參數(shù)的設(shè)置對(duì)求解影響很大，通過(guò)實(shí)驗(yàn)仿真驗(yàn)證得出種群大小、交叉概率、變異概率的最優(yōu)取值分別為200、0.8、0.02。分別使用GA與GASA算法對(duì)不同分批數(shù)的訂單各運(yùn)行10次，結(jié)果如表5所示。f值為目標(biāo)函數(shù)的解，即為最大完工時(shí)間值；Min（f）、Avg（f）分別表示運(yùn)行10次的結(jié)果中的最優(yōu)值、平均值；t為算法的運(yùn)行時(shí)間。

表3 PCBA車(chē)間各生產(chǎn)線加工時(shí)間 單位：s

表4 GA與GASA在不同分批數(shù)中的運(yùn)算結(jié)果（單位：s）

從表4可看出在不同分批數(shù)的情況下，GASA算法所得到的最優(yōu)值以及平均值結(jié)果均要優(yōu)于GA算法。GASA算法與GA算法相對(duì)比，Avg（f）在四種分批情況中分別減少總完工時(shí)間153min、129min、147min、71min。當(dāng)分批數(shù)為2時(shí)，兩種算法分別獲得2910min、2787min的最優(yōu)值，均優(yōu)于同算法中其余分批數(shù)的結(jié)果。在GASA算法中的Min（f）值中，分2批比不分批減少總完工時(shí)間95min。

圖4 GA算法在分2批情況下的搜索過(guò)程

圖5 GASA算法在分2批情況下的搜索過(guò)程

圖6 GASA算法在分2批情況下Min（f）的調(diào)度甘特圖

圖7 GASA算法在不分批情況下Min（f）的調(diào)度甘特圖

對(duì)比圖4與圖5，雖然GA算法全局搜索能力強(qiáng)，但是容易使算法的搜索過(guò)程過(guò)早地收斂，獲得的最優(yōu)值不佳；在GA算法中加入SA算法，有利于提高算法的局部搜索能力，避免算法的搜索過(guò)程過(guò)早地收斂。圖6與圖7中的黑色塊為切換時(shí)間段，通過(guò)對(duì)比分析，訂單分2批的完工時(shí)間要低于不分批的情況。

3.2 批量與分批次數(shù)關(guān)系分析

以實(shí)例中的10個(gè)訂單種類(lèi)為前提，依據(jù)隨機(jī)均勻分布的方式生成各生產(chǎn)類(lèi)型中批量范圍內(nèi)（如表1所示）的訂單批量，采用GASA算法來(lái)求解，依次將四種生產(chǎn)類(lèi)型的批量數(shù)據(jù)輸入程序中，每種類(lèi)型在不同分批情況下各運(yùn)算10次，各生產(chǎn)類(lèi)型不同分批數(shù)的運(yùn)行結(jié)果與對(duì)應(yīng)分批策略如表6所示。

從表6可以得出，同種生產(chǎn)類(lèi)型，Min(f)與Avg(f)值的變化趨勢(shì)具有一致性；從不同生產(chǎn)類(lèi)型的變化趨勢(shì)看，隨著批量的增加，分批次數(shù)也隨之增加。

4 結(jié)語(yǔ)

相對(duì)于傳統(tǒng)柔性作業(yè)車(chē)間調(diào)度，各種批量生產(chǎn)類(lèi)型下的柔性作業(yè)車(chē)間分批調(diào)度更加符合生產(chǎn)實(shí)際，對(duì)于現(xiàn)實(shí)的車(chē)間調(diào)度也更有指導(dǎo)意義。本文針對(duì)PCBA車(chē)間這一柔性作業(yè)車(chē)間分批調(diào)度問(wèn)題，以最大完工時(shí)間最小為目標(biāo)，將整個(gè)求解過(guò)程分為訂單批量分批、子批排程兩個(gè)階段。通過(guò)改進(jìn)算法的編碼以便更好地體現(xiàn)分批調(diào)度問(wèn)題，在交叉操作上采用洗牌與單點(diǎn)交叉的方式以保證獲得多樣化的種群個(gè)體，在變異操作上采用生產(chǎn)線效率偏好選擇的方式以獲得較低的工序加工時(shí)間，在模擬退火算法方面，引入了Metropolis接受準(zhǔn)則，有效避免算法陷入早熟。通過(guò)實(shí)例中的算例測(cè)試與不同算法的對(duì)比分析，驗(yàn)證了GASA算法與批量分批策略的有效性。最后，確定了各批量生產(chǎn)類(lèi)型下的最優(yōu)分批次數(shù)，對(duì)企業(yè)各訂單批量調(diào)度的分批數(shù)選擇具有指導(dǎo)意義。但是，本文僅考慮了靜態(tài)調(diào)度問(wèn)題，對(duì)于動(dòng)態(tài)調(diào)度未做進(jìn)一步的研究，后續(xù)需要考慮更多的影響因素以保證模型更為完善。

表6 各生產(chǎn)類(lèi)型不同分批數(shù)的運(yùn)算結(jié)果與分批策略