Abstract： The place-timed Petri net was used to model the flexible manufacturing system scheduling problems. Combined with the execution capacity and heuristic search, Petri net can achieve the minimum makespan strategy by expanding the partial reachability tree. The heuristic function for calculating the machine remaining operation time was improved. First, remaining operations for general FMS were classified into two categories to guarantee the optimality. Besides, the remaining time of onprocessing operations was also considered, which improved the lower bound for heuristic function. As a result, the optimal scheduling strategy could be achieved in less effort. Experiment results demonstrate the proposed heuristic function performs better as expected.