Research On The Job-Shop Scheduling Problem With Hybrid Algorithms

Job-Shop Scheduling Problem(JSP)is one of the most intractable and classic combination optimization problems.The use of efficient optimization of job-shop scheduling technology can make quick and scientific response to the emergencies happening in the logistics,industrial production and other conditions,and can effectively improve productivity and reduce business costs,thereby enhancing market competitiveness.There are two main methods to solve the JSP:exact method and approximation method.The exact method can obtain the theoretical optimal solution,but only limited to the problems for small scale scheduling.For large scale scheduling problems,the approximation method is a better choice.At present,the meta-heuristic algorithm in the approximation method is the focus of research,such as Estimation of Distribution Algorithm(EDA),Tabu Search(TS)algorithm and Imperialist Competitive Algorithm(ICA),which provide new ideas and means for solving the job shop scheduling problem quickly.Recent studies have shown that a single technique cannot solve stubborn JSP,and hybrid methods are better options to provide powerful search capabilities.Based on EDA,TS and ICA,this paper will study the new hybrid algorithm to solve the JSP.The main work is as follows:(1)An operation-based encoding mechanism was presented to guarantee the feasibility of the solutions and the new optimal solution genetic strategy was designed.The probability model is constructed by using the Univariate Marginal Distribution Algoritm in the EDA to solve the JSP effectively.(2)To improve the ability of the imperialist competition algorithm to solve the JSP,a crossover and mutation strategy from GA was incorporated into the assimilation of ICA,which promotes the learning ability and diversity of the population.(3)To improve the local search ability of TS,a new hybrid neighborhood structure,double-moved strategy,block tabu strategy,selection strategy,jump and adjustment strategy were designed.By integrating the advantages of EDA,TS and ICA,the tabu estimation of distribution algorithm(TSEDA)and the hybrid imperialist competitive algorithm with tabu search(HICATS)were proposed in this paper.In this way,the proposed hybrid algorithms can achieve the right balance between local and global search,and overcome the weakness of EDA and ICA in local search.Through computational experiments on the classical Benchmark and comparison with the given results from the well-known hybrid algorithms in recent years.it verifies that the proposed hybrid algorithms are effective and stable for JSP.