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.