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

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