یکپارچه سازی پتری به جستجوی اکتشافی ترکیبی برای برنامه ریزی FMS

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.

An FMS usually consists of several numerically controlled manufacturing machines and automated material handling systems that transport work-pieces between machines and tool systems. In a facility with routing flexibility, each product can be manufactured via one of several available routes. A high-level control system must decide which resources to assign to which product at what time, to optimise some criteria, (for example, makespan). The planning/scheduling of an FMS is the process of determining the allocation of parts to machines and the sequence of operations so that the constraints of the system are met and performance criteria are optimised. Unfortunately flexibility in manufacturing systems comes at a price. In the case of FMS the price is one of operation complexity, which means that, without an effective means of scheduling and controlling production FMS, economic returns will be poor. Consequently, the problem has been of considerable interest to both academic and industrial researchers over the last three decades [2], [14], [18] and [26]. The recent integration of PN as a representation tool with AI problem solving methods as a reasoning paradigm appears to be a promising answer to the need to develop models that factor in the full complexity of the FMS, yet are efficient enough to obtain good solutions.

The combination of PN modelling as a representation formalism and AI-based heuristic search methodologies has been studied in this paper. The systematic modelling of FMS descriptions allowed the definition of a PN subclass, B-nets, which allows the formulation of a new heuristic function that can be integrated with traditional AI-based search strategies. However, to make this integration useful, the combinatorial explosion encountered in larger problems must be addressed. A hybrid algorithm based on the reduction of the scope of selection and recovery, respectively, has been developed and implemented. Such algorithm has allowed to effectively address the complexity problem while fully exploiting the PN capabilities, an issue not observed in previous work. Experimental studies have showed promising results in terms of optimality and also have shown the superiority of the approach over previous work integrating PN with AI-based search methods. Both PN’s analysis capabilities and PN-based exploration of alternatives have shown the convenience of the use of PNs as a representation formalism for the scheduling of complex manufacturing scenarios based on AI-based search strategies.