Deadlock and Blockage Control of Automated Manufacturing Systems with an Unreliable Resource

This work studies the deadlock and blockage control problem of an automated manufacturing system (AMS) with a single unreliable resource. It aims to develop a robust control policy to ensure that AMS can produce all parts in the absence of resource failures, and when the unreliable resource fails, the system can continuously produce all parts that do not require the failed resource. To this end, we divide the system into two regions, continuous and non‐continuous, based on whether all parts in them can be produced continuously or not. For the non‐continuous region, dominating region constraints are established to ensure that all parts in it do not block the production of parts in the continuous region, and an optimal deadlock avoidance policy based on a Petri net model is introduced to guarantee its deadlock‐free operation. For the continuous region, we configure a resource order policy to ensure the smooth productions of AMS. By integrating the dominating region constraints and deadlock avoidance policy with the configured resource order policy, we propose a novel robust control policy. It is proven to be of polynomial complexity and more permissive than the existing one with the same resource order policy. Also, it is tested to be more permissive than other existing policies.     

Petri-net-based robust supervisory control of automated manufacturing systems

Supervisory control that ensures deadlock-free and nonblocking operation has been an active research area of manufacturing engineering. So far, most of deadlock control policies in the existing literature assume that allocated resources are reliable. Additionally, a large number of methods are for systems of simple sequential processes with resources (S³PRs), where a part uses only one copy of one resource at each processing step. In contrast, we investigate the automated manufacturing systems (AMSs) that can be modeled by a class of Petri nets, namely S^*PUR. S^*PUR is a generalization of the S^*PR Petri net model, while S^*PR is a superclass of S³PR. This work addresses the robust supervision for deadlock avoidance in S^*PUR. Specifically, we take into account unreliable resources that may break down while working or being in idle, and the considered AMSs allow the use of multiple copies of different resources per operation stage. Our objective is to control the system so that: 1) when there are breakdowns, the system can continue producing parts of some types whose production does not need any failed resources; and 2) given the correction of all faults, it is possible to complete all the on-going part instances remaining in the system. We illustrate the characteristics of a desired supervisor through several examples, define the corresponding properties of robustness, and develop a control policy that satisfies such properties.     

基于LSTM的集群用户作业执行时间预测模型

为提升服务质量,数据中心需要确保在规定的截止时间前完成用户作业,因此必须根据实时的系统资源对作业进行有效的调度。提出了一种作业调度算法,根据预测的作业执行时间进行批作业调度,以最小化批作业的完成时间。作业执行时间预测模型基于长短期记忆LSTM网络,根据用户作业类型、作业量、作业需要的CPU核数和内存数量,以及作业需要的资源在系统总资源中的占比,对用户作业的执行时间进行预测。预测结果用于判断集群是否有能力按时完成用户作业,同时为合理安排各作业的执行顺序提供依据。通过实验确定了影响LSTM时间预测模型性能的各超参数取值,如迭代次数、学习率和网络层数等。实验表明,与SVR模型、ARIMA模型和BP模型相比,基于LSTM的作业执行时间预测模型的决定系数R²分别有2.97%,2.34%和5.66%的提升效果,且预测的平均误差仅为0.78%。     

Robust supervision using shared-buffers in automated manufacturing systems with unreliable resources

It has been an active area of research to solve the modeling, analysis, and deadlock control problems for automated manufacturing systems (AMSs). So far, all the system resources are assumed to be reliable in most of the existing approaches for deadlock-free and nonblocking supervisory control. However, many resources of AMSs are subject to failure in the real world. In order to develop a more practical and applicable supervisor, this work takes into consideration of multiple unreliable resources in a class of AMSs. On the basis of two variants of Banker’s Algorithm, this paper presents a robust supervisory control policy to avoid deadlock and blocking in these systems. The policy tries to make the best use of buffers of the shared resources to achieve the control objectives. Our controller is qualified to handle simultaneous multi-resource failures. By using formal language and automata theory, we establish its correctness. Moreover, our proposed method is verified via an AMS example, and we make comparison studies between our policy and some of the other similar type of policies in the literature.     

Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems

Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.      

SNA based QoS and reliability in fog and cloud framework

Fog and Cloud computing are ubiquitous computing paradigms based on the concepts of utility and grid computing. Cloud service providers permit flexible and dynamic access to virtualized computing resources on pay-per-use basis to the end users. The users having mobile device will like to process maximum number of applications locally by defining fog layer to provide infrastructure for storage and processing of applications. In case demands for resources are not being satisfied by fog layer of mobile device then job is transferred to cloud for processing. Due to large number of jobs and limited resources, fog is prone to deadlock at very large scale. Therefore, Quality of Service (QoS) and reliability are important aspects for heterogeneous fog and cloud framework. In this paper, Social Network Analysis (SNA) technique is used to detect deadlock for resources in fog layer of mobile device. A new concept of free space fog is proposed which helps to remove deadlock by collecting available free resource from all allocated jobs. A set of rules are proposed for a deadlock manager to increase the utilization of resources in fog layer and decrease the response time of request in case deadlock is detected by the system. Two different clouds (public cloud and virtual private cloud) apart from fog layer and free space fog are used to manage deadlock effectively. Selection among them is being done by assigning priorities to the requests and providing resources accordingly from fog and cloud. Therefore, QoS as well as reliability to users can be provided using proposed framework. Cloudsim is used to evaluate resource utilization using Resource Pool Manager (RPM). The results show the effectiveness of proposed technique.     

New Controllability Condition for Siphons in Ws3PR Nets

Existing policies for deadlock control are mainly based on siphons due to their ability to indicate deadlocks, and can be used as a powerful tool to deal with deadlock situations in flexible manufacturing systems. In order to avoid deadlocks, researchers often add monitors to control siphons. This may result in redundant monitors, unnecessary cost, and restriction of the behavior permissiveness. For example, for a system of sequential systems with shared resources (S⁴R), the existing deadlock control policies based on max, max′ or max′′‐controlled siphons tend to overly restrict the behavior of a controlled system. To ensure maximal permissive behavior of controlled systems, a new concept of siphon controllability named W‐control is defined and then a sufficient and necessary condition under which a WS³PR is live if all its siphons are W‐controlled. Examples are given to demonstrate them.     

Deadlock resolution strategy for automated manufacturing systems including conjunctive resource service

Automated manufacturing systems (AMSs) can process different parts according to operation sequences sharing a finite number of resources. In these systems, deadlock situations can occur so that the flow of parts is permanently inhibited, and the processing of jobs is partially or completely blocked. Hence, one of the tasks of the control system is ruling resource allocation to prevent such situations from occurring. A large part of the existing literature focused on systems in which every operation is performed by only one resource. This paper proposes a deadlock strategy to avoid deadlock conditions in more complex systems where multiple resource acquisitions are allowed to complete a working operation conjunctive resource service system (CRSS). The AMS structure and dynamics is described by a colored timed Petri net model, suitable for following resource changes and working procedure updating. Moreover, digraphs characterize the complex interactions between resources and jobs so that the conditions for the deadlock occurrence are derived. Finally, an event-based controller is defined to avoid deadlock in CRSSs on the basis of the system state knowledge and of the given priority law ruling the concurrent job selection.     

一种基于DAG的网络流量调度器

在如今的数据中心中,各种分布式任务往往会对各种不同的资源进行竞争,特别是网络资源.如果没有有效的网络调度,那么这种竞争就会降低整个数据中心的运行效率.以往的网络资源调度研究由于忽视了任务里计算与网络需求之间的具体关系,对于任务性能的提升十分有限.因此,旨在探索如何通过网络调度来缩短数据中任务的完成时间(job completion time, JCT),从而提升数据中心的整体效率.通过对基于有向无环图(directed acyclic graph, DAG)的分布式任务的深度分析,发现可以在降低它们的网络占用的同时,却不影响它们的JCT.根据这个发现,提出了一个利用计算图来加速任务执行的网络调度器JIT.为了实现JIT,首先将调度问题建模成为一个整数线性规划问题(integer linear programming, ILP),然后证明了这个ILP可以通过一个等价的线性规划模型(linear programming, LP)来快速求解.此外,通过一些合理的简化,将求解时间降低到了1s.与其他调度器的比较实验结果说明了JIT可以取得1.55倍的整体加速效果,从而有效提升数据中心的工作效率.     

Fault-tolerant deadlock avoidance algorithm for assembly processes

Unreliable resources pose challenges in design of deadlock avoidance algorithms as resources failures have negative impacts on scheduled production activities and may bring the system to dead states or deadlocks. This paper focuses on the development of a suboptimal polynomial complexity deadlock avoidance algorithm that can operate in the presence of unreliable resources for assembly processes. We formulate a fault-tolerant deadlock avoidance controller synthesis problem for assembly processes based on controlled assembly Petri net (CAPN), a class of Petri nets (PNs) that can model such characteristics as multiple resources and subassembly parts requirement in assembly production processes. The proposed fault-tolerant deadlock avoidance algorithm consists of a nominal algorithm to avoid deadlocks for nominal system state and an exception handling algorithm to deal with resources failures. We analyze the fault-tolerant property of the nominal deadlock avoidance algorithm based on resource unavailability models. Resource unavailability is modeled as loss of tokens in nominal Petri Net models to model unavailability of resources in the course of time-consuming recovery procedures. We define three types of token loss to model 1) resource failures in a single operation, 2) resource failures in multiple operations of a production process and 3) resource failures in multiple operations of multiple production processes. For each type of token loss, we establish sufficient conditions that guarantee the liveness of a CAPN after some tokens are removed. An algorithm is proposed to conduct feasibility analysis by searching for recovery control sequences and to keep as many types of production processes as possible continue production so that the impacts on existing production activities can be reduced.     

面向资源Petri网的自动制造系统死锁预防

在自动制造系统(automated manufacturing systems, AMSs)中,死锁是一个急需解决的问题,其主要由资源的循环等待造成.为了解决该问题,本文首先基于面向资源Petri网(resource-oriented Petri nets, ROPNs)的特征,建立特殊资源标记图(special resource marked graphs, SRMGs).其次,在SRMGs中建立死锁与饱和回路之间的关系.最后通过为一些特殊回路添加控制器,阻止系统出现不安全标记.考虑到资源故障问题,为危险库所添加资源缓冲子网,保证需要故障资源的零件不会阻塞其他零件的持续生产.相比现有的控制器,本文的监督控制器具有控制开关,其通过实时改变控制库所的容量可以允许更多安全标记发生.     

不可靠网络环境下的数字时间戳服务研究

数字时间戳(DTS)技术被广泛用于数字签名、电子商务及各种软硬件产品的专利和产权保护。在一些网络状况差、网速变化大、时断时续的不可靠网络中,缺乏必要的技术手段来保证时间戳服务的正常、有效运行。根据不可靠网络的特点,设计了一个不实时依赖时间戳服务中心(TSA)的时间服务模型,每次进行时间戳服务时不再需要与远程TSA进行通信,而是通过本地可信平台来进行时间戳服务。还提出一种不可靠网络环境下基于可信平台模块(TPM)的数字时间戳服务协议,并对协议进行了安全性分析。结果表明,协议是安全的,协议产生的时间误差是可控的,对不可靠网络有很好的适应性。     

基于混合整数规划的一般Petri网死锁检测方法

信标的受控性是检测柔性制造系统(flexible manufacturing system,FMS)Petri网模型是否存在死锁的关键因素.对于普通Petri网,在任何可达标识下所有信标不被清空是检测网系统非死锁的充分条件.然而,该条件对于建模能力更强的一般Petri网并不适用,max可控性条件由此产生.研究证明,该条件对于一般Petri网的死锁检测过于严格了.虽然其后有很多研究者通过改进max可控性条件以求给出条件更宽松的一般Petri网非死锁的充分条件,但大部分的研究成果都仅仅局限于一种顺序资源共享分配系统Petri网模型S4PR(systems of sequential systems with shared resources)网.因此,本文在max可控性条件的基础上提出了新的名为max#可控的信标可控性条件,并在此条件的基础上实现了基于混合整数规划(mixed integer programming,MIP)的死锁检测方法.与现有研究成果相比,max#可控性条件更宽松,可适用于更多类型的一般网,为解决大规模柔性制造系统中死锁监督控制器的结构复杂性问题提供了有力的理论支撑.     

Using Shared-Resource Capacity for Robust Control of Failure-Prone Manufacturing Systems

Deadlock-free resource allocation has been an active area of research in flexible manufacturing. Most researchers have assumed that allocated resources do not fail, and thus, little research has addressed the discrete-event supervision of manufacturing systems that are subject to resource failure. In our previous work, we developed supervisory controllers to ensure robust deadlock-free operation for systems with unreliable resources. These controllers guarantee that parts requiring failed resources do not block the production of parts that are not requiring failed resources. This previous work assumes that parts requiring failed resources can be advanced into failure-dependent (FD) buffer space (buffer space exclusively dedicated to parts requiring unreliable resources). Supervisors admit only states for which a sequence of such part advancements is feasible. The research presented in this paper relaxes this assumption because, in some systems, providing FD buffer space might be too expensive or it might be desirable to load the system more heavily with FD parts. In this paper, we concentrate on distributing parts requiring failed resources throughout the buffer space of shared resources so that these distributed parts do not block the production of part types that are not requiring failed resources. The approach presented here requires no state enumeration and is polynomial in stable measures of system size. We also present results from simulation experiments that compare system performance under these new policies with system performance under our previously published supervisors. These results show that our new policies allow better performance if the required part mixes favor FD part types. The systems of interest are single-unit resource allocation systems.     

Network model and effective evolutionary approach for AGV dispatching in manufacturing system

Automated guided vehicles (AGVs), are the state-of-the-art, and are often used to facilitate automatic storage and retrieval systems (AS/RS). In this paper, we focus on the dispatching of AGVs in a flexible manufacturing system (FMS). A FMS environment requires a flexible and adaptable material handling system. We model an AGV system by using network structure. This network model of an AGV dispatching has simplexes decision variables with considering most AGV problem’s constraints, for example capacity of AGVs, precedence constraints among the processes, deadlock control. Furthermore, these problems can be solved by using a lot of heuristic algorithms as network optimization problems. We are also proposed an effective evolutionary approach for solving a kind of AGV’s problems in which minimizing time required to complete all jobs (i.e. makespan) and minimizing the number of AGVs, simultaneously. For applying an evolutionary approach for this multicriteria case of AGV problem, priority-based encoding method and Interactive Adaptive-weight GA (i-awGA) were proposed. Numerical analyses for case study show the effectiveness of proposed approach. Received: June 2005 / Accepted: December 2005     

Comparing digraph and Petri net approaches to deadlock avoidance inFMS

Flexible manufacturing systems (FMSs) are modern production facilities with easy adaptability to variable production plans and goals. These systems may exhibit deadlock situations occurring when a circular wait arises because each piece in a set requires a resource currently held by another job in the same set. Several authors have proposed different policies to control resource allocation in order to avoid deadlock problems. These approaches are mainly based on some formal models of manufacturing systems, such as Petri nets (PNs), directed graphs, etc. Since they describe various peculiarities of the FMS operation in a modular and systematic way, PNs are the most extensively used tool to model such systems. On the other hand, digraphs are more synthetic than PNs because their vertices are just the system resources. So, digraphs describe the interactions between jobs and resources only, while neglecting other details on the system operation. The aim of this paper is to show the tight connections between the two approaches to the deadlock problem, by proposing a unitary framework that links graph-theoretic and PN models and results. In this context, we establish a direct correspondence between the structural elements of the PN (empty siphons) and those of the digraphs (maximal-weight zero-outdegree strong components) characterizing a deadlock occurrence. The paper also shows that the avoidance policies derived from digraphs can be implemented by controlled PNs.     

基于混合整数规划的非阻塞监督控制器设计

提出一种新的死锁控制策略, 保证含有并发执行装配过程的一类柔性制造系统(Flexible manufacturing system, FMS) G-system的非阻塞性, 即在控制下, 受控系统从任意可达状态都可到达理想状态. 首先对Petri网模型运用混合整数规划算法求取一个最大的死信标, 然后从最大的死信标中求取一个需要受控的极小信标, 并对其添加控制库所, 从而保证所有信标的最大可控. 和现有方法相比, 该策略避免了求取所有的信标, 且添加较少的控制库所即可获得结构简单、许可行为趋于最优的控制器.     

MPI-RCDD: A Framework for MPI Runtime Communication Deadlock Detection

The message passing interface (MPI) has become a de facto standard for programming models of highperformance computing, but its rich and flexible interface semantics makes the program easy to generate communication deadlock, which seriously affects the usability of the system. However, the existing detection tools for MPI communication deadlock are not scalable enough to adapt to the continuous expansion of system scale. In this context, we propose a framework for MPI runtime communication deadlock detection, namely MPI-RCDD, which contains three kinds of main mechanisms. Firstly, MPI-RCDD has a message logging protocol that is associated with deadlock detection to ensure that the communication messages required for deadlock analysis are not lost. Secondly, it uses the asynchronous processing thread provided by the MPI to implement the transfer of dependencies between processes, so that multiple processes can participate in deadlock detection simultaneously, thus alleviating the performance bottleneck problem of centralized analysis. In addition, it uses an AND⊕OR model based algorithm named AODA to perform deadlock analysis work. The AODA algorithm combines the advantages of both timeout-based and dependency-based deadlock analysis approaches, and allows the processes in the timeout state to search for a deadlock circle or knot in the process of dependency transfer. Further, the AODA algorithm cannot lead to false positives and can represent the source of the deadlock accurately. The experimental results on typical MPI communication deadlock benchmarks such as Umpire Test Suit demonstrate the capability of MPIRCDD. Additionally, the experiments on the NPB benchmarks obtain the satisfying performance cost, which show that the MPI-RCDD has strong scalability.     

HLA中时间管理算法死锁的规律性

Frederick算法在通常情况下能够比较好地工作,并且完全符合HLA时间管理的原则。但在特殊情况下,该算法会造成死锁。研究表明,死锁是有规律的。文章分析了文献[5]中对Frederick算法死锁规律的描述,指出了其中存在的问题,并一一加以修正。最后给出了新的死锁规律。     

基于Petri网的无死锁控制器设计

对柔性制造系统提出了一种新的死锁预防控制算法。运用区域理论对Petri网模型设计一个控制器,对控制器中所有严格极小信标求取控制库所与资源库所的代数式,保证了所有的严格极小信标受控。与现有方法相比,该策略不必考虑控制器结构,只需根据这些代数式分布控制器中的资源,就可以得到相应无死锁监督控制器。