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

Solving Job-Shop scheduling problem by quantum-inspired ant colony optimization algorithm

作　　者：刘长平[1,2] 叶春明[1] 唐海波[1] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]淮阴工学院,江苏淮安223001

出　　处：《计算机应用研究》2011年第12期4507-4509,共3页Application Research of Computers

基　　金：国家教育部人文社会科学规划基金资助项目(10YJA630187);高校博士点专项科研基金项目(20093120110008);上海市重点学科建设资助项目(S30504)

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

关 键 词：作业车间调度 量子蚁群算法 析取图 关键路径 最大完工时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O22[自动化与计算机技术—计算机科学与技术]