Abstract: Aiming at the job shop scheduling optimization problem with objective of minimizing maximum completion time,a neighborhood search genetic algorithm based on idle time was proposed.Through analyzing the different decoding methods,an idle time-based neighborhood structure and its search method were designed.The idle time between two adjacent operations on the same machine was analyzed,and the method of fully finding critical operation's machine idle time was provided.To find the machine idle time for back and forth of critical operation,the neighborhood search was realized by shifting critical operation to idle time position on condition of guaranteeing feasible solution.The operation shifting conditions to ensure the feasible solution were given with any two operation positions on the same machine.The idle-time-based neighborhood search was implanted in the genetic algorithm,and its effectiveness was verified by using typical examples.

Key words: job shop scheduling, neighborhood search, idle time, genetic algorithms

摘要： 针对最小化最大完工时间的作业车间调度优化问题,提出一种基于空闲时间的邻域搜索遗传算法。通过对不同解码方式的分析,设计了一种基于空闲时间的邻域结构及其邻域搜索方法|分析了同一机器上相邻两工序间的空闲时间,给出最大限度查找关键工序相关机器空闲时间的方法|查找关键工序前后的机器空闲时间,在保证可行解的条件下,移动关键工序到空闲时间位置实现邻域搜索|给出同一台机器上任意两个工序位置相对移动时保证可行解的工序移动条件及证明。将基于机器空闲时间的邻域搜索方法融入遗传算法,采用典型算例进行测试,与文献中不同算法的求解结果进行比较,验证了所提方法的有效性。

关键词: 作业车间调度, 邻域搜索, 空闲时间, 遗传算法