基于NSGA2算法的并行機(jī)多目標(biāo)調(diào)度問題研究
引言
并行機(jī)調(diào)度問題是一個被廣泛研究的優(yōu)化問題，它具有豐富的研究內(nèi)容，同時在生產(chǎn)調(diào)度、機(jī)械制造等方面有廣泛的實際應(yīng)用價值。但是在實際操作中，人們常常按經(jīng)驗法則進(jìn)行調(diào)度，這樣得到的調(diào)度結(jié)果一般不能滿足實際環(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個獨立的工件要在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的矩陣來實現(xiàn)染色體的編碼。其方法描述如下：
例如有5個工件在2臺機(jī)器上加工，則它的編碼可表示成表 1 所列的形式。
表15個工件在2臺機(jī)器上加工的編碼
|
項目 |
編碼 |
|||
|
工件號 |
1 |
2 3 |
4 |
5 |
|
機(jī)器號 |
1 |
21 |
1 |
2 |
|
在機(jī)器上的順序 |
2 |
1 1 |
3 |
2 |
2.2選擇、交叉及變異操作
本文采用二元競賽的選擇操作，即在種群中隨機(jī)選出8個解，然后兩兩進(jìn)行比較，得出一個最優(yōu)的解作為母體。我們選擇了經(jīng)典的單點交叉算法，在變異操作中，兩列隨機(jī)選取，并將選出的這兩列相互交換。圖1所示是NSGA2算法的流程圖。
圖1NSGA2算法的流程圖
3算法結(jié)果舉例及分析
采用上述描述的NSGA2算法的計算實例：加入加工的工件個數(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 工件的加工時間列表
|
工件號 |
月 |
r |
d |
|
1 |
68 |
97 |
72 |
|
2 |
71 |
76 |
78 |
|
3 |
74 |
79 |
83 |
|
4 |
78 |
58 |
91 |
|
5 |
81 |
38 |
97 |
|
6 |
84 |
40 |
103 |
|
7 |
87 |
20 |
109 |
|
8 |
91 |
120 |
118 |
|
9 |
94 |
1 |
125 |
|
10 |
97 |
102 |
131 |
圖2仿真結(jié)果
4結(jié)語
本文運用NSGA2算法較好地求出了并行機(jī)的最優(yōu)解,由仿真分析圖得出，完工時間最小，總延遲時間最大。本算法有一定的使用價值，然而實際影響并行機(jī)調(diào)度的因素很多，希望在今后的研究中，能將并行機(jī)調(diào)度問題與更多實際因素結(jié)合起來。
20211106_618650de15a3b__基于NSGA2算法的并行機(jī)多目標(biāo)調(diào)度問題研究
下載文檔
