PCBA柔性作業車間等量分批調度問題研究

黃夏寶，楊立熙，傅光炎

（1.福建江夏學院 工商管理學院，福州 350108；2.福州大學 經濟與管理學院，福州 350108）

0 引言

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

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

PCBA車間的主板加工主要包含SMT、自動插件（Automatic Insertion，AI）、手工插件（Manual Insertion，MI）三道流程，現階段大部分文獻集中于SMT子車間生產調度的研究，而對PCBA全局的研究較少。在實際排程過程中，三個子車間的排程相互獨立，排程人員僅負責各自車間的排程任務，且采用手工Excel排程的方法，缺乏協調性與高效性；排程人員僅對超大訂單進行分批，未考慮其它批量生產類型的分批。因此，設計自動排程的程序對PCBA車間全局生產在多種批量生產類型下分批調度的研究很有必要。文獻中不少分批策略需要不斷嘗試不同批量劃分的解，搜索效率低，多用于解決較小批量的生產調度，而本文為解決PCBA車間存在的不少中、大批量的問題，采用等量分批調度策略。

本文面向PCBA車間生產全流程，構建了柔性作業車間等量分批調度模型。針對遺傳算法（Genetic Algorithm，GA）存在的過早收斂、容易陷入局部最優的缺點，設計了改進的遺傳模擬退火算法（Genetic Simulated Annealing Algorithms，GASA）來求解該問題。

1 PCBA柔性作業車間分批調度模型

1.1 問題描述

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

1.2 模型的建立

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

針對分批調度問題，約束如下：

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

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

2 分批調度混合算法

本文將整個求解過程分為訂單批量分批、子批排程兩個階段，如圖1所示。其中批量分批包括批量生產類型劃分和等量分批兩個子問題，子批排程又包括子批排序和生產線選擇兩個子問題。

圖1 訂單分批排程流程圖

2.1 批量分批

批量的劃分標準并非以量作為唯一衡量標準，而是需要與產品的價值量、加工難度等因素綜合考慮。依據技術經濟原則，確立了一種批量劃分的經驗方法，該種劃分方法與切換時間密切相關[15]。需要給定一個生產線的損失系數閾值，引用文獻[15]中式(8)與表1閾值系數。

式中：δ為生產線損失系數閾值；tαd為某訂單總切換時間；t某訂單單個產品總的加工時間；Qmin批量數量界限。

PCBA加工的四道工序總切換時間tαd=7200s。根據PCBA車間各生產線加工時間，求得單件產品總加權時間t=145s，再依據中件的劃分確定各生產類型的批量范圍。

表1 閾值系數與生產類型批量范圍表

通常，批量的大小與生產周期呈現“U”型的關系，批量過大或過小都會影響生產的效率。等量分批過程中可能遇到無法均勻分配的問題，此時需對算法進行優化，如某一大批量訂單批量為1550，若分3批，（批量/分批數）后的值取整作為前2批批量，余下作為第3個子批批量，結果為[516，516，518]。

2.2 子批排程算法

2.2.1 GASA算法流程

本文采用GASA算法來解決子批排程問題，具體流程如圖2所示。

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

2.2.2 編碼與解碼

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

1）子批工序排序部分

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

2）生產線選擇部分

前部分工序排序的染色體和后部分生產線選擇的染色體是一一對應的。生產線編碼上染色體的數字代表對應工序的可選擇加工生產線的序號。這種生產線編碼方式能夠保證后續進行算法的各項操作依舊能獲得可行解。

圖3 分段編碼

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

2.2.3 交叉與變異操作

本文采用洗牌交叉與單點交叉結合的方式對工序排序部分進行交叉。洗牌交叉：隨機打亂種群中各個個體的排序，以避免每次迭代后，依舊選擇相同次序的兩個父代個體進行交叉操作；單點交叉：在基因串長度的范圍內產生一個隨機變異位置點Pos，交換兩父代染色體的前1～Pos位基因，用父代染色體多余基因修補子代缺失基因，將兩個個體基因串的后位的生產線選擇部分也做相同的交叉操作，保持原有工序排序的各個基因對應的生產線選擇不變。

變異操作主要針對生產線選擇部分，通過隨機選擇變異位置，在需要變異的位置上以更高的概率選擇加工時間最少的生產線，從而達到局部優化的目的。

2.2.4 模擬退火操作

本文將模擬退火算法的Metropolis準則與遺傳算法串聯使用，擴展到遺傳算法的交叉、變異操作后的新個體接受準則中，先采用SWAP操作產生新個體，若新個體結果優于原有個體，則接受新個體；若新個體結果劣于原有個體，則以一定概率接受新個體。在這里引入了初始溫度t0以及狀態接受函數k，式(11)為退溫函數。

式中FitnV（i）為種群中個體i的適應度值，df為原個體與新個體的適應度值差值，pr為初始接受概率，λ為溫度衰減系數，通過多次實驗驗證，本文pr取0.8，λ取0.95。

3 實例分析

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

實例分析有兩個目的：一是比較本文提出的算法與遺傳算法在求解實際調度問題方面的表現；二是研究不同生產類型下批量與分批數之間的關系。算法采用MATLAB編程實現。

表2 各訂單的批量及其加工點數

3.1 GA與GASA算法比較

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

表3 PCBA車間各生產線加工時間 單位：s

表4 GA與GASA在不同分批數中的運算結果（單位：s）

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

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

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

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

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

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

3.2 批量與分批次數關系分析

以實例中的10個訂單種類為前提，依據隨機均勻分布的方式生成各生產類型中批量范圍內（如表1所示）的訂單批量，采用GASA算法來求解，依次將四種生產類型的批量數據輸入程序中，每種類型在不同分批情況下各運算10次，各生產類型不同分批數的運行結果與對應分批策略如表6所示。

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

4 結語

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

表6 各生產類型不同分批數的運算結果與分批策略