In this paper an efficient algorithm for finding an optimal deadlock-free schedules in an 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.