基于NSGA2算法的并行机多目标调度问题研究
扫描二维码
随时随地手机看文章
引言
并行机调度问题是一个被广泛研究的优化问题，它具有丰富的研究内容，同时在生产调度、机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则进行调度，这样得到的调度结果一般不能满足实际环境的需求。当并行机数量、工件数量和优化目标增加时，传统的方法更不适合解决这类问题，因此，本文提出了非劣排序遗传算法来解决这类问题，同时还提出了一种特殊的染色体编码。
1多目标并行机问题及数学模型
1.1多目标并行机问题
多目标并行机调度问题可描述为:N个独立的工件要在M台相同的机器上加工。每个工件都包括加工时间林提交时间r和工期pj.每个工件可以在m台机器中的任一台上加工。
1.2数学模型
多目标并行机的一般假设为：一台机器一次只能加工一个工件，而且一个工件只能被加工一次。这样，如果选择完工时间Cmax和总延迟时间£Tj为优化目标，则可建立的目标函数是:
Minimize(Cmax，£Tj)
2求解多目标并行机的NSGA2算法设计
非劣排序遗传算法(NGSA2)是NSGA算法的第二个版本。在该算法中，程序从初始化种群开始，所有可行的解都在这一种群中随机产生。每一代的选择、交叉、变异都是该算法的重要步骤。
2.1编码方法
这里采用一种3XN的矩阵来实现染色体的编码。其方法描述如下：
例如有5个工件在2台机器上加工，则它的编码可表示成表 1 所列的形式。
表15个工件在2台机器上加工的编码
|
项目 |
编码 |
|||
|
工件号 |
1 |
2 3 |
4 |
5 |
|
机器号 |
1 |
21 |
1 |
2 |
|
在机器上的顺序 |
2 |
1 1 |
3 |
2 |
2.2选择、交叉及变异操作
本文采用二元竞赛的选择操作，即在种群中随机选出8个解，然后两两进行比较，得出一个最优的解作为母体。我们选择了经典的单点交叉算法，在变异操作中，两列随机选取，并将选出的这两列相互交换。图1所示是NSGA2算法的流程图。
图1NSGA2算法的流程图
3算法结果举例及分析
采用上述描述的NSGA2算法的计算实例：加入加工的工件个数N=10,机器数M=5,种群大小为50,迭代次数为100，交叉概率为0.9,变异概率为0.1。则工件的加工时间如表2所列。图2所示则是其Matlab仿真结果。
由图2所示的仿真结果图可得，其(258,883)，(270,860)，(277,798),(282,774)是所得到的最优解。
表 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仿真结果
4结语
本文运用NSGA2算法较好地求出了并行机的最优解,由仿真分析图得出，完工时间最小，总延迟时间最大。本算法有一定的使用价值，然而实际影响并行机调度的因素很多，希望在今后的研究中，能将并行机调度问题与更多实际因素结合起来。
20211106_618650de15a3b__基于NSGA2算法的并行机多目标调度问题研究
下载文档
