学文网摘 要：针对并行机多目标调度问题，以完工时间和总延迟时间最小为目标函数建立了数学模型，从而将具有解决复杂组合优化问题的非劣排序遗传算法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.
转载请注明出处学文网 » 基于NSGA2算法的并行机多目标调度问题研究