孫新宇

(上海理工大學(xué)機(jī)械工程學(xué)院，上海 200093)

807713550@qq.com

1 引言(Introduction)

柔性作業(yè)車間調(diào)度的概念是在1990 年BRUCKER和SCHLIE提出的，其作為經(jīng)典作業(yè)車間調(diào)度問(wèn)題的進(jìn)一步擴(kuò)展，屬于一個(gè)典型的NP-hard問(wèn)題，存在求解優(yōu)化的困難。不同于作業(yè)車間調(diào)度，柔性作業(yè)車間調(diào)度可以使每個(gè)作業(yè)在不同的機(jī)器上進(jìn)行加工，也可以在機(jī)械設(shè)備出現(xiàn)故障時(shí)處理問(wèn)題，并滿足不同加工需求的變化，更有利于提高生產(chǎn)效率，貼近現(xiàn)實(shí)具體的生產(chǎn)環(huán)境。按照求解目標(biāo)，柔性作業(yè)車間調(diào)度問(wèn)題可分為單目標(biāo)和多目標(biāo)，單目標(biāo)一般的優(yōu)化目標(biāo)為最大完工時(shí)間、機(jī)器空閑時(shí)間、總流動(dòng)時(shí)間等，目前研究最多的是最大完工時(shí)間。多目標(biāo)是將多個(gè)目標(biāo)同時(shí)考慮，選擇最優(yōu)情況，更符合現(xiàn)實(shí)生產(chǎn)要求。

灰狼優(yōu)化算法(Grey Wolf Optimizer，GWO)是MIRJALILI等在2014 年觀察模仿狼群生活和狩獵方式提出來(lái)的一種基于群體的優(yōu)化搜索算法。該算法的搜索原理簡(jiǎn)單、魯棒性較好、收斂性能較強(qiáng)、求解速度較快和參數(shù)較少。通過(guò)近些年的研究，其已經(jīng)很好地應(yīng)用在車間調(diào)度問(wèn)題的求解、圖像分類、參數(shù)優(yōu)化等領(lǐng)域。

灰狼算法較多用于解決連續(xù)函數(shù)方面的問(wèn)題，對(duì)于柔性作業(yè)車間問(wèn)題，特別是本文對(duì)多目標(biāo)的優(yōu)化方面的應(yīng)用還是較少。因此本文通過(guò)優(yōu)化初始種群，在此基礎(chǔ)上，與非支配排序算法結(jié)合，引入非支配排序與擁擠度，提出了一種解決多目標(biāo)優(yōu)化問(wèn)題的思路，并通過(guò)調(diào)度算例進(jìn)行有效驗(yàn)證。

2 問(wèn)題描述(Problem description)

對(duì)柔性作業(yè)車間問(wèn)題的描述如下：假設(shè)一個(gè)柔性作業(yè)車間有臺(tái)加工機(jī)器和個(gè)工件，不同機(jī)器會(huì)加工多種工件，每個(gè)工件的工序數(shù)量也不一定相同，每個(gè)工序的加工需要按照一定的先后順序進(jìn)行，并且加工的時(shí)間也會(huì)各不相同。按照某些優(yōu)化目標(biāo)，為每道工序分配合適的加工機(jī)器，并且每臺(tái)機(jī)器按照分配的任務(wù)進(jìn)行順序加工，從而實(shí)現(xiàn)最優(yōu)化的目標(biāo)安排。

對(duì)于柔性作業(yè)車間，還存在下面的假設(shè)條件：

(1)一臺(tái)機(jī)器某一時(shí)刻只能加工處理一個(gè)工件；

(2)所有工件在開始的零時(shí)刻都可以被加工；

(3)同種工件的工序一定要按照次序加工，不同工件的工序之間相互獨(dú)立；

(4)各個(gè)工件之間不存在加工的優(yōu)先級(jí)的差別；

(5)任意工序只要開始加工，就不能中斷；

(6)同一工件的同一道工序在同一時(shí)刻被加工的機(jī)器數(shù)是一。

3 模型建立(Model building)

把車間的最大完成加工時(shí)間、機(jī)器總耗能及總機(jī)器負(fù)荷作為優(yōu)化目標(biāo)，建立柔性車間的多目標(biāo)模型。

(1)最大加工完成時(shí)間最小化

加工完成時(shí)間是每個(gè)工件的最后一道工序完成的時(shí)間，當(dāng)最后一個(gè)工件的最后一步工序結(jié)束時(shí)，加工零件所用時(shí)間最長(zhǎng)的就是最大完工時(shí)間。在調(diào)度排產(chǎn)中，完工時(shí)間可以體現(xiàn)一個(gè)車間生產(chǎn)效率的高低，表示為

式中，表示最大完成加工時(shí)間；表示工件序號(hào)；表示工件總數(shù)；C表示每個(gè)工件的完成加工時(shí)間。

(2)機(jī)器總耗能最小化

總耗能是空載能耗與負(fù)載能耗之和，零時(shí)刻機(jī)器開工，能耗計(jì)算公式表示為

式中，表示機(jī)器序號(hào)；表示機(jī)器總數(shù)；表示速度擋位序號(hào)； d表示機(jī)器的速度擋位； E表示單位時(shí)間內(nèi)機(jī)器加工時(shí)的加工能耗；p表示工件以速度擋位在機(jī)器上的實(shí)際加工時(shí)間； x表示0或1變量，若工件在機(jī)器以速度擋進(jìn)行加工則為1，否則為0；SE表示機(jī)器單位時(shí)間內(nèi)的平均空載能耗；MC表示機(jī)器的完成加工時(shí)間；W表示機(jī)器的總負(fù)載。

(3)總機(jī)器負(fù)荷最小化

在不同的調(diào)度安排下，機(jī)器的總負(fù)荷也會(huì)不同，所以在不同機(jī)器上同種工序花費(fèi)的時(shí)間也不同，因此最小化機(jī)器的總耗能顯得很有必要，前提是最大完工時(shí)間最好一致，表示為

式中， h表示第個(gè)工件的工序總數(shù)； p表示第個(gè)工件的第道工序在機(jī)器上的加工時(shí)間； x為0或1變量，如果第個(gè)工件的第道工序在機(jī)器上加工則值為1，否則為0。

(4)上述假設(shè)條件的約束模型

式中， s為第個(gè)工件的第道工序加工開始的時(shí)間； c為第個(gè)工件的第道工序加工完成的時(shí)間；代表工序序號(hào)；表示不同于的工件序號(hào)； y為0或1變量，如果第臺(tái)機(jī)器上第個(gè)工件的第道工序先于該臺(tái)機(jī)器上第個(gè)工件的第道工序加工則為1，否則為0。

式(4)和式(5)表示工序加工時(shí)按照工件規(guī)定的次序；式(6)表示總的完工時(shí)間一定大于每個(gè)工件的完成加工時(shí)間；式(7)和式(8)表示一臺(tái)機(jī)器某一時(shí)刻只能加工處理一個(gè)工件的工序；式(9)表示工件的工序在任意時(shí)刻有且僅有一臺(tái)機(jī)器可以加工處理它；式(10)和式(11)表示車間中的任何一臺(tái)機(jī)器的操作是可重復(fù)的；式(12)表示各個(gè)變量不可小于零。

4 改進(jìn)的灰狼算法(Improved GWO algorithm)

4.1 基本的灰狼算法

灰狼算法的數(shù)學(xué)模型由兩部分組成：包圍獵物的部分和獵殺獵物的部分。包圍獵物的數(shù)學(xué)公式如下：

獵殺獵物的數(shù)學(xué)模型如下：

4.2 初始化種群的改進(jìn)

對(duì)于群智能優(yōu)化算法來(lái)說(shuō)，好的初始化種群可以加快全局收斂的速度，以及尋找更精確的解，所以改進(jìn)算法的初始種群，提高尋優(yōu)能力就顯得很有必要。在標(biāo)準(zhǔn)灰狼算法中，種群的多樣性無(wú)法保證，因?yàn)槠洳捎秒S機(jī)初始化的方法來(lái)初始種群。

本文采用了LUO等提出的復(fù)數(shù)值編碼的方法，初始化種群，并與工序結(jié)合，較好地提高了全局優(yōu)化的策略，尋找工序中最優(yōu)的分配，減少最大完工時(shí)間和機(jī)器耗能等。該方法為了提高種群的多樣性，引入了復(fù)數(shù)，因?yàn)閺?fù)數(shù)包含實(shí)部和虛部，可以單獨(dú)分別更新，從而包含了更多的信息，進(jìn)而增強(qiáng)了種群的多樣性。

4.3 非支配排序及擁擠度

為了解決柔性作業(yè)車間的多目標(biāo)問(wèn)題，標(biāo)準(zhǔn)的灰狼算法對(duì)于單目標(biāo)問(wèn)題，個(gè)體的優(yōu)劣比較容易判斷，但當(dāng)涉及多目標(biāo)問(wèn)題時(shí)，就很難尋找目標(biāo)。引入非支配排序遺傳算法中的非支配排序和擁擠度的概念，將每個(gè)個(gè)體按照它們的支配與非支配關(guān)系進(jìn)行分層，再根據(jù)擁擠度，選出同級(jí)別中的優(yōu)解，保持了種群的多樣性，從而達(dá)到求解多目標(biāo)問(wèn)題的目標(biāo)。

(1)在種群中尋找單獨(dú)的個(gè)體，這類個(gè)體不受上一級(jí)個(gè)體的控制影響，把它們放入集合中。

(2)對(duì)上述集合中的每個(gè)個(gè)體，找出受它影響控制的下一級(jí)個(gè)體集合，那么因?yàn)檎页隽艘活惿弦患?jí)個(gè)體，集合中個(gè)體的受上一級(jí)影響數(shù)量需要減去一類。

(3)當(dāng)該個(gè)體受上一級(jí)影響的數(shù)量減去1后值為0時(shí)，存入另一個(gè)集合中。那么集合中的個(gè)體都是非支配的，第一次分級(jí)找出的這些個(gè)體也被叫作第一級(jí)非支配個(gè)體。然后重復(fù)上面的操作，由集合開始分級(jí)，不斷進(jìn)行下去，那么所有的個(gè)體都可以分級(jí)完成。

密度估計(jì)：對(duì)同一個(gè)前沿面的解集合按各個(gè)目標(biāo)分量大小排序，計(jì)算每個(gè)解在該分量下的兩側(cè)點(diǎn)的距離差值，而后進(jìn)行累加各個(gè)分量上的距離作為擁擠系數(shù)。

4.4 算法流程

圖1 算法步驟流程圖Fig.1 Flow chart of algorithm steps

步驟1：設(shè)置算法參數(shù)、種群大小及迭代次數(shù)。

步驟2：采用上文所述的復(fù)數(shù)值編碼的方法初始化種群。

步驟3：解碼得到加工時(shí)間、耗能和機(jī)器負(fù)荷，進(jìn)行非支配排序和擁擠度計(jì)算。

步驟4：對(duì)擁擠度排序后，找出決策層的、和狼。

步驟5：更新每個(gè)灰狼個(gè)體的位置。

步驟6：計(jì)算更新后群體個(gè)體的適應(yīng)度，再找出最優(yōu)的三條狼。

步驟7：判斷迭代次數(shù)是否滿足，是則轉(zhuǎn)到步驟8，否則轉(zhuǎn)到步驟5。

步驟8：算法結(jié)束，輸入結(jié)果。

5 實(shí)例結(jié)果與分析(Example results and analysis)

為了驗(yàn)證上述模型和算法在解決FJSP問(wèn)題方面的有效性，本文采用了Brandimarte中的基準(zhǔn)算例MK10，算例中的工件數(shù)為20，機(jī)器數(shù)量為10。

以最小完工時(shí)間、最小機(jī)器負(fù)荷及最小機(jī)器耗能為目標(biāo)，在柔性作業(yè)車間中，通過(guò)改進(jìn)的灰狼算法進(jìn)行甘特圖的排產(chǎn)安排，其中灰狼優(yōu)化算法的種群大小設(shè)置為100，最大迭代次數(shù)為100。最終優(yōu)化的三個(gè)目標(biāo)結(jié)果圖如圖2、圖3和圖4所示；甘特圖排產(chǎn)的結(jié)果如圖5所示。

圖2 最小完工時(shí)間趨勢(shì)曲線Fig.2 Trend curve of the minimum completion time

圖3 最小機(jī)器負(fù)荷趨勢(shì)曲線Fig.3 Trend curve of the smallest machine load

圖4 最小機(jī)器耗能趨勢(shì)曲線Fig.4 Trend curve of the minimum machine energy consumption

根據(jù)運(yùn)行結(jié)果，從圖2—圖4中可以看出收斂的所有零件完成加工的最小時(shí)間在510 分鐘左右，最小機(jī)器負(fù)荷為2，395 kW，最小機(jī)械總能耗為6，175 kW。可以看到改進(jìn)后的灰狼算法可以較快收斂到最優(yōu)解，加入非支配排序和擁擠度后，該算法在解決三目標(biāo)的優(yōu)化問(wèn)題方面是有效的。

圖5 實(shí)例MK10的甘特圖Fig.5 Gantt Chart of example MK10

6 結(jié)論(Conclusion)

為了研究柔性作業(yè)車間多目標(biāo)調(diào)度的優(yōu)化問(wèn)題，本文采用改進(jìn)的灰狼優(yōu)化算法，用復(fù)數(shù)值編碼的方式初始化種群，使用了非支配排序遺傳算法中的非支配排序和擁擠度，使得改進(jìn)后的灰狼算法，也可以用于解決多目標(biāo)優(yōu)化問(wèn)題。

建立了關(guān)于完工時(shí)間、機(jī)械負(fù)荷和機(jī)械總能耗的數(shù)學(xué)模型，并用灰狼算法對(duì)模型進(jìn)行驗(yàn)證，結(jié)果表明改進(jìn)后的灰狼算法可以較快地收斂，找到多目標(biāo)的最優(yōu)解，說(shuō)明了該算法的有效性。

本文研究的內(nèi)容都是在靜態(tài)調(diào)度的情況下，針對(duì)動(dòng)態(tài)調(diào)度的情況沒(méi)有考慮，下一步需要考慮更多的現(xiàn)實(shí)問(wèn)題和與其他智能隨機(jī)算法結(jié)合對(duì)比研究，獲得更高效的算法。