解决作业车间调度问题的改进蚁群优化算法

应用科学学报 ›› 2010, Vol. 28 ›› Issue (2): 182-188.

解决作业车间调度问题的改进蚁群优化算法

1. 西安理工大学计算机科学与工程学院，西安710048
2. 西安理工大学机械与精密仪器工程学院，西安710048

收稿日期:2009-05-21 修回日期:2009-11-11 出版日期:2010-03-30 发布日期:2010-03-22
作者简介:张志强，博士生，讲师，研究方向：智能计算、网络化制造，E-mail: chinazzq@126.com；张璟，教授，博导，研究方向：人工智能、网络化制造，E-mail: zhangjing@xaut.edu.cn

Improved Ant Colony Optimization Algorithm for Job Shop Scheduling Problem

1. Faculty of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China
2. Faculty of Mechanical and Precision Instrument Engineering, Xi’an University of Technology, Xi’an 710048, China

Received:2009-05-21 Revised:2009-11-11 Online:2010-03-30 Published:2010-03-22
Supported by:
国家“863”高技术研究发展计划基金(No. 2007AA010305)资助

摘要/Abstract

摘要：

针对作业车间调度问题，提出一种改进的蚁群优化算法. 首先设计禁忌表以产生活动调度，然后对传统的蚁群优化算法进行简化，并提出一种新型优先规则作为启发式信息. 为增强算法的收敛性和提高求解质量，引入基于作业车间调度问题邻域结构的局部搜索. 实验表明该文算法有效.

关键词: 作业车间调度, 蚁群优化算法, 优先规则, 邻域结构

Abstract:

An improved ant colony optimization algorithm for job shop scheduling problems is proposed in this paper. The tabu list which can generate active schedule is designed. The traditional ant colony optimization algorithm is hen simplified, and a new priority rule proposed to serve as heuristic information. A local search procedure based on the neighborhood structure of job shop scheduling problem is introduced to improve convergence and solution quality of the proposed algorithm. Experiments show effectiveness of the proposed algorithm.

Key words: job shop scheduling, ant colony optimization, priority rule, neighborhood structure

中图分类号:

TN301

张志强，张璟，张翔，李淑娟. 解决作业车间调度问题的改进蚁群优化算法[J]. 应用科学学报, 2010, 28(2): 182-188.

ZHANG Zhi-qiang, ZHANG Jing, ZHANG Xiang, LI Shu-juan. Improved Ant Colony Optimization Algorithm for Job Shop Scheduling Problem[J]. Journal of Applied Sciences, 2010, 28(2): 182-188.