Deadlock-free scheduling of an automated manufacturing system based on Petri nets

This paper presents a Petri net based method for deadlock-free scheduling of an automated manufacturing system. The deadlock states are explicitly defined in the Petri net framework. Thus no equation is needed to describe deadlock avoidance constraints to derive deadlock-free schedules as done using mathematical programming techniques. A hybrid heuristic search algorithm which combines heuristic best-first search and controllable backtracking search is employed to generate an optimal or near-optimal deadlock-free schedule. The issues such as deadlock, multiple lot size, limited buffer size and material handling (loading/unloading) are explored through an automated manufacturing system adopted from the work of Ramaswamy and Joshi (1996)