改進(jìn)粒子群算法在柔性作業(yè)車(chē)間調(diào)度中的應(yīng)用

楊文理 李長(zhǎng)云

（1、湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲412007 2、智能信息感知及處理技術(shù)湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 株洲412007）

近年來(lái)，在“中國(guó)制造2025”政策的支持下，制造業(yè)正迅速朝著信息化的方向發(fā)展，車(chē)間排產(chǎn)的復(fù)雜性、不確定性、多目標(biāo)性、多約束性導(dǎo)致車(chē)間管理仍存在諸多問(wèn)題，引發(fā)很多專(zhuān)家學(xué)者對(duì)其進(jìn)行研究。

為了解決柔性車(chē)間調(diào)度中存在的諸多問(wèn)題，國(guó)內(nèi)外專(zhuān)家學(xué)者提出了一系列改進(jìn)優(yōu)化算法。如彭建剛[1]對(duì)多目標(biāo)柔性作業(yè)車(chē)間調(diào)度算法進(jìn)行了總結(jié)，主要采取加權(quán)聚合法和Pareto 優(yōu)化方法對(duì)該問(wèn)題進(jìn)行求解，但是存在很難得到最有權(quán)重值、種群收斂性能等問(wèn)題。孫麗珍[2]等人提出一種改進(jìn)的遺傳算法，提出了MCGI 的解碼方案，但是沒(méi)有考慮復(fù)合動(dòng)態(tài)調(diào)度問(wèn)題。李傳鵬[3]等人討論了柔性作業(yè)車(chē)間調(diào)度現(xiàn)存問(wèn)題及未來(lái)的發(fā)展趨勢(shì)，提出目前工作對(duì)工件生產(chǎn)批量不同的問(wèn)題研究較少等問(wèn)題。王艷[4]等人提出一種改進(jìn)的多目標(biāo)差分進(jìn)化算法進(jìn)行求解，在尋優(yōu)能力和綜合決策方面表現(xiàn)較優(yōu)。其中文獻(xiàn)[5]提出了一種對(duì)粒子位置狀態(tài)更新的改進(jìn)粒子群優(yōu)化算法獲得最優(yōu)工序排序，但是結(jié)果受計(jì)算經(jīng)驗(yàn)限制，性能有待進(jìn)一步提高。

綜上所述，借鑒研究學(xué)者們的經(jīng)驗(yàn)，設(shè)計(jì)了一種混合輪盤(pán)賭選擇算子的粒子群算法。通過(guò)算例分析，驗(yàn)證了使用該方法改進(jìn)的粒子群算法的有效性。

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

1.1 問(wèn)題描述

在實(shí)際生產(chǎn)過(guò)程中，柔性作業(yè)車(chē)間調(diào)度問(wèn)題可以描述為：有n 個(gè)工單在m 臺(tái)機(jī)器上進(jìn)行生產(chǎn)排程，每個(gè)工單對(duì)應(yīng)唯一的生產(chǎn)工藝路線，每條工藝路線包含不完全相同的工序，各工藝路線對(duì)應(yīng)的工序之間具有嚴(yán)格的先后順序，每個(gè)工序可以選擇多臺(tái)機(jī)器進(jìn)行生產(chǎn)，但是每道工序只能在對(duì)應(yīng)的機(jī)器上加工一次，相同工序在不同機(jī)器上加工時(shí)間不同。

一般的車(chē)間調(diào)度需要滿足以下約束條件：（1）所有工單在生產(chǎn)開(kāi)始前優(yōu)先級(jí)相同，即不考慮其他因素的情況下，所有工單都有機(jī)會(huì)在開(kāi)始時(shí)刻進(jìn)行加工。（2）特定機(jī)器上生產(chǎn)某個(gè)工單對(duì)應(yīng)工序的生產(chǎn)時(shí)間是不變的。（3）若當(dāng)前生產(chǎn)工序沒(méi)用完成時(shí)，當(dāng)前機(jī)器不能暫停進(jìn)行其他任務(wù)生產(chǎn)。

1.2 模型構(gòu)建

本文以最大完工時(shí)間最小化為優(yōu)化目標(biāo)，結(jié)合上述約束條件和數(shù)學(xué)符號(hào)，將柔性作業(yè)車(chē)間調(diào)度數(shù)學(xué)模型描述如下：

目標(biāo)函數(shù):

式（1）表示求所有訂單的生產(chǎn)時(shí)間之和的最小值，即本文的優(yōu)化目標(biāo)；式（2）表示一個(gè)工單有且僅有一條加工工藝路線與其匹配；式（3）表示所有訂單的初始優(yōu)先級(jí)都相同；式（4）表示上一個(gè)訂單的開(kāi)始加工時(shí)間小于下一個(gè)訂單的開(kāi)始時(shí)間，即同一時(shí)刻，同一機(jī)器在完成當(dāng)前生產(chǎn)任務(wù)前，不能加工其他生產(chǎn)任務(wù)。

2 改進(jìn)的粒子群算法求解FJSP

2.1 粒子群算法

粒子群算法[6]是美國(guó)心理學(xué)家Kennedy 和電氣工程師Eberhart 在1995 年提出來(lái)的，該算法可以由兩個(gè)向量表示，它們分別是位置向量和速度向量。粒子所處的位置表示當(dāng)前問(wèn)題的可行解，速度則表示粒子在空間中的搜索方向。粒子在求解空間中不斷飛行，更新粒子優(yōu)化位置，最終尋到全局最優(yōu)解。可以用下面兩個(gè)公式表示：

其中，i 表示第i 個(gè)粒子；j 表示粒子的第j 維；vij(t)表示粒子i在t 時(shí)刻的第j 維飛行速度向量；xij(t)表示粒子i 在t 時(shí)刻的第j維的位置分量；pbestij(t)表示粒子種群在t 時(shí)刻最佳位置gbestij(t)表示粒子i 在t 時(shí)刻第j 維度的分量；c1,c2為學(xué)習(xí)因子，通常在[0,1]之間隨機(jī)取值。

2.2 基于輪盤(pán)賭的粒子群算法

為了解決算法早熟收斂問(wèn)題，我們引入輪盤(pán)賭選擇算子對(duì)粒子群算法進(jìn)行改進(jìn)，具體步驟如下：

步驟5：重復(fù)步驟4，得到足夠多的新個(gè)體，構(gòu)建一個(gè)新種群。

3 實(shí)驗(yàn)結(jié)果與分析

本文選擇10*6 的算例對(duì)兩種算法進(jìn)行實(shí)驗(yàn)，截取其中一個(gè)工單的數(shù)據(jù)如表1 所示。

表1 工單的工序和生產(chǎn)時(shí)間表

表1 反映了一個(gè)工單對(duì)應(yīng)的工藝路線中包含5 道工序，這5 道工序可以在6 臺(tái)機(jī)器上進(jìn)行加工，每道相同工序在不同機(jī)器上的加工時(shí)間不完全相同。在該問(wèn)題中，每個(gè)訂單對(duì)應(yīng)的工藝路線包含了5 個(gè)工序，這些工序可以在全部或部分機(jī)器上進(jìn)行加工，在不同機(jī)器上的加工時(shí)間不完全相同。

文章設(shè)置改進(jìn)粒子群算法的種群規(guī)模為50，最大迭代次數(shù)為500，進(jìn)行實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)結(jié)果可知，改進(jìn)粒子群算法計(jì)算的最小完工時(shí)間為28，傳統(tǒng)方法為33，由此可知，改進(jìn)的粒子群算法在全局尋優(yōu)和種群適應(yīng)度最小值變化上表現(xiàn)更好。實(shí)驗(yàn)結(jié)果如圖1、圖2 所示。

4 結(jié)論

文章提出一種改進(jìn)粒子群算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題，該方法引入了輪盤(pán)賭策略對(duì)粒子初始化進(jìn)行改進(jìn)。實(shí)驗(yàn)表明，改進(jìn)算法的收斂速度更快、全局尋優(yōu)能力更強(qiáng)，驗(yàn)證了本文改進(jìn)粒子群算法對(duì)求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題的有效性。

圖1 改進(jìn)算法的全局最優(yōu)解的變化情況和種群適應(yīng)度最小值的變化情況

圖2 傳統(tǒng)算法的全局最優(yōu)解的變化情況和種群適應(yīng)度最小值的變化情況