A Petri-Net-Based Anytime A∗ Search for Scheduling Resource Allocation Systems

This article proposes a novel anytime search method for the scheduling problem of resource allocation systems (RASs) based on Petri nets (PNs). The method combines the A* search with the depth-first search to iteratively search for transition firing sequences from a start state to a goal state within the reachability graph of a place-timed PN. It usually finds a near-optimal solution quickly and continuously improves the solution until an optimal solution is reached if given more time. When compared with similar work, this method requires only one parameter and does not require any deadlock control policy. Additionally, it can handle generalized PNs with flexible routes and weighted arcs, which are common in the PN models of RASs. Experimental results on benchmark systems demonstrate the effectiveness of the proposed method.