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

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

Abstract

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.

Citation

Moro, A., Yu, H., & Kelleher, G. (2000, April). Advanced scheduling methodologies for flexible manufacturing systems using Petri nets and heuristic search. Presented at 2000 ICRA. IEEE International Conference on Robotics and Automation, San Francisco, CA, USA

• 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
• DOI: https://doi.org/10.1109/robot.2000.846386
• Public URL: http://researchrepository.napier.ac.uk/Output/2880351