ThispaperproposesandevaluatestwoimprovedPetrinet(PN)-basedhybridsearchstrategiesandtheirapplicationstoflexiblemanufacturingsystem(FMS)scheduling.Thealgorithmsproposedinsomepreviouspapers,whichcombinePNsimulationcapabilitieswithA*heuristicsearchwithinthePNreachabilitygraph,maynotfindanoptimumsolutionevenwithanadmissibleheuristicfunction.Toremedythedefectsanimprovedheuristicsearchstrategyisproposed,whichadoptsadifferentmethodforselectingthepromisingmarkingsandreservestheadmissibilityofthealgorithm.Tospeedupthesearchprocess,anotheralgorithmisalsoproposedwhichinvokesfasterterminationconditionsandstillguaranteesthatthesolutionfoundisoptimum.TheschedulingresultsarecomparedthroughasimpleFMSbetweenouralgorithmsandthepreviousmethods.Theyarealsoappliedandevaluatedinasetofrandomly-generatedFMSswithsuchcharacteristicsasmultipleresourcesandalternativeroutes.
