Integrating Petri Nets and hybrid heuristic search for the scheduling of FMS

Reyes, A.; Yu, H.; Kelleher, G.; Lloyd, S.

Abstract

This paper studies modelling and scheduling of Flexible Manufacturing Systems (FMS) using Petri Nets (PNs) and Artificial Intelligence (AI) based on heuristic search methods. A subclass of PNs, Buffer nets or B-nets is obtained by the systematic synthesis of PN models from FMS formulations. Scheduling is performed as heuristic search in the reachability tree, which is guided by a new heuristic function that exploits PN information. This heuristic is derived from a new concept, the Resource Cost Reachability (RCR) matrix which builds on the properties of B-nets. To mitigate the complexity problem, a hybrid search algorithm is proposed. The algorithm combines dispatching rules based on analysis information provided by the PN simulation with a modified stage-search algorithm. Experimental results are provided and indicate the effectiveness of the approach and the potential of PN-based heuristic search for FMS scheduling.

Citation

Reyes, A., Yu, H., Kelleher, G., & Lloyd, S. (2002). Integrating Petri Nets and hybrid heuristic search for the scheduling of FMS. Computers in Industry, 47(1), 123-138. https://doi.org/10.1016/s0166-3615%2801%2900124-5

• Journal Article Type: Article
• Acceptance Date: May 19, 2001
• Online Publication Date: Nov 27, 2001
• Publication Date: 2002-01
• Deposit Date: Jun 15, 2022
• Journal: Computers in Industry
• Print ISSN: 0166-3615
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 47
• Issue: 1
• Pages: 123-138
• DOI: https://doi.org/10.1016/s0166-3615%2801%2900124-5
• Keywords: Heuristic search, Flexible Manufacturing Systems, Modelling, Scheduling, Petri Nets
• Public URL: http://researchrepository.napier.ac.uk/Output/2879284