Font Size: a A A

Researching On The Flexible Flow Shop Scheduling Problem With Limited Buffer Based On Improved ICA Algorithm

Posted on:2018-05-03Degree:MasterType:Thesis
Country:ChinaCandidate:Y SunFull Text:PDF
GTID:2428330542997590Subject:Control theory and control engineering
Abstract/Summary:PDF Full Text Request
The flexible flow-shop scheduling problem with limited buffer(FFSP-LB)is an extension of the flexible flow-shop scheduling problem(FFSP),and its production process is limited by the capacity of the buffer.Because of the characteristics of multi-station and multi-process,the flexible flow-shop is widely used in steel production,vehicle manufacturing,semiconductor packaging and other industries in the production enterprises,the FFSP is a class of NP-hard problem.In the theoretical studies,the buffer is often assumed to be an infinite buffer,but the actual manufacturing enterprises are limited by the workshop resources,the buffer capacity is limited.When the number of jobs in the buffer reaches the capacity limit,the finished product remains in the workstation,waiting for the buffer to be released,the production process is blocked.Therefore,when the production process of the flexible flow-shop is limited by the buffer constraint,the difficulty of solving the scheduling optimization problem is increased.This paper explores a more efficient solution to FFSP-LB,which can reduce production congestion and improve equipment utilization rate of the manufacturing enterprises.At present,FFSP-LB has attracted more and more attention,the demand for the products of customers increasingly diversified and personalized.It is difficult to control the production beat and it can increase the uncertainty of the production process.Demand capacity of production tasks is more difficult to match with production capacity provided by enterprise production line.The buffer on the production and processing of the regulatory role becomes more prominent.At the same time,new types of limited buffers are emerging,there is a complex routing buffer in.vehicle manufacturing enterprises,which control the movement of the job in the buffer process by the routing rules.The existence of the routing buffers further increases the complexity of the scheduling problem.So,it plays an important role in improving the utilization rate of enterprises by giving full play to the buffer zone to regulate the production process and control the role of production tasks assigned.Therefore,it is of great value to study the FFSP-LB.In this paper,a mathematical programming model for flexible flow-shop with limited buffers is established for FFSP-LB,which take the makespan as the optimization objective.The improved imperialist competitive algorithm(ICA)is combined with the initial population establishment method based on the optimization target as a global optimization method,which can be used to solve the FFSP-LB better,and further combined with routing rules to solve flexible flow-shop scheduling problem with routing buffer(FFSP-RB),and verify the effectiveness and practicability of the method.The main contents of this paper are as follows:(1)Establish the mathematical programming model of FFSP-LBOn the basis of the classical flexible flow-shop mathematical programming model,the model elements with limited buffer constraints are added to establish the mathematical relation model with buffer constraints.In this paper,the evaluation index system based on minimizing makespan is considered as optimization target and the process of flexible flow-shop with limited buffer is further analyzed.(2)Research on global optimization method based on ICAIn this paper,ICA algorithm is adopted as a global optimization method which is a simple,easy to use and can quickly converge to the optimal solution.In this paper,ICA algorithm can give full play to its advantages in solving the complex problem quickly,which is closely related to actual engineering.(3)Research on the improvement of ICA algorithmICA algorithm has faster convergence speed,but it is also easy to fall into the local extreme value.Therefore,this paper introduces the reform operation,elite individual retention strategy and Hamming distance individual selection mechanism,and proposes the improved imperialist competition algorithm(IICA).In the iterative process,due to the assimilation of ICA algorithm is too simple,and does not have a strong global search ability,therefore,this paper proposed improved imperialist competitive algorithm based on simulated annealing algorithm(IICA-SA),which can expand the search range of the algorithm,enhance the ability of individuals to jump out of the local extreme value and enhance the ability of continuous evolution of the algorithm.Finally,IICA-SA algorithm is verified the performance optimization on FFSP-LB.(4)Research on initial population establishment method based on optimization objectiveThe initial population of the ICA algorithm is randomly generated,and the population generation method makes the initial individual(country)not evenly distributed in the feasible domain,which will affect the global search ability of the algorithm.In this paper,IICA-SA algorithm based on the optimization objective initial population establishment method is proposed to improve the quality of the initial solution in the initial population,and further improve the search efficiency of ICA algorithm.Finally,a multi group simulation examples are used to verify that the IICA-SA algorithm based on the optimization objective initial population establishment method can obtain better optimization effect for solving FFSP-LB problem.(5)Research on the FFSP-RB problemThe limited buffer with routing rules is a complex limited buffer,that is,routing buffer.The jobs can move between the buffer sequences,and are re-adjusted to allocate.The moving process of jobs is directed through certain routing rules.The global optimization algorithm(IICA-SA algorithm based on the optimization objective initial population optimization method)and the local routing rules are combined to solve the FFSP-RB problem.The main content of this paper is divided into research methods and research issues.ICA algorithm and its improved algorithm are used as global optimization method,which combined with the local routing rules to study FFSP-LB problem and FFSP-RB problem.Based on the simulation examples of each group,it proved that the IICA-SA algorithm based on the optimization objective initial population establishment method can achieve better optimization effect in solving FFSP-LB problem and FFSP-RB problem.
Keywords/Search Tags:Imperialist competitive algorithm, Simulated annealing algorithm, Flexible flow shop, Limited buffer, Routing rule, Initial population establishment method
PDF Full Text Request
Related items