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

摘 要：针对并行机多目标调度问题，以完工时间和总延迟时间最小为目标函数建立了数学模型，从而将具有解决复杂组合优化问题的非劣排序遗传算法NSGA2应用于求解多目标并行机调度问题。文中详细描述了用NSGA2算法求解并行机调度问题的步骤，并通过Matlab仿真，表明了用NSGA2算法求解多目标并行机调度问题的可行性和有效性。

关键词：并行机；调度；NSGA2；多目标

中图分类号：TP18 文献标识码：A 文章编号：2095-1302（2013）10-0044-02

0 引 言

并行机调度问题是一个被广泛研究的优化问题，它具有丰富的研究内容，同时在生产调度、机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则进行调度，这样得到的调度结果一般不能满足实际环境的需求。当并行机数量、工件数量和优化目标增加时，传统的方法更不适合解决这类问题，因此，本文提出了非劣排序遗传算法来解决这类问题，同时还提出了一种特殊的染色体编码。

1 多目标并行机问题及数学模型

1.1 多目标并行机问题

多目标并行机调度问题可描述为：N个独立的工件要在M台相同的机器上加工。每个工件都包括加工时间dj、提交时间rj和工期pj。每个工件可以在M台机器中的任一台上加工。

1.2 数学模型

多目标并行机的一般假设为：一台机器一次只能加工一个工件，而且一个工件只能被加工一次。这样，如果选择完工时间Cmax和总延迟时间ΣTj为优化目标，则可建立的目标函数是：

Minimize（Cmax，ΣTj）

2 求解多目标并行机的NSGA2算法设计

非劣排序遗传算法 （NGSA2）是NSGA算法的第二个版本。在该算法中，程序从初始化种群开始，所有可行的解都在这一种群中随机产生。每一代的选择、交叉、变异都是该算法的重要步骤。

2.1 编码方法

这里采用一种3×N的矩阵来实现染色体的编码。其方法描述如下：

a（1，j） 第j列代表第j个工件，j=1，2，…，n

如果工件j在机器k上加工，则为k，否则为0

如果工件j在机器上加工的顺序为r，则为r，否则为0

例如有5个工件在2台机器上加工，则它的编码可表示成表1所列的形式。

2.2 选择、交叉及变异操作

本文采用二元竞赛的选择操作，即在种群中随机选出8个解，然后两两进行比较，得出一个最优的解作为母体。我们选择了经典的单点交叉算法，在变异操作中，两列随机选取，并将选出的这两列相互交换。图1所示是NSGA2算法的流程图。

3 算法结果举例及分析

采用上述描述的NSGA2算法的计算实例：加入加工的工件个数N=10，机器数M=5，种群大小为50，迭代次数为100，交叉概率为0.9，变异概率为0.1。则工件的加工时间如表2所列。图2所示则是其Matlab仿真结果。

由图2所示的仿真结果图可得，其（258，883），（270，860），（277，798），（282，774）是所得到的最优解。

4 结 语

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

参 考 文 献

[1] 刘民，吴澄，蒋新松. 用遗传算法解决并行多机调度问题[J].系统工程理论与实践，1998（1）：15-18.

[2] 王凌.车间调度及其遗传算法[M]. 北京：清华大学出版社，2003.

[3] 王万良，吴启迪.生产调度智能算法及其应用[M].北京：科技出版社，2007

[4] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithms： NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation，2002， 6（2）： 182-197.

[5] 刘民，吴澄，杨英杰. 并行机优化调度问题的新算法[J]. 清华大学学报：自然科学版， 1999（5）： 116-118.