一种新的混合优化算法及其在车间调度中的应用  

A New Hybrid Optimization Algorithm and Its Application in Job Shop Scheduling

作　　者：闫利军[1] 李宗斌[1] 卫军胡[1] 杜轩[1] 

机构地区：[1]西安交通大学机械制造系统工程国家重点实验室,西安710049

出　　处：《自动化学报》2008年第5期604-608,共5页Acta Automatica Sinica

基　　金：陕西省科学技术研究发展计划项目(2006K05-G20);陕西省自然科学基础研究计划项目(2007F41)资助~~

摘　　要：提出了一种解决车间调度问题的新方法,该方法将序优化思想融入巢分区算法框架,采用"序比较"的方法进行算法的局部寻优."序"的指数收敛性加快了巢分区算法的局部收敛速度,从而提高了算法整体的优化效率.最优计算量分配技术则依据在线数据对计算量进行合理的分配.进一步提高算法的收敛速度和结果的可靠性.混合算法继承了巢分区算法的全局搜索特性以及序优化的快速收敛性.用该算法解决标准Jobshop调度问题,并与序优化方法和模拟退火算法进行比较,发现本文算法在收敛速度与优化质量方面均优于这些算法.This paper proposes a new hybrid optimization algorithm for solving stochastic job shop scheduling problems, which integrates the idea of ordinal optimization into the framework of nested partitions （NP） algorithm. Ordinal comparison method is used to perform local search of NP and its exponential convergence rate improves the efficiency of local search and thereby the efficiency of global search greatly. And the optimal computing budget allocation technique further improves the convergence rate and reliability of the optimization result. The new algorithm retains the feature of global search of nested partitions and fast convergence of ordinal optimization. The algorithm is used to solve job shop scheduling benchmark problems. The results of numerical simulations, which are compared with those of other well-known algorithms, show better performance of the proposed algorithm.

关 键 词：随机车间调度 序优化 最优计算量分配 巢分区 

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