混合量子衍生进化规划算法及其在并行机拖期调度中的应用

A Hybrid Quantum-Inspired Evolutionary Programming and Its Application in Tardiness Identical Parallel Machines Scheduling

针对并行机调度问题的求解,提出一种新的混合量子衍生进化规划算法(Hybrid Quan-tum-Inspired Evolutionary Programming,HQEP)。目标函数是最小化所有工件的拖期总和。HQEP将量子进化算法中的量子位、线性叠加态和量子旋转门的概念引入到进化规划算法中。定义了新的用于调度问题的量子旋转角,使个体向更好的解靠近。此外,针对并行机问题本身,改进了个体的编码方式和新的变异方法。为了验证算法的有效性和收敛性,将HQEP算法应用于同等并行机调度拖期问题的求解并加以不同规模的算例进行仿真实验。结果显示,即使在小种群情况下,所得解均优于进化规划求得的解。

In this paper, a hybrid quantum-inspired evolutionary programming （HQEP） is proposed for identical parallel machines scheduling. The objective is to minimize the total tardiness of all jobs. In HQEP, the concept and principles of quantum computing, such as a quantum bit and superposition of states, are combined with evolutionary programming, and the Q-gate is introduced as a variation operator to drive the individuals toward better solutions. Moreover, an improved representation structure of individuals and mutation operator is proposed for scheduling problems in HQEP. Finally, an illustrative experiment is carried out on different scales of randomly generated test problems. Computational results show that HQEP outperforms evolutionary programming, even with a small population.