Algorithms Studying For Job Shop Scheduling Problem

Job Shop Scheduling Problem (JSSP) can be described as follows: Given a set of jobs and a set of machines, each job consists of some operations, which work in a certain order. The aim of the problem is to find the minimum makespan of the schedule to complete all operations on the specific constraints.This problem is an NP complete problem. The computing time of the precision algorithm for the problem will increase exponentially with the problem size. So, it's unwieldy to solve the problem with a precision algorithm. However, approximate methods can be used to work out the satisfactory solution in shorter time. For the JSSP is an important practical problem, it is meaningful to find an approximate algorithm for this problem.In this paper, a method which is based on priority rules is used to decide the order for the operations. The SP (Simple Priority) algorithm originated from workers' practical experience in scheduling. The testing result shows that the SP algorithm can get an approximate solution, rather than the best solution, in a short time. To find the best solution, SP has been improved in this paper. Both the ESP (Enumerate based on Simple Priority rule) algorithm, which combined SP with enumerate, and the LS ( Local Search) algorithm, which combined SP with local search, can obtain the best approximate solution.The resolution of Tabu Search algorithm, which can get the best approximate solution, has close relationship with the goodness of the initial solution and neighborhood structure and the length of the tabu list. The classical Tabu Search algorithm has also been improved in this paper. Through testing, the improved Tabu Search algorithm proved to be able to obtain the best solution and be an effective local search algorithm for the Job Shop Scheduling problem.