A kind of deadlock-free scheduling method based on Petri net

Author

Gang, Xu ; Wu, Zhiming

Author_Institution

Inst. of Autom., Shanghai Jiao Tong Univ., China

fYear

2002

fDate

2002

Firstpage

195

Lastpage

200

Abstract

In this paper an efficient algorithm for finding an optimal deadlock-free schedules in a flexible manufacturing system (FMS) modeled by a kind of Petri net, systems of simple sequential processes with shared resources (S⁴R) nets, is presented. This algorithm is based on the effective genetic algorithm (GA) search method, and the structural elements analysis of Petri net. In order to find the optimum and deadlock-free scheduling strategy from the population generated by GA, Petri net structural analysis procedure is involved as a criterion to select among population and make the job scheduling deadlock-free. The effectiveness and efficiency of the proposed approach is illustrated using an example at the end of the paper.

Keywords

Petri nets; concurrency control; flexible manufacturing systems; formal specification; genetic algorithms; processor scheduling; system recovery; Petri net; deadlock-free scheduling method; flexible manufacturing system; genetic algorithm; shared resources; simple sequential processes; Automatic control; Flexible manufacturing systems; Job shop scheduling; Manufacturing automation; Manufacturing processes; Resource management; Robotic assembly; Robotics and automation; Scheduling algorithm; System recovery;

fLanguage

English

Publisher

ieee

Conference_Titel

High Assurance Systems Engineering, 2002. Proceedings. 7th IEEE International Symposium on

ISSN

1530-2059

Print_ISBN

0-7695-1769-2

Type

conf

DOI

10.1109/HASE.2002.1173123

Filename

1173123