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

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