计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (6): 52-55.DOI: 10.3778/j.issn.1002-8331.2010.06.015

• 研究、探讨 • 上一篇    下一篇

离散微粒群算法求解批量流水线调度问题

潘玉霞,潘全科,桑红燕,武 磊   

  1. 聊城大学 计算机学院,山东 聊城 252059
  • 收稿日期:2008-09-22 修回日期:2008-12-01 出版日期:2010-02-21 发布日期:2010-02-21
  • 通讯作者: 潘玉霞

Discrete particle swarm optimization algorithm for lot-streaming flow shop problem

PAN Yu-xia,PAN Quan-ke,SANG Hong-yan,WU Lei   

  1. School of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China
  • Received:2008-09-22 Revised:2008-12-01 Online:2010-02-21 Published:2010-02-21
  • Contact: PAN Yu-xia

摘要: 提出了解决批量流水线调度问题的离散微粒群优化算法。该算法采用了基于工序的编码方式,设计了新的粒子生成公式,从而使微粒群算法可以直接应用于调度问题。同时,针对微粒群算法容易陷入局部最优的缺陷,将其与模拟退火算法结合,得到了改进的微粒群优化算法。仿真实验表明了上述算法的有效性。

关键词: 批量流水线调度, 微粒群算法, 模拟退火算法

Abstract: A Discrete Particle Swarm Optimization(DPSO) algorithm is presented for the Lot-streaming Flow Shop Problem(LFSP).The natural encoding scheme based on job permutation and newly designed methods are adopted to produce new individual.This makes PSO more suitable for scheduling problems.Pure PSO may produce premature and poor results.Improved PSO is put forward by combining the PSO and SA.Simulation results show the effectiveness of the above algorithms.

Key words: lot-streaming flow shop, particle swarm optimization algorithm, simulated annealing algorithm

中图分类号: