解决单机准时调度问题的混合粒子群算法  

Solving single machine total earliness and tardiness problem with common due date by Hybrid Particle Swarm Optimization

作　　者：段俊华[1] 潘全科[1] 

机构地区：[1]聊城大学计算机学院,山东聊城252059

出　　处：《计算机工程与应用》2009年第4期67-71,共5页Computer Engineering and Applications

基　　金：中国博士后科学基金No.20070410791

摘　　要：针对共同交货期给定的单机准时调度问题,提出了一种混合粒子群优化(Hybrid Particle Swarm Optimization,HPSO)算法。该算法采用了工件排列和开工时间混合的粒子编码方式及新的粒子产生策略,非常适合于求解开工时间不为零的调度问题。为了提高算法性能,将HPSO分别与模拟退火算法、局部搜索算法和迭代的局部搜索算法相结合,得到了三种混合算法:HPSO1、HPSO2和HPSO3。基于典型算例的试验表明:三种算法在求解质量和求解效率两方面均优于Hino等人的研究成果。A Hybrid Particle Swarm Optimization（HPSO） is presented for minimizing earliness and tardiness penalties in a single machine problem with a common due date.A representation,which consists of two components：the sequence itself and the idle time inserted at the beginning of the schedule,is employed,and a newly designed position updating method is developed.So,PSO can be easily applied to all classes of scheduling problems with the beginning of the schedule large than time zero.In order to improve solution quality,authors combine HPSO with simulated annealing,local search and iterated local search respectively,and three hybrid heuristics,HPSO1,HPSO2 and HPSO3,are derived.Computational results based on the well known benchmark suites in the literature show that all the hybrid heuristics produce slightly better results than the GA of Hino et al.

关 键 词：单机调度问题 粒子群优化算法 局部搜索 模拟退火算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]