Deadlock avoidance in an automated guidance vehicle system using a coloured Petri net model

This paper addresses the problem of deadlock control in automated guided vehicle (AGV) systems for automated manufacturing systems with unidirectinal guided paths. First, a Petri net (PN) model was developed for the problem. Then, by using the PN model developed, the condition for deadlock-free operation in AGV system and a control law are presented. To avoid deadlocks in AGV systems by this law, one needs only to observe the state of the system and check the number of free spaces available in some of the circuits. It is estimated that the proposed control law is simple enough to be used in the real-time control of contemporary system configuration. Three examples are used to show the application and efficiency of the proposed control law.     

An efficient real-time deadlock-free control algorithm for automated manufacturing systems

In recent years, deadlock issue has received considerable attention in the real-time control realm of automated manufacturing system (AMS). In this paper, we propose a simple and easily adaptable deadlock avoidance algorithm using a graph theoretic approach. Unlike Petri-net based methods which are complex and static from the viewpoint that once they are constructed and implemented, it is not easy to modify them as the system configuration is changed, and operate them coupled with other shop-floor control modules such as a dispatching controller, our algorithm can be used cooperatively with a dispatching controller and expanded with little modification. The core of the algorithm consists of two modules: resource allocation policy and a cycle detection method. In particular, the resource allocation policy is of importance in our algorithm because even though the cycle detection method is employed, deadlock may occur under wrong resource allocation policies. Throughout this paper, we propose a quasi two-step resourceallocation policy with which our deadlock avoidance algorithm can detect and avoid deadlock just one step before deadlock.     

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.     

Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers

In this paper, a new deadlock-free scheduling method based on genetic algorithm and Petri net models of flexible manufacturing systems is proposed. The optimisation criterion is to minimise the makespan. In the proposed genetic scheduling algorithm, a candidate schedule is represented by a chromosome that consists of two sections: route selection and operation sequence. With the support of a deadlock controller, a repairing algorithm is proposed to check the feasibility of each chromosome and fix infeasible chromosomes to feasible ones. A feasible chromosome can be easily decoded to a deadlock-free schedule, which is a sequence of transitions without deadlocks. Different kinds of crossover and mutation operations are performed on two sections of the chromosome, respectively, to improve the performance of the presented algorithm. Computational results show that the proposed algorithm can get better schedules. Furthermore, the proposed scheduling method provides a new approach to evaluate the performance of different deadlock controllers.     

Deadlock control of autonomous vehicle storage and retrieval systems via coloured timed Petri nets and digraph tools

This paper addresses the deadlock control problem for the autonomous vehicle storage and retrieval system (AVS/RS). For an AVS/RS with several autonomous vehicles running in bi-direction, deadlock control is one of the key issues in the implementation of AVS/RS. The cycle-deadlock is the main type of deadlock in AVS/RS. In the paper, the dynamic model of AVS/RS is investigated by using coloured timed Petri nets (CTPN). Based on the CTPN model, a route digraph is built to detect cycle-deadlock in AVS/RS with digraph tools; the necessary and sufficient conditions of deadlock-free are established. Moreover deadlock-free control policies are proposed, the critical state in deadlock free is also identified and FCFS policy is applied to solve it. Finally, a case study is given to validate the policies.     

Deadlock prevention technique using additional transitions for Petri nets

ABSTRACT

Siphon control has been utilized as a general methodology for systems of simple sequential process with resource (S³PR) deadlock systems. Although siphon control imposes additional control places on S³PR systems, it cannot guarantee that the maximum permissiveness is achieved. To solve the problem of deadlock prevention for S³PR, a new policy to design a deadlock-free supervisor with the maximally permissive system is proposed using additional transitions. Additionally, this approach can solve the problem of deadlock prevention for systems of sequential systems with shared resources (S4PR) system models.     

Hybrid Petri net and digraph approach for deadlock prevention in automated manufacturing systems

This paper proposes a hybrid approach to deadlock prevention in automated manufacturing systems that combines Petri nets (PNs) and digraphs, so taking advantage of the strong points of both techniques. The approach uses digraphs to make the detection of deadlock conditions easier and then translates the obtained information in empty siphons of the PN modelling the same system. The proposed methodology allows the implementation of new PN‐based deadlock prevention control policies. A case study and the simulation results show the benefits of the new control strategies.     

Deadlock modeling and control of semiconductor track systems using resource-oriented Petri nets

This paper addresses the deadlock avoidance problem in track systems in semiconductor fabrication. For the system 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. This paper models a track system using coloured resource-oriented Petri net (CROPN). Based on the model, a sufficient condition for deadlock-free operation and the corresponding control law are presented. This proposed policy is shown computationally efficient and less conservative than existing methods. An example is presented to demonstrate its application.     

On-line loading and dispatching in flexible manufacturing systems

This paper aims to contribute to the knowledge of factors influencing the performance of flexible automation systems, through the analysis of the behaviour of control rules (loading and dispatching rules) implemented in the real time control system of such plants. The research objective was to obtain some general indications on modes of approaching loading and dispatching of flexible manufacturing systems, bearing in mind that, on the one hand, the performances of the rules are influenced by the configuration of the plant to run, and on the other that for a given plant, there is the further influence of the production mix.     

Two-step approach to robust deadlock control in automated manufacturing systems with multiple resource failures

ABSTRACT

In an automated manufacturing system (AMS), resource failures are inevitable, which renders the existing deadlock control policies for AMSs without considering resource failures ineffective. For the AMSs with multiple unreliable resources, in this paper, a method is developed for robust deadlock resolution using the framework of Petri nets (PNs). The considered AMSs are modeled with PN models called system of simple sequential process with resources (S³PR). An unreliable S³PR (U-S³PR) is obtained by adding recovery subnets that model the resource failures and recovery procedures of the places where resource failures may happen. Based on the model, a two-step approach is developed to design a robust controller. At Step 1, we use a siphon-based deadlock control method to analyze the behavior with resource failures and propose an incomplete robust deadlock controller for a U-S³PR. At Step 2, a reachability-graph-analysis-based method is utilized to consummate the robust deadlock controller. Then, a robust liveness-enforcing supervisor is derived to make an unreliable S³PR live even if multiple types of resources break down. Finally, the proposed method is illustrated by using an example.     

SAW device implementation of a weighted stepped chirp code signal for direct sequence spread spectrum communications systems

This paper introduces a new weighted stepped chirp code signal for direct sequence spread spectrum (DS/SS) communications systems. This code signal uses the truncated cosine series functions as the chip functions, and it is the result of discretizing a continuous wave (CW) chirp that results in enhanced performance versus a pseudonoise (PN) code and equivalent performance and easier implementation than a CW chirp. This code signal will be shown to have improved compression ratio (CR) and peak sidelobe level (PSL) versus a PN code with identical code length and chip length. It also will be shown to have a similar CR and PSL compared to a CW chirp with identical pulse length and frequency deviation. The code signal is implemented on surface acoustic wave (SAW) devices that will be used as the code generator at the transmitter and the correlator at the receiver. The design considerations for the SAW device implementation of the code signal are discussed, including the effects of intersymbol interference. Experimental data is presented and compared to the predicted results for 8 different SAW devices examining the effects of code length (9 or 13 chips), weighting (uniform, cosine-squared, and Hamming), and sampling on the performance of the code signal.     

A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems

This paper presents a new algorithm for the flexible manufacturing system (FMS) scheduling problem. The proposed algorithm is a heuristic based on filtered beam search. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and automated guided vehicle (AGV) schedules for a given scheduling period. A new deadlock resolution mechanism is also developed as an integral part of the proposed algorithm. The performance of the algorithm is compared with several machine and AGV dispatching rules using mean flow time, mean tardiness and makespan criteria. It is also used to examine the effects of scheduling factors (i.e., machine and AGV load levels, routing and sequence flexibilities, etc.) on the system performance. The results indicate that the proposed scheduling algorithm yields considerable improvements in system performance over dispatching rules under a wide variety of experimental conditions.     

A due-date based production control policy using WIP balance for implementation in semiconductor fabrications

Production control policies are critical in the re-entrant processes of semiconductor fabrication. Manufacturing control policies such as input dispatching rules, CONWIP, and optimization-based rules have been implemented according to the managerial objectives of the wafer fabrication line. When few semiconductor wafer fabrication facilities were available, and the semiconductor industry was a seller's market, fabrications were operated to achieve both a high rate of production and high utilization of equipment. With the availability of more fabrications and the gradual shift to a buyer's market, customer satisfaction became a major measure of performance in semiconductor manufacturing. In this paper, due-date based production control policies for semiconductor fabrications are suggested, and their performances evaluated. Target balance (TB) optimization models using production target, due-dates, and WIP (work-in-process) are presented. The evaluation result shows that the TB models perform better than the ones cited in the literature.     

Towards an approach of synthesis,validation and implementation of distributed control for AMS by using events ordering relations

We study distributed control synthesis and validation for automated manufacturing systems (AMS) in the framework of supervisory control theory. To reduce the size of the control problem, we view an AMS as comprised of asynchronous subsystems which are coupled through imposed logical Boolean specifications. The principle of the distributed control approach is the decomposition of the global monolithic control action into local coordinated control strategies for the individual subsystems. Owing to its importance in a distributed scheme, the order in which events occur arouses interest. By extending our previous results, we develop a set of rules of events precedence ordering, under which the control strategy via decomposition promises the subsystems synchronisation and coordination. We show how these rules contribute to reduce the size of the controller models used in the verification/validation and implementation steps. The effectiveness of the proposed approach is demonstrated by means of an industrial AMS example.     

Real-time batch sequencing using arrival time control algorithm

This paper proposes a new feedback control method for batch sequencing in process industries where meeting customer due-date is important. Specifically, short-term batch sequencing for Just-In-Time is solved using an arrival time control approach. An integral controller embedded in each order adjusts the arrival time in real-time using the feedback obtained from a fast-mode simulation of the batch processing system. The applicability of the proposed batch sequencing method for the Penn State University Creamery is studied. Comparison of due-date performance with commonly used dispatching rules is presented. The proposed method has also been tested for general batch processing systems and has been found to produce good, feasible schedules with significantly better performance than the dispatching rules in terms of due-date deviation minimization.     

A conceptual framework for the generation of simulation models from process plans and resource configuration

Although simulation is a popular tool for modelling and analysing modern manufacturing systems, to model shop floor control systems (SFCSs) in simulation requires quite costly efforts, since they are responsible for resolving various decision problems, such as deadlock, part dispatching, and resource conflict. The objective of the paper is to address a conceptual framework necessary to generate a WITNESS simulation model automatically from graph-based process plans and resource configurations. A graph-based process plan is used to capture part operations, their related resource requirements, and their temporal precedence relationships. A WITNESS simulation model is a graphical representation of shop floor resources with the part flow logic embedded within each resource element. To generate a WITNESS model, a process plan is automatically converted into a machine-centred part routeing graph (MCPRG) and then a transport-tending part routeing graph (TTPRG). The MCPRG implies part flows among machines, in which a node represents a machine and an edge represents a part route. The TTPRG implies part flows among machines and material handling devices, in which a node represents either machine or material handler, and an edge represents a part route. From the TTPRG, the part's input and output rules for each resource can be automatically extracted and plugged into the WITNESS model. The approach proposed in the paper enables manufacturers to generate a simulation model rapidly and effectively for performance measurement, such as bottleneck identification, work in progress, throughput times, dynamic resource utilization, and deadlock, of the SFCSs.     

Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis

This paper presents a simulation-based experimental study of scheduling rules for scheduling a dynamic flexible flow line problem considering sequence-dependent setup times. A discrete-event simulation model is presented as well as eight adapted heuristic algorithms, including seven dispatching rules and one constructive heuristic, from the literature. In addition, six new proposed heuristics are implemented in the simulation model. Simulation experiments are conducted under various conditions such as setup time ratio and shop utilisation percentage. One of the proposed rules performs better for the mean flow time measure and another one performs better for the mean tardiness measure. Finally, multiple linear regression based meta-models are developed for the best performing scheduling rules.     

Quasi on-line scheduling procedures for flexible manufacturing systems †

This paper presents three quasi on-line scheduling procedures for FMSs consisting of work stations, transport devices, and operators. In the scheduling, different types of decisions are taken to perform a particular operation, i.e. the selection of (a) a work station, (b) a transport device and (c) an operator. Further, (d) the scheduling sequence of the operations has to be determined. The three developed procedures differ in the way these four decision problems are solved hierarchically. Several dispatching rules (SPT, SPT.TOT, SPT/ TOT and EFTA) are available to solve the last mentioned decision problem. Limited buffer capacities in an FMS may cause deadlock in the procedures as well as in practice. The scheduling procedures involve a buffer handling method to avoid deadlock. A case study is presented to demonstrate the three procedures and to show some of its properties. Based on simulation tests, some conclusions are drawn about the performance of the scheduling procedures and the various dispatching rules.     

Dynamic production control with dispatching within pre-emption

This paper deals with a production control problem for the testing and rework cell in a dynamic and stochastic computer integrated manufacturing (CIM) system. This research first defines dispatching within pre-emption for an extended form of pre-emption. A dynamic controller called competitive decision selector (CDS) is then modified and extended as CDSplus to handle three different production control decisions; dispatching, pre-emption, and dispatching within pre-emption. It observes the status of the system and jobs at every decision point, and makes its three different decisions in real time. The CDSplus dynamic control shows better performance than static control rules with respect to the number of tardy jobs.     

PN PLC: A methodology for designing,simulating and coding PLC based control systems using Petri nets

Flexible manufacturing cells (FMCs) are well established as a means of improving manufacturing efficiency in many batch production industries. They consist of an integrated group of computer numerically controlled (CNC) machine tools, programmable logic controller (PLC) based work/tool handling equipment and a control system to synchronize their operation. The safe and reliable operation of FMCs is clearly essential for their efficient use. However, FMCs are complex systems with elements that operate concurrently and interact at irregular times, depending upon the components to be produced. This inherent complexity demands intricate and sophisticated control systems which require development methodologies that are both comprehensive and rigorous. In this paper the authors introduce a methodology (PN PLC) which uses Petri nets for producing correct programmable logic controller (PLC) programs directly from the specifications. The methodology is specifically contrasted with the benefits, and problems, encountered in using tools such as 'ladder diagrams' (LDs) and 'sequential function charts' (SFCs) for designing logical control systems. PN PLC has advantages over ladder logic in clarity, which allows the program to be checked, maintained and updated reliably. Furthermore, the Petri net graph is a one-to-one equivalent of a ladder logic diagram, and thus either representation may be algorithmically translated to the other without loss of information. Finally, the rules for creating Petri net graphs, and subsequently translating them, are both simple and robust in use.