A Hybrid Genetic Tabu Search Algorithm For The Job Shop Scheduling Problem

Job shop scheduling problem(JSP)is a famous NP-hard combinatorial optimization problem.Over the decades,many researchers have designed various algorithms to solve this problem,but even for small-scale problems,state-of-the-art algorithms struggle to obtain the optimal solutions.The JSP problem is widely used in the field of industrial manufacturing,involving automobiles,ships,space shuttles,and electronic components.Therefore,the academic value and engineering significance of the JSP problem are significant.Based on the traditional JSP problem and its extension,this paper considers two problem characteristics of machine flexibility and distributed manufacturing,and uses the hybrid genetic and tabu search algorithm(HGTSA)as the main technical tools.Finally,the effectiveness and practicability of the method are demonstrated through two practical engineering cases.The main research of the dissertation is as follows:For the classical JSP problem,an HGTSA algorithm is proposed to minimize the makespan.In the aspect of encoding,a machine position-based encoding scheme is proposed to facilitate individuals to perform crossover,mutation,and neighborhood search operations.In the genetic algorithm phase,a crossover operator based on path relinking is designed to guarantee the population diversity;a mutation operator on the basis of the critical path is devised to help individuals jump out of the local optimum.In the tabu search phase,an N8 neighborhood structure is devised for expanding the search space of neighborhood solutions.The experimental result on three benchmark sets demonstrates the effectiveness of the HGTSA algorithm.In particular,the HGTSA algorithm improves the upper bounds of two instances.For the Flexible Job Shop Scheduling Problem(FJSP),an HGTSA algorithm is proposed to minimize the makespan.In the aspect of encoding,an encoding scheme that simultaneously represents machine selection and operation sequence is designed for the machine flexible.In the genetic algorithm phase,two crossover operators are developed to guarantee the population diversity;two mutation operators are devised to avoid individuals getting stuck at the local optimum.In the tabu search phase,a hybrid neighborhood structure,combining N8 and k-insertion,is proposed to improve the local search ability.The computational result on three benchmark sets demonstrates the effectiveness of the HGTSA algorithm.In particular,the HGTSA algorithm improves the upper bounds of five instances.For the Distributed Job Shop Scheduling Problem(DJSP),an HGTSA algorithm is proposed to minimize the global makespan.In the aspect of encoding,a two-dimensional encoding scheme that simultaneously represents factory assignment and operation sequence is proposed for the distributed manufacturing characteristic.In the genetic algorithm phase,two crossover operators are designed on the basis of critaical factories to guarantee the population diversity;two mutation operators are devised on the basis of critaical factories to help individuals jump out of the local optimum.In the tabu search phase,the N8 neighborhood structure is applied to critical factories,while ensuring the search depth and computational efficiency of the algorithm.The experimental result on 240 benchmark instances demonstrate the effectiveness of the HGTSA algorithm.In particular,the HGTSA algorithm improves the upper bounds of 235 instances.For the Distributed and Flexible Job Shop Scheduling Problem(DFJSP),an HGTSA algorithm is proposed to minimize the global Makespan.In the aspect of encoding,a threedimensional code that simultaneously represents factory assignment,machine selection,and operation sequence is proposed for the characteristics of machine flexibility and distributed manufacturing.In the genetic algorithm phase,three crossover operators are designed on the basis of critical factories to guarantee the population diversity;three mutation operators are devised on the basis of critical factories to avoid individuals getting stuck at the local optimal solution.In the tabu search phase,the hybrid neighborhood structure,combining N8 and k-insertion,is applied to critical factories,which expands the search space of neighborhood solutions and ensures the search efficiency.The experimental result on 69 benchmark instances demonstrate the effectiveness of the HGTSA algorithm.In particular,the HGTSA algorithm improves the upper bounds of 13 instances.The practicality of the HGTSA algorithm is verified by two engineering cases.The first case is the shell parts production workshop of an aerospace equipment manufacturer.Itis a typical FJSP problem.The second case is an engine cooling fan parts production workshop.It is a typical DFJSP problem.The HGTSA algorithm is applied to the two engineering cases,and the experimental result verifies the practicality and effectiveness of the proposed method in solving the practical production scheduling problems.Finally,the main work of the paper is concluded,and the future research direction is discussed.