求解作业车间调度问题的并行模拟退火算法  

Parallel simulated annealing algorithm for solving job-shop scheduling problem

作　　者：吴大为[1] 陆涛栋[1] 刘晓冰[2] 孟永胜[2] 

机构地区：[1]大连理工大学应用数学系,辽宁大连116024 [2]大连理工大学CIMS中心,辽宁大连116024

出　　处：《计算机集成制造系统》2005年第6期847-850,共4页Computer Integrated Manufacturing Systems

基　　金：国家863/CIMS主题资助项目(2002AA414710)。~~

摘　　要：针对作业车间调度问题,提出了一种并行模拟退火算法。该算法实行群体搜索策略,由此定义了邻域搜索规则来增强个体的搜索能力,并运用马尔科夫链分析了算法的全局收敛性。该算法在一些基准问题上得到了检验,通过与其他常规方法的比较,证明此算法可提高搜索效率,改进收敛性能。A Parallel Simulated Annealing(PSA) algorithm was proposed for the job-shop scheduling problem. In the scheduling algorithm, the whole search strategy was applied and a rule of neighborhood search was defined to improve the performance of the individual search. Furthermore the global convergence of the algorithm was analyzed via Markov chain. The algorithm was verified on several standard benchmark problems. Compared with other traditional approaches, the efficiency of search has been increased and the convergence has been improved.

关 键 词：模拟退火 作业车间调度 全局收敛 马尔科夫链 

分 类 号：O244[理学—计算数学] TP18[理学—数学]