Research On Flow Shop Scheduling Problem With Deterioration Time Based On Genetic Algorithm

With the increasingly rapid progress of science,technology and the rapid development of the productive force, manufacturing enterprises have gradually transformed the initial mode of production from single species, large quantities, unified, streamlined production methods, to many varieties, small batch, diversified, highly flexible production pattern, in order to meet the demands from customers. However, it makes the difficulty of production planning and scheduling be increased. It also has an important significance to improve the production efficiency, resource utilization and reduce production costs in manufacturing enterprises.As a typical NP-hard problem, the Flow shop scheduling problem (FSSP) is a common production scheduling issue for manufacturing enterprises. More and more researchers have done much work to find an effective solution to tackle it. In the classical Flow shop scheduling problem, the processing time of operations in a machine is considered constant. However, in the actual situation, due to affected by the characteristics of the resource, the processing time is changeable. If the processing time of the job increases, we call this kind of flow shop scheduling problem the flow shop scheduling problem with deteriorating time. In recent years, the flow shop scheduling problem with deteriorating time catches more and more attention of researchers.The main research in this thesis is flow shop scheduling problem with deteriorating time, the main research work are as follows:Firstly, we summarized the main task and purpose of the scheduling and also introduced the shop scheduling problem and its characteristics and research methods.Secondly, we summarized the flow shop scheduling problem and the deteriorating time problem, then established a model of the flow shop scheduling problem with deteriorating time, in which we considered the processing time as a linear function of its starting time and the normal processing time. The actual processing time is influenced by the inherent process of the job, resource capacity and other constraints.Finally, according to the problem characteristics, we designed the basic genetic algorithm, an improved genetic algorithm, and the heuristic improved genetic algorithm respectively, then we applied the enumeration algorithm and other algorithms above to solve the scheduling problem. The algorithms simulation results show that:when the problem size is small, the enumeration algorithm and other algorithms can obtain better result, moreover, the improved GA has advantage in computing time and stability. When the solution space increases larger, the enumeration algorithm can not find the optimal solution of the problem, other algorithms show excellent performance on stability and efficiency, especially the heuristic improved genetic algorithm.The research of this thesis provided an effective tool for solving the flow shop scheduling problem with some practical factors.