Research And Improvement Of Tabu Search Algorithm For Job Shop Scheduling Problem

Job Shop Scheduling Problem (JSSP) is one kind of scheduling problems and it is also among the hardest combinatorial optimization problems. The research on JSSP is not only significant for theory but also valuable for engineer application.Tabu Search (TS) algorithm is a kind of efficient approximation approach for solving scheduling problem; the basic thought is to find a neighbor solution according to the neighborhood space from a given solution; at the same time, TS adopts a tabu list in order to avoid the local search procedure trapped into local optimation. In this paper, based on the neighborhood structure and the tabu list, a Tabu Search algorithm based on hybrid neighborhood structure is propsed for solving JSSP.In order to enlarge the neighborhood space, the neighborhood based on the longest active chain and the neighborhood based on the current moved active block are proposed; also these two kinds of neighborhood structures are adopted together. In order to increase the efficiency of tabu list, a way of tabu which is saving the position of operation is proposed; and also the length of tabu list is fixed as 1/7 of all the operations. According to the simulation experiment, the proposed approach is feasible and effectual; but there are still some problems for the proposed approach needed to be solved, therefore in the end, the advantage and the problem of the proposed approach is concluded systematically.