基于量子状态转移算法的作业车间调度问题  

JOB SHOP SCHEDULING PROBLEM BASED ON QUANTUM STATE TRANSITION ALGORITHM

作　　者：吴贝贝 李喆 Wu Beibei;Li Zhe(College of Electrical Engineering,Xinjiang University,Urumqi 830047,Xinjiang,China;The Center of Network and Information Technology,Xinjiang University,Urumqi 830046,Xinjiang,China)

机构地区：[1]新疆大学电气工程学院,新疆乌鲁木齐830047 [2]新疆大学网络与信息技术中心,新疆乌鲁木齐830046

出　　处：《计算机应用与软件》2021年第7期232-239,共8页Computer Applications and Software

基　　金：国家自然科学基金项目(51767022,51967019);新疆维吾尔自治区自然科学基金项目(2019D01C082)。

摘　　要：针对传统优化方法存在种群多样性受限、寻优能力差等问题,提出一种量子状态转移算法求解作业车间调度问题。构建以最大完工时间最小为目标的数学模型;利用量子状态转移算法进行问题求解,通过状态转移算法中的旋转、伸缩、平移和坐标变换操作对量子旋转角进行更新,从而实现状态转移框架下的量子旋转、量子伸缩、量子平移和量子坐标变换操作;为提高算法的局部和全局探索能力,提出将移位解码和位置交换编码相结合对解空间进行映射,并提出非局部最优解容忍机制可有效避免算法早熟及丰富解的多样性以提高收敛精度。通过对12种基准算例进行仿真,结果表明,该算法与传统算法相比可有效缩短最大完工时间且具有精度高、寻优能力强及可跳出局部最优等优点。In order to solve the problems of limited population diversity and poor optimization ability in traditional optimization methods,a quantum state transition algorithm is proposed to solve the job shop scheduling problem.The mathematical model was constructed with the goal of minimizing the maximum completion time,and the quantum state transition algorithm was used to solve the problem,and the quantum rotation angle was updated by the rotation,expansion,translation and axesion operations in the state transition algorithm,so as to realize the quantum rotation,quantum expansion,quantum translation and quantum axesion operations in the framework of state transition.In order to improve the local and global exploration ability of the algorithm,the shift decoding and position exchange coding were combined to map the solution space,and the non-local optimal solution tolerance mechanism was proposed to effectively avoid the prematurity of the algorithm and enrich the diversity of solutions in order to improve the convergence accuracy.Through the simulation of 12 reference examples,the results show that compared with the traditional algorithm,the quantum state transition algorithm can effectively shorten the maximum completion time and has the advantages of high precision,strong optimization ability and can jump out of local optimization.

关 键 词：状态转移算法 量子计算 量子状态转移算法 作业车间调度 容忍机制 

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