基于混合離散粒子群算法的非等同并行機(jī)分批調(diào)度研究

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

（1.長春工業(yè)大學(xué)機(jī)電工程學(xué)院，長春 130012；2.緯湃汽車電子（長春）有限公司，長春 130000）

0 引言

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

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

1 非等同并行機(jī)分批調(diào)度模型

1.1 問題描述

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

1.2 符號定義

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

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

1.3 數(shù)學(xué)模型

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

2 混合離散粒子群算法設(shè)計

2.1 混合離散粒子群算法流程設(shè)計

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

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

2.2 零件分批的主模擬退火算法設(shè)計

FSA算法采用標(biāo)準(zhǔn)模擬退火算法求解工件分批方案，對每代分批方案通過DPSO算法進(jìn)行加工順序的改變進(jìn)行多次適應(yīng)度值計算，取最優(yōu)粒子的適應(yīng)度值作為本代分批方案的適應(yīng)度值, 適應(yīng)度函數(shù)如式（12）所示，F(xiàn)SA算法流程圖如圖1所示。

圖1 FSA算法流程圖

2.2.1 個體更新方式

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

表1 個體位置更新表

2.2.2 Metropolis準(zhǔn)則

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

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

2.3 子批排序的離散粒子群算法設(shè)計

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

圖2 DPSO算法流程圖

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

圖3 粒子個體數(shù)據(jù)結(jié)構(gòu)

2.4 設(shè)備分配的次模擬退火算法設(shè)計

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

圖4 SSA算法流程圖

2.4.1 設(shè)備分配

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

圖5 設(shè)備分配

2.4.2 保優(yōu)策略

為了防止最優(yōu)解的丟失，在SSA算法中，若最優(yōu)個體被更新，則更新全局最優(yōu)個體的設(shè)備分配方案、適應(yīng)度值，同時更新當(dāng)前適應(yīng)度值下的生產(chǎn)序列與分配方案。

3 實驗仿真及分析

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

表2 工件在設(shè)備上的加工時間

采用混合離散粒子群算法進(jìn)行生產(chǎn)計劃優(yōu)化排序，參數(shù)設(shè)置如下：粒子群規(guī)模為20、粒子最大速度為0.5，粒子最小速度為-0.5，離散粒子群進(jìn)化30代，?1=0.7，?2=0.3[8]。目標(biāo)值隨進(jìn)化代數(shù)的變化過程如圖6所示。

圖6 SMT貼片線最優(yōu)解收斂迭代圖

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

最優(yōu)解甘特圖如圖7所示。

圖7 SMT貼片線最優(yōu)解甘特圖

為了進(jìn)一步驗證本文中算法的有效性與穩(wěn)定性，與文獻(xiàn)中遺傳進(jìn)化差分改進(jìn)算法與灰狼差分改進(jìn)算法進(jìn)行對比，僅以最小化最大完工時間作為優(yōu)化目標(biāo)，其他參數(shù)不變，待加工工件共有10種，可選擇設(shè)備5臺，每種工件的模具數(shù)為3。

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

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

表3 最優(yōu)解完工時間任務(wù)分配

圖8 5×10最優(yōu)解迭代圖

表4 最優(yōu)解統(tǒng)計結(jié)果

4 結(jié)語

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