吳曉雯，鄭巧仙

(湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院, 湖北 武漢 430062)

0 引言

作業(yè)車間調(diào)度問題(job-shop scheduling problem,JSP)是指一個(gè)加工系統(tǒng)有m臺機(jī)器,要求加工n項(xiàng)組裝元件,不同的作業(yè)包含不同的操作數(shù),假設(shè)L為任務(wù)集的總操作數(shù).在JSP問題中，每項(xiàng)組裝元件的操作時(shí)間已經(jīng)確定，對于元件中的每項(xiàng)操作，其存在相應(yīng)的先后順序，每項(xiàng)操作需要按照對應(yīng)的先后順序進(jìn)行加工。對于作業(yè)車間調(diào)度問題而言，是指將所有組裝元件的所有操作進(jìn)行加工排序，使之滿足約束，并且達(dá)到目標(biāo)最優(yōu).

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)與傳統(tǒng)的JSP問題相比，其主要特點(diǎn)是工件的操作可以選擇一臺或者幾臺機(jī)器進(jìn)行加工，不存在資源唯一性約束的相關(guān)問題.與之相比，由于機(jī)器的選擇不同，其問題的復(fù)雜程度也呈指數(shù)級增長.

通過已有的研究發(fā)現(xiàn),研究者們對JSP問題研究透徹,但關(guān)于FJSP問題的研究卻很少.近年來,因?yàn)镕JSP問題的復(fù)雜性,顯示出其更高的實(shí)用價(jià)值,關(guān)于FJSP問題的研究也在日益增多.1993年,Paolo Brandimarte采用分層思想,將禁忌搜索算法同分布思想進(jìn)行結(jié)合,將FJSP問題中的復(fù)雜問題分解為幾個(gè)復(fù)雜程度較小的子問題,在對子問題解決的基礎(chǔ)上對完整問題進(jìn)行解決[1].2000年,Maciej Hapke在其論文中,采用模擬退火算法對FJSP問題進(jìn)行求解[2].

2009年,張國輝等使用改進(jìn)遺傳算法求解FJSP問題,通過考慮各個(gè)機(jī)器的負(fù)荷平衡，建立所有機(jī)器總負(fù)荷和最大完工時(shí)間為優(yōu)化目標(biāo)的數(shù)學(xué)模型,在此問題上提出一種改進(jìn)遺傳算法,提高該種群初始解的質(zhì)量.并結(jié)合問題,設(shè)計(jì)更加合理的變異算子,提高求解效率[3].2011年,Li等采用關(guān)鍵路徑法結(jié)合禁忌算法對FJSP進(jìn)行求解[4].2016年,Li等提出一種新的染色體編碼方式,將遺傳算法同禁忌搜索算法相結(jié)合用于求解FJSP,以此保證種群多樣性及良好的全局搜索能力[5].目前，針對FJSP問題,隨著“中國制造2025”的提出,智能制造中深度強(qiáng)化學(xué)習(xí)為構(gòu)建智能化生產(chǎn)調(diào)度系統(tǒng)提供了有效的指導(dǎo).

1975年,John Holland首次提出遺傳算法(genetic algorithm,GA).遺傳算法是從其研究問題的解空間的一組解開始進(jìn)行并行搜索.并且通過計(jì)算搜索到的解的好壞，來判定該種群是否需要進(jìn)行進(jìn)化.這種搜索方式使得種群以更快速率集中在較好質(zhì)量個(gè)體的區(qū)域[6],使該算法的全局搜索能力增強(qiáng).1995年，Eberhart和Kennedy認(rèn)為鳥類在覓食過程中，個(gè)體之間可以進(jìn)行信息交流，鳥類的每個(gè)個(gè)體可以記住自己所處的最好位置，也能找到群體中的最佳位置，這兩個(gè)最優(yōu)的位置吸引鳥類朝這兩個(gè)位置靠近.綜合這些特性，他們提出了粒子群算法(particle swarm optimization，PSO)[7].

1985年,Falkenauer首次將遺傳算法用于求解傳統(tǒng)JSP問題[8],2002年,Kacem首次將遺傳算法應(yīng)用于求解FJSP問題[9].2012年，Lin等混合遺傳算法和粒子群算法，并在此基礎(chǔ)上提出了混合演化算法[10].2015年,李俊等提出求解柔性作業(yè)車間調(diào)度的混合粒子群算法，采用基于輪盤賭的編碼方式和基于鄰域互換的局部搜索方法，并將此編碼方式應(yīng)用于粒子群算法使得柔性作業(yè)車間調(diào)度問題具有更好的求解性能[11].2017年，劉勝輝等提出了一種分布式粒子群優(yōu)化算法以求解柔性作業(yè)車間調(diào)度問題，解決了傳統(tǒng)粒子群算法在遇到突發(fā)事件時(shí)不能實(shí)時(shí)進(jìn)行響應(yīng)并做出合理決策的問題，在該算法中設(shè)計(jì)了兩個(gè)多Agent粒子群優(yōu)化模型，實(shí)驗(yàn)表明該算法能夠有效解決柔性作業(yè)車間調(diào)度問題[12].2021年，蔡敏等針對實(shí)際工廠中不確定加工時(shí)間的柔性作業(yè)車間調(diào)度問題，提出一種混合粒子群優(yōu)化算法，采用三角模糊數(shù)表示加工時(shí)間，以最小化最大模糊完工時(shí)間為優(yōu)化目標(biāo)進(jìn)行建模，采用粒子群算法融合模擬退火算法的方法對該模型進(jìn)行求解，使得改進(jìn)粒子群算法跳出局部最優(yōu)，同時(shí)也能兼顧搜索速度快等特性，再實(shí)例中取得較好的效果[13].

由于將粒子群算法與遺傳算法融合用于求解柔性作業(yè)車間調(diào)度問題的論文較少，大多數(shù)都是將粒子群算法同模擬退火算法融合，使粒子群算法的搜索速度兼顧跳出局部最優(yōu)的能力加強(qiáng)，但在柔性作業(yè)車間調(diào)度問題中，由于整個(gè)作業(yè)車間的工序未知，采用遺傳算子增加整個(gè)粒子群算法的變異能力，在一定程度上也能使得改進(jìn)后的粒子群算法具有跳出局部最優(yōu)同時(shí)兼顧搜索速度快的能力.針對柔性作業(yè)車間調(diào)度問題,建立以最小化最大完工時(shí)間為目標(biāo)的數(shù)學(xué)模型,利用JSP的8*8經(jīng)典算例和FJSP的Brandimarte算例驗(yàn)證該模型及解的有效性,同時(shí)對需要進(jìn)一步研究的問題和未來發(fā)展趨勢作出展望.

1 問題描述與模型構(gòu)建

1.1 柔性作業(yè)車間調(diào)度問題描述本研究主要針對柔性作業(yè)車間調(diào)度問題(FJSP)進(jìn)行求解,柔性作業(yè)車間調(diào)度問題是在一定的約束條件之下,將各組裝元件的操作合理地分配到各機(jī)器,合理地安排各操作的加工次序和操作的開始時(shí)間,在滿足其優(yōu)化條件的情況下,更好地優(yōu)化其設(shè)定的目標(biāo).

將柔性作業(yè)車間調(diào)度問題(FJSP)描述為：

初始情況下,給定m臺機(jī)器,以及n項(xiàng)組裝元件.按照元件的工藝路線,每項(xiàng)組裝原件由一種或者多種有順序約束的操作組成.每種操作可以在多臺機(jī)器上進(jìn)行加工.操作進(jìn)行加工的過程中,需要滿足以下約束條件：

1)同一時(shí)刻,每種操作只能在一臺機(jī)器進(jìn)行加工,若操作開始加工,直至加工完成，此項(xiàng)操作不能被中斷；

2)同一時(shí)刻,每臺機(jī)器最多只能選擇一種操作進(jìn)行加工；

3)同一組裝元件間的操作之間存在先后約束關(guān)系，不同組裝元件的操作之間不存在順序約束；

4)不同的組裝原件之間具有相同的加工優(yōu)先等級.

1.2 柔性作業(yè)車間調(diào)度問題模型構(gòu)建基于以上假設(shè),構(gòu)建柔性作業(yè)車間問題的數(shù)學(xué)模型,表1給出模型的參數(shù)含義：

表1 模型參數(shù)含義

根據(jù)問題描述,建立以下優(yōu)化目標(biāo)：

(1)

dijk={0,1},i,j∈Oij

(2)

(3)

(4)

其中：式(1)表示該問題的目標(biāo)為最小化最大完工時(shí)間；式(2)保證每個(gè)組裝元件的每一項(xiàng)操作同一時(shí)間只能分配至一臺機(jī)器；式(3)是其中的順序約束,即在對同一組裝元件的不同操作進(jìn)行加工時(shí),某項(xiàng)操作j如果需要在另一項(xiàng)操作j1之前完成,則該項(xiàng)操作應(yīng)該優(yōu)先被分配至機(jī)器；式(4)表示所有機(jī)器的完工時(shí)間之和不超過目標(biāo)函數(shù).

2 粒子群算法(PSO算法)

(5)

(6)

一般而言，PSO算法是一種基于自身經(jīng)驗(yàn)和社會經(jīng)驗(yàn)不斷學(xué)習(xí)的算法，它具有較強(qiáng)的通用性，且群體在進(jìn)行搜索時(shí)具有記憶能力，粒子間聯(lián)系緊密，學(xué)習(xí)能力較強(qiáng)，也可以根據(jù)問題的規(guī)模自動調(diào)整學(xué)習(xí)速度，搜索速度較快，原理較為簡單，但其局部搜索能力較差，搜索的精度有待提高，而且容易因?yàn)閰?shù)的設(shè)置問題而陷入局部最優(yōu)解，所以針對粒子群算法的特點(diǎn)，將遺傳算法中的遺傳算子引入粒子群算法中，在粒子陷入局部最優(yōu)解的過程中對粒子進(jìn)行交叉變異，從而可以使得PSO算法跳出局部最優(yōu)解.

3 改進(jìn)粒子群算法(IPSO算法)

本研究主要采用改進(jìn)粒子群算法對FJSP問題進(jìn)行求解,針對粒子群算法中的慣性因子進(jìn)行自適應(yīng)調(diào)整，在算法運(yùn)行過程中，將遺傳算法中的遺傳算子引入粒子群算法中，提高算法的深度尋優(yōu)能力.

3.1 慣性因子調(diào)整策略首先針對慣性因子采取自適應(yīng)調(diào)整策略，基本的粒子群算法的慣性因子是固定的，在PSO算法中，一個(gè)較大的慣性因子有利于全局搜索；反之，適合局部搜索，所以固定的慣性因子并不適合復(fù)雜的FJSP問題.此時(shí)，需要將慣性因子調(diào)整為自適應(yīng)改變自身大小，在需要全局搜索時(shí)自動增加其大小.以式(7)對慣性因子進(jìn)行更新：

(7)

3.2 工序交叉與工序變異在PSO算法中，由于粒子只能通過速度的大小和當(dāng)前的位置來尋找最優(yōu)位置，由于參數(shù)設(shè)置的問題，極易陷入局部最優(yōu)位置，如何跳出局部最優(yōu)位置，找到全局位置成為改進(jìn)算法的關(guān)鍵之處，本研究將遺傳算法的遺傳算子引入粒子群算法中，對工序采用編碼、交叉、編譯等方式，進(jìn)一步提高粒子的搜索性能.

3.2.1 工序編碼 對于已經(jīng)過位置和速度更新的粒子，尋找粒子適應(yīng)度值位于前30%的粒子，對該粒子所處位置進(jìn)行染色體編碼，染色體的長度與總操作數(shù)相等.每一個(gè)基因用組裝元件號直接編碼,元件號出現(xiàn)的順序表示該元件操作間的先后加工順序.此時(shí),對染色體從左到右進(jìn)行編譯,對于第q次出現(xiàn)的元件號,表示該元件i的第q項(xiàng)操作,并且元件號的出現(xiàn)次數(shù)等于該元件的操作總數(shù).對工序編碼之后，根據(jù)柔性作業(yè)車間調(diào)度問題的特點(diǎn)，需要進(jìn)行機(jī)器選擇，選擇當(dāng)前工序完工時(shí)間最小的機(jī)器進(jìn)行加工.

3.2.2 工序交叉 對于已經(jīng)進(jìn)行編碼的工序，對其染色體進(jìn)行交叉，以父代新的組合方式產(chǎn)生新的粒子，并計(jì)算新的適應(yīng)度，若新的粒子的適應(yīng)度的值優(yōu)于原先粒子的適應(yīng)度，則將其進(jìn)行替換.

3.2.3 工序變異 若此時(shí)產(chǎn)生新的粒子的適應(yīng)度與原先的相比無變化或者大于原先粒子的適應(yīng)度，則將染色體進(jìn)行變異，設(shè)定變異概率P_variation，且P_variation≤0.05，對交叉粒子集中每個(gè)粒子的每一位，產(chǎn)生一個(gè)隨機(jī)數(shù)r?[0,1]，若r≤P_variation，則將該位取反，否則該位不變.對變異后新的粒子，進(jìn)行適應(yīng)度計(jì)算，若新粒子適應(yīng)度優(yōu)于原先粒子的適應(yīng)度，則將其進(jìn)行替換.

該算法求解FJSP問題的流程偽代碼如下所示.

1) 初始化：設(shè)置參數(shù)，設(shè)置變量；

2) 生成種群，設(shè)置最大迭代次數(shù)；

3) 計(jì)算每個(gè)粒子的初始適應(yīng)度值，并將其初始適應(yīng)度值作為每個(gè)粒子的局部最優(yōu)值，保存其局部最優(yōu)值，從局部最優(yōu)值中選取最好的值，并將該值作為初始的全局最優(yōu)值；

4)While 未到迭代次數(shù) do；

5)根據(jù)式(5)～(7)對粒子位置和速度進(jìn)行更新；

6)計(jì)算當(dāng)前種群粒子的適應(yīng)度，更新粒子最優(yōu)位置；

7)對FJSP問題中的工序進(jìn)行編碼；

8)針對該編碼方式對工序進(jìn)行交叉，計(jì)算交叉后產(chǎn)生新粒子的適應(yīng)度；

9)若新的粒子適應(yīng)度值>原粒子的適應(yīng)度值；

10)粒子替換；

11)若新的粒子適應(yīng)度值≤原粒子的適應(yīng)度值；

12)工序變異；

13)計(jì)算變異后產(chǎn)生新粒子的適應(yīng)度，將選出的最好適應(yīng)度值的粒子所處的位置設(shè)定成為全局最優(yōu)位置；

14)生成新的粒子群；

15)End while；

16)根據(jù)最終結(jié)果更新最好解.

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

為了驗(yàn)證該問題具有可行解及算法的性能,算法在Windows10下使用python進(jìn)行求解,在11th Gen lntel(R) Core(TM) i5-1135G7@2.40 GHz CPU,16 GB內(nèi)存PC上運(yùn)行.對于車間作業(yè)調(diào)度問題的8*8算例和柔性作業(yè)車間調(diào)度問題的Brandimarte算例進(jìn)行測試.

初始情況下,設(shè)定種群數(shù)量pop_size=30,交叉概率P_cross=0.8,變異概率P_variation=0.05,最大迭代次數(shù)max_iterations=30,8*8算例求解的最大完工時(shí)間Cmax=15,該算例的甘特(Gatt)圖和收斂圖如圖1和2所示.

圖1 8*8算例Gatt圖

種群數(shù)量和迭代次數(shù)改變后,車間作業(yè)調(diào)度問題的8*8算例的結(jié)果如表2所示.

圖2 8*8算例收斂情況

表2 種群數(shù)量和迭代次數(shù)改變后的8*8算例最大完成時(shí)間

由表2結(jié)果可以看出種群數(shù)量和迭代次數(shù)對最小化最大完成時(shí)間都具有一定的影響，其中種群數(shù)量為300,迭代次數(shù)為50次得到的解最好,最小化最大完工時(shí)間Cmax=14.并且初始情況下,最小化最大完工時(shí)間Cmax=17,與其他情況相比,此情況下的解較好.

為了更好地檢測算法的有效性,對Brandimarte算例進(jìn)行測試,Brandimarte算例中含組裝元件10項(xiàng),機(jī)器數(shù)6臺，總操作數(shù)58項(xiàng).在給定初始條件下,Brandimarte算例求解的最大完工時(shí)間Cmax=29,該算例的甘特圖和收斂情況如圖3和4所示.

圖3 Brandimarte算例Gatt圖

圖4 Brandimarte算例收斂情況

該算例的求解結(jié)果如表3所示：

表3 種群數(shù)量和迭代次數(shù)改變后Brandimarte算例最大完成時(shí)間

由上表結(jié)果可以看出種群數(shù)量和迭代次數(shù)對最小化最大完成時(shí)間都具有一定的影響，其中種群數(shù)量為300,迭代次數(shù)為50次得到的解最好,最小化最大完工時(shí)間Cmax=28.并且初始情況下,最小化最大完工時(shí)間Cmax=41,與其他情況相比,此情況下的解較好.

5 結(jié)論

本文中采用IPSO對FJSP進(jìn)行求解，在粒子群算法的基礎(chǔ)上，將遺傳算法中的遺傳算子加入粒子群算法中，根據(jù)FJSP問題的特點(diǎn)，提出針對機(jī)器排序和操作選擇的編碼過程，在后續(xù)的染色體交叉和變異過程中，同樣考慮機(jī)器排序和操作選擇的過程.這樣進(jìn)一步提升了種群的多樣性，避免粒子群算法陷入局部最優(yōu)解，同時(shí)使得求解速度加快，求出更好的最優(yōu)解.下一步將探討使用改進(jìn)粒子群算法求解在人為因素和中途中斷等條件下的柔性作業(yè)車間調(diào)度問題.