Scheduling Flexible Manufacturing Systems Based On Petri Nets And An Ant Colony Algorithm

A flexible manufacturing system（FMS）is an automatic manufacturing system for multi-variety and small-batch production mode,which has attached great attention and in-depth research for its high-quality,high-efficiency,and high-flexibility.The scheduling problem of FMS can be described as a reasonable and efficient allocation of a set of shared resources,achieving the desired performance index while completing the production task,and the ulti-mate goal is to improve the economic benefits of enterprises.How to schedule FMS to meet the changing market demands and maximize the benefits of systems is of great significance.As a modeling tool for discrete event systems,Petri net has both mathematical representation and graphical representation,which can describe concurrency,conflict,asynchronous,and so on in FMS effectively.In this thesis,the ant colony optimization（ACO）is used as the optimization algorithm to study the scheduling problem of FMS with the goal of minimizing the processing completion time,and a method based on Petri net and improved ant colony optimization is proposed to solve this problem.The main research contents are as follows:1.Construct the Petri net model of an FMS according to the constraints that the system needs to meet in the actual production process,and based on this model,a system scheduling algorithm by using ant colony algorithm is proposed.2.Due to the shortcomings of ant colony algorithm,such as long search time and easy to fall into local optimal solution,an improved ant colony algorithm is proposed to opti-mize the scheduling problem of FMS.The improvements are summarized in the following four aspects:considering the waiting time between operations due to various constraints,the reciprocal of the operation’s earliest completion time is used as its heuristic information value.Due to the limitation that ants can only be guided by local pheromone,an estimation function that can evaluate the completion time of the system is introduced,so as to avoid the ants missing the global optimal path since they are greedy for the current optimal path.The pseudo-random proportional rule is used to select the nodes,and the parameter q₀is dy-namically set in the ant colony system.The path pheromone is updated by a combination of local update and global update,and after each iteration is completed,only the pheromone is updated on the optimal path globally.3.The steps of the proposed improved ant colony algorithm to solve the FMS schedul-ing problem based on Petri net model are designed.The scheduling algorithm is applied to several practical FMS cases,and the scheduling results are analyzed and compared with other algorithms to verify the feasibility and efficiency of the improved ant colony algorithm.4.According to the special technological requirements of some FMS in the actual produc-tion environment,several different types of time constraints for operations are proposed.The improved ant colony algorithm is used to design the corresponding effective produc-tion scheduling algorithm for different situations,and the optimal scheduling scheme of the system under different situations is obtained.