一种求解作业车间调度的混合粒子群算法*

针对车间作业调度问题，提出了一种混合了知识进化算法和粒子群优化的算法。算法主要是结合知识进化算法的进化选择机制和粒子群优化的局部快速收敛性特性，首先让粒子替代知识进化算法中的进化个体，在群体空间中按粒子群优化规则寻找局部最优，然后根据知识进化算法的全局选择机制寻找全局最优，最后，将车间作业调度问题的特点融入到所提出的混合算法中求解问题。采用基准数据进行测试的仿真实验，并比对标准遗传算法，结果表明所提算法的有效性。

Hybrid particle swarm optimization for Job-Shop scheduling

A new hybrid algorithm is introduced into solving job shop scheduling problems, which combines knowledge evolution algorithm(KEA) and particle swarm optimization(PSO) algorithm. By the mechanism of KEA, its global search ability is fully utilized for finding the global solution. By the operating characteristic of PSO, the local search ability is also made full use. Through the combination, better convergence property is obtained for job shop scheduling with the criterion of minimization the maximum completion time (makespan). Simulation results based on well-known benchmarks and comparisons with standard genetic algorithm demonstrate the feasibility and effectiveness of the proposed hybrid algorithm.