This paper introduces a unified supervisory control framework for automated manufacturing systems (AMSs) based on Transition-Bounded Unbounded Petri Nets (tUPNs). The approach integrates hierarchical Generalized Mutual Exclusion Constraints (GMECs) with decentralized predicate-based supervision to address scalability, fault tolerance, and real-time adaptability in distributed manufacturing. By enforcing boundedness at critical transitions, tUPNs enable accurate modeling of high-throughput systems while preserving liveness and safety through P-semiflow invariants. The hybrid architecture combines centralized supervisors with local feedback controllers to ensure deadlock-free operation. Simulation-based validation demonstrates robust performance: 97.2% recovery success, zero deadlocks, and stable throughput (1.66 ± 0.01 parts/s) under dynamic faults. The framework achieves polynomial-time complexityO(|T|) and provides a direct mapping to IEC 61131-3 constructs, supporting future industrial deployment.

The transition from classical automated manufacturing to high-volume, asynchronousSystem-of-Systems(SoS) architectures has exposed a fundamentaltractability collapsein Petri-net-based supervisory control. Existing frameworks face an inherent expressiveness–control trade-off: bounded models guarantee decidability only by imposing artificial material-flow constraints, while unbounded Petri nets (UPNs) capture manufacturing realism but suffer from state-space explosion and observational delay. This paper formalizes eight structural shortcomings (S1–S8), referred to as theDetectability Fight, which prevent existing paradigms from achieving simultaneous scalability and semantic fidelity. We show that supervisory approaches based on non-bisimilar abstractions cannot ensure safety and liveness without sacrificing performance. To resolve this limitation, we introduce theTransition-bounded Unbounded Petri Net (tUPN)framework. By shifting the supervisory locus from place-centric capacity constraints (stock) to transition-centric execution causality (flow), tUPN enables deterministic supervisory control withlinear-time complexityO(n), even in the presence of unbounded work-in-process. We further demonstrate that the tUPN constructs (K, κt, ϕt) admit direct realization withinISA-95 manufacturing hierarchies andIEC61131-3-compliant PLC runtime environments, providing a formally verified supervisory envelope for safe AI-assisted optimization. This work establishes an execution-centric foundation for scalable, plug-and-play supervisory control in next-generation manufacturing systems.

Assembly operations are common in automated manufacturing systems (AMSs). AMSs with assembly operations belong to complex systems due to their complicated structures. The traditional supervisory control techniques (SCTs) are generally not suitable for such large-scale systems. In this article, we propose a distributed control technique for AMSs with assembly operations to achieve a near-optimal liveness enforcement. Specifically, we define a type of decomposable system modeled by decomposable augmented marked graphs (AMGs) and create buffer-linked AMGs (BAMGs) by connecting each subsystem through buffers with specified capacities. Next, we construct the complemented subsystems to ensure structural completeness and simplify their structures to condense their reachability graphs. By conducting liveness analysis of BAMGs employing siphons, we demonstrate that the liveness of BAMGs depends solely on that of each individual subsystem. Finally, we design monitors for simplified subsystems utilizing reachability analysis and achieve distributed control of AMGs. Since the scale of reachable states is greatly reduced in simplified subsystems compared with the original AMGs, our method can save a significant amount of computation. An experimental study demonstrates the effectiveness of the proposed method.

Deadlock and blocking issues have received more and more attention in automated manufacturing systems (AMSs). This article studies an adaptive supervisory control problem for AMSs with multiple unreliable resources which may fail at any time. By using general Petri nets (PNs), each processing stage in the AMSs under consideration allows to utilize multiple types and quantities of resources. Based on a transformation technique, a general net is first converted to an ordinary net. In an ordinary net, a set of formulas is used to check the undermarked siphons, each of which is designed as a control place to prohibit it from being undermarked. By analyzing the relationship between the unreliable resources and the detected siphon, an adaptive controller is designed which can automatically adjust working modes such that the undermarked siphon caused by resource failures is marked. Finally, an adaptive supervisory controller is iteratively synthesized for AMSs with unreliable resources to ensure the controlled system can execute continuous operations even if unreliable resources malfunction. A representative example is given to illustrate the effectiveness of our approach.

Resource failures are commonly viewed in automated manufacturing systems (AMSs), such as control errors and mechanical failures. Therefore, a robustness analysis and control policy are highly desirable. Different methods are proposed by researchers and practitioners. However, they are incapable of performing robustness analysis for partially observable AMSs since few works consider the existence of unobservable events. In this article, we solve the robustness analysis and control problem for partially observed AMSs in the paradigm of Petri nets (PNs). A marking is denoted as a robust (resp., nonrobust) one if from it the system can (resp., cannot) proceed continuously even though there exist resource failures. We show that the robustness of markings under partial observation can be determined using a compact reachability graph (RG), namely, a remarkably reduced RG. Then, we define robustness observability, and propose a simple method to check the robustness observability with respect to a given set of robust markings. Finally, we design robust controllers under partial observation so as to ensure continuous production of partially observable AMSs against resource failures.

In recent years, due to the complexity of workflow processes and the fluctuation of business environments, the timed security requirements of workflow processes have attracted more and more attentions from the designers and users of workflow processes. The existing methods cannot analyze the security requirements of data-aware workflow processes with dynamic changes. In this paper, we propose a novel analysis approach to verify timed security requirements for data-aware workflow processes with dynamic changes. First, we analyze the feasibility of changes on workflow processes. Second, we propose the analysis procedure to automatically determine the affected segments of changes. Third, the timed security requirements affected by changes are obtained and verified without repeatedly analyzing all of them. Compared with the existing works, our approach can detect incorrect changes in advance so as to avoid meaningless analysis, also can reduce the cost and time of enterprises as well as eliminate repeated verification of all timed security requirements.

In the paradigm of Petri nets (PNs), this paper focuses on the maximally permissive robustness analysis for automated manufacturing systems (AMSs) with arbitrary resource failures through server failure detection. First, unreliable system of sequential systems with shared resources (U-S4Rs) are constructed by adding detection subnets to the original PNs for each unreliable place. Based on different failed statuses of unreliable resources, the reachable marking set of a U-S4R is partitioned into one safe and multiple failed subsets, where there exists a one-to-one relationship between all markings in the safe subset and those of the original system. Second, subnet systems corresponding to part types are categorized to provide the definitions of the robust, strongly robust, and weakly robust markings. Third, we provide algorithms to compute the sets of strongly connected, weakly connected, and dangerous markings in each failed zone. When resources are in a failed statusXf, we establish anXf-failure-dependent marking set. The robustness of all markings within that set can be evaluated by examining the connectedness of the markings derived from those in that set. Moreover, for all markings not in theXf-failure-dependent marking set but in the safe subset, we provide conditions further to determine the robustness of these markings. Finally, examples are presented to illustrate the proposed methods and show the advantage over the existing ones.

As one of the essential issues when designing optimal control policies for automated manufacturing systems (AMSs) with unreliable resources, maximally permissive behavior should be ensured for the controlled system. This paper is devoted to the maximally permissive robustness analysis for AMSs allowing multiple server failures. First, all subnet systems are categorized by their usage of unreliable resources so as to provide more general definitions of the robust, strongly robust, and weakly robust markings. Second, we provide algorithms to compute reduced reachability graphs (R2Gs) and strongly connected components (SC2s), respectively. Then, the necessary and sufficient conditions to verify the robustness of markings are obtained by analyzing the transitions involved in each component in an SC2 and the relation between markings in the disconnected marking subset and SC2. Finally, the effectiveness and efficiency of the theoretical results are validated via examples. Note to Practitioners—Maximally permissive robustness analysis is an essential criterion for evaluating the control performance of robustness for AMSs with failure-prone resources. Ineffective handling of resource failures can lead to unexpected disruptions, decreased throughput, and diminished product quality. While much research has focused on developing robust control policies to ensure system resilience, there remain certain states that do not comply with these policies, even when they are designed to be robust. We present significant findings that assess the robustness of all system states when unreliable resources experience various failure scenarios. These results allow the researchers to design optimal robust controllers, thereby significantly enhancing the flexibility and efficiency of manufacturing processes. By applying the results of our robustness analysis, manufacturers can better prepare for and respond to resource failures, ultimately improving overall production performance.

Cloud manufacturing (CMfg) service systems can provide solutions for large-scale personalized customization. Service composition optimal selection, which is in charge of the selection and allocation of cloud services to multiple tasks, is of great importance for providing significant improvement of CMfg service systems with respect to performance measures such as time and cost. To increase resource utilization and decrease cost consumption, we develop a design method of production schemes for CMfg service systems. Specifically, we define a formalism named transition-rewritable Petri nets (RTPNs) to model and reconfigure the multi-task manufacturing processes in environments allowing resource uncertainty. The reconfiguration process is described by the rewritable rules of RTPNs. On this basis, the performance of the reconfiguration of the manufacturing process is analyzed. In addition, we establish a production strategy considering reconfiguration to obtain the optimized service compositions in terms of time, cost, quality, and reliability. Theoretical comparisons highlight the distinctions between our method and the others in the existing literature. Moreover, the results of simulation experiments and comparative studies show that the method proposed in this paper can obtain better schemes with the lower total completion time and total production cost than a closely-related one presented in a recently published paper.Note to Practitioners—The uncertainty of resources exists when using cloud manufacturing service system based on distributed resources to complete manufacturing tasks. However, for the large-scale orders, the resource uncertainty is rarely considered by existing work in the literature. This paper proposes a production strategy to ensure that the utilized schemes are always feasible and optimal despite resource uncertainty. A type of Petri nets is defined to model the manufacturing process for the purpose of reconfiguration of the production schemes when the some services change due to resource alterations. Total completion time and total cost are significant considerations. A problem decomposition based genetic algorithm is employed to generate production schemes, which can be easily implemented.

Event-aware information flow security in cyber–physical systems (CPSs) emphasizes the correlation among events. Event-aware noninterference is a security property capable to describe such a correlation. In light of the event-aware noninterference assessment problem, system modeling is a common means, and many studies have been done on such a problem by using formal modeling tools, i.e., Petri nets (PNs), at present. However, classical PNs suffer from the lack of modeling for patterns with semantic sharing of events, which can be modeled by labeled PNs (LPNs). In this article, we present the concept of semantics-based noninterference for the CPSs modeled by LPNs and focus on the assessment problem of semantics-based noninterference properties represented by semantics-based strong nondeterministic noninterference (SNNI) and extended bisimulation SNNI (EBSNNI). To this end, we first give the formal definitions of semantics-based SNNI and EBSNNI. Then, we analyze the assessment mechanisms of them according to the characteristics of semantic sharing of events in LPNs. On this basis, we provide the semantics-based noninterference assessment method involving the coarse and fine assessments to reveal the event-aware security of CPSs. Finally, a case study is provided to explain the significance of our research and the effectiveness of our method.

In the field of workflow management, a recent hot research point is to analyze secure collaboration plans of multiple workflow processes with dynamic relations and shared users. However, existing research works neither consider the time limits of timed dynamic relations (TDRs), nor analyze the delayed time of activities caused by shared users. In this article, we propose a new approach to analyzing secure collaboration plans of multiple workflow processes withTDRs and user conflicts: 1) we propose the computing patterns for basic structures in workflow processes withTDRs and shared users; 2) we develop the next-generation parametric sprouting graph (NPSG) based on the above patterns; and 3) we obtain the optimal secure collaboration plan based on NPSG. Compared with the existing methods, our approach can effectively deal with the problem of collaboration plans withTDRs and shared users. Furthermore, our approach is more efficient, because NPSG of multiple workflow processes can be constructed in parallel and its recommendation ability is improved by deleting invalid paths in advance.

This article concentrates on maximally permissive robustness analysis for automated manufacturing systems (AMSs) that allow multiple server failures in the paradigm of Petri nets (PNs). First, we fully describe resource failures in a more general perspective, formalized as generalized dangerous transitions, and develop an algorithm for computing the set of these transitions. The presence of such transitions results in all subnet systems being divided into two types: dangerous subnet systems and nondangerous subnet systems. Second, based on the number of nondangerous subnets consistently operated, the more general definitions of strongly robust, weakly robust, and nonrobust markings are established. Third, generalized reduced reachability graphs (R2Gs) are constructed to provide a formal tool for robustness analysis. An algorithm is formulated to compute the maximum nondangerous elementary circuits (NDE circuits) for each marking in generalized R2G. Subsequently, by analyzing the transitions involved in the maximum NDE circuits, we derived the necessary and sufficient conditions for identifying the robustness of markings. Finally, examples are provided to demonstrate the proposed methods and illustrate their advantages over existing approaches.

This study tackles the issue of deadlock resolution in networked automated manufacturing systems (AMSs) with communication delays and losses in the framework of Petri nets (PNs). First, we refer to the transitions in which communication losses may occur as loss transitions and mathematically model the communication delays and losses. Second, we derive a necessary and sufficient condition for determining whether deadlock can be resolved in networked PNs, referred to as the networked deadlock resolution controllability theorem (NDRCT), within the framework of the observed reachability graph (ORG). Through the ORG, the networked supervisor can intuitively obtain the estimated marking set for a specific observation in the presence of communication delays and losses. Based on NDRCT, one can determine whether deadlock can be resolved and how to design the controller to avoid deadlock in networked PNs with communication delays and losses.

User delegation is a type of access control mechanisms that allow a person to delegate all or part of his$/$her authorities to others. It is an important access control policy that can significantly improve workflow flexibility. A crucial requirement after delegations is to check the satisfiability of workflow, i.e., determining whether there exists a valid execution schedule ($ES$) in the workflow that can ensure it to proceed from the beginning to the end while satisfying all authorization constraints. Existing works perform in a centralized manner to find such a valid$ES$by exploring all$ES$s. Unfortunately, the enumeration of$ES$s is highly inefficient from the perspective of computational complexity. This study proposes a novel approach to overcoming this difficulty in a distributed way. First, we use Petri nets (PNs) to formalize workflow and user delegations. Then, we directly specify a conflict-free workflow that satisfies all authorization constraints. Hence, determining the satisfiability of a workflow amounts to directly checking the existence of$ES$s in the corresponding conflict-free workflow. Finally, we present a distributed strategy, which is of polynomial complexity, to determine the existence of$ES$s.

The problem considered in this paper is the verification and enforcement of separation of duty (SoD) constraints in attribute based access control (ABAC) systems. We propose an efficient algorithm for checking the satisfiability of SoD constraints. It is based on the idea of partitioning all permissions of SoD constraints into two classes so as to compute the minimal number of users to accomplish each class of permissions, respectively. As a result, several SoD constraints with certain class of permissions can be verified in polynomial time. Experimental results show that our method performs well compared with existing ones. When SoD violations occur, a 0-1 integer programming (IP) based enforcement solution is presented such that SoD violations can be solved once for all and it is provably shown that such solution does not result in the violation of other SoD constraints.

Given a role-based access control (RBAC), resiliency checking problem (RCP) aims at determining whether every permission is executed by a user and all authorization constraints are satisfied when some users become absent. Although the problem is computationally hard, desirable solutions are still expected so as to guarantee the continuity of access control. In this article, we solve RCP for RBAC based on constraint enforcement and mathematical programming. We use Petri nets (PNs) to formalize RBAC. It is shown that each separation of duty constraint imposed on a PN modeling of RBAC can be enforced by a maximally permissive PN-based control structure. After implementing such control structure on the PN modeling of RBAC, we can obtain an admissible RBAC. We show that RCP of RBAC can be transformed into another problem, which determines whether each permission can be executed by a user in the admissible RBAC against the absence of some users. An integer linear programming-based approach is presented to accomplish such verification. The comparison between our approach and the existing one is given to illustrate the effectiveness and efficiency of ours.

There are two foundational problems in automated manufacturing systems. One is to determine their robustness (i.e., checking whether a marking is robust or nonrobust) while the other is to determine their liveness (i.e., determining whether a marking is live, bad, deadlock, or livelock). However, existing methods deal with them separately. This renders the existing methods inefficient in practice. In this article, we investigate the relation between robustness and liveness. First, we show how to define robustness in different net systems, i.e., the live, bounded, and nonreversible or reversible net systems. Second, we present a reachability graph-based method to assess the robustness of markings. Third, we clarify the relation between robustness and liveness, and conclude that liveness is a special case of robustness, under which the set of unreliable transitions is null. As a result, the robustness determination method developed in this article proves to be much general and can be used to check the liveness of each marking.

Marking estimation is crucial in the area of discrete event systems. This paper proposes algorithms for addressing the problem of minimum initial markings (MuIMs) estimation in a known Petri net (PN) structure. The existence of unobservable transitions makes this problem challenging since the number of transition sequences consistent with an observed label sequence can potentially be infinite. It is assumed that only minimal explanations can fire before the firing of each observable transition (OT). We present the definition of minimal explanation places, which allows potential minimal explanations to fire before the firing of each OT to obtain more minimal initial markings. Since the number of initial markings may be infinite, we aim to obtain the initial markings that not only enable at least one transition sequence consistent with both the observed label sequence and the PN structure, but also exhibit the minimum total number of tokens (i.e., the minimum total number of tokens when summed over all places). After developing the algorithms, we also propose two heuristic methods to reduce the computational cost, resulting in a subset or an approximation of the final MuIMs. An illustrative example is provided to indicate how the proposed algorithms and heuristics can be utilized to reveal the minimum number of resources required which are indispensable at the initial state for the completion of a specified task sequence.

Distributed motion control is critical in multiple mobile robot systems (MMRSs). Current research usually focuses on either discrete approaches, which aim to deal with high-level collisions and deadlocks without considering the low-level motion commands, or continuous approaches, which can optimize low-level continuous commands to mobile robots but cannot deal with deadlocks efficiently. In this article, by combining discrete and continuous methods, we design a hybrid motion control method for MMRSs where each robot should move along a predefined path. First, each robot’s motion is modeled as a discrete transition system, based on which a real-time supervisory control policy is illustrated to avoid collisions and deadlocks. Second, according to the discrete decisions, the continuous speed at each discrete state is computed using model predictive control and sequential convex programming. The proposed hybrid approach brings two advantages. First, the discrete control component guarantees collision and deadlock avoidance and reduces the scale of the optimization problems. Second, continuous control optimizes the continuous speed in real time and fulfills other performance requirements like time and energy costs. To move in a fully distributed way, each robot needs to predict the motion of its neighbors by retrieving their immediately available information through communications. The simulation and real-world experimental results show the effectiveness of our approach.

Deadlock avoidance of flexible manufacturing systems (FMSs) has received increasing attention from both academic and industrial communities. There have been a large number of different types of deadlock avoidance policies discussed in the literature. However, how to avoid deadlocks in an efficient way is still one of the major obstacles, especially for large systems. In this paper, we propose a new Petri net structure, i.e., event circuit structures ($ESs$), based technique to overcome this difficulty. First, we provide details of$ESs$and develop an algorithm to calculate$ESs$in the systems of sequential systems with shared resources ($S^{4}Rs$). Second, we analyze the liveness of$S^{4}Rs$using undermarked$ESs$. A necessary and sufficient condition between undermarked$ESs$and deadlocks of$S^{4}Rs$is established. Third, we describe how undermarked$ESs$can be applied to avoid deadlocks for$S^{4}Rs$. Only structure information is needed during this procedure, thereby improving the efficiency and convenience of deadlock avoidance. Several examples are presented to illustrate our approach. Note to Practitioners—Deadlock avoidance of flexible manufacturing systems (FMSs) is extremely important in real-world manufacturing scenarios. A large body of deadlock avoidance policies are presented in the existing literature. Through an effective deadlock avoidance policy, all deadlocks can be prevented from happening in advance, so as to avoid the reallocation of resources and the re-execution of deadlocked processes. This shortens the production cycle of systems and improves the utilization of resources. However, most existing approaches suffer from formidable computational difficulty since they necessarily rely on the whole reachability graph to avoid deadlocks. In this paper, we present event circuit structures ($ESs$) as a new technique for deadlock avoidance. We show that undermarked$ESs$can be used to avoid deadlocks by using only key structure information instead of complicated state information. Thus, it not only can greatly improve the efficiency of predicting deadlock markings for FMSs, but also reduce operating costs as much as possible while ensuring stable operation of FMSs.

In this paper, we address the robustness analysis problem of automated manufacturing systems with uncontrollable events in the paradigm of Petri nets (PNs). First, we formalize unreliable resource failures as the removal of all ingoing transitions of unreliable resource places (denoted by unreliable transitions hereafter). Second, we obtain a necessary and sufficient condition to check the robustness of markings, so called robustness controllability theorem (abbreviated as RCT hereafter) in the paradigm of reduced reachability graph (abbreviated as R2G hereafter). All markings involved in the R2G of a PN are equivalent to that of its reachability graph, except that all arcs associated to unreliable transitions are removed from R2G. Based on RCT, the robustness of all markings in an R2G can be determined. An example is proposed to illustrate the approach. Note to Practitioners—In reality, it is an urgent issue to analyze the behaviors of automated manufacturing systems (AMSs) so as to guarantee their stable operation against resource failures, e.g., the missing of a signal or the failure of a sensor. In this connection, different methods are proposed to deal with the robustness analysis and control problem of AMSs with unreliable resources. The objective is to avoid any deadlock in the AMSs or to ensure the liveness of the subsystems that require only reliable resources when there exist resource failures. Due to limited actuating and sensing abilities, AMSs may be partially controlled, i.e., there exist events whose firing may not be inhibited by an external action. However, fewer research works consider this practical situation when handling robustness analysis and control issue, which renders the existing approaches impracticable. In this paper, we solve the robustness analysis problem of AMSs with uncontrollable events by using Petri nets. A necessary and sufficient condition is proposed to check the robustness of markings, called robustness controllability theorem (abbreviated as RCT hereafter) in the paradigm of reduced reachability graph. With the aid of RCT, the robustness of all markings can be determined so as to guarantee the flexibility of AMSs.

Currently, recommending collaboration plans of dynamic multiple workflow processes under security requirements or constraints has become a hot topic, as it not only can reduce the risk during execution, but also can avoid enormous financial loss caused by security breaches. However, the existing methods cannot solve the parametric problem caused by dynamic relations of multiple workflow processes or recommend an optimal collaboration plan because of erroneous information. In this article, we propose a new approach to recommend security-aware collaboration plans for multiple workflow processes with dynamic relations. First, we develop three basic computing patterns of dynamic relations and construct a parametric sprouting graph for multiple workflow processes with dynamic relations. Second, we present the procedure of recommending an optimal secure collaboration plan that satisfy security requirements. By comparison with the existing methods via two experiments, our approach not only can solve the parametric problem caused by dynamic relations of multiple workflow processes, but also can recommend an optimal secure collaboration plan under security requirements.

It is very important to obtain assignment plans of roles and users for business processes or workflow processes under security requirements in enterprises. The assignment plans can help the enterprises improve the efficiency of execution as well as reduce their costs. However, the existing methods ignore the dynamics of users and roles, and cannot deal with security requirements. In this article, we propose a new approach to solve the problem of dynamic assignment of roles and users for business processes under security requirements. First, a role and user assignment graph (RUAG) based on Petri nets is constructed to record detailed information about assignment plans. Second, the optimal composition of assignment plans meeting security requirements is extracted from RUAG for multiple concurrent business processes. Third, we analyze the changes of assignment plans during execution of business processes and present the procedure to adjust them. Compared with the existing methods, our approach can improve the accuracy of assignment plans, enhance the efficiency of dynamic assignment, and reduce the costs of enterprises.

This paper focuses on constraint verification and violation resolution for Petri nets (PNs) modeling of role-based access control (RBAC) policy. Checking the satisfiability of authorization constraints imposes a major challenge when the number of states of a target system is large. To overcome this difficulty, we provide three necessary and sufficient conditions to check three different constraints, namely Separation of Duties (SoDs), Binding of Duties (BoDs), and Constraints of Cardinality (CoCs). The proposed results are based on the solutions of integer linear programming problems (ILPs). By relying on an ILP formulation that does not require the explicit computation of the net reachability set, the proposed approach is particularly well suited for large-size PNs. When the given system does not satisfy a considered constraint, the objective is to propose a suitable violation resolution strategy to correctly enforce the given constraint. In this paper, enforcement of control places and administration of RBAC are presented to solve the SoD, BoD, and CoC violations. All violations can be corrected in a once for all manner while simultaneously ensuring the satisfaction of all other constraints. The comparison between our approach and the existing ones is given to illustrate the effectiveness and efficiency of ours.

One of the noteworthy investigations in workflows is the implementation of authorization-related security requirements. There are two typical security requirements, i.e., separation of duty (SoD) and binding of duty (BoD). However, most of the previous works are only focused on SoD while ignoring BoD. In this article, we consider both of them by proposing an extended-structural implementation approach, namely beacon-based firing control, to enforce security requirements. Thanks to the flexibility of beacon-based firing control, both BoD and SoD can be enforced in a straightforward way with no sophisticated operations for their implementation, although they are a pair of security requirements in conflict. As a preparation of beacon-based firing control, we define the beacon-extended Petri nets (PNs) by introducing a new object, namely beacon, to PNs so as to lay the foundation. In addition, we present the firing-based linear equations and inequalities for BoD and SoD to provide the standardized descriptions for their implementation. For the sake of expansibility, the applicability analysis is provided for the more general security requirements. Ultimately, the comparative experiments and discussions are presented to show the effiectiveness and efficiency of the proposed approach.

Authorization-related security requirements are of great significance in workflow management systems. Existing studies are restricted in their scopes of research. There is no unified principle for their implementation. In this paper, we focus on the unification of authorization-related security requirements using Petri nets (PNs). These security requirements are expressed by constraints, being imposed on tasks, namely task-based security requirements (TSRs). By downgrading TSRs to a kind of authorization-conflict relationship, we provide a standardized expression for TSRs. Such a standardized expression can be transformed to firing-based linear inequalities which are a more general representation of constraints. Then, we propose the firing control for the unified implementation of TSRs based on firing-based linear inequalities. In fact, firing control is enforced by structural controllers namely monitors which are structurally consistent with PNs. For the sake of conciseness, simplification techniques are provided for the monitors. Ultimately, the experiments and discussions are presented to show the performance and advantages of the proposed approach.

In automated manufacturing systems, the completion of all essential products must be guaranteed. Hence, each process of a system should have outputs. This outcome requires assurance that a system composed of a set of processes with shared and dedicated resources will operate smoothly. Shared resources can introduce deadlock problems through circular waits. In most methods to investigate the deadlock issues, shared and dedicated resources are assumed to never fail. However, the failure of one resource may cause the real crash of an entire system such that no finished products can output. Systems with unreliable resources are classified in this article into three types: 1) nonrobust systems; 2) weakly robust systems; and 3) strongly robust systems. A robust control method based on this classification is necessary for a system. Two approaches to robust control are developed. First, systems of sequential systems with shared and copied resources$(S^{4} C R\text{s}$), which is a new type of petri nets, is designed to strengthen the robustness of systems. It ensures that processes with unreliable resources complete their products. In addition, based on a deadlock-avoidance algorithm, a robustness algorithm is proposed. This ensures a system can operate without disruption under any situations.

For real-world automated manufacturing systems (AMSs), the failures of multiple unreliable resources are very common. Maximal permissiveness is a key aspect for evaluating the performance of robust control strategies of failure-prone AMSs. However, there exist fewer works in the existing literature that can achieve maximally permissive robustness analysis. This may impede the applicability of existing robust control strategies in realistic AMSs. This article tackles the issue in the paradigm of Petri nets (PNs). We present an innovative mechanism to formalize unreliable resource failures by preventing all ingoing transitions of unreliable resource places from firing. Both reachability graph-based and integer linear programming-based methods are proposed to analyze the robustness of AMSs with either single or multiple unreliable resources. Several examples are proposed to illustrate the approach.

This paper studies the maximally permissive robustness analysis of automated manufacturing systems (AMSs) with unreliable resources in the paradigm of Petri nets (PNs). Two types of robust markings, i.e., strongly robust markings and weakly robust markings, are defined in this paper. We propose robustness equivalence and non-robustness equivalence to characterize the markings that exhibit the same robustness and non-robustness, respectively. Reachability graph (or RG hereafter) is directly used to determine the robustness of markings; however, it is difficult to use in large-scale systems due to formidable computational difficulty. As an alternative, we present a reduced reachability graph (or R2G hereafter) based necessary and sufficient condition to check the robustness of markings, in terms of the liveness analysis of markings in R2G. We show that all safe markings of an R2G correspond to strongly robust markings of the corresponding RG, and deadlock markings as well as their bad markings and livelock markings as well as their bad markings of an R2G correspond to non-robust markings and weakly robust markings of the corresponding RG, respectively. Hence, the robustness of markings in an RG can be determined effectively and efficiently through the liveness analysis of markings in the corresponding R2G. Note to Practitioners—In practical manufacturing scenarios, it is urgent to analyze and control the automated manufacturing systems (AMSs) so as to ensure their continual production against any resource failure. If the failures of an AMS are not handled gracefully, the whole system may fall into a blocking. As a consequence, system production does not meet rapid manufacturing goals and objectives. In this paper, we focus on the maximally permissive robustness analysis of AMSs with unreliable resources in the paradigm of Petri nets. We define two types of robustness in terms of markings, i.e., strong robustness and weak robustness. From the viewpoint of reachability graph, we propose robustness equivalence and non-robustness equivalence among markings and present the procedures to check the robustness of markings. Furthermore, a set of necessary and sufficient conditions are established to provably ensure that the robustness of markings can be determined through liveness analysis in a reduced reachability graph. Therefore, the robustness of markings can be determined in a computationally efficient way.

The problem under consideration in this paper is how to avoid deadlocks and livelocks in the paradigm of Petri nets (PNs). Although deadlock and livelock avoidance has been extensively studied in existing literature, fewer results can be applied to practical automated manufacturing systems (AMSs) due to expensive computations and reduced permissiveness. In this paper, we propose an efficient and maximally permissive control scheme to avoid deadlocks and livelocks by using critical distance. From the perspective of the reachability graph of a PN, critical distance is equal to the maximum number of transitions among all transition sequences from any critical state to its corresponding deadlock or livelock state. First, we show how to calculate the critical distance of a PN in an efficient way by using a portion of reachable states. Then, local reachability graphs are established based on critical distance to avoid deadlocks and livelocks. The provided policy is maximally permissive since only the necessary minimum number of illegal transitions are forbidden at each state. Several representative examples are presented to illustrate our approach. Note to Practitioners—Deadlock and livelock avoidance is a crucial problem in automated manufacturing systems (AMSs). Various methods have been proposed to deal with deadlocks and livelocks by researchers and practitioners. However, there exist fewer works that focus on deep exploration regarding how long a deadlock or livelock will occur from a safe state. As a consequence, the existing works suffer from the disadvantages of being too aggressive or conservative, i.e., checking the whole state space or forbidding many acceptable states when avoiding deadlocks and livelocks. Through the analysis of a partial of reachable states, this paper derives the critical distance of Petri nets modeling AMSs, which is equal to the maximum number of transitions among all transition sequences from any critical marking to its corresponding deadlock or livelock marking. All deadlocks and livelocks, if exist, can be detected at any given marking within the critical distance. Our approach not only is maximally permissive but also explores only a partial of states, thereby mitigating state explosion problem.

Much attention is being paid to security requirements of workflow processes with authorization policies, e.g., safety properties, liveness properties, separation of duties, binding of duties, and constraints of cardinality. However, existing methods neglect the execution condition of activities and the logical structures among activities along with their time attributes, suffer from low efficiency when checking the security requirements of large-scale and structurally complex workflow processes, and provide no solutions as a response to the violations of various security requirements. Thus, existing methods cannot guarantee the absolute security and smooth execution of such workflow processes. In this article, we propose a security team timed automaton (STTA) based approach to analyzing security requirements in timed workflow processes. First, we construct STTAs for timed workflow processes with authorization policies. Second, security requirements are automatically verified based on STTAs. Third, based on two effective strategies, we provide solutions to violated security requirements, if any. Compared with the existing methods, our approach can not only formally describe and analyze five commonly-viewed and frequently-adopted security requirements for timed workflow processes and dramatically decrease their temporal and spatial complexity for verification, but also provide solutions to the violations of security requirements so as to implement the security management of workflow processes.

Separations of Duties (SoDs) are an important class of security requirements in business process management. Their violation may result in system misuse and fraud, leading to economic losses or legal implications. Hence, it is of paramount importance to ensure that a business process meets all SoDs. Existing works usually adopt model checking to verify SoDs. However, building formal models that simultaneously account for both workflow and SoDs is a time-consuming and error-prone activity. In this article, we propose a new approach to specifying and enforcing SoDs in business processes using Petri nets (PNs). First, we derive a necessary and sufficient condition for the SoD violations from the viewpoint of structure and marking of PNs. We show that the SoD constraints can be enforced by disallowing the process to reach certain markings, with the constraints being written as linear inequalities. Then, we design supervisors to enforce SoDs in an off-line and a real-time manner, respectively, based on the linear inequalities. Meanwhile, inequality analysis is provided for the structural simplicity of supervisors. Finally, the complexity analysis of our approach and the comparison with the work in the literature are given to illustrate the effectiveness and efficiency of ours.

In supervisory control of Petri nets (PNs), the place-invariant ($P$-invariant) control principle is the most typical and principal method to deal with the siphon control problem. Although it has a relatively narrow application, this principle is widely acknowledged due to its simplicity and efficiency. In this article, we first propose the extended$P$-invariant control principle in order to extend the application of$P$-invariants and provide a general methodology for the control of siphons. Second, three types of$P$-invariants, from the special to the general, are developed to implicitly or explicitly invariant control the siphons. In the most general case, the virtual$P$-invariants are constructed in the PNs. Third, the extended principle is further applied to the supervisor simplification. In the paradigm of the extended principle, it presents the redundancy from a structural perspective in contrast to several typical methods, and shows the significant importance of structural analysis in PNs, especially the important role of$P$-invariants. As a consequence, the extended$P$-invariant control principle can be considered as the fundamental principle of siphon control as well as its supervisor simplification.

In recent decades, deadlock control for automated manufacturing systems has been an active area. Most researchers have assumed that allocated resources, such as sensors, actuators, and controllers never fail. However, this case is not prevalent in practice due to the unexpected failure of resources. Thus, the objective of robust control is presented in this article. Several methods have been developed along this direction, such as methods that combine neighborhood constraints and the modified Banker’s algorithm, as well as methods based on critical places. To explore their effectiveness and performance, we not only conduct a comparison investigation but also develop new theoretical results. According to the experimental results, critical place-based approaches are simpler, more efficient, and more comprehensive than the Banker’s algorithm-based approaches in response to resource failures. This article is motivated by the control of production Petri nets; however, the results are also applicable to other more complex systems.

In recent years, the research on robust deadlock control has become increasingly popular in automated manufacturing systems (AMSs) because resource failures may lead any system to stagnation, e.g., deadlock. In this article, we study robust supervisory control issues in AMSs with multiple unreliable resources. Petri nets are used to model the considered AMSs that allow multi-quantity and multi-type of resource acquisitions. A set of integer linear programming formulations are introduced to detect a class of deadlocks that have the maximal number of dead transitions. By analysis, a deadlock is characterized by a saturated circuit, which only consists of a set of unmarked resources and a set of critical transitions. Based on the circuit, a linear marking constraint is developed to prevent such circuits from being saturated. A control place (monitor) with its control variable is thus designed for the constraint to prevent the deadlock from appearing even if some resource failures occur. Therefore, we can synthesize a robust deadlock supervisor, which can guarantee that the controlled system can implement the continual operations even if some unreliable resources fail. Finally, the theoretical analysis and comparative study are provided to elucidate the effectiveness and efficiency of our proposed method.Note to Practitioners—In practice, resource failures in automated manufacturing systems (AMSs) are common. Deadlock prevention control in AMSs allowing resource failures has gained more and more attention from researchers and practitioners. Most prior research is based on the enumeration of either siphons or perfect resource transition circuits whose number exponentially increases with the system scale. This means that the synthesized supervisor has a much complex structure. In this article, based on a special kind of circuits at a deadlock marking detected by using a set of mathematical formulations, we develop an effective and efficient method for AMSs with multiple unreliable resources to iteratively control deadlocks such that the controlled system can continue to operate smoothly even if some unreliable resources fail. The computational and comparative results show that our proposed approach can acquire more permissive states with a simpler supervisor.

Generalized mutual exclusion constraints (GMECs) are a class of state specifications on Petri nets (PNs). They are generally enforced on the nets by a simple control structure called control places (monitors). Unfortunately, this conventional procedure is implemented in an offline and monolithic manner, which suffers from computational difficulty and is arduous for the control of a system in real time. Additionally, the flexibility and fault tolerance of such a method are somewhat unacceptable, and the method suffers from a lack of adaptability to net variations incurred by system reconfiguration, communication failure, and constraint integration. This article aims to enforce GMECs for a live PN model by using critical places and marking estimation. First, we define GMECs on some so-called critical places, such that the satisfaction of the GMECs can be determined by only monitoring the number of tokens in their corresponding critical places during runtime. Then, an efficient and effective control strategy is developed such that the controllers forbid all those transition firings that lead to the violated GMECs based on the estimated markings of critical places derived by observers from a resource perspective rather than exploring the markings of the entire system. Finally, we present procedures to deal with decision deadlocks, which are induced by one-sided decisions made by some controllers and may prevent all enabled transitions from firing. Global GMECs are always implemented through the local observation and control of processes without knowing an extra information.

In a multidomain application environment, it is of paramount importance for different organizations to collaborate with each other to facilitate secure interoperation. However, various types of conflicts related to access control constraints may arise as a result of integrating access control policies for individual domains, such as role inheritance violations (RIVs) and separation of duty violations (SoDVs). Current methods solve the conflicts in a centralized way by withdrawing or removing all crossdomain relationships resulting in the violations with the knowledge of all domains. However, these methods are inappropriate for large-scale systems due to their high computational complexity. In this article, we propose a distributed approach to avoid secure conflicts in a multidomain environment. We first model the role inheritance hierarchies of multiple domains as an interoperation graph. We then develop RIVs and SoDVs avoidance algorithms based on the interoperation graph and the communications among different domains. Each domain can execute the algorithms autonomously and in real time by evaluating whether its succeeding activated role can result in RIVs and SoDVs. We show that the new algorithms perform well in contrast to the existing algorithms.

Deadlock is a rather undesirable case in automated manufacturing systems (AMSs). The appearance of deadlock can cause the partial or total stagnation of a system. So far, a large number of deadlock control policies have been developed; nevertheless, the majority are dependent on the assumption that allocated resources cannot break down. In the real world, an AMS consists of a set of concurrent production routes that share and compete for a limited number of resources, such as automated material/component handling devices, buffers, robots, and machines. Resource failures occur unexpectedly. If reasonable control does not exist, a simple resource failure can lead an entire system to stagnation, which can cause enormous economic loss. Therefore, researchers have gradually paid attention to AMSs allowing resource failures in recent years. In this paper, we focus on reviewing and comparing various robust supervisory control policies from the perspective of their structural complexity, behavioral permissiveness, and computational complexity. Some potential future directions are explored. This paper provides a reference source of robust supervisory control of AMSs for researchers and practitioners in this area. Note to Practitioners-In automated manufacturing systems (AMSs), resource failures are common. Their occurrences can lead a system to stagnation, which can cause unnecessary downtime and bring vast economic loss for enterprises. To resolve such stagnation issues, a great number of robust supervisory control policies have been proposed for AMSs with unreliable resources. These policies guarantee that a controlled system can continue to progress without deadlock and blocking states even if some unreliable resources fail to work. By a thorough review of existing robust supervisory control policies for AMSs with unreliable resources, this paper compares and analyzes these policies in terms of their structural complexity, behavioral permissiveness, and computational complexity. The goal of this paper is to provide a reference source in the area to help researchers and practitioners choose a suitable method for solving industrial application problems that are subject to resource failures.

Deadlock resolution has been an important research topic in the field of automated manufacturing systems (AMSs). Researchers generally assume that AMS resources never break down whereas only a few resolve the issues of resource failures in the discrete-event supervision of AMSs. In fact, an AMS consists of a number of numerically controlled machines interacting with each other. The failure of resources happens unexpectedly. In this article, we allow parallel routes to use unreliable resources. Because of their powerful modeling capabilities, Petri nets are used to model the considered AMSs. By using a look-ahead control strategy, a robust supervisory control policy is developed for AMSs with assembly operations allowing resource failures. Our objective is to advance parts requiring failed resources in their remaining routes into a special position so as to release shared resources in case some unreliable resources fail. Consequently, those parts not necessarily requiring any failed resource can keep progressing all the time. The conventional methods are on the basis of monolithic and structure-oriented control specifications with centralized supervisors. Our policy can be implemented in a distributed, online, and local way. Several examples are given to elucidate our control policy clearly. Note to Practitioners-In automated manufacturing systems (AMSs), resources such as machines and tools with higher reliablity are always expensive. Sometimes, when it is not cost-effective to use resources with higher reliability, manufacturers may choose some resources with possible failures. These resources are thus considered as unreliable ones in our article. Normally, unreliable resources may fail unexpectedly. Their occurrences can lead a system to stagnation, causing unnecessary downtime, and bringing economic loss to enterprises. To resolve such stagnation issues, we develop a robust supervisory control policy to synthesize a robust liveness-enforcing supervisor for AMSs with assembly operations and unreliable resources. The supervisor can guarantee that a controlled system continues to progress without deadlock and blocking states even if some unreliable resources fail to work.

Self-adaptive execution of workflow processes by dynamically and autonomously updating their decisions is especially important for improving the quality of business management. However, the existing methods neglect the impacts of data relationships and temporal constraints on modeling and execution of workflow processes. In this article, based on sprouting graph we propose a new approach for self-adaptive decision-making for dynamic execution of data-aware workflow processes. First, a data-oriented sprouting graph is developed for retrieving information on data-aware workflow processes, so as to eliminate incorrect paths and handle waiting situations. Second, decision point setting and self-adaptive decision strategies are investigated for solving two fundamental decision problems: waiting for information and selecting one among several paths. Third, the whole procedure of automatic implementation is proposed for self-adaptive execution of data-aware workflow processes. Compared with the existing methods, our approach can improve the efficiency of analysis by reducing the model size and can significantly minimize the overall operational cost of the workflow processes.

Up to now, the supervision and control of deadlock-free resource allocation has received considerable attention, particularly regarding their deadlock problems. To date, most solutions have supposed that allocated resources never fail. However, this is quite the opposite in reality since some resources may fail unexpectedly. A robust system should be resilient to such failures. In this paper, resources are divided into reliable ones and unreliable ones. On the basis of the deadlock avoidance algorithm which is proposed for the problem of deadlocks, we propose a robust control algorithm in the paradigm of systems of sequential systems with shared resources, which can acquire and release resources in a multitype and multiquantity way. It is validated to be a polynomially complex robust control algorithm by the distributivity analysis. Finally, experimental results show that the proposed approaches are effective as well as efficient in response to resource failures.

The subject of deadlock control for automated manufacturing systems has been extensively studied in the past several years. For most of them, researchers have supposed that shared and dedicated resources never fail. As any manufacturing practitioner knows, resource failures, e.g., defective parts, faulty sensors, blurred signals, and broken actuators, are a common problem. Hence, the robust supervision and control for a system with unreliable resources is necessary. In our previous work, we proposed a robustness intensification algorithm based on a deadlock avoidance algorithm to ensure that processes not requiring unreliable resources can operate smoothly. In this article, a new robust method, which combines the advantages of absorbing policies and distributing policies with the aid of critical regions, is developed. It includes two algorithms, i.e., a robustness algorithm for processes not requiring unreliable resources and an intensification algorithm for processes requiring unreliable resources. Compared with existing absorbing and distributing policies, the new robust method can increase the production rate while decrease the algorithm complexity for a system allowing flexible routes apart from each process stage acquiring more than one type of resources.

The development of efficient solutions for deadlock problem in large-scale automated manufacturing systems (AMSs) is an issue of increasing interest in the scientific community, largely because of the nonapplicability of most existing approaches as AMS grows in size. Furthermore, much of these approaches is focused on systems with either assembly operations or flexible routes, implying that generalizing these existing results to more complex systems is difficult. As a result, we initiate on the deadlock problem of AMSs embedding assembly operations in flexible routes. By modeling AMSs as Petri nets, an innovative distributed approach is developed in this paper, which can be realized in an online, look-ahead, and dynamic way without requiring external and extra information. Beyond the value of the presented results, this paper is also intended to develop more general results which will be adaptable to a broader class of AMSs.

It has been an active research area to develop robust supervisory control policies for production systems with unreliable resources. So far, most methods for robust deadlock resolution apply only to systems without flexible routes, where each processing step of any part type requires a unique prespecified resource. In this paper, we address deadlock avoidance control problem in production systems with both failure-prone resources and flexible routings, which allow that a part has options when deciding the resource acquisition at each step. This paper presents properties that a controller with robustness must satisfy. Specifically, at any system reachable state, neither the failed resources nor part instances trapped in these resources should have too much detrimental effect on the other portions of the system. Thus, the full range of part types' production could be assured at all time. After defining the notions of reduced system and reduced state with respect to unreliable resources, we identify and prove conditions for determining whether or not the state resulting from the occurrence of an event is feasible. Subsequently, we develop a method for robust deadlock avoidance, which uses the solutions to state safety checking problem for the reduced production system with only reliable resources. An illustrative example shows the effectiveness of this method. Finally, we conduct a comparison investigation of some representative approaches in the literature about robust supervisory control for deadlock resolution in resource allocation systems with routing flexibility.

With growing environmental and sustainability-related concerns, recovery optimization of mechanical products has been gaining increased exposure. It facilitates environmental sustainability through the improvement in the life-cycle material efficiency and reduction in environmental impact with disassembly sequence planning, component reuse, and material recycling. Traditional product recovery separates end-of-life (EOL) products into components and selects EOL options of components. However, there are many practical cases in which the recovery of a set of subassemblies and components leads to better net revenue than that of a complete set of single components. This paper proposes to model and optimize hybrid disassembly and EOL operations of product recovery to maximize the recovery profit and minimize the environmental impact. Flexible process planning of hybrid disassembly determines a disassembly level by identifying the reusability of subassemblies and disassembly sequences mixed with subassemblies and components. Optimal EOL decisions for each subassembly and component are investigated such that the economic and environmental objectives can be achieved. Finally, a case study is described to illustrate the proposed method and the influence on decision variables of the tradeoff between the recovery profit and environmental impact is discussed. Note to Practitioners-This paper deals with the process planning and EOL decision-making problem of product recovery. Based on hybrid disassembly, this paper proposes a flexible process planning and EOL decision-making method for product recovery. Flexible process planning of hybrid disassembly determines a disassembly level by identifying the reusability of subassemblies and disassembly sequences mixed with subassemblies and components. Optimal EOL decisions for each subassembly and component are investigated such that the economic and environmental objectives can be achieved. The goal of this paper is to model and optimize hybrid disassembly and EOL operations of product recovery to maximize the recovery profit and minimize the environmental impact. The results demonstrate that the proposed method can leads to small environmental impact and low cost. Subassemblies and components with high reliability and expensive price are suggested to be destined for reuse. Minimizing transportation distances is more effective to reduce product recovery cost. Such results can help decision makers to perform better judgments when a disassembly process of an EOL product is executed.

With the reduction of wafer batch size on account of the diversification and individuation of consumption demands, increasing importance has been attached to the schedulability and controllability of the cluster tools with multiple wafer types being concurrently processed, while the corresponding research is seldom and still open. This paper is devoted to addressing the steady-state scheduling of single-arm cluster tools with multiple wafer types and residency time constraints. Inspired by the definition of wafer flow pattern for the single wafer type, a novel description for the multiple wafer types is introduced. For the sake of efficiency and simplicity, the multiplex backward sequence is proposed. To balance the workload of process steps, a virtual module technology with a two-tiered architecture is implemented. Furthermore, several sufficient and necessary conditions are derived to verify the schedulability of the system. Finally, an efficient algorithm is presented to find the periodic steady-state schedule, and its practicability and availability are validated by the given illustrative examples.Note to Practitioners—Cluster tools are a kind of highly automated, flexible, and integrated equipment applied widely in diversified semiconductor fabrication processes. Due to the strictness of processing constraints and unavailability of in-built buffers, it is challenging to effectively operate cluster tools. For a higher utilization of processing modules, fabs tend to concurrently process several kinds of wafers with dissimilar recipes in a cluster tool. However, the related scheduling and control problems remain open. With residency time constraints, this paper addresses the scheduling problems of single-arm cluster tools with multiple wafer types. By dissecting the mechanism of mixed-processing of multiple wafer types, several formal conditions are obtained to test the schedulability. Based on the multiplex backward sequence, a cyclic scheduling approach to single-arm cluster tools with multiple wafer types is presented. With the proposed method, schedulability conditions can be readily checked and a periodic schedule can be found easily. Thus, it can be applied to solve practical application problems.

Nowadays, workflow process changes frequently in a fast-changing business environment. When updating a workflow process via some structural changes, one of the most important tasks is to maintain its consistency under temporal constraints. Several approaches have been developed to cope with this issue. However, they are either inaccurate in locating changed parts or inefficient in analyzing temporal constraints owing to their excessive or erroneous estimation of affected portions for the updated workflow processes. Based on a sprouting graph (a graph that records the structure and time information of all paths in a workflow process in advance), this paper proposes a novel approach to analyzing temporal constraints for workflow processes with dynamic changes. First, changed parts are located via affected collaboration execution paths in the new model, i.e., the workflow process after changes. Second, instead of updating all the elements, only necessary (changed) nodes corresponding to the changed parts are updated in the sprouting graph of the original model, i.e., the workflow process before changes. Finally, based on the updated sprouting graph, only affected temporal constraints (the temporal constraints whose partial or all paths are contained in the affected collaboration execution paths) are checked. Compared with the existing works, our approach is applicable and efficient to check temporal constraints for large-scale and complex workflow processes thanks to its much lower time and space complexity.

Motion planning is one of the most critical problems in multirobot systems. The basic target is to generate a collision-free trajectory for each robot from its initial position to the target position. In this paper, we study the trajectory planning for the multirobot systems operating in unstructured and changing environments. Each robot is equipped with some sensors of limited sensing ranges. We propose a fully distributed approach to planning trajectories for such systems. It combines the model predictive control (MPC) strategy and the incremental sequential convex programming (iSCP) method. The MPC framework is applied to detect the local running environment real-timely with the concept of receding horizon. For each robot, a nonlinear programming is built in its current prediction horizon. To construct its own optimization problem, a robot first needs to communicate with its neighbors to retrieve their current states. Then, the robot predicts the neighbors' future positions in the current horizon and constructs the problem without waiting for the prediction information from its neighbors. At last, each robot solves its problem independently via the iSCP method such that the robot can move autonomously. The proposed method is polynomial in its computational complexity.

Although supervisor simplification in the framework of automated manufacturing systems has been studied in many literatures, there is still an intense demand for essential and general techniques. Basically, supervisors can be synthesized by specifications which are expressed by generalized mutual exclusion constraints (GMECs). In this paper, we propose static and dynamic partitions on GMECs to remove redundant ones while retain necessary ones. These two partitions are distinctly different in the utilization of system information. Static partition separates inequalities into independent and dependent ones without doing any structure analysis. While dynamic partition divides inequalities into active and inactive ones necessarily with the aid of system information. Nevertheless, mathematical analysis shows that statically dependent inequalities are essentially dynamically inactive while dynamically active ones are substantially statically independent. Thus, these partitions are contradictory in theory whereas compatible in practice. Since static partition is more general while its dynamic counterpart is more precise, they together complementarily explain many simplification principles. Furthermore, they are applicable to both ordinary and general systems. Experimental results show the effectiveness and efficiency of supervisor simplification based on static and dynamic inequality partitions.

One of the major challenges from both a theoretical and practical perspectives, for effectively establishing unattended operation of automated manufacturing systems (AMSs), is to resolve the deadlock. In the existing methods on deadlock problem, most of them are focused on the models with either flexible routes or assembly operations, whereas few method investigates them with both. Furthermore, applying these methods into large-scale systems is usually nontrivial, primarily because of the fact that they generally require the enumeration of all the states or siphons. The work presented in this paper proposes a Petri net-based model which can deal with both features and develops an innovative distributed strategy that provides an online and dynamic mechanism for deadlock resolution. Each step's execution depends on a search-based procedure that seeks to determine whether there exists a feasible event sequence bringing the currently-active process or sub-processes to the nearest global critical place when other processes stagnate. By taking our approach, system can benefit from minimal communication amount among different processes, better toleration to many contingencies like resource failure, and improved system performance like throughput.

Collision avoidance is a critical problem in motion planning and control of multirobot systems. Moreover, it may induce deadlocks during the procedure to avoid collisions. In this paper, we study the motion control of multirobot systems where each robot has its own predetermined and closed path to execute persistent motion. We propose a real-time and distributed algorithm for both collision and deadlock avoidance by repeatedly stopping and resuming robots. The motion of each robot is first modeled as a labeled transition system, and then controlled by a distributed algorithm to avoid collisions and deadlocks. Each robot can execute the algorithm autonomously and real-timely by checking whether its succeeding state is occupied and whether the one-step move can cause deadlocks. Performance analysis of the proposed algorithm is also conducted. The conclusion is that the algorithm is not only practically operative but also maximally permissive. A set of simulations for a system with four robots are carried out in MATLAB. The results also validate the effectiveness of our algorithm.

Automated manufacturing systems (AMSs) with complex topologies have become increasingly active in the area of research. However, a prerequisite is indispensable for numerous researchers to investigate AMSs. That is resources are presumptively and arbitrarily assumed never to fail; nevertheless, this does not completely match the reality. In this paper, we consider deadlock and blocking problems in AMSs with unreliable resources and assembly operations. Our objective is to develop a robust supervisory control policy that allocates resources so that parts requiring the failed resource do not block the production of parts not necessarily requiring the failed resource in case any unreliable resource fails unexpectedly. Conventional methods are based on structure-oriented and monolithic specifications. On the contrary, our supervisory policy looks ahead to anticipate whether currently-available resources are enough in their quantity to assist a concerned token to reach its desired destination without knowing the global information. Our strategy is achieved in a local and dynamic manner. It can effectively respond to resource failures.

As an important branch of production facilities, automated manufacturing systems are a promising perspective of modern factories which become increasingly complex and flexible. From the perspective of development, time variable is a significant concern. In this paper, we propose a class of time-varying systems, Tv-S4R. After involving a global time information loop, it can represent realistic system whose manufacturing process varies with time variables. Event-based control is introduced for serving two important purposes. First, it exerts time-varying specifications on the system, i.e., different processes are executed at different time stages. Second, it prevents the system from reaching any first-met bad marking which will eventually result in deadlocks. We will show that the event-based control can enhance our specifications' expressivity capability compared to their state-based counterparts in terms of generalized mutual exclusion constraints. At last, supervisors are simplified according to the identification of dependence and independence of inequalities. An experimental study illustrates the application of Tv-S4R and the effectiveness of event-based control method.

Supervisory control techniques (SCTs), as one of the fundamental researches in the domain of automated manufacturing systems, implement specifications upon a plant model, leading the system to tendentiously desired behaviors. Generalized Mutual Exclusion Constraints (GMECs) are a typical kind of SCTs which correspond to a linear supervisory specification in the context of Petri nets (PNs). Given a set of admissible GMECs, supervisor simplification is needed to reduce implementation cost and mitigate fabrication complexity. In this paper, two methods are proposed and improved in the paradigm of arbitrary GMECs simplification. For the method based on P-invariant control, it develops in the semantics of PN structure analysis, exhibiting drawbacks like low computational efficiency, high failure probability, and definite failure to control weakly L1-dependent inequalities. On the contrary, for the method based on inequality analysis, it germinates on the ground of algebra theory, tackling both L1- and L2-dependent inequalities. Experimental results show the effectiveness and efficiency of supervisor simplification based on inequality analysis.

Most contemporary manufacturing systems appear as complex event-driven automation facilities. Supervisor synthesis and simplification are fundamental in automated manufacturing systems (AMSs). From design and implementation standpoints, it is preferable to decrease supervisor scales so as to mitigate their realization expense. Ordinary and general Petri nets are considered as powerful formalisms to describe, analyze, and control AMSs. The former is concise while the latter is compact. By considering both cases, our approach shows some properties so as to disclose their rationales with regard to liveness enforcement. Many control methodologies are developed in the context of the ordinary ones. They are straightforward but might be unadaptable to the general ones. This work develops new theory in this perspective. Some comparison and contrast survey has been demonstrated in order to clarify their common theoretical basis and distinct supervisory effect. In accordance to a thorough study, a novel simplification method is developed so as to unify both cases and facilitate their application. Experimental results show that the developed strategy is effective and efficient when simplifying supervisors.

Colored Petri nets are widely used to model Automated Manufacturing Systems thanks to their compactness to describe complex networked systems. Compared to general Petri nets, they allow many folding techniques so as to condense the system model. With them, many control synthesis problems are reduced to the solution of matrix operations. Supervisory control techniques can be realized in a computationally efficient way. In this work, these matrices are further distinguished by independent and dependent ones. A method is proposed to identify these independent ones while removing those dependent ones. As a result, a supervisor can be significantly simplified. In practice, this implies the significant reduction of cost, increase of reliability, and improvement of performance. Examples are presented to illustrate the effectiveness and efficiency of this method.

Facility location allocation (FLA) is considered as the problem of finding optimally a facility's location with the maximum customer satisfaction, the maximum profit of investors of the facility, and the minimum transportation cost of its oriented-customers. In practice, some factors of the FLA problem, i.e., customer demands, allocations, even locations of customers and facilities, are usually changing, and thus the problem features with uncertainty. To account for this uncertainty, some researchers have addressed the stochastic profit and cost issues of FLA. However, a decision-maker hopes to obtain the specific profit of investors of building facility and meanwhile to minimize the cost of target customers. To handle this issue via a more practical manner, it is essential to address the cost-profit tradeoff issue of FLA. Moreover, some region constraints can greatly influence FLA. By taking the vehicle inspection station as a typical automotive service enterprise example, this work presents new stochastic cost-profit tradeoff FLA models with region constraints. A hybrid algorithm integrating stochastic simulation and Genetic Algorithms (GA) is proposed to solve the proposed models. Some numerical examples are given to illustrate the proposed models and the effectiveness of the proposed algorithm.

For event-driven systems like automated manufacturing systems (AMSs), intelligent part dispatching, i.e., to assign various parts to proper processing routes, is crucial to gain high resource utilization and production efficiency. This work proposes an innovative dispatching mechanism, which can better these metrics by minimizing the cycle time, i.e., the mean time to produce a product, while avoiding any deadlock, i.e., no part can proceed due to circuit wait. Its prerequisite is liveness supervision; however, temporal information is associated to certain operation stages for the sake of performance evaluation and throughput maximization, i.e., to maximize the finished-part quantity per time unit. In the paradigm of Petri nets, we show the criticality to prioritize certain activities locally. Our method can well design ratio parameters among distinct processes to improve system productivity.

Due to the competition for limited resources by many concurrent processes in large scale automated manufacturing systems (AMS), one has to resolve a deadlock issue in order to reach their production goal without disruption and downtime. Monolithic resolution is a conventional approach for optimal or acceptable solutions, but suffers from computational difficulty. On the other hand, some decentralized methods are more powerful in finding approximate solutions, but most are application-dependent. By modeling AMS as Petri nets, we develop an innovative distributed control approach, which can create a trajectory leading to a desired destination and are adaptable to different kinds of constraints. Control strategies are applied to processes locally such that they can concurrently proceed efficiently. Global destinations are always reachable through the local observation upon processes without knowing external and extra information. Efficient algorithms are proposed to find such distributed controllers.

In the framework of automated manufacturing systems (AMS), Petri nets are widely used to model, analyze, and control them. Resolving deadlocks is of paramount significance because their emergence may likely zero a systems throughput, if not necessarily. Supervisory control technique is the most widely adopted method to resolve them. A control policy can be converted into satisfying a set of inequalities, each of which corresponds to a siphon in a Petri net structure. The number of siphons can be exponential in the worst case, so does the number of inequalities. Taking into account the independent and dependent inequalities, this paper proposes a method to remove all the dependent inequalities, while preserving only the independent ones. This method can significantly reduce the size of a supervisory controller. Examples are presented to illustrate the effectiveness and efficiency of this method.

In the framework of automated manufacturing systems (AMS), Petri nets are widely used to model, analyze, and control them. Resolving deadlocks is of paramount significance because their emergence reduces the system throughput to zero. Supervisory control technique is the most widely adopted method to resolve them. A control policy can be converted into satisfying a set of inequalities, each of which corresponds to a siphon in a Petri net structure. The number of siphons can be exponential in the worst case, so does the number of inequalities. Taking into account the independent and dependent inequalities, this paper proposes a method to remove all the dependent inequalities while preserving only the independent ones. This method can significantly reduce the size of a supervisory controller. Examples are presented to illustrate the effectiveness and efficiency of this method.

Sensors and actuators are two indispensable parts in the paradigm of feedback control. Their implementation cost should be properly evaluated and constrained. In the previous work, a Petri net monitor with the least cost is synthesized through integer programming formulation. Despite its technical correctness, the existing method may lead to undesirable results when the net structure contains some shared or unshared resource places of a manufacturing-oriented net model. A necessary and sufficient condition is established to show that certain structures can lead to deadlock-prone supervisors. An efficient algorithm is developed to identify such structures. Furthermore, it is shown that if one can identify such structures at the initial stage, it is possible to achieve desirable controllers for the original systems. The theoretical correctness of the proposed algorithm is discussed. A manufacturing example is provided to illustrate the proposed approach.

In the context of automated manufacturing systems (AMS), Petri nets are widely adopted to solve the modeling, analysis, and control problems. So far, nearly all known approaches to liveness enforcing supervisory control investigate AMS with either flexible routes or assembly operations, whereas little work investigates them with both. In this paper, we propose a novel class of systems, which can well deal with both features so as to facilitate the control of more complex AMS. Using structural analysis, we show that liveness of their Petri net model can be attributed to the absence of undermarked siphons, which is realizable by synthesizing a proper supervisory controller. Moreover, an efficient method is developed and verified via AMS examples.

In the context of automated manufacturing systems (AMS), Petri nets are widely adopted to solve the modeling, analysis, and control problems. So far, nearly all known approaches to liveness-enforcing supervisory control study AMS with flexible routes whereas little work investigates the ones with synchronization operations. Compared with flexibility, synchronization allows the disassembly and assembly operations which correspond to the splitting and merging to and from different sub-processes, respectively. Such structures bring difficulties to establish liveness condition upon the analysis of the underlying process flows. In this paper, we propose a novel class of systems, which can well deal with these features so as to facilitate the investigation of such complex systems. Using structural analysis, we show that their liveness can be attributed to deadlock-freeness, which is much easier to analyze, detect, and control by synthesizing a proper supervisory controller. Furthermore, a set of mathematical formulations are proposed to describe and extract the corresponding deadlocks. This facilitates the synthesis of liveness enforcing supervisors as it avoids the consideration of deadlock-free but non-live scenarios. The effectiveness and efficiency of this work is verified through examples.

In automated manufacturing systems (AMSs), Petri nets are widely adopted to solve supervisory control problems. Among them, how to enforce liveness and fairness for AMS constitutes an important problem. Enforcing liveness avoids the occurrence of deadlock situations to inhibit the emergence of partial or complete blockness for processing jobs in AMS. Fairness requires the determination of a reasonable regulation scheme for orderly resolution such that a desired ratio can be assigned among different processes. This paper proposes an efficient method to design supervisors that enforce both, which is based on the invariance property of Petri nets. A novel approach is proposed to iteratively identify empty siphons as solutions to a set of linear inequalities. Supervisors are then designed to control these siphons. The applicability of the proposed methodology is illustrated through examples. Its comparison with existing works is presented to demonstrate its advantages.

In the context of automated manufacturing systems (AMS), Petri nets are widely adopted to solve the modeling, analysis, and control problems. So far, nearly all known approaches to liveness-enforcing supervisory control study AMS with either flexible routes or assembly operations, whereas little work investigates them with both. In this paper, we propose a novel class of systems, which can well deal with both features so as to facilitate the investigation of more complex systems. Using structural analysis, we show that liveness of such systems can be attributed to the absence of undermarked siphons, which is realizable by synthesizing a proper supervisory controller.

For automated manufacturing systems (AMSs), deadlock resolution in terms of Petri nets remains an attractive topic to which many approaches are dedicated. However, few of them can quantitatively optimize certain indices during their supervisor synthesis process. This causes unnecessary control limitations and often leads to high implementation cost. In the framework of Petri nets, this paper proposes a method to synthesize a cost-effective supervisor with the aid of a set of mathematical programming formulations. Along the same vein, we also show some results by investigating timed Petri nets, which can be utilized to make a good tradeoff between implementation cost and system cycle time. Examples are used to validate the effectiveness of our result.

This paper proposes a new Petri net class, namely, Ratio-enforced weighted Augmented Marked Graphs (RAMGs), and solves ratio control and liveness-enforcing supervision problems for automated manufacturing systems. RAMGs can ensure the required product ratios as demanded by production planners. Since the deadlock of such a system can be attributed to improper acquisition of finite shared resources, a supervisor is introduced such that they are properly allocated. This paper proves that ratio and supervisory controllers for an RAMG can be separately designed. Their design methods are presented. Examples are given to illustrate them.

For automated manufacturing systems (AMS), deadlock resolution in terms of their Petri net models remains an attractive topic to which many approaches are dedicated. However, few of them can quantitatively optimize certain indices during their supervisor synthesis process. This causes unnecessary control limitations and often leads to unnecessary implementation cost. In the framework of Petri nets, this paper proposes a method to synthesize a cost-effective supervisor with the aid of a set of mixed integer programming (MIP) formulations. Examples are used to validate the legality of the proposed method.

For practical automated manufacturing systems (AMSs), the time dimension is of great significance and should be integrated in their plant models. Reasonably, many of the realistic general mutual exclusion constraints (GMECs) imposed on these discrete models should be timed rather than merely algebraic or logic. In the past, such a problem was studied on the basis of the Ramadge-Wonham supervisory control technique (SCT) and the theory of regions. It proves to be NP-hard since it necessitates the generation of reachability graphs. This paper shows that it can be solvable in polynomial time by using generalized linear constraints, which are originally proposed to increase the expressive power of the linear marking constraints. By dividing each constraint into marking, firing vector, and Parikh terms, its respective control place can be synthesized algebraically without considering the separation of dangerous states and events. Several examples are used to validate the effectiveness and efficiency of the proposed approach.

In the context of automated manufacturing, this work proposes a new special class of timed Petri nets, namely, Timed ratio-enforced Augmented Marked Graph (TAMG) and its low-cost and high-performance supervisor synthesis methodology. A supervisor is composed of a set of control places (monitors), each of which is easy to be algebraically specified by a generalized mutual exclusion constraint (GMEC) to prevent certain siphons from being undermarked. In order to make a good tradeoff between the supervisor implementation cost and system performance, a mixed integer programming (MIP) approach is formulated to synthesize the monitors. An example is used to validate the effectiveness and efficiency of the proposed method. The results show that the proposed method remarkably outperforms any existing ones.

This paper presents a class of Petri nets that can well model ratio-enforced resource allocation systems (RASs). Such RASs are required to enforce certain ratio among their processes to meet a desired production plan. A ratio-enforced system of sequential systems with shared resources (RS4R) can model an RAS whose processes are described by state machines. Both a ratio-enforcing controller and liveness-enforcing supervisor must be designed to fulfil the deadlock-free and ratio-constrained production of products. We theoretically prove that their design can be separately performed.

In previous work, an acceptable transformation of an unacceptable specification on a Petri net can be implemented through a set of mathematical programming formulations. However, such a method becomes invalid when no solution exists in practice. In this paper, we reestablish these formulations and show their correctness.

Internet-motivated video streaming systems face such complicated issues as a high degree of network-resource sharing amongst many flows, which potentially leads to deadlocks. Using siphons and their corresponding dangerous markings, this work investigates a method to enforce control iteratively. At each iteration, a generalized mutual exclusion constraint is produced to keep only those markings under which liveness is enforced. Furthermore, a generalized elementary siphon control method is proposed such that the final supervisor is structurally simple. Examples are used to illustrate the proposed approach.

This paper considers the deadlock prevention problem for a class of conjunctive/disjunctive resource allocation systems (C/D-RAS) in which multiple resource acquisitions and flexible routings are allowed. The proposed policy is developed in a generalized Petri net framework by an iterative algorithm. Each iteration uses a mixed integer programming (MIP) formulation to find both a bad marking and insufficiently marked siphon. Two new strategies are then presented. One aims to maximize the permissiveness of a liveness-enforcing supervisor while another to minimize the computational and supervisor's complexity. Experimental results validate the effectiveness of these two strategies.