关键词: 加工时间离散可控, 非支配排序遗传算法, 禁忌搜索, 分解策略, 精英进化

Abstract: To solve Job-shop Scheduling Problem with Discretely Controllable Processing Times(JSP-DCPT),a Non-dominated Sorting Genetic Algorithm II(NSGA-II)and Tabu Search(TS)algorithm based hybrid algorithm NSGAII-TS was put forward.On the premise of resources allocation,the decomposition strategy of solving control scheme first and then solving process plan was used in NSGAII-TS.NSGA-II was used for global optimization of population,and TS algorithm was used for local optimization of the new individuals in population.An extended coding method based on preferred list was presented,and elitism evolution strategy was adopted to participate in genetic evolution operation based on elitism preservation so that the optimum solution was obtained.The duplicate comparison of individuals in fast non-dominated sorting approach of NSGA-II was eliminated so that the time complexity of NSGA-II would be reduced.The simulation experiments indicated the effectiveness of NSGAII-TS algorithm.

Key words: discretely controllable processing times, non-dominated sorting genetic algorithm, tabu search, decomposition strategy, elitism evolution