基于混合離散粒子群算法的非等同并行機分批調度研究

徐兵，潘沐，趙傳宇，姜再龍

（1.長春工業大學機電工程學院，長春 130012；2.緯湃汽車電子（長春）有限公司，長春 130000）

0 引言

非等同并行機問題是典型的離散柔性車間問題之一，不同設備加工同種工件的生產節拍不同，如何將待加工工件進行合理分批，將各工件子批按照一定的加工順序安排到各設備上進行加工是有待解決的問題。在多品種小批量生產方式研究中表明，并行機批調度方式能夠在降低設備等待時間、提高設備利用率、減少庫存成本、縮短生產周期方面有顯著效果[1-3]。徐修立[4]提出考慮零件需求約束與加工工藝可選的混合遺傳模擬退火算法。吳繼浩[5]提出針對柔性車間的改進灰狼算法。?？×諿6]提出基于工件動態到達的最小化最大拖期時間的單機調度問題。曾強針[7]對多目標等量分批調度問題，提出了一種集成優化方法。史青濤[8]提出了單工序并行機等量分批數學模型。張震[9]提出了基于模具約束的并行機分批方式。

在多品種小批量的生產模式下，緯湃汽車電子有限公司的SMT貼片線因生產不同工件所需調整時間不同，不同生產排序會使優化目標有較大差異。因此，文章根據SMT貼片線的周生產計劃，研究分批優化排序問題。

1 非等同并行機分批調度模型

1.1 問題描述

本文研究問題描述如下：待加工工件種類為N，各類工件的數量為Gi，共有M臺設備可供選擇進行加工，所有工件均可在任意一臺設備上進行加工，不同種工件在不同設備上的加工時間不盡相同，在只考慮調整成本并保證每種工件的子批個數不超過模具數量的前提下，確定各訂單的拆分方案及各機器所需加工子批作業，從而使生產總成本最低，生產成本包括加工成本與完工時間。

1.2 符號定義

非等同并行機等量分批調度的前提條件為：1）所有機器與任務在0時刻均處于可加工狀態；2）各工件均按子批方案等量分批，當不可完全等分時，保證不同子批間數量差最大值為1；3）一個訂單可拆分的子批數量不大于模具數；4）加工過程中作業不可中斷，一臺機器同一時間內只能加工一個子批。

根據以上假設條件，定義如下參數：N為待加工工件的種數；Di為工件i的待加工數量；M為設備總數；a為設備k上的子批編號；k為第k臺機器（k=1,2,3,…,M）；Ji為第i種工件（i=1,2,3,…,N）；X為工件總數；Xi,j為工件i的第j個子批大小；B為所有工件加工子批個數；Bi為第i種工件的子批個數；Ji,j為第i種工件的第j個子批；Ti,k為工件i在設備k上的加工時間Ji,k為在設備k上加工的工件；Ck為設備k的調整次數；Pk為設備k的調整單次調整成本；Mo為模具總數；Moi為第i種工件模具數；Ti,k為工件i在設備k上的生產節拍；STijk為工件i的第j個子批在設備k上的開始加工的時間；SFijk為工件i的子批j在設備k上的完工時間；STak為子批a在設備k上的開始時間；SFak為子批a在設備k上的完工時間；SFk為設備k上最后一個加工子批的完工時間。

1.3 數學模型

式（1）表示目標函數是由最短完工時間和調整成本組成的優化目標，其中Time表示完工周期，Expense表示制造成本。式（2）表示最小完工時間取各設備總完工時間的最大值。式表（3）表示調整成本為各設備調整次數與設備單次調整成本之積的和。式（4）表示各工件的加工子批個數之和為總的加工子批個數。式（5）表示子批的完工時間為子批的開始時間與該子批在本臺設備上的加工時間之和。式（6）表示不同批次工件在同一機床上加工的約束關系。式（7）表示各個工件等量分批。式（8）～式（11）表示變量取值范圍。

2 混合離散粒子群算法設計

2.1 混合離散粒子群算法流程設計

為求解非等同并行機等量分批調度問題模型，以離散粒子群算法為基礎，混入模擬退火算法，以最小化最大完工時間與調整成本作為目標函數，求解最佳分批方案與各設備所需加工工件編號與子批大小。

主模擬退火算法（FSA）求解待加工工件的分批方案，離散粒子群算法（DPSO）求解待加工工件的加工序列，次模擬退火算法（SSA）求解同一加工順序下，不同分配策略的最優排產計劃。

2.2 零件分批的主模擬退火算法設計

FSA算法采用標準模擬退火算法求解工件分批方案，對每代分批方案通過DPSO算法進行加工順序的改變進行多次適應度值計算，取最優粒子的適應度值作為本代分批方案的適應度值, 適應度函數如式（12）所示，FSA算法流程圖如圖1所示。

圖1 FSA算法流程圖

2.2.1 個體更新方式

FSA算法采用變異方式更新個體，根據工件種類的不同選擇個體位置更新數，隨機產生所需更新位置的變異點，以新生成的分批方案更新變異點的分批方案。個體位置更新選擇表如表1所示。

表1 個體位置更新表

2.2.2 Metropolis準則

為了增強算法的全局搜索能力，避免提前收斂或陷入局部最優解的問題，當本代最優解的次于全局最優解時，使算法以一定概率接受較差解，擴大搜索范圍。

式中：Fc和Fmin分別為本代最優解與全局最優解的適應度值；df為Fc和Fmin的差值；rand為（0,1）之間的隨機數；Tk+1為當前溫度；Tk為更新前溫度；Q是一個常數。

2.3 子批排序的離散粒子群算法設計

采用DPSO算法作為內層算法求解子批排序，在分批方案既定的前提下，初始化粒子群，對各個粒子通過SSA算法進行設備分批，計算適應度值，取SSA算法中最優個體的適應度值作為粒子適應度值，適應度函數如式（15）所示。DPSO算法流程如圖2所示。

圖2 DPSO算法流程圖

針對所研究問題，提出了圖3所示編碼方式。其中，第一行position表示粒子中各元素所處位置；第二行number表示各子批編號；第三行workpiece表示工件種類；第四行quota表示子批容量；第五行sequence表示以ROV規則進行升序排列后粒子中各元素位置，即子批加工序列。

圖3 粒子個體數據結構

2.4 設備分配的次模擬退火算法設計

采用模擬退火算法作為內層算法求解工件各子批在設備上的分配方式，在子批加工序列既定的前提下，進行設備分配，完成加工，以每次分配下各設備的最大完工時間與調整成本作為適應度值，適應度函數如式（16）所示。SSA算法流程如圖4所示。

圖4 SSA算法流程圖

2.4.1 設備分配

不同工件在不同設備上的加工時間不完全相同，所以同一個生產序列會有多種分配方式，為了得到最小完工時間的分配方式，以每次隨機分配加工方案后的完工時間為基準，使完工時間最大的設備加工子批數減1，完工時間最小的設備加工子批數加1，將生產序列重新分配給各設備,設備分配如圖5所示。

圖5 設備分配

2.4.2 保優策略

為了防止最優解的丟失，在SSA算法中，若最優個體被更新，則更新全局最優個體的設備分配方案、適應度值，同時更新當前適應度值下的生產序列與分配方案。

3 實驗仿真及分析

緯湃汽車電子公司SMT貼片線是一個單工序非等同并行機調度問題，其生產種類包括CERGY_VD46、CM2150C、CM2150E等，對8種工件實行等量分批調度，其總量分別為130、210、150、230、240、130、270、180。可供選擇設備共有5臺，各類工件模具數為5個，產品生產節拍如表2所示。

表2 工件在設備上的加工時間

采用混合離散粒子群算法進行生產計劃優化排序，參數設置如下：粒子群規模為20、粒子最大速度為0.5，粒子最小速度為-0.5，離散粒子群進化30代，?1=0.7，?2=0.3[8]。目標值隨進化代數的變化過程如圖6所示。

圖6 SMT貼片線最優解收斂迭代圖

通過10次獨立運行，最優結果算法迭代圖如圖2所示，隨著代數的增加，混合離散粒子群算法在102代后開始收斂，最優目標值為1554。

最優解甘特圖如圖7所示。

圖7 SMT貼片線最優解甘特圖

為了進一步驗證本文中算法的有效性與穩定性，與文獻中遺傳進化差分改進算法與灰狼差分改進算法進行對比，僅以最小化最大完工時間作為優化目標，其他參數不變，待加工工件共有10種，可選擇設備5臺，每種工件的模具數為3。

為了進一步驗證算法的有效性，將文中算法與文獻[10] 中遺傳進化差分算法與灰狼差分進化算法以同一算例進行對比，將最小化最大完工時間作為研究目標，建立非等同并行機調度模型，共有10種待加工工件，每種工件的模具數均為3。

10次獨立運行后，最優解各設備排產計劃及完工時間如表3所示，相比文獻[10]中遺傳差分混合算法最大完工時間減少262 min，比灰狼差分混合算法最大完工時間減少64 min，表明混合離散粒子群算法在搜尋性能上表現較優。4中3種算法10次獨立運行所得最優解的平均值與標準差可以看出，混合離散粒子群算法在保證每次的近似最優解精度更高的同時，離散程度較低，穩定性較高，表明混合離散粒子群算法對于陷入局部最優解有一定的抑制作用。4中3種算法10次獨立運行所得最優解的平均值與標準差可以看出，混合離散粒子群算法在保證每次的近似最優解精度更高的同時，離散程度較低，穩定性較高，表明混合離散粒子群算法對于陷入局部最優解有一定的抑制作用。

表3 最優解完工時間任務分配

圖8 5×10最優解迭代圖

表4 最優解統計結果

4 結語

非等同并行機的分批計劃與排產順序是保證最大完工時間最小化的關鍵問題。為了解決多層級問題，文章采用多種算法混合的方式逐步解決各級問題，以同一目標函數判定各層級解的好壞。本文算法的優勢在于，提高了離散粒子群解的質量、采用Metropolis準則避免局部最優的問題，提高了全局搜索能力。通過實驗結果，驗證了本文算法在求解非等同并行機分批調度問題的有效性與穩定性。