Job-Shop调度问题的量子蚁群算法求解

摘要

针对最小化最大完工时间的作业车间调度问题,提出了一种量子蚁群调度算法.该算法结合了量子计算中量子旋转门的量子信息和蚁群寻优的特点,通过作业车间调度问题的析取图表示,将原问题转换为求解析取图的关动路径,并利用量子蚁群算法进行求解.采用该算法对作业车间调度问题的基准数据进行测试,仿真结果表明了该算法的可行性和有效性.%Aiming at JSP with the criterion for minimizing the maximum completion time( makespan) , this paper proposed ahybrid algorithm, which combined the quantum information rules of quantum rotation gate with the characteristics of ant colonyoptimization. It transformed solving makespan into finding the critical path in disjunctive graph based on the representation ofJSP, then used QACO algorithm to find the critical path. The simulation results for benchmark problems show the feasibilityand effectiveness of QACO compared to classical ant colony optimization algorithm.