Title :
Deadlock avoidance for manufacturing systems with partially ordered process plans
Author :
Sulistyono, Widodo ; Lawley, Mark A.
Author_Institution :
Sch. of Ind. Eng., Purdue Univ., West Lafayette, IN, USA
fDate :
12/1/2001 12:00:00 AM
Abstract :
Most deadlock avoidance work in manufacturing deals with systems where each part type requires a fixed sequence of operations. In contrast, the paper deals with those systems that support sequencing flexibility, that is, the operations required by the part are partially ordered. In this setting, the order in which operations are performed is not predetermined but becomes a real-time decision. Specifically, the paper presents a detailed resource allocation model and proves the NP-completeness of optimal deadlock avoidance for a highly flexible subclass of these systems. It also identifies several cases and conditions for which optimal deadlock avoidance is of polynomial complexity
Keywords :
computational complexity; concurrency control; discrete event systems; flexible manufacturing systems; industrial control; real-time systems; resource allocation; NP-completeness; deadlock avoidance work; discrete event dynamic systems; fixed operation sequence; flexible manufacturing; flexible sequencing; manufacturing systems; optimal deadlock avoidance; part type; partially ordered process plans; polynomial complexity; real-time decision; resource allocation model; sequencing flexibility; Automatic control; Flexible manufacturing systems; Industrial engineering; Manufacturing automation; Manufacturing processes; Manufacturing systems; Polynomials; Resource management; Supervisory control; System recovery;
Journal_Title :
Robotics and Automation, IEEE Transactions on
