A hybrid heuristic algorithm for flowshop inverse scheduling problem under a dynamic environment

In this paper, a novel inverse scheduling strategy has been proposed to solve dynamic flowshop inverse scheduling problem (DFISP) with random job arrivals and machine breakdowns. Firstly, a mathematical model of DFISP is developed to minimize the adjustment of the parameter. Secondly, an adaptive hybrid algorithm is proposed to solve the DFISP with dynamic events and uncertain processing parameters. The hybrid algorithm is combined improved GA with an adaptive local search (GA-LSAM). A new decimal system encoding method is proposed to ensure parameter controllable, which contains 4-layer information in one chromosome. GA-LSAM applies a separate local search process to improve quality of solutions. Thirdly, a simulator is designed to generate the unexpected disruptions in order to simulate dynamic events. The proposed algorithm can solve 90 public flowshop instances. The comparison with the traditional scheduling and the inverse scheduling shows a good performance of the algorithms with an average deviation of only 2.00%. The analysis of variance has been carried out to determine the significant difference of the algorithms. Finally, inverse scheduling also has been applied to solve a real factory instance with dynamic events. The result shows that GA-LSAM algorithm outperforms other algorithms in terms of searching for quality and efficiency.