基于NSGA2算法的并行機(jī)多目標(biāo)調(diào)度問(wèn)題研究

引言

并行機(jī)調(diào)度問(wèn)題是一個(gè)被廣泛研究的優(yōu)化問(wèn)題，它具有豐富的研究?jī)?nèi)容，同時(shí)在生產(chǎn)調(diào)度、機(jī)械制造等方面有廣泛的實(shí)際應(yīng)用價(jià)值。但是在實(shí)際操作中，人們常常按經(jīng)驗(yàn)法則進(jìn)行調(diào)度，這樣得到的調(diào)度結(jié)果一般不能滿足實(shí)際環(huán)境的需求。當(dāng)并行機(jī)數(shù)量、工件數(shù)量和優(yōu)化目標(biāo)增加時(shí)，傳統(tǒng)的方法更不適合解決這類問(wèn)題，因此，本文提出了非劣排序遺傳算法來(lái)解決這類問(wèn)題，同時(shí)還提出了一種特殊的染色體編碼。

1多目標(biāo)并行機(jī)問(wèn)題及數(shù)學(xué)模型

1.1多目標(biāo)并行機(jī)問(wèn)題

多目標(biāo)并行機(jī)調(diào)度問(wèn)題可描述為:N個(gè)獨(dú)立的工件要在M臺(tái)相同的機(jī)器上加工。每個(gè)工件都包括加工時(shí)間林提交時(shí)間r和工期pj.每個(gè)工件可以在m臺(tái)機(jī)器中的任一臺(tái)上加工。

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

多目標(biāo)并行機(jī)的一般假設(shè)為：一臺(tái)機(jī)器一次只能加工一個(gè)工件，而且一個(gè)工件只能被加工一次。這樣，如果選擇完工時(shí)間Cmax和總延遲時(shí)間￡Tj為優(yōu)化目標(biāo)，則可建立的目標(biāo)函數(shù)是:

Minimize(Cmax，￡Tj)

2求解多目標(biāo)并行機(jī)的NSGA2算法設(shè)計(jì)

非劣排序遺傳算法(NGSA2)是NSGA算法的第二個(gè)版本。在該算法中，程序從初始化種群開始，所有可行的解都在這一種群中隨機(jī)產(chǎn)生。每一代的選擇、交叉、變異都是該算法的重要步驟。

2.1編碼方法

這里采用一種3XN的矩陣來(lái)實(shí)現(xiàn)染色體的編碼。其方法描述如下：

例如有5個(gè)工件在2臺(tái)機(jī)器上加工，則它的編碼可表示成表 1 所列的形式。

表15個(gè)工件在2臺(tái)機(jī)器上加工的編碼

2.2選擇、交叉及變異操作

本文采用二元競(jìng)賽的選擇操作，即在種群中隨機(jī)選出8個(gè)解，然后兩兩進(jìn)行比較，得出一個(gè)最優(yōu)的解作為母體。我們選擇了經(jīng)典的單點(diǎn)交叉算法，在變異操作中，兩列隨機(jī)選取，并將選出的這兩列相互交換。圖1所示是NSGA2算法的流程圖。

圖1NSGA2算法的流程圖

3算法結(jié)果舉例及分析

采用上述描述的NSGA2算法的計(jì)算實(shí)例：加入加工的工件個(gè)數(shù)N=10,機(jī)器數(shù)M=5,種群大小為50,迭代次數(shù)為100，交叉概率為0.9,變異概率為0.1。則工件的加工時(shí)間如表2所列。圖2所示則是其Matlab仿真結(jié)果。

由圖2所示的仿真結(jié)果圖可得，其(258,883)，(270,860)，(277,798),(282,774)是所得到的最優(yōu)解。

表 2 工件的加工時(shí)間列表

圖2仿真結(jié)果

4結(jié)語(yǔ)

本文運(yùn)用NSGA2算法較好地求出了并行機(jī)的最優(yōu)解,由仿真分析圖得出，完工時(shí)間最小，總延遲時(shí)間最大。本算法有一定的使用價(jià)值，然而實(shí)際影響并行機(jī)調(diào)度的因素很多，希望在今后的研究中，能將并行機(jī)調(diào)度問(wèn)題與更多實(shí)際因素結(jié)合起來(lái)。

20211106_618650de15a3b__基于NSGA2算法的并行機(jī)多目標(biāo)調(diào)度問(wèn)題研究