Deadlock-Free Optimal Scheduling for an Extended S3PR with Correlated Resources

Deadlock free scheduling is a critical problem in an extended S 3 333 PR with correlated resource (ESPR -CR), where the processing ability of each kind of resource equals 1, and there exist two kinds of resources interrelate. In this paper, a deadlock prevention method and its genetic based algorithm designed for ESPR -CR are investigated. Firstly, the ESPR -CR Petri net is characterized and defined, and then the modeling procedures are presented based on Petri nets. Secondly, based on the purposed deadlock prevention method, an algorithm for deadlock free scheduling is presented. The purposed method is based on net-structure that behaving polynomial complexity. As long as the initial objects distribution vector of the Petri net system satisfies the scheduling conditions, the controlled system will never enter a deadlock state, which guarantees that a controlled system has no deadlock while scheduling. Then, an optimal scheduling method based on genetic algorithm is presented, and locomotives dispatching system of underground coal mine is analyzed as an example to illustrate the validation of the purposed method. Compared with the existing literature conclusions, the purposed deadlock free optimal method is net-structured, and it can be realized without any controller places, which provides smaller size.