转移资源受限多项目调度的改进量子遗传算法

Improved Quantum Genetic Algorithm for the Resource Constrained Multi-Project Scheduling Problem with Transfer Times

传统的资源受限多项目调度问题没有考虑资源在项目内部以及项目之间的转移时间,针对考虑了资源转移的多项目调度问题提出了一种改进的量子遗传算法。算法采用改进的并行进度生成机制,结合多项目任务优先权以及资源转移优先权设计了基于角度的编码方法,该编码能够转换成双链随机键编码,增加了种群的多样性,给出了量子旋转门以及随机组合量子非门算子,同时将混沌变异引入量子遗传算法中,避免了早熟现象。设计了相应的算例,并将本文算法与各种优先规则和普通遗传算法的求解效果进行了比较。实验表明:改进的量子遗传算法能够有效地求解转移资源受限多项目调度问题,并且求解质量和时间均优于普通遗传算法。

Traditional resource constrained multi-project scheduling problem do not consider the resource transfer times within or between projects,an improved quantum genetic algorithm is presented to solve the resource constrained multi-project scheduling problem with transfer times.The modified parallel schedule generation scheme is used to construct project schedules.An angle-based coding method is devised which can represent both task and resource transfer priority values,each chromosome can be converted into two chains of random key representation to increase the diversity of the population.The quantum rotation gate and quantum non-gate operations are given,meanwhile the chaotic mutation is introduced to avoid the premature.An example is designed and the proposed algorithm with priority rules algorithm,the common genetic algorithm are all tested on the problem.The experimental results show that：the improved quantum genetic algorithm can effectively solve the resource constrained multi-project scheduling problem with transfer times,and the solution quality and time are better than common genetic algorithm.