基于置换Flow Shop调度问题的混合量子算法研究  

A Hybrid Quantum Algorithm for Permutation Flow Shop Scheduling Problems

作　　者：傅家旗[1] 叶春明[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《机械科学与技术》2010年第1期113-118,共6页Mechanical Science and Technology for Aerospace Engineering

基　　金：国家自然科学基金项目(70672110);上海市(第三期)重点学科项目(S30504)资助

摘　　要：安排合理有效的生产调度是生产活动能井然有序开展,生产资源得到最佳配置,运作过程简明流畅的有力保证。置换Flow Shop调度问题是流水车间的典型问题,同时也是NP-C难题。从问题出发,设计了由量子进化,最佳模式和其他优化技术所构成的混合量子算法(HQA)。HQA模仿量子行为迭代演化,将种群一分为二,种群1在量子作用和其他优化作用下,探索解空间。种群2保留最佳模式,提高了搜索的效率。经计算测试,验证了HQA在求解排序问题中的可行性,测试结果表明HQA具备了求解置换Flow Shop调度问题的能力。Arranging feasible and effective production scheduling enables production activities to unfold orderly, allows production resources to achieve best configuration and guarantees operation process to be simple and easy. Permutation Flow Shop scheduling problems are classical problems in Flow Shop, and they are also NP-C problems. Proceeding from the characteristics of the problems, hybrid quantum algorithm （HQA） is designed, which contains quantum evolution, best-mode evolution and other optimization techniques. HQA involves imitating quantum behaviors, dividing one population into two smaller populations. The first population explores solution space with the help of quantum evolution and other optimization technique, while the second population keeps best mode and enables HQA to search more efficiently. The feasibility of HQA in solving scheduling problems is demonstrated by tests. The results of several tests have shown the capability of HQA to solve permutation Flow Shop scheduling problems.

关 键 词：混合量子算法 优化 置换Flow Shop调度问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.4[自动化与计算机技术—控制科学与工程]