A New Genetic Algorithm For A Kind Of Flow Shop Problems And Applications

Flow shop scheduling problems have a wide range of applications such as in computer science, management science and control theory, etc. Most of them are very hard NP-complete problems, and it is very difficult to design effective algorithms for them. For small scale problems, heuristic algorithms are usually used to find an approximate optimal solutions, while for large scale problems, there is no any efficient algorithm until now. Therefore, doing the research on this topic is not only of great importance from the point of view of scientific research, but also of great value in wide applications.The flow shop scheduling problems are problems as follows:there are m machines and n jobs (tasks). Every job has to be processed on m machines successively in the fixed order, and all jobs have to be processed in a fixed order in a machine. In this paper, the permutation flow shop problems are considered, that is, the set of all jobs should be processed in the same order on each machine. Then requirement of the permutation problem is as follows:When the processing time of each job on each machine is given, the goal is to find a single permutation of the n jobs that minimizes the maximum job completion time (makespan) of the schedule. When the number of machines is more than two, there have not been efficient algorithms for the permutation flow-shop scheduling problems. In this paper, the research is focused on this kind of problems, and the main work of this thesis is as follws:First, based on a thorough analysis of the permutation scheduling problems, the mathematical formula of the maximum job completion time (makespan) of the schedule is given, and a methematical model of global optimization is set up. This model is a minimum-maximum optimization model.Second, By considering the characheristics and specific construction of the problems, an encode mothed of the candidate solutions is given and it can represent the candidate solutions reasonably and naturally. Moreover, the fitness function of candidate solutions is defined.Furthermore, a new crossover operator and a new mutation operator are designed. Based on these, a new genetic algorithm is proposed for the minimum-maximum optimization model of the permutation flow-shop scheduling problems.Finally,a minimum-maximum optimization model of the permutation flow-shop scheduling problems is set up for a practical scheduling problem of a factory, and the proposed genetic algorithm is applied to this model, and the obtained scheduling reduces the completion time of each month from full month without stopping production of 24 hours each day to 26.6 days. Thus, this new scheduling can greatly improve the existing scheduling which was adopted by the factory in the past. In addition, the computer simulations are also made on five test problems, and the results demonstarte that the proposed algorithm is effective and applicable.