工业工程

工业工程 ›› 2012, Vol. 15 ›› Issue (3): 62-68.

• 专题论述 • 上一篇    下一篇

蚁群系统结合指派规则求解HFS调度问题

  

  1. 1.北京科技大学 经济管理学院，北京 100083；2.河南理工大学 经济管理学院，河南 焦作 454000；3. 广东海洋大学 工程学院，广东 湛江 524088
  • 出版日期:2012-06-30 发布日期:2012-07-21
  • 作者简介:屈国强（1970-），男，河南省人，博士研究生，主要研究方向为生产计划与调度、智能优化算法.

Hybrid Flow Shop Scheduling by Using Ant Colony System Combined with Dispatching Rules

  1. 1. School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China; 2.School of Economics and Management, Henan Polytechnic University, Jiaozuo 454000, China；3.Engineering College, Guangdong Ocean University, Zhanjiang 524088, China
  • Online:2012-06-30 Published:2012-07-21

摘要： 以NP-难的最小化时间表长为目标的混合流水车间调度问题为研究对象。把工件在第1阶段开始加工的排序问题转化为旅行商问题，采用蚁群系统求得初始排序；在第1阶段后各阶段采用工件先到先服务规则选择工件、最先空闲机器优先规则选择机器以构建初始工件的机器指派与排序；充分利用已知的机器布局和工件加工时间特点，确定工件加工瓶颈阶段，并以此为基础对工件的机器指派与排序进行改进。用Carlier和Neron设计的Benchmark算例仿真后与著名的NEH算法比较，表明这种算法是有效的。

关键词: 混合流水车间（HFS）, 调度, 蚁群算法, 指派规则

Abstract: The scheduling problem of hybrid flow shop with makespan as objective is discussed. In a hybrid flow shop, there are multiple machines at each stage and its scheduling problem is known to be NPhard. A new method is proposed in this paper. By the proposed method, for the first stage, the job sequencing is formulated as a traveling salesman problem and the ant colony method is used to solve it. For the following stages, dispatching rules, such as first come first served and first available machine first, are used to obtain an initial solution. Then, the initial solution is improved by identifying the bottleneck stage in taking the advantage of knowledge about job processing times and machine configurations. To evaluate the performance of the proposed algorithm, it is tested by using the Carlier and Nerons benchmark problems. It is shown that proposed method is effective and outperforms the wellknown NawazEnscoreHam (NEH) heuristic.

Key words: hybrid flow shop（HFS）, scheduling, ant colony system, dispatching rule