Research On Scheduling Algorithm Based On Petri Nets And Heuristic Search

With the arrival of "Industry 4.0" era, manufacture is confronted with two main schemes: Smart Factory and Smart Manufacturing. Rapidly responding to customization demand of client, producing high quality and personalized products in effective time will become the core com-petitiveness of future factory, which make the research on scheduling problem of manufacturing system under this circumstance very important. Based on a review of the existing solving method for manufacturing system scheduling problem that belongs to a kind of combinatorial optimization problem, the solving method based on Petri net reachability graph and heuristic search is discussed and multiple methods are proposed to improve the efficiency.The main idea of the method for solving the scheduling problem is to generate the reachability graph by combining the exectuion capacity of Petri net and heuristic search that is guided by heuristic function, then the optimal schedule is obtained in the format of transition firing sequence. However, the number of states increases exponentially as the scale of the problem grows. To improve the efficiency, the existing researches rely on partial reachability graph that is affected by two key parts:the generation method of reachability graph and design of heuristic function. This thesis focuses on these two key points from the shallower to the deeper, do the following research:1) For the minimum makespan scheduling problem, heuristic function calculates the remain-ing operation time of each machine, selects the maximum value to predict the lower bound for completion time of the whole process, which has been confirmed as an important kind of heuristic function. However, existing function has two main shortcomings as follows:in the context of flex-ible manufacturing system, non-optimal solution is obtained because of inaccurate classification of surplus processing operation, the solving efficiency is affected by without considering the remain-ing time of unfinished operation. In this thesis, an improved method is proposed accordingly that guarantee optimality and enhance the lower bound prediction of mimimum comletion time. As a result, the algorithm within the placed-timed Petri-net (PTPN) framework can achieve an optimal schedule in less time.2) Existing heuristic functions are all developed under the PTPN framework. The overall ef-ficiency is not high due to the model framework limitation. This thesis designs heuristic function under the framework of transition-timed Petri nets (TTPN) for the first time, this method can ef-fectively take advantage of the time attribute of token timestamp, take the feasible time of each resource into consideration, predict the lower bound for completion time from machine and job perspectives. In addition, the existing methods are using a single transition firing way to expand the the reachability graph, and for JPS (Job-shop Scheduling Problem), it is proved that if some conditions are satisfied, some transitions can fire simultaneously and the subsequent identifier can be exploreed deeper without affecting the optimality of the results.3) Different ways to add time attribute:PPTN can restrain more redundant states during the expansion of reachability graph, while TTPN can develop more effective heuristic function with the token timestamp. This thesis proposes a hybrid framework to combine the advantage of both frameworks. In this novel framework, the former is used to construct the algorithm framework to generate partial reachability graph and limit redundant identifiers, the latter is applied to design heuristic function to calculate lower bound for completion time and guide the expansion of reach-ability graph. Until now, the efficiency of algorithms based on Petri net execution and heuristic search has been improved remarkably.4) The proposed heuristic design method and the hybrid framework is not only applicable for manufacturing system, but also can be expanded for other combinational optimization problem with sequence constraints. This thesis takes the manufactuing execution system (MES) of petro-chemical enterprise as an example and designs a workflow control system based on MES. In view of the scheduling problem of workflow, the proposed algorithm and framework are adopted in the design of workflow and existing heuristic functions are modified according to the more complex Petri net structure to solve the minimum makespan problems.At last, promising studies and applications are discusses in the conclusion.