Based on Petri net (PN) models of automated manufacturing systems, this paper proposes a deadlock prevention method to obtain a maximally permissive (optimal) supervisor while minimizing its structure. The optimal supervisor can be achieved by forbidding all first-met bad markings (FBMs) and permitting all legal markings in a PN model. An FBM obtained via a single transition’s firing at a legal marking is a deadlock or marking that inevitably evolves into a deadlock. A lexicographic multiobjective integer programming problem with multiple objectives to be achieved sequentially is formulated to design such an optimal and structurally minimal supervisor. As a nonlinear function, the quantity of its directed arcs is minimized. A conversion method is proposed to convert the nonlinear model into a linear one. With the premise that each place in the supervisor is associated with a nonnegative place invariant, the controlled net holds all legal markings of the net model, and the supervisor has the minimal structure. Finally, some examples are used to illustrate the application of the proposed approach.