An evolutionary hybrid scheduler based in Petri net structures for FMS scheduling

摘要

This paper addresses a hybrid scheduling methodology for Flexible Manufacturing Systems (FMS) that uses Petri nets (PN) as a modeling tool and several successfully employed scheduling methods: conflict- solving based on heuristic dispatching algorithms, Artificial intelligence (Al) heuristic search, problem decomposition and evolutionary approximation algorithms as search tools. PNs have been traditionally employed in scheduling approaches based on discrete event simulation and recently, the combination of PN and Al heuristic search has produced interesting results. PNs also allow easy structural analysis towards a decomposition of the problem. In this paper PNs are employed as a representation paradigm and a decomposition-construction scheduling method is built over them. A PN-based Al systematic heuristic search is used to solve sub-problems which are progressively joined by an evolutionary building procedure. Experimental results based on a preliminary implementation of the method are presented.