上海交通大学学报(自然版)

• 自动化技术、计算机技术 • 上一篇    下一篇

应用混合蚁群算法求解并行批处理机组批与调度问题

郭乘涛,江志斌
  

  1. (上海交通大学 机械与动力工程学院, 上海 200240)
  • 收稿日期:2009-11-24 修回日期:1900-01-01 出版日期:2010-08-31 发布日期:2010-08-31

A Hybrid Ant Colony Optimization Method for Scheduling Jobs on Parallel atch Machines

GUO Chengtao,JIANG Zhibin

  

  1. (School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2009-11-24 Revised:1900-01-01 Online:2010-08-31 Published:2010-08-31

摘要: 晶圆制造系统的批处理机具有长加工时间的特征, 其调度性能指标对车间总体绩效有重要影响.批处理机调度分为组批与批次调度.针对工件的动态到达特性导致组批困难,提出了一种混合型蚁群算法.利用该算法的全局并行搜索能力对工件进行组批, 并使用BATC算法对批次进行调度, 可以解决多产品并行批处理机调度问题.以工件总拖期最小为性能指标, 通过实例仿真, 对蚁群算法性能进行分析评价和比较. 结果表明,所提出的算法具有有效性和实用性.

关键词: 蚁群算法, 调度, 批处理

Abstract: In wafer fabrication system, the performance measures of batch processing machine’s schedule have significant impact on plant performance because these machines have time consuming feature. Two phases, batches forming and batches scheduling, are needed to schedule batch machines. The difficulties lie in the former phase because of the dynamic arriving time of jobs. A hybrid ant colony optimization (ACO) algorithm was proposed, which batches the jobs by using the global and parallel searching mechanism of ACO, and schedules these batches by BATC algorithm.With respect to a due datebased objective (minimizing total weighted tardiness), the proposed algorithm was applied to schedule parallel batch process machine with incompatible job families. The performance of the hybridACO algorithm was evaluated and compared with that of other approach through simulations, and the results show that the proposed algorithm can generate quite effective and practical schedule.

中图分类号: