Hybrid Of Genetic Algorithm For Constrain Flow Shop Scheduling Problems

No-wait flow shop scheduling problems with total flow time minimization is an important manufacturing system widely existing in industrial environments. No-wait flow shop problem is one of flow shop problems, and is a typically NP-complete problem, which means that it is impossible to find the global optimum in polynomial complexity. Good algorithms for this problem can promote productivity of enterprises, and make the cost down. So the study of no-wait flow shop scheduling plays an important role on theory and practice. Meta-heuristics (include of genetic algorithm, tabu search and so on) and heuristics are two kinds of algorithm for flow shop problem. But the two methods have their own advantages. In efficiency, meta-heuristics is better than heuristics in general, but it is very instable. In effectiveness, meta-heuristics is not better than heuristics; it will cost much more CPU time. Therefore, it is not easy to be used in industry production, especially in large-scale flow shop problem. So, hybrid algorithm proposed in this paper can get a better solution in less CPU time is very significant in real application.The proposed heuristics are compared with the existing ones in both efficiency and effectiveness. The experimental results show that the proposed heuristics can solve the considered problems effectively and efficiently.First, a new genetic algorithm is designed to construct the initial solution for no-wait flow shop scheduling problems to minimize total flow time, then in basis of DS, a multi-move method is induced in to construct heuristic DSM, which use local search and improve the initial sequence. Hybrid algorithm is compared with three best existing heuristics, RC, DS and DSM, on 4000 randomly generated instances. Experiment results show that it is the best in ARPD (average relative percentage deviation), STD (standard deviation) and OPT (number of optimum solutions...