• CN:11-2187/TH
  • ISSN:0577-6686

›› 2010, Vol. 46 ›› Issue (11): 156-164.

• 论文 • 上一篇    下一篇

基于改进非支配排序遗传算法的多目标柔性作业车间调度

张超勇;董星;王晓娟;李新宇;刘琼   

  1. 华中科技大学数字制造装备与技术国家重点实验室
  • 发布日期:2010-06-05

Improved NSGA-II for the Multi-objective Flexible Job-shop Scheduling Problem

ZHANG Chaoyong;DONG Xing;WANG Xiaojuan;LI Xinyu;LIU Qiong   

  1. State Key Laboratory of Digital Manufacturing Equipment and Technology,Huazhong University of Science and Technology
  • Published:2010-06-05

摘要: 采用多目标进化算法解决具有工件释放时间、工件目标差异的柔性作业车间调度问题。依据实际制造系统中存在较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本性能指标,建立多目标柔性作业车间调度模型。针对柔性作业车间调度问题的特点,设计一种扩展的基于工序的编码及其主动调度的解码机制,以及初始解产生机制和有效的交叉、变异操作;针对非支配排序遗传算法(Non-dominated sorting genetic algorithm II, NSGA-II)在非支配解排序和精英选择策略方面的不足,设计一种改进的非支配排序遗传算法,应用改进的算法求解柔性作业车间调度问题得到一组Pareto解集,并运用层次分析法选出最优妥协解。通过测试基准和模拟实际生产的实例,验证提出算法的可行性和有效性。

关键词: 层次分析法, 多目标进化算法, 非支配排序遗传算法, 柔性作业车间调度

Abstract: An improved multi-objective evolutionary algorithm is proposed for solving the flexible job-shop scheduling problem (FJSP) with released time and job-oriented multi-objective. The multi-objective FJSP optimization model is put forward, in which the makespan, the mean flow-time, total tardiness, total workload of machines, workload of the bottleneck machine and production cost widely concerned in complex manufacturing system are considered. According to the characteristics of the FJSP, an extended operation-based encoding and an active scheduling decoding mechanism are presented, an initial solution generation mechanism, and two effective crossover and mutation operations are designed for the genetic algorithm. In order to ensure convergence and the diversity of the solutions, an improved non-dominated sorting genetic algorithm (NSGA-II) is proposed. A set of Pareto solutions are obtained by the improved NSGA-II, and the analytic hierarchy process (AHP) approach is used to select the optimal compromise solution. The approach is tested on instances taken from the literature and practical data. The computation results validate the effectiveness of the proposed algorithm

Key words: Analytical hierarchy process, Flexible job-shop scheduling problem, Multi-objective evolutionary algorithm, Non-dominated sorting genetic algorithm II

中图分类号: