This paper develops a distributed method, namely, distributed allocation with time windows (DATW) for managing the multi-UAV task assignment problem (MTAP) with complex time window constraints. By aiming directly to minimize the average task completion time, the pro-posed DATW intends to achieve a conflict-free result that allocates all tasks within the validity time windows. Based on the decentralized PI (Performance Impact) framework, the proposed algorithm addresses the MTAP in a three-phase task assignment strategy, which includes task inclusion, conflict resolution, and task reallocation. The newly introduced task allocation phase achieves a noteworthy increase in an average number of allocated tasks. Unlike the traditional PI methods, the start time of each task is broadcasted among agents via communication typology, and the significance value of each task is directly related to its validity time window, such that the vast majority of tasks are able to be assigned properly without imposing any extra communication burdens. In the obtained conflict-free allocation solution by DATW, each task is allocated to a proper UAV with all given constraints satisfied. Finally, the simulation results demonstrate the effectiveness and superiority of the proposed DATW. Compared with existing (CBBA-based) solutions, results show up to an 18% increase in success rate (SR) using the proposed method.

Recently, the problem of robust control for automated manufacturing systems (AMSs) with unreliable resources receives increasing attentions. Almost all the existing related works are only concerned with the failure-prone AMSs in which each part stage utilizes only one unit of resources. While, in real-world AMS, it is often necessary to use multiple units of different resources to complete a part. This paper focuses on the robust control of such complex AMSs with a type of unreliable resources. General Petri nets are used to model all the behavior of such AMSs. By adding a control place to the Petri net models for each considered siphon, we develop robust deadlock controllers for the considered AMS. Such a robust controller ensures that the parts of all types can be processed continuously through any of its processing routes, even if one of the unreliable resources fails. Finally, some examples are used to illustrate the proposed method.

This paper focuses on the liveness analysis and deadlock control for automated manufacturing systems (AMSs) with multiple resource requirements. Such an AMS is modeled by a class of generalized Petri nets called systems of simple sequential processes with multiple resources (S³PMR). It is shown that a deadlock of the considered AMSs can be characterized by the saturation of a structural object in S³PMR, called perfect resource transition-circuit (PRT-circuit). As a consequence, an S³PMR is live if and only if no PRT-circuit is saturated at any reachable marking. To ensure the system liveness, one has to prevent all PRT-circuits from being saturated at all reachable markings. To develop a structurally simple Petri net deadlock controller, we present the concept of an effective transition cover, which is a special subset of PRT-circuits that may be saturated. Then by designing a control place with a proper control variable for each PRT-circuit in an effective transition cover, we obtain a deadlock controller for the system. The needed control variables are determined by an integer linear program. Since the number of PRT-circuits in an effective transition cover is much less than that of all PRT-circuits that need to control, our controller is of small structural size. For an AMS with saturable PRT-circuits, there exists at least a transition cover. An algorithm is presented for checking the effectiveness of transition covers, and transforming noneffective transition covers into effective ones. Finally, some examples are used to illustrate the proposed method.

It is inevitable that resource failures occur in real production processes, and sometimes many different types of unreliable resource failures may occur. Once there are resource failures, the stagnation states of production caused by these failures, called as failure blockings (FBs), tend to appear. Hence, both deadlocks and FBs can arise to reduce production efficiency sharply. Designing robust control policies for such an automated system is thus very important. Our work focuses on a novel robust Petri net controller of flexible manufacturing systems with multitype and multiunit of unreliable resources. First, under the assumption that all resources are reliable, these systems are modeled by a class of Petri nets called systems of simple sequential processes with resources (S3PRs). For each operation place that is a holder of an unreliable resource, the corresponding repair place and related transitions are added to the net and an S3PR with unreliable resources (S3PRu) is developed. For an S3PRu, the formal definition of FBs is then proposed. Such an FB is characterized by a maximal perfect resource-transition circuit (MPC). Next, the concept of a critical set of MPCs is introduced. For any two adjacent MPCs in such a critical set, one input transition of the former and one output transition of the latter are connected by passing through resource places. A $\xi $ -resource is a one-unit resource shared by two or more MPCs that do not contain each other. For an S3PRu without $\xi $ -resources and critical sets of MPCs, a control place corresponding to an MPC is added to the net with its output arcs to the input transitions of the MPC. However, for an S3PRu with $\xi $ -resources or critical sets of MPCs, the output arcs of each control place are added to the source transitions of the original net. Thus, a novel robust controller of an S3PRu is synthesized. Such a robust controller can guarantee that as long as at least one unit of each type of unreliable resources can work normally, all kinds of parts can be processed to complete smoothly their tasks through any one of their process routes. Finally, three examples are provided to illustrate the efficiency of the proposed robust controller.

This article addresses the scheduling problem of deadlock-prone flexible manufacturing systems subject to no-wait constraints for the first time, and develops a new scheduling algorithm based on the place-timed Petri net (PN) model and heuristic search. The considered problem can be solved by two procedures: 1) timetabling and 2) sequencing. The timetabling is to translate a given job sequence into a feasible schedule that satisfies the deadlock-free and no-wait constraints. A novel timetabling algorithm based on the controlled PN model is then proposed for solving it. The goal of sequencing is to find a job sequence so that the makespan of the corresponding schedule is the minimum. To this end, a hybrid heuristic search (HHS) is developed by combining the A* algorithm and dynamic window. Two new heuristic functions are designed to guide the search, and the dynamic window is used to limit the searched space. The performance of HHS with different heuristic functions and deadlock controllers is evaluated by ten instances. The computational results demonstrate that through the proposed approach, optimal or suboptimal feasible schedules can be obtained within a reasonable time.

This article focuses on the problem of deadlock for sequential automated manufacturing systems (AMSs) that allow for the general resource allocation and flexible routings. A class of Petri nets, systems of sequential systems with shared resources (S ⁴ PR), are used to model these considered AMSs. Our previous work has showed that deadlocks in S ⁴ PR are characterized by saturated perfect activity-circuit (PA-circuit). In this article, we divide all saturable PA-circuits into two categories: 1) dependent and 2) independent. An algorithm is proposed to compute all independent saturable PA-circuits. We prove that by adding a monitor for each independent PA-circuit to ensure that it is not saturated, all dependent PA-circuits cannot be saturated either and deadlocks in S ⁴ PR are successfully prevented. The presented method simplifies the structure of the deadlock controller without imposing tight constraints on the system. Finally, the proposed controller is illustrated by some examples.