Structural analysis and control of resource allocation systems using Petri nets

Sequential resource allocation among concurrently executing technological applications, like flexibly automated production environments, driver-less transportation systems, and workflow management systems. In the resulting modeling framework, characterized as a sequential resource allocation system (RAS), the competition of the processes for the finite system resources gives rise to conflicting situations that need to be carefully controlled.; In this thesis, we consider the problem of synthesizing the structural control policy (SCP) that ensures the logically correct and consistent operation of sequential RAS. Specifically, the first part of the thesis considers the most fundamental RAS class, SU-RAS, in which every process stage requires only a single unit of a single resource. It develops a novel modeling and analysis framework for SU-RAS controlled under an SCP, by unifying the current theoretical developments in the fields of Petri net (PN) structural analysis and deadlock avoidance. It also provides a computational tool for evaluating the correctness of SCPs, and enhancing the permissiveness of currently known SCPs.; In the second part of thesis, the aforestated PN-based modeling framework is extended so that it covers the class of CD-RAS, in which multiple resource acquisitions and routing flexibility are allowed, and a new structural characterization of liveness for this class of systems is developed. Furthermore, a polynomial-time SCP for the CD-RAS is proposed, and the policy flexibility is enhanced through the pertinent exploitation of the policy parameterization, and the systematic relaxation of the policy-imposed constraints. Subsequently, the results on the CD-RAS are further extended by analyzing the liveness properties of new RAS class, named ECD-RAS, resulting from the introduction of internal rework loops to the CD-RAS routing structure, and presenting a series of computational methods for the synthesis of polynomial-complexity SCPs appropriate for the ECD-RAS.; Finally, the problem of synthesizing computationally efficient SCPs for the ECD-RAS with forbidden states and uncontrollable events, is considered. We develop an SCP that can effectively accommodate uncontrollable job routings, uncontrollable resource allocations, and additional, externally imposed logical specifications. The thesis concludes with a discussion on potential extensions to this work.