Abstract: This paper provides a new scheduling method for flexible manufacturing systems (FMS). Through introducing the test arc to traditional timed-place Petri net, a new Petri net, the extended timed-place Petri net, is proposed. It can concisely represent not only general features of FMS, hut also the device maintenance, device priority, and operation priority. By the use of search method to reachability graph of constructed models, the optimized scheduling is obtained. Experimental results are presented to show the effectiveness of the method.