Search strategy for scheduling flexible manufacturing systems simultaneously using admissible heuristic functions and nonadmissible heuristic functions

• A Petri net based search strategy for FMS scheduling is proposed.
• The method can simultaneously use admissible and nonadmissible heuristic functions.
• The resulting combinational heuristic function is still admissible.
• The combinational function is more informed than any of its constituents.

To scheduling flexible manufacturing system (FMS) efficiently, we propose and evaluate an improved search strategy and its application to FMS scheduling in the P-timed Petri net framework. On the execution of Petri net, the proposed method can simultaneously use admissible heuristic functions and nonadmissible heuristic functions for A* algorithm. We also prove that the resulting combinational heuristic function is still admissible and more informed than any of its constituents. The experimental results of an example FMS and several sets of random generated problems show that the proposed search method performs better as we expected.