Research On The Self-learning Backtracking Search Algorithm And Its Application

With the globalization of the market,the competition between the traditional manufacturing industry and the emerging manufacturing industry is increasingly fierce.The enterprise has changed from the single production workshop mode to the decentralized multi-workshop mode.The distributed production and manufacturing emerge at the historic moment.Comparing with the traditional production and manufacturing,distributed production and manufacturing break the regional restrictions and realize the optimal allocation of global resources and the deep integration of global interests.Therefore,distributed manufacturing has become an important problem in the domain of manufacturing.Shop Scheduling plays a crucial role in distributed manufacturing problems.Efficient scheduling strategy is an effective mean for enterprises to improve their competitiveness in face of uncertainty and dynamic problems.Numerous distributed shop scheduling problems have been proved to be NP-hard problems,and the traditional precise solution methods are not able to solve the problem or obtain the optimal solution efficiently.Meta-heuristic method is a new optimization method in recent years.It has been widely used in shop scheduling problems because of its simple algorithm structure and problem-free characteristics.Backtracking search algorithm(BSA)is a typical meta-heuristic method,which has attracted the attention of numerous researchers in recent years because of its unique operating mechanism and better global search ability.The research contents of this paper are as follows.(1)A hierarchical knowledge guided backtracking search algorithm with selflearning strategy(HKBSA)is proposed in this paper to solve the problem of nonseparable.In HKBSA,the current population is divided into three levels of subpopulations according to the domain knowledge of individual.The individuals in the dominant population are utilized to guide the evolution of the other two populations.In the course of evolution,the three sub-populations constantly exchange and share information.Secondly,a multi-strategy mutation mechanism is designed for different sub-populations and different iteration stages of populations to better adapt to the evolution of specific populations.Finally,a self-learning strategy with feedback mechanism is designed based on the optimal and the worst candidate solutions of the current population to further improve the inferior candidate solutions in the current population.The proposed HKBSA is compared with other seven state-of-the-art BSA variants and five other types of meta-heuristic algorithms on the CEC2017 test suite.The experimental results show that the performance of HKBSA is better than the comparison algorithms in this paper in solving the non-separable problem.The proposed HKBSA is also applied to the no-wait flow-shop scheduling problem,and compared with the other three methods.The experimental results show that HKBSA is able to effectively solve the no-wait flow-shop scheduling problem.(2)An optimal block knowledge driven backtracking search algorithm(BKBSA)is proposed in this paper to solve the distributed assembly no-wait flow shop scheduling problem(DANWFSP)with the optimization objective of minimizing the assembly completion time of the product.In BKBSA,three construction heuristics are proposed to generate potential initial solutions.The block shifting based on the optimal job block is embedded into the mutation strategy to ensure that the optimal subsequence of the candidate solution is not destroyed in the evolutionary process.A variable neighborhood descent(VND)algorithm based on two kinds of neighborhood structures is used to further optimize the optimal solution.Finally,BKBSA is compared with the three state-of-the-art algorithms on 810 large test sets and 900 small test sets.The experimental results show that BKBSA has better performance than the other three algorithms in solving the problem.(3)The distributed two-stage assembly no-wait flow-shop scheduling problem(DTSANWFSP)is studied.In DTSANWFSP,each factory is divided into processing stage and assembly stage,and all the jobs belonging to the same product are assigned to the same factory.The objective of DTSANWFSP is to minimize assembly completion time for products in the critical factory.A new iterated greedy algorithm(IG_VND)is proposed to solve this problem.In IG_VND,a job assignment principle of time balance(TB)is proposed and extended to heuristics to generate the initial solution of the algorithm.A variable neighborhood descent algorithm based on three neighborhood structures is proposed to enhance the local search ability of IG_VND.The proposed IG_VND is compared with the algorithm for solving this problem on810 large-scale test sets.The experimental results show that the construction heuristic using TB principle generates better initial solutions in a shorter CPU time than that of comparison algorithm,and the optimal solutions obtained by IG_VND under different stop criteria are superior to the comparison algorithm.