基于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台机器上加工的编码

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 工件的加工时间列表

图2仿真结果

4结语

本文运用NSGA2算法较好地求出了并行机的最优解,由仿真分析图得出，完工时间最小，总延迟时间最大。本算法有一定的使用价值，然而实际影响并行机调度的因素很多，希望在今后的研究中，能将并行机调度问题与更多实际因素结合起来。

20211106_618650de15a3b__基于NSGA2算法的并行机多目标调度问题研究