Skip to main content

Research Repository

Advanced Search

Advanced scheduling methodologies for flexible manufacturing systems using Petri nets and heuristic search

Moro, A.R.; Yu, H.; Kelleher, G.


A.R. Moro

G. Kelleher


The combination of Petri net (PN) and AI to solve flexible manufacturing systems (FMS) scheduling problems has been proven to be a promising approach. However, the NP-hard nature of the problem prevents the PN capability of reasoning about the behavior of a practical system. To overcome this drawback, we propose two techniques: a systematic method to avoid the generation of unpromising paths within the search graph, and a stage-search based algorithm. The algorithm developed is based on the application of the A* algorithm and the PN-based heuristics. The search is performed within a limited local search window where an optimization policy is applied to evaluate the most promising paths. For each state, the algorithm is able to decide whether an enabled operation is applied, and to maintain the decision until new system information makes the reconsideration meaningful. Comparison with previous work is presented to show the superiority of the proposed approach.

Presentation Conference Type Conference Paper (Published)
Conference Name 2000 ICRA. IEEE International Conference on Robotics and Automation
Start Date Apr 24, 2000
End Date Apr 28, 2000
Online Publication Date Aug 6, 2002
Publication Date 2000
Deposit Date Jun 18, 2022
Publisher Institute of Electrical and Electronics Engineers
Series ISSN 1050-4729
Book Title Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065)
ISBN 0-7803-5886-4
Public URL