Scheduling Problems for a Class of Hybrid FMS Using T-TPN and Beam Search

This paper is about scheduling problems for a class of flexible manufacturing systems (FMS) that have some operations with total precedence constraints and other operations with full routing flexibility (namely hybrid FMS). The objective is to find a control sequence from an initial state to a reference one in minimal time. For that, a systematic multi-level formalism is introduced to model the hybrid FMS based on the hierarchical structuration of the operations. Transition-timed Petri nets (T-TPN) that behave under earliest firing policy are used for that purpose. Then a new cost function is introduced to estimate the residual time to the reference. This estimation is proved to be a lower bound of the true duration. A modified Beam Search algorithm is proposed that uses the cost function to selectively explore the Petri net (PN) state space. Computational experiments illustrate the efficiency of the approach in comparison with other existing methods.