The Hybrid Genetic Algorithm For Solving Flexible Job-shop Scheduling Problem

Scheduling attempts to assign restricted resource to several tasks in a predefined time to achieve some objectives,such as reducing inventory,shortening the manufacturing period and increasing the efficiency of manufacturing facilities.After the introduction of flexible manufacturing systems,flexible job-shop scheduling problem(FJSP)has become an urgent issue in scheduling aera,which attracts more and more attentions.FJSP is a NP-hard problem,so exact method is hard to obtain the best solution in a reasonable time.Recently,meta-heuristics developed to offer a new way to solve FJSP efficiently.Due to the fact that single algorithm is hard to keep a balance between the global exploration and local exploitation of the search space,hybrid algorithms have become one of the most efficient methods for solving FJSP.Among these methods,genetic algorithms and tabu search are two main algorithms adopted in hybrid algorithms.Applying genetic algorithms to FJSP,the critical issue is to design a suitable chromosome representation.However,existing chromosome representations lack the diversity of genetic operations.Therefore,a new chromosome representation,i.e.MSOS-III,is proposed to guarantee the feasibility of chromosomes,increase the diversity of genetic operations.In addition,applying tabu search to FJSP,the critical issue is to design an effective neighborhood structure and corresponding move evaluation.Therefore,profitable neighborhood structures are proposed to combine the process of constructing neighbors and move evaluation,which reduces the computation time on evaluation.In order to keep the connectivity,a two-pace neighborhood search strategy is proposed to improve the effectiveness of tabu search.The hybrid genetic algorithm is designed combining the proposed chromosome representation,neighborhood structure and two-pace neighborhood search strategy.Then the proposed algorithm is tested on four groups of well-known benchmark instances of different size and flexibility and compared with the existing state-of-the-art methods.The proposed algorithm updates 8 out of 69 benchmark instances and provides competitive solutions for the others.The experimental results validate the outstanding performance of the proposed algorithm for solving FJSP.