作业车间调度问题的随机邻域交换算法  

Random neighborhood swapping algorithm for job shop scheduling problem

作　　者：崔健双[1] 李铁克[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083

出　　处：《系统工程学报》2010年第1期111-115,共5页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(70771008)

摘　　要：针对作业车间调度问题提出了一种随机邻域交换算法RNSA(random neighborhood swapping algorithm).算法由几个紧密衔接的执行阶段组成,其核心思想是如何设计生成多样性调度以及如何判断新调度的可行性.为此,采用了一种组合随机邻域交换策略并证明了一个调度可行性判定定理.为了验证算法的有效性,对一批Benchmark算例进行了测试并与国内外现有研究结果做出了比较.A random neighborhood swapping algorithm(RNSA) is presented.The algorithm is composed of several interrelated phases.Its key ideas are how to generate diversified solutions and how to judge if the new solutions are feasible.For doing that,we put forward a random neighborhood swapping policy and prove a theorem which indicates the calculability of a solution is the sufficient and necessary condition for its feasibility.Finally,the algorithm was tested with a batch of Benchmark problems and compared with exis...

关 键 词：作业车间调度问题 随机邻域交换 关键路径算法 

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