›› 2019, Vol. 25 ›› Issue (第8): 1991-1999.DOI: 10.13196/j.cims.2019.08.013

Previous Articles     Next Articles

Improved small world genetic algorithm for intercell scheduling in network environment

  

  • Online:2019-08-31 Published:2019-08-31
  • Supported by:
    Project supported by the National Natural Science Foundation,China(No.51675206),and the Fundamental Research Funds for Central Universities,China(No.2016YXMS75).

基于改进小世界遗传算法的网络环境下跨单元调度

邹萌邦,刘琼+,尹勇   

  1. 华中科技大学数字制造装备与技术国家重点实验室
  • 基金资助:
    国家自然科学基金资助项目(51675206);中央高校基本科研业务费专项资金资助项目(2016YXMS75)。

Abstract: To improve overall utilizations of equipment,reduce production costs and quickly response to market demands,the intercell scheduling problem of particular worklpieces in cellular manufacturing system in network environment was studied,and an intercell scheduling model aiming at minimizing total costs and makespan was proposed.Due to poor global search ability and slow convergence speed of multi-objective genetic algorithm for solving large-scale scheduling problems,an improved small world genetic algorithm was designed.Through analysing the relationship between optimization objective and modularity of manufacturing network,an initial solution generation mechanism based on modularity was proposed to improve the quality of initial solution.A case was used to verify the significant correlation between optimization objective and modularity of manufacturing network,and modularity of manufacturing network could be used to improve the quality of initial solution.To compare with operation results of small world genetic algorithm and fast elitist Non-dominated Sorting Genetic Algorithm (NSGAⅡ),the convergence speed and solution quality of the improved small world genetic algorithm were better than other two algorithms.The research idea of this paper offered a new idea on using complex network characteristics in solving large-scale scheduling problem in the future.

Key words: cellular manufacturing system, intercell scheduling, complex network, small world genetic algorithm

摘要: 为了从总体上提高设备利用率、降低企业生产成本、快速响应市场需求,针对网络环境下单元制造系统中特殊工件需要跨单元加工的问题,建立了以最小化最大完工时间和总成本为优化目标的跨单元调度模型。针对多目标遗传算法求解大规模调度问题时全局搜索能力差、收敛速度慢等问题,设计了一种改进小世界遗传算法。通过分析优化目标和制造网络模块度的关系,提出基于制造网络模块度的初始解生成机制,对小世界遗传算法初始解进行改进。通过计算实例,说明优化目标与制造网络模块度呈显著相关性,将制造网络模块度用于初始解的生成可有效改进初始解的质量;通过与带精英策略的快速非支配排序遗传算法、小世界遗传算法的运算结果进行对比,得出改进小世界遗传算法在求解大规模调度问题时,收敛速度更快、求解质量更高的结论。

关键词: 单元制造系统, 跨单元调度, 复杂网络, 小世界遗传算法

CLC Number: