Hybrid Heuristic Search Based on Petri Net for FMS Scheduling

This paper describes FMS scheduling problem based on Petri net with the goal of minimizing makespan. A hybrid heuristic search approach for the scheduling is presented, which combine dynamic search window with best-first algorithm and backtracking search., In addition redundant markings can be eliminated to reduce the searched state space. We use the proposed method to search for an optimal schedule of an example with varied lot sizes for each job type considered. Comparison with previous work is given to show the proposed approach can generate an optimal solution, but with much less search time and memory space. This hybrid algorithm can be deal with large systems.