A Study Of Algorithms For Job Shop Scheduling Problem

The job shop scheduling problem is a notorious NP-Hard problem and has attractedlots of interests since its appearance in last century. As the exact algorithms needexpensive cost of time to get the best result, the approximate approaches become popularand have achieved some promising results.Heuristic algorithms, such as priority dispatching algorithms, have a far speed forsolving the job shop scheduling problem. In this paper, we present a fast heuristicalgorithm PD-INSA, which has combined the characteristics of both priority dispatchingalgorithm and INSA algorithm. The results prove that PD-INSA algorithm is better thanINSA algorithm. Since heuristic algorithms have lower quality of results, they are oftenused to generate initial results which would further be improved by more sophisticatedalgorithms.Tabu search algorithm has been applied to solve combinatorial problems successfully.However, it still falls into the local primal when it’s used to solve job shop schedulingproblem. We present a strategy to jump off the local primal. Based on this strategy and theN5neighborhood function in TSAB algorithm, we present a new r-TSAHB algorithmusing tabu search technology.The single meta-heuristic algorithm has limited ability to solve the job shopscheduling problem, as a result hybrid algorithm which combines the strong points ofdifferent meta-heuristic algorithms has become popular in academic fields. In this paper,we analysis the characteristics of ILS (iterated local search algorithm) and TS (tabu searchalgorithm), and present a hybrid algorithm ITS (iterated tabu search algorithm) whichcombines ILS and TS together. The experiment result proves that ITS has some goodperformance in solving job shop scheduling problem.