Abstract: 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.

Key words: single machine problem, Particle Swarm Optimization（PSO）, local search, simulated annealing algorithm

摘要： 针对共同交货期给定的单机准时调度问题，提出了一种混合粒子群优化（Hybrid Particle Swarm Optimization，HPSO）算法。该算法采用了工件排列和开工时间混合的粒子编码方式及新的粒子产生策略，非常适合于求解开工时间不为零的调度问题。为了提高算法性能，将HPSO分别与模拟退火算法、局部搜索算法和迭代的局部搜索算法相结合，得到了三种混合算法：HPSO1、HPSO2和HPSO3。基于典型算例的试验表明：三种算法在求解质量和求解效率两方面均优于Hino等人的研究成果。

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