On the complexity of optimal deadlock avoidance in flexible manufacturing systems Conference Paper

abstract

• The problem of the manufacturing system deadlock has received considerable attention recently, since its effective solution is a prerequisite to the implementation of large-scale flexibly automated discrete-part manufacturing systems (FMS). Its difficulty arises from the fact that in the FMS context, the computation of the optimal deadlock avoidance policy is NP-hard. This paper proves, though, that for a large subclass of FMS, with significant practical relevance, the optimal DAP is polynomially tractable in real-time. The implications of this result to broader FMS classes are also considered.

authors

• Lawley, Mark

published proceedings

• Proceedings of the American Control Conference

author list (cited authors)

• Reveliotis, S. A., Lawley, M. A., & Ferreira, P. M.

complete list of authors

• Reveliotis, SA||Lawley, MA||Ferreira, PM

publication date

• January 1997

published in

• Proceedings of the ... American Control Conference. American Control Conference  Journal

start page

• 1008

end page

• 1012

volume

• 2