ABSTRACT
This chapter presents a Petri net-based method for deadlock-free scheduling of automated manufacturing systems. It investigates different hybrid heuristic search strategies for scheduling of automated manufacturing systems in a Petri net framework. Petri net theory has been applied for modeling, analysis, simulation, planning, scheduling, and control of flexible manufacturing systems. The hybrid heuristic search strategies combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The boundedness, liveness, and reversibility of Petri nets have their significance in manufacturing systems. An optimal event sequence is sought in a timed Petri net framework to achieve minimum or near minimum makespan. Once the Petri net model of the system is constructed, given initial and final markings, an optimal schedule can be obtained using the algorithm. The chapter the two hybrid heuristic search strategies best first- backtracking (BF-BT) and BT-BF through their applications to a semiconductor test facility scheduling.
