A Hybrid Local Search Algorithm For Job Shop Scheduling Problem

The job shop scheduling problem is not only NP hard, but also regarded as one of the most difficult combinatorial optimization problems as well. Job shop scheduling is that assigning the operation sequence and the start operation time of each job on the corresponding machine with the limited machine resource, satisfying the needs of the jobs, in order to optimize the chosen performance value.Local search is a very important heuristic method for the job shop scheduling problem. The method is discussed in this paper, and its application in the problem is introduced. Through the heuristic strategies for the problem, aiming at the shortcoming of the existing local search algorithms, an improved local search algorithm that utilizes the one-machine scheduling method and the idea of quasi-physical and personification to solve the problem is presented.In order to deliver the ideas of the proposed algorithm more clearly, some definitions and theories are brought forward and strict mathematical prove is given for each theory. A new dispatch rule for generation the initial solution is presented. The local search procedure starts with the initial solution. A new neighborhood structure, which utilizes the idea of quasi-physical and personification, is presented. The advantages and disadvantages of the sub algorithm of the shifting bottleneck procedure are analyzed, an improved one-machine scheduling algorithm is proposed.Aiming at the shortcoming that local search procedure often gets trapped in local optima, a local search algorithm HNLS with hybrid neighborhood, which combines the one-machine scheduling and the proposed neighborhood structure is presented. The used hybrid neighborhood is not only efficient in local search procedure, but also may help overcome entrapments effectively and carry the search to areas of the feasible set with better prospect. In HNLS, not only one-machine scheduling method is used as a strategy for breaking out of local optimum to find optimal solution in the range of whole, but also three other strategies utilizing the idea of quasi-physical and personification, simulated adjustment, single machine adjustment and the"discrimination"against the minimal job, are proposed to do that.HNLS tested 68 varying size and difficult problems. These problems are often referred in international literature during the past ten years. For all 10 jobs, 10 machines problems, including the famous hard problem FT10, HNLS found optimal solution for each problem. Among 40 LA problems, HNLS found optimal solutions for 37 problems. HNLS outperform some classical algorithms, for example, neural network, simulated annealing, tabu search and SB procedure. HNLS is compared with two advanced algorithms at present, TSSB and algorithm proposed by Balas. Balas's algorithm has different forms according to the different methods and arguments used in his algorithm, such as GLS, SB-GLS1, SB-GLS2, SB-RGLS1 and SB-RGLS2 etc, and BV-best is the best solutions among of those provided by Balas. For 63 problems, HNLS outperform TSSB on 19 but TSSB outperform HNLS only on 1 in solution quality. For 63 problems, the computational results of HNLS outperform BV-best on 6 while BV-best outperform the computational results of HNLS on 7. But the argument in HNLS is fixed for all problems, the test results show that HNLS outperform any algorithm with fixed arguments provided by Balas in solution quality.Finally, a backtracking algorithm for job shop scheduling is presented. The algorithm is tested and the effect on the algorithm of different arguments is analyzed on 22 problems, it found optimal solutions for 17 problems. The algorithm is a fast and effective method to solve the problem, and for any fixed heuristic procedure, the solution quality of the procedure can be improved by backtracking method.