• CN:11-2187/TH
  • ISSN:0577-6686

›› 2006, Vol. 42 ›› Issue (2): 129-134.

• 论文 • 上一篇    下一篇

基于粒子群优化的开放式车间调度

高亮;高海兵;周驰   

  1. 华中科技大学工业及制造系统工程系
  • 发布日期:2006-02-15

PSO BASED SCHEDULING ALGORITHM FOR OPEN SHOP SCHEDULING PROBLEM

GAO Liang;GAO Haibing;ZHOU Chi   

  1. Department of Industrial & Manufacturing System Engineering, Huazhong University of Science & Technology
  • Published:2006-02-15

摘要: 开放式车间调度(OSP)是重要的调度问题,它在制造领域中的应用非常广泛。优化调度算法是调度理论的重要研究内容。基于人工智能的元启发式算法是解决该问题的常用方法。分析了一种新的元启发式算法——粒子群优化(PSO)在信息共享机制上的缺陷,提出新的基于群体智能的信息共享机制。在该信息共享机制的基础上,设计新的基于PSO的元启发式调度算法——PSO-OSP。该算法利用问题的邻域知识指导局部搜索,可克服元启发式算法随机性引起的盲目搜索。该算法应用于开放式车间调度问题的标准测试实例。仿真结果显示,PSO-OSP算法在加快收敛速度的同时提高了开放式车间调度解的质量

关键词: 开放式车间调度, 粒子群优化, 邻域知识, 信息共享机制

Abstract: Open shop scheduling is an important scheduling problem and has wide engineering applications in manufacturing. Optimization algorithms are important research content in scheduling theory. Artificial intelligence based meta-heuristic algorithms are effective methods for this problem. A new meta-heuristic based on particle swarm optimization (PSO) is proposed to obtain optimized open shop schedule. First, the limitation of information sharing mechanism in PSO model is discussed, and then new information sharing mechanism based on swarm intelligence is put forward. Based on the new infor-mation sharing mechanism, a new PSO based on scheduling algorithm–PSO-OSP is proposed. The proposed algorithm util-izes neighborhood knowledge to direct its local search proce-dure which can overcome the blindness or randomness intro-duced by meta-heuristics. Finally, OSP benchmarks are used to test its efficiency. Simulation results show that the new proposed algorithm can improve the convergence speed and obtain optimized open shop schedules.

Key words: Neighborhood knowledge, Information sharing mechanism, Open shop scheduling, Particle swarm optimization

中图分类号: