使用帕累托方法解决多目标平行机批调度问题
Multi-Objective Scheduling of Jobs on Parallel Batch Machines with Pareto Algorithm
DOI: 10.12677/CSA.2015.53009, PDF,   
作者: 王 超*, 贾兆红*, 宋 浩*：安徽大学计算机科学与技术学院，安徽 合肥
关键词: 多目标；批调度；帕累托解集；MOC；ΣCj ；Ulti-Objective； Batch Scheduling； Pareto Solution Set； MOC； ΣCj
摘要: 本文将批调度问题扩展到针对多目标(ΣCj, MOC)的批调度问题，这一调度问题分为两个阶段：分批和批调度。分批过程使用的是传统的BFLPT分批规则，得到分批结果；而批调度过程中，针对多个目标函数，本文提出了改进型进化算法Improved-NSGA-II来完成多目标的极化问题，同时列举了算法NSGA-II和SPEA2作为对比。通过仿真实验，分别从帕累托解集的数量、质量和算法运行时间三个方面对三种算法进行比较，从而证明算法Improved-NAGS-II的有效性。
Abstract: In this paper, the batch scheduling problem is extended to the multi-objective (ΣCj, MOC) batch scheduling problem. The scheduling problem is divided into two stages: batching and batch sche-duling. In the batching process using the traditional BFLPT batch rule to obtain the batching results; while in the batch scheduling process, for the multi-objective function, this paper not only presents improved evolutionary algorithm Improved-NSGA-II to solve the multi-objectives minimization problem, but also lists the algorithms of NSGA-II and SPEA2 as the contrast. Through the simulation experiment, to compare the three algorithms in three aspects, respectively from the number, the quality and the running time of Pareto solution set, this paper proves the effectiveness of the Improved-NAGS-II algorithm.
文章引用：王超, 贾兆红, 宋浩. 使用帕累托方法解决多目标平行机批调度问题[J]. 计算机科学与应用, 2015, 5(3): 62-73. https://dx.doi.org/10.12677/CSA.2015.53009

参考文献

[1] Uzsoy, R. (1994) Scheduling a single batch processing machine with nonidentical job sizes. International Journal of Production Research, 32, 1615-1635.
[2] Dupont, L. and Ghazvini, F.J. (1998) Minimizing makespan on a single batch processing machine with non-identical job sizes. European Journal of Automation, 32, 431-440.
[3] Melouk, S., Damodaran, P. and Chang, P.Y. (2004) Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 87, 141-147.
[4] 席裕庚, 柴天佑, 恽为民 (1996) 遗传算法综述. 控制理论与应用, 06, 697-708.
[5] 刘彦鹏 (2007) 蚁群优化算法的理论研究及其应用. 浙江大学, 杭州.
[6] 杨维, 李歧强 (2004) 粒子群优化算法综述. 中国工程科学, 05, 87-94.
[7] Dupont, L. and Dhaenens-Flipo, C. (2002) Minimizing the makespan on a batch machine with non-identical job sizes: An exact procedure. Computers & Operations Research, 29, 807-819.
[8] Deb, K., Pratap, A., Agarwal, S., et al. (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6, 182-197.
[9] Deb, K., Agrawal, S., Pratap, A. and Meyarivan, C. (2000) A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II. Proceedings of the Parallel Problem Solving from Nature VI Conference, 849- 858.
[10] Deb, K. and Srinivas, N. (1994) Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 221-248.
[11] Zitzle, E. and Thiele, L. (1999) Multiobjective evolutionary algorithms: A comparative case study and the Strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3, 257-271.
[12] 舒锋 (2011) SAGA算法在差异工件平行机批调度问题中的应用研究. 中国科学技术大学, 合肥.
[13] Zitzler, E., Laumams, M. and Thiele, L. (2001) SPEA2: Improving the strength Pareto evolutionary algorithm: Evolutionary Methods for Desigri. Optimization and Control with Applications to Industrial Problems, Athens, 95-100.
[14] 杜冰 (2011) 批处理机调度问题的模型与优化方法研究. 中国科学技术大学, 合肥.