基于离散量子微粒群优化的作业车间调度

Discrete quantum-behaved particle swarm optimization for job-shop scheduling

针对强非确定性多项式难的作业车间调度(JSP)问题,提出一种离散量子微粒群优化算法(DQPSO).该算法基于量子态波函数描述微粒群粒子位置,结合遗传算法中的交叉、变异操作,采用随机键编码方法对连续空间内的解进行离散化,使得DQPSO能够直接用于求解车间生产调度这类组合优化问题.另外,针对JSP的复杂性,通过引入2层结构的局部搜索策略,构造在局部优化解附近不同搜索半径的微粒,增强算法的搜索能力,进一步提高解的多样性和寻优质量.应用结果表明,对大部分作业车间调度测试算例,DQPSO表现出更有效的寻优性能.

A novel discrete quantum-behaved particle swarm optimization （DQPSO） approach was proposed to address Job-shop scheduling （JSP） problem. JSP is a complex combinatorial optimization problem with many variations, and it is strong nondeterministic polynomial time （NP）-complete. The proposed DQPSO approach utilized the principle of quantum-PSO and described the particle positions with quantum wave function. Crossover and mutation operators in GA were involved which makes DQPSO applicable for searching in combinatorial space directly. In addition, a new two-layer local searching algorithm was also incorporated into the DQPSO algorithm. The two layer local searching algorithm randomly generated new particles around the local optimums, which in turn updated solutions with high quality and diversity. The application demonstrated that DQPSO can achieve better results on most benchmark scheduling problems.