Analysis And Application Of Optimal Execution Sequence In Automated Manufacturing Systems

Under the background of rapid development of science and technology,manufacturing automation has become the mainstream direction of industrial production.As a kind of complex artificial systems,automated manufacturing systems exhibit the characteristics of complexity,uncertainty,multi-objective,multi-constraint and multi-resource coordination.The analysis of automated manufacturing systems is to evaluate the various performance of the system when the configuration and decisions of the system are known.The control of manufacturing systems is to determine the configuration and decision-making of the system according to certain objectives and constraints.Therefore,the fundamental purpose of performance analysis,evaluation and management of automated manufacturing systems is to improve and optimize their performance.Performance analysis and comprehensive evaluation of automated manufacturing system have always been two basic problems in the field of advanced manufacturing technology.In the face of the continual expansion of industrialization,how to improve the production efficiency of automated manufacturing systems and improve the system performance is the key to promote social development.Therefore,the research on the optimal execution sequence in automated manufacturing systems is of great theoretical and practical significance.This thesis is based on flow shop scheduling problem,which is a kind of combinatorial optimization problem with time constraints,sequence constraints as well as resource constraints.It is one of the most considerable topics in manufacturing production planning,and also one of the research hotspots in this field.The flow shop scheduling problem is NPhard and cannot obtain an optimal solution in polynomial time,so a large number of effective approximate/heuristic algorithms are applied.Approximation/heuristic algorithms can usually produce scheduling results in reasonable computational time;nevertheless,it is often difficult to evaluate the gap between these schedules and optimal solutions.The existing research shows that the Lagrange relaxation method is one of the effective methods to obtain better suboptimal solutions,and can solve the lower bound of the optimal value(for minimization problems)to evaluate the advantages and disadvantages of the scheduling results,so it has been widely used in the study of practical scheduling problems.This thesis mainly completes the following work on the basis of existing research:First,this thesis introduces the mathematical model of flow shop scheduling problem of automated manufacturing systems based on Lagrangian relaxation method,normalizes the definition of related concepts and model parameters,analyzes the key technology of the Lagrangian relaxation method,including how to choose relaxation constraints,the basic principle of subgradient algorithm which updates Lagrange multiplier as well as the feasible method of solution and so on.Then a general framework for automated manufacturing systems scheduling problem based on Lagrange relaxation method is established.Second,aiming at the flow shop scheduling problem with the objective function of minimizing the due date penalties,two algorithms are introduced to obtain the optimal scheduling scheme.One is the genetic algorithm belonging to the heuristic algorithm,which performs a global search on the flowshop scheduling model to minimize the objectice function.The other is to apply the Lagrangian relaxation algorithm to decompose and coordinate the problem,i.e.,the scheduling problem is decomposed into machine-level subproblems rather than job-level sub-problems.And the effectiveness of these two algorithms is verified by simulation.In addition,the oscillation of the multiplier values in the Lagrangian relaxation method and its caused uncertainty of the feasible solution are analyzed.In this research,a new correction strategy is given.Third,the MATLAB software is used to conduct simulation experiments while the Lagrangian relaxation algorithm proposed in this thesis is applied to industrial production.Through the tests of examples of production problems with different scales,the results show that the algorithm can effectively reduce the due date penalty in the production process.On this basis,several groups of experiments are carried out,and the similarities and differences of using genetic algorithm and Lagrangian relaxation algorithm to solve scheduling problems are analyzed and compared through the experimental results.