Grid Application Scheduling Model Based on Petri Net with Changeable Structure

This paper proposes a scheduling net based on a hierarchical color Petri net and a job net based on a Petri net with changeable structure. According to the granularity of grid applications, the scheduling net is designed into four levels, which makes it easy to deploy distributed schedulers in grid environment and benefits the management of different application granularities. The job net model is based on Petri net with changeable structure, which can change its structure dynamically according to the real-time state of running jobs. This model supports the dynamic mergence and division of subtasks and has ability to handle the running exceptions of subtasks. Finally, we validate the liveness and reachability of the scheduling net and the job net by analyzing their reachability trees. A transition tree algorithm is also presented to analyze the cost and time properties of job net, which can be used for the optimization of resource allocation.