Research On Scheduling Optimization Method Of Resource Allocation System Based On Petri Net

The resource allocation system consists of limited resources that must be allocated to the competition process,and must compete to be allocated and achieve some system goals,such as maximizing the completion time and minimizing the delay.Due to the fierce competition in today's market,many actual resource allocation systems have to respond to changes quickly through integrated planning and scheduling.These planning and scheduling allocate limited resources for tasks over time,and determine the order of operations,so as to meet the constraints of the system and optimize performance standards.Petri net can describe the concurrency,mutual exclusion,conflict,sharing and other behaviors of system resources succinctly and intuitively,and can study these behaviors qualitatively and quantitatively.Therefore,using Petri net to model,analyze and schedule the resource allocation system has become one of the mainstream methods in the research of resource allocation system.However,in the existing theoretical framework,the analysis of resource allocation system by Petri net has the problem of state explosion,that is,the reachable state set of Petri net increases exponentially with the increase of system scale.The traditional Petri net analysis method based on reachable state graph has some problems,such as too long computation time or memory overflow,when dealing with large-scale systems.This thesis mainly studies the modeling and analysis method of resource allocation system based on Petri net.Aiming at the state explosion problem caused by the large scale of the system,several optimization methods are proposed to speed up the analysis speed and reduce the system model,and the efficient modeling ability of Petri net is applied to the actual industrial system.The main contents and innovations of this thesis are as follows:(1)In order to solve the problem that the speed of solving the reachable state set is slow in the existing Petri net analysis,a fast analysis generation method is proposed by combining A* search algorithm with Petri net.This method makes full use of the efficient search ability of A* algorithm,and uses heuristic function to evaluate the quality of the generated nodes,discards the nodes with poor quality,so as to find the path from the starting state to the ending state more quickly in the reachable graph of the model.The experimental results show that the computational speed of A* search algorithm based on Petri net is 100 times faster than that of traditional algorithm when calculating large-scale Petri net model.(2)In practical applications,system scheduling problems usually involve multiple,conflicting and disproportionate goals,such as the minimum total processing time,the minimum energy consumption,etc.minimizing one goal is usually at the cost of another goal,so it is difficult to accurately and effectively determine these multi-objective values to obtain all the non dominated solution sets(i.e.Pareto solution).To solve this problem,we propose a multi-objective A* algorithm based on the reachable graph of the system Petri net model.Each objective is modeled by scalar value,and then compared with the single scalar value function to determine these criteria,the set of non dominated schemes is determined.In this thesis,a multi-objective A* scheduling optimization algorithm based on reachable graph is proposed and implemented,and the corresponding heuristic function is designed for it.The feasibility and effectiveness of the algorithm are verified by an example.(3)In the process of multi-objective A* search algorithm implementation,for some largescale examples with low search efficiency,two kinds of approximate adoptable algorithms for multi-objective search are proposed,which can greatly reduce the operation scale and shorten the running time while ensuring the results are nearly optimal.