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

Random neighborhood swapping algorithm for job shop scheduling problem

针对作业车间调度问题提出了一种随机邻域交换算法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...