The Experts below are selected from a list of 2583 Experts worldwide ranked by ideXlab platform
Fu-shiung Hsieh - One of the best experts on this subject based on the ideXlab platform.
-
Fault-tolerant Deadlock Avoidance algorithm for assembly processes
IEEE Transactions on Systems Man and Cybernetics - Part A: Systems and Humans, 2004Co-Authors: Fu-shiung HsiehAbstract: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.
-
Robustness of Deadlock Avoidance algorithms for sequential processes
Automatica, 2003Co-Authors: Fu-shiung HsiehAbstract:Although Deadlock Avoidance issue has attracted much attention and has been extensively studied, most of the existing results assume reliable machines. This assumption makes it difficult to apply existing Deadlock Avoidance algorithms to real manufacturing systems with unreliable machines. This paper presents the results to apply an existing Deadlock Avoidance algorithm to systems with unreliable machines by analyzing the robustness of the Deadlock Avoidance algorithm. Sequential production processes are considered in this paper, and Petri Net is adopted as the tool for modeling and analysis of the sequential processes. Different types of tolerable machine failures under which liveness property can be preserved are characterized. Computational complexity of the proposed algorithm is analyzed.
-
ROBUSTNESS OF Deadlock Avoidance ALGORITHMS FOR SEQUENTIAL PROCESSES
IFAC Proceedings Volumes, 2002Co-Authors: Fu-shiung HsiehAbstract:Abstract Although Deadlock Avoidance issue has attracted much attention and has been extensively studied, most of the existing results assume reliable machines, which makes it difficult to apply existing Deadlock Avoidance algorithms to a real manufacturing system with unreliable machines. This paper presents the results to apply existing Deadlock Avoidance algorithms to systems with unreliable machines by analysing the robustness of the Deadlock Avoidance algorithms. Sequential production processes are considered in this paper and Petri Net is adopted as the tool for modelling and analysis of the sequential processes. The tolerable machine failure under which liveness property can be preserved is characterized.
-
reconfigurable fault tolerant Deadlock Avoidance controller synthesis for assembly production processes
Systems Man and Cybernetics, 2000Co-Authors: Fu-shiung HsiehAbstract:Guarantee of Deadlock-free operations is a prerequisite for achieving high resource utilization in flexible manufacturing systems. As production processes may contend for shared resources, the addition or removal of production processes has impacts on the liveness property of the systems. Uncertainties in manufacturing systems may result in unavailability of resources and may in turn lead to Deadlocks and have negative impacts on the scheduled activities and performance. The design of Deadlock Avoidance control logics for manufacturing systems with unreliable machines to meet changeable, high-variety of product demands is a challenging problem. We develop Deadlock Avoidance control synthesis algorithms that are: (1) reconfigurable to incorporate or remove production processes while maintaining the liveness property, (2) robust to cope with uncertainties, and (3) scalable for realistic cases.
-
dispatching driven Deadlock Avoidance controller synthesis for flexible manufacturing systems
International Conference on Robotics and Automation, 1994Co-Authors: Fu-shiung Hsieh, Shi-chung ChangAbstract:This paper develops a new method for synthesizing Deadlock Avoidance controllers (DACs) that realize job and machine dispatching policies of a flexible manufacturing system (FMS) into Deadlock free control actions. Such controllers not only keep the FMS capable of repeating any of its operations, but also achieve a high resource utilization under any given dispatching policy. Our methodology is based on an untimed Petri net formalism. It consists of four ingredients: 1) a bottom-up approach for synthesizing a controlled production Petri net (CPPN) model of a FMS; 2) a necessary and sufficient liveness condition based on decomposition of the CPPN into controlled production subnets and the concept of minimal resource requirements; 3) a sufficient procedure to test whether the liveness condition is kept after a control action is executed; and 4) an algorithm that combines the test procedure with the given dispatching policy to generate valid and utilization maximizing control actions. We assess that this method is of polynomial time complexity and show that it results in a much larger class of controls than that of an existing Deadlock Avoidance scheme. >
Zohar Manna - One of the best experts on this subject based on the ideXlab platform.
-
a family of distributed Deadlock Avoidance protocols and their reachable state spaces
Fundamental Approaches to Software Engineering, 2007Co-Authors: César Sánchez, Henny B Sipma, Zohar MannaAbstract:We study resource management in distributed systems. Incorrect handling of resources may lead to Deadlocks, missed deadlines, priority inversions, and other forms of incorrect behavior or degraded performance. While in centralized systems Deadlock Avoidance is commonly used to ensure correct and efficient resource allocation, distributed Deadlock Avoidance is harder, and general solutions are considered impractical due to the high communication overhead. However, solutions that use only operations on local data exist if some static information about the possible sequences of remote invocations is known. We present a family of efficient distributed Deadlock Avoidance algorithms that subsumes previously known solutions as special instances. Even though different protocols within the family allow different levels of concurrency and consequently fewer or more executions, we prove that they all have the same set of reachable states, expressed by a global invariant. This result enables: (1) a design principle: the use of different protocols at different sites does not compromise Deadlock Avoidance; (2) a proof principle: any resource allocation protocol that preserves the global invariant and whose allocation decisions are at least as liberal as those of the least liberal in the family, guarantees absence of Deadlock.
-
FASE - A family of distributed Deadlock Avoidance protocols and their reachable state spaces
Fundamental Approaches to Software Engineering, 2007Co-Authors: César Sánchez, Henny B Sipma, Zohar MannaAbstract:We study resource management in distributed systems. Incorrect handling of resources may lead to Deadlocks, missed deadlines, priority inversions, and other forms of incorrect behavior or degraded performance. While in centralized systems Deadlock Avoidance is commonly used to ensure correct and efficient resource allocation, distributed Deadlock Avoidance is harder, and general solutions are considered impractical due to the high communication overhead. However, solutions that use only operations on local data exist if some static information about the possible sequences of remote invocations is known. We present a family of efficient distributed Deadlock Avoidance algorithms that subsumes previously known solutions as special instances. Even though different protocols within the family allow different levels of concurrency and consequently fewer or more executions, we prove that they all have the same set of reachable states, expressed by a global invariant. This result enables: (1) a design principle: the use of different protocols at different sites does not compromise Deadlock Avoidance; (2) a proof principle: any resource allocation protocol that preserves the global invariant and whose allocation decisions are at least as liberal as those of the least liberal in the family, guarantees absence of Deadlock.
-
FASE - A family of distributed Deadlock Avoidance protocols and their reachable state spaces
Fundamental Approaches to Software Engineering, 2007Co-Authors: César Sánchez, Henny B Sipma, Zohar MannaAbstract:We study resource management in distributed systems. Incorrect handling of resources may lead to Deadlocks, missed deadlines, priority inversions, and other forms of incorrect behavior or degraded performance. While in centralized systems Deadlock Avoidance is commonly used to ensure correct and efficient resource allocation, distributed Deadlock Avoidance is harder, and general solutions are considered impractical due to the high communication overhead. However, solutions that use only operations on local data exist if some static information about the possible sequences of remote invocations is known. We present a family of efficient distributed Deadlock Avoidance algorithms that subsumes previously known solutions as special instances. Even though different protocols within the family allow different levels of concurrency and consequently fewer or more executions, we prove that they all have the same set of reachable states, expressed by a global invariant. This result enables: (1) a design principle: the use of different protocols at different sites does not compromise Deadlock Avoidance; (2) a proof principle: any resource allocation protocol that preserves the global invariant and whose allocation decisions are at least as liberal as those of the least liberal in the family, guarantees absence of Deadlock.
-
efficient distributed Deadlock Avoidance with liveness guarantees
Embedded Software, 2006Co-Authors: César Sánchez, Henny B Sipma, Zohar Manna, Christopher GillAbstract:We present a Deadlock Avoidance algorithm for distributed systems that guarantees liveness. Deadlock Avoidance in distributed systems is a hard problem and general solutions are considered impractical due to the high communication overhead. In previous work, however, we showed that practical solutions exist when all possible sequences of resource requests are known a priori in the form of call graphs; in this case protocols can be constructed that perform safe resource allocation based on local data only, that is, no communication between components is required. While avoiding Deadlock, those protocols, however, did not avoid starvation: they guaranteed that some process could always make progress, but did not guarantee that every individual process would always eventually terminate.In this paper we present a resource allocation mechanism that avoids Deadlock and guarantees absence of starvation, without undue loss of concurrency. The only assumption we make is that the local scheduler is fair. We prove the correctness of the algorithm and show how it can be implemented efficiently.
-
EMSOFT - Efficient distributed Deadlock Avoidance with liveness guarantees
Proceedings of the 6th ACM & IEEE International conference on Embedded software - EMSOFT '06, 2006Co-Authors: César Sánchez, Henny B Sipma, Zohar Manna, Christopher GillAbstract:We present a Deadlock Avoidance algorithm for distributed systems that guarantees liveness. Deadlock Avoidance in distributed systems is a hard problem and general solutions are considered impractical due to the high communication overhead. In previous work, however, we showed that practical solutions exist when all possible sequences of resource requests are known a priori in the form of call graphs; in this case protocols can be constructed that perform safe resource allocation based on local data only, that is, no communication between components is required. While avoiding Deadlock, those protocols, however, did not avoid starvation: they guaranteed that some process could always make progress, but did not guarantee that every individual process would always eventually terminate.In this paper we present a resource allocation mechanism that avoids Deadlock and guarantees absence of starvation, without undue loss of concurrency. The only assumption we make is that the local scheduler is fair. We prove the correctness of the algorithm and show how it can be implemented efficiently.
Mengchu Zhou - One of the best experts on this subject based on the ideXlab platform.
-
Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems
IEEE Transactions on Systems Man and Cybernetics - Part A: Systems and Humans, 2009Co-Authors: Ke Yi Xing, Mengchu Zhou, Feng TianAbstract: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.
-
SMC - Tractability of Deadlock Avoidance problem in automated manufacturing systems modeled with Petri Net
2008 IEEE International Conference on Systems Man and Cybernetics, 2008Co-Authors: Mengchu ZhouAbstract:For Deadlock Avoidance in automated manufacturing systems (AMSs), it is desired that a Deadlock control policy is maximally permissive. However, up to now, the tractability problem of Deadlock Avoidance in AMSs is still open. This paper conducts study on the tractability problem of Deadlock Avoidance for the general sequential resource allocation problem with each step requiring a single resource. An AMS is modeled by colored resource-oriented Petri net (CROPN). Based on the model, necessary and sufficient condition, under which the Deadlock Avoidance problem is tractable, is presented. At the same time, a one step look-ahead control policy is presented.
-
ICRA - Deadlock Avoidance in semiconductor track systems
Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292), 1Co-Authors: Mengchu ZhouAbstract:Addresses the Deadlock Avoidance problem in track systems in semiconductor fabrication. Without buffer space in it, the existing Deadlock Avoidance policies tend to be too conservative. Routing flexibility provides a chance to develop better ones, but makes their computation more complex. The paper models a track system using colored resource-oriented Petri nets. Based on the model, a sufficient condition for Deadlock-free operation and the corresponding control law are presented. The proposed policy is shown to be computationally efficient. An example is presented to demonstrate its application.
Brigitte Jaumard - One of the best experts on this subject based on the ideXlab platform.
-
Deadlock Avoidance and Detection in Railway Simulation Systems
2014 Joint Rail Conference, 2014Co-Authors: Bertrand Simon, Brigitte JaumardAbstract:Avoiding or preventing Deadlocks in simulation tools for train scheduling remains a critical issue, especially when combined with the objective of minimizing, e.g., the travel times of the trains. In this paper, we revisit the Deadlock Avoidance and detection problem, and propose a new Deadlock Avoidance algorithm, called DEADAALG, based on a resource reservation mechanism. The DEADAALG algorithm is proved to be exact, i.e., either detects an unavoidable Deadlock resulting from the input data or provide a train scheduling thanks to the scheduling algorithm, called SIMTRAS, which is free of Deadlocks. Moreover, we show that the SIMTRAS algorithm is a polynomial time algorithm with an O(|S| × |T|2log |T|) time complexity, where T is the set of trains and S is the set of sections in the railway topology. Numerical experiments are conducted on the Vancouver-Calgary single-track corridor of Canadian Pacific. We then show that the SIMTRAS algorithm is very efficient and provides schedules of a quality that is comparable to those of an exact optimization algorithm, in tens of seconds for up to 30 trains/day over a planning period of 60 days.Copyright © 2014 by ASME
-
Deadlock Avoidance and Detection in Railway Simulation Systems
Transportation Research Record, 2014Co-Authors: Bertrand Simon, Brigitte JaumardAbstract:Avoiding or preventing Deadlocks in simulation tools for train scheduling remains a critical issue, especially when combined with the objective of minimization (e.g., the travel times of the trains). The Deadlock Avoidance and detection problem is revisited, and a new Deadlock Avoidance algorithm, called DEADAALG, is proposed based on a resource reservation mechanism. The DEADAALG algorithm is proved to be exact; that is, it either detects an unavoidable Deadlock resulting from the input data or provides train scheduling free of Deadlocks with the scheduling algorithm SIMTRAS. Moreover, it is shown that SIMTRAS is a polynomial time algorithm with an O(|S|·|T|2 log |T|) time complexity, where T is the set of trains and S is the set of sections in the railway topology. Numerical experiments are conducted on Canada's Vancouver-Calgary single-track corridor of Canadian Pacific Railway Limited. Then it is shown that SIMTRAS is efficient and provides schedules of a quality that is comparable with that of an exa...
Mark Lawley - One of the best experts on this subject based on the ideXlab platform.
-
Observations on the interactions among Deadlock Avoidance policies and dispatching rules in automated manufacturing systems
International Journal of Production Research, 2003Co-Authors: Haldun Aytug, Mark Lawley, A. Barua, Reha UzsoyAbstract:In automated manufacturing systems, Deadlock Avoidance policies guarantee Deadlock-free operation while performance controllers, such as dispatching rules, attempt to achieve performance thresholds. In an automated system, dispatching rules must work within the constraints imposed by the Deadlock Avoidance policy in order to assure continuing system operation, and thus, the Deadlock Avoidance logic defines the decision space over which the dispatching rule can work. This paper investigates the interactions that arise between Deadlock Avoidance flexibility and the effectiveness of dispatching rules in achieving good system performance. Two major findings are that the positive effects of intelligent dispatching are highly influenced by the flexibility of the Deadlock Avoidance policy, and that a nayve dispatching rule can sometimes achieve better system performance under an inflexible Deadlock Avoidance policy.
-
Deadlock Avoidance for Sequential Resource Allocation Systems: Hard and Easy Cases
International Journal of Flexible Manufacturing Systems, 2001Co-Authors: Mark Lawley, Spyros ReveliotisAbstract:Deadlock is a major problem for systems that allocate resources in real time. The key issue in Deadlock Avoidance is whether or not a given resource allocation state is safe: that is, whether or not there exists a sequence of resource allocations that completes all processes. Although safety is established as NP-complete for certain broad resource allocation classes, newly emerging resource allocation scenarios often exhibit unique features not considered in previous work. In these cases, establishing the underlying complexity of the safety problem is essential for developing the best Deadlock Avoidance approach. This work investigates the complexity of safe resource allocation for a class of systems relevant in automated manufacturing. For this class, the resource needs of each process are expressed as a well-defined sequence. Each request is for a single unit of a single resource and is accompanied by a promise to release the previously allocated resource. Manufacturing researchers have generally accepted that safety is computationally hard, and numerous suboptimal Deadlock Avoidance solutions have been proposed for this class. Recent results, however, indicate that safety is often computationally easy. The objective of this article is to settle this question by formally establishing the NP-completeness of safety for this class and investigating the boundary between the hard and easy cases. We discuss several special structures that lead to computationally tractable safety characteristics.
-
Integrating flexible routing and algebraic Deadlock Avoidance policies in automated manufacturing systems
International Journal of Production Research, 2000Co-Authors: Mark LawleyAbstract:Deadlock Avoidance policies guarantee Deadlock free buffer space allocation to concurrent computing parts in flexible manufacturing systems. Typically, these policies require enumeration of the routes that parts follow. In systems with flexible routing, where parts can choose from a set of machines at each processing step, route enumeration can be of exponential complexity. Set-up and execution of Deadlock Avoidance constraints are rendered computationally intractable. The objective of this work is to develop a control model that allows for several processing alternatives at each step while maintaining Deadlock free operation and avoiding complete route enumeration.
-
Deadlock Avoidance for production systems with flexible routing
IEEE Transactions on Robotics and Automation, 1999Co-Authors: Mark LawleyAbstract:The objective of this work is to characterize the Deadlock Avoidance problem for systems with flexible routing capabilities. Specifically, the paper addresses Deadlock Avoidance for single capacity systems (each machine has a single unit of buffer capacity), and mixed capacity systems (some machines have multiple units of buffer capacity). For each of these, we characterize Deadlock and prove the correctness of several methods of suboptimal Deadlock Avoidance. We also address two interesting special cases. The first assumes that every stage of every part type can be performed on at least one multiple capacity machine, whereas the second provides a finite central buffer that can be revisited after every processing stage. For the first case, we present two suboptimal Deadlock Avoidance approaches, while for the second case, we show optimal Deadlock Avoidance to be computationally tractable.
-
SMC - Deadlock Avoidance in manufacturing systems with flexible routing and mixed capacity
SMC'98 Conference Proceedings. 1998 IEEE International Conference on Systems Man and Cybernetics (Cat. No.98CH36218), 1Co-Authors: Mark LawleyAbstract:Deadlock Avoidance is essential in the operation of flexible manufacturing systems. Many of these systems have redundant processing capabilities that support flexible part routing. This work characterizes Deadlock Avoidance for systems with flexible routing capabilities. Specifically, we address Deadlock Avoidance in systems where every stage of every part type possesses some processing alternatives, and one or more machines are equipped with multiple units of buffer capacity. Several necessary conditions for Deadlock and Deadlock Avoidance are identified.