An Evolutionary-Tabu Algorithm For Solving Job Shop Scheduling Problem

Production Management is one of main activities in modern manufacture enterprise, which executes production scheduling by allocating resources in order to perform a number of tasks, which are assigned to resources in a temporal order. The research and application of effective production scheduling methods and optimization techniques are the key elements to implement modern manufacture and promote production efficiency. This paper consists of two major parts.The 1st part is the research on theory algorithms of Job Shop Scheduling Problem (JSSP). By analyzing the domestic and foreign research developments, this paper notes exact and approximate methods' characteristics respectively. Tabu Search is an effective local search algorithm for the job shop scheduling problem, but the quality of the best solution found depends on the initial solution. Evolutionary algorithm is a global search algorithm by choosing, crossover and mutation operations to operate the population. The method itself cannot decrease the search space, but the population search mechanism can cover a large scale solution spaces. To overcome this problem we present a new Evolutionary-Tabu alogrithm (ETA) that uses a population of Tabu Search runs in an Evolutionary Computation framework. ETA adopts a search strategy to classify the individuals by their fitness. Individuals' classification differentiate respective function in search process, that's the excellent individuals mine the local optimal solution and others explore the search domain to find new local optimal solution. By testing benchmark instances the results show the new algorithm is satisfactory.The 2nd part is the application of ETA. Testing Traveling Salesman Problem (TSP), which is a similar combination optimization problem to JSSP. In addition, we explain how to design production scheduling system by planting ETA into a real-world scheduling system. Based on analyzing the failures using intelligent algorithms in real-world scheduling system, we put forward an intelligent scheduling framework. The characteristics of the framework are collecting the production response information and the judge modal of scheduler using multi algorithms.