引言

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

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

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

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

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

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

Minimize(Cmax，￡Tj)

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

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

2.1編碼方法

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

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

表15個工件在2臺機(jī)器上加工的編碼

2.2選擇、交叉及變異操作

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

圖1NSGA2算法的流程圖

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

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

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

表 2 工件的加工時間列表

圖2仿真結(jié)果

4結(jié)語

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

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