北京航空航天大学学报 ›› 2017, Vol. 43 ›› Issue (2): 410-416.doi: 10.13700/j.bh.1001-5965.2016.0103

• 论文 • 上一篇    

基于混合多智能体遗传算法的作业车间调度问题研究

李小涛, 彭翀   

  1. 北京航空航天大学 机械工程及自动化学院, 北京 100083
  • 收稿日期:2016-01-26 出版日期:2017-02-20 发布日期:2016-06-29
  • 通讯作者: 彭翀,E-mail:pch@buaa.edu.cn E-mail:pch@buaa.edu.cn
  • 作者简介:李小涛,男,硕士研究生。主要研究方向:智能优化算法理论及其应用;彭翀,男,博士,高级实验师。主要研究方向:制造过程优化方法研究及应用、数控装备可靠性技术。
  • 基金资助:
    国家重大科技专项(2015ZX04005005)

Hybrid multiagent genetic algorithm for job shop scheduling problem

LI Xiaotao, PENG Chong   

  1. School of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2016-01-26 Online:2017-02-20 Published:2016-06-29
  • Supported by:
    National Science and Technology Major Project (2015ZX04005005)

摘要: 针对作业车间调度问题(JSP)的非确定性多项式特性与解空间分布的大山谷属性,本文提出一种多智能体遗传算法(MAGA)与自适应模拟退火算法(ASA)的混合优化算法,用于寻找最大完工时间最短的调度。首先,将每个染色体视作独立的智能体并采用工序编码方式随机初始化每个智能体,结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子,进而利用一定数量智能体进行全局搜索,找到多个适应度较高的可行解。其次,为避免算法陷入局部最优,采用ASA对每个智能体开展局部寻优。最后,通过基准测试库中典型实例的计算结果验证了该算法的有效性。

关键词: 作业车间调度(JSP), 多智能体, 遗传算法, 邻居交互算子, 自适应模拟退火算法(ASA)

Abstract: For the NP-hard characteristic of job shop scheduling problem (JSP) and big valley property of its solution space, this paper proposes a hybrid algorithm based multiagent genetic algorithm (MAGA) and adaptive simulated annealing algorithm (ASA) to obtain the minimal makespan schedule. First, each chromosome is regarded as independent agent which is randomly initialized under condition of operation-based encoding method. Combined with multiagent cooperation and competition theory, a neighborhood interaction operator is designed to realize the interaction between agents, and then a certain number of agents are utilized to do global searching to find several individuals with high fitness. Second, in order to prevent the algorithm from falling into local optimum, ASA is adopted to carry out local optimization for each agent. Finally, the effectiveness of the proposed hybrid algorithm is verified by the computational results of typical problems from benchmark library.

Key words: job shop scheduling, multiagent (JSP), genetic algorithm, neighborhood interaction operator, adaptive simulated annealing algorithm (ASA)

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发