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

Authors: Reyes, A., Yu, H., Kelleher, G. and Lloyd, S.

Journal: Computers in Industry

Volume: 47

Issue: 1

Pages: 123-138

ISSN: 0166-3615

DOI: 10.1016/S0166-3615(01)00124-5

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. © 2002 Elsevier Science B.V. All rights reserved.

Source: Scopus