SAA-based novel hybrid intelligent evolutionary algorithm for job shop scheduling problem

Through systematic analysis and comparison of the common features of SAA, ES and traditional LS (local search) algorithm, a hybrid strategy of mixing SA, ES with LS, namely HIEA (Hybrid Intelligent Evolutionary Algorithm), is proposed. Viewed as a whole, the hybrid strategy is also an intelligent heuristic searching procedure. But it has some characteristics such as generality, robustness, etc., because it synthesizes advantages of SA, ES and LS, while the shortages of the three methods are overcome. This paper applies Markov chain theory to describe the hybrid strategy mathematically, and proves that the algorithm possesses the global asymptotical convergence and analyzes the performance of HIEA.