Real-time scheduling with deadlock avoidance in flexible manufacturing systems

The dynamic nature of manufacturing makes rescheduling essential in today's complex production environment, particularly in flexible and re-configurable systems. Research on optimising schedules, which includes deadlock avoidance, is rather limited. Furthermore, the deadlock problem is mostly ignored in research on rescheduling. A rescheduling algorithm, that uses time petri-nets and the minimal siphons concept, was developed to deal with sources of disturbance such as machine breakdowns in real-time. The algorithm guarantees a deadlock-free new schedule. The existence of alternative routes, availability of material handling facilities and the limitation of buffer capacities were taken into consideration. The developed algorithm modifies only the affected portion of the original schedule, rather than rescheduling all jobs, in order to limit changes to the original schedule and reduce the impact on the response time.The effect of flexible routing, machine breakdowns, machine downtime, routing criterion and the use of the dispatching rule on the performance of manufacturing systems was studied. The systems performance was measured by the average flow time, the makespan and the average machine utilisation. The results indicate that utilising the system routing flexibility in real-time rescheduling, while avoiding deadlocks, improves system performance. Moreover, routing the interrupted operation to an alternative machine, based on the minimum expected completion time rather than the least utilised machine criterion, resulted in better performance.     

A genetic algorithm for scheduling flexible manufacturing systems

General job shop scheduling and rescheduling with alternative route choices for an FMS environment is addressed in this paper. A genetic algorithm is proposed to derive an optimal combination of priority dispatching rules pdrs (independentpdrs one each for one Work Cell WC), to resolve the conflict among the contending jobs in the Giffler and Thompson GT procedure. The performance is compared with regard to makes-pan criteria and computational time. The optimal WCwise-pdr is proved to be efficient in providing optimal solutions in a reasonable computational time. Also, the proposed GA based heuristic method is extended to revise schedules on the arrival of new jobs, and on the failure of equipment to address the dynamic operation mode of flexible manufacturing systems. An iterative search technique is proposed to find the best route choice for all operations to provide a feasible and optimal solution. The applicability and usefulness of the proposed methodology for the operation and control of FMS in real-time are illustrated with examples. The scope of the genetic search process and future research directions are discussed.     

Generation of optimal control policy for flexible manufacturing cells: A Petri net approach

For flexible manufacturing cells (FMCs), the major control problem is to determine the optimal part routeing and machines dispatching policy. In this research, we present a methodology for generating optimal operating strategies for FMCs. The methodology is built on two techniques: stochastic timed Petri net (STPN) and Markov decision process (MDP). The operating strategy devised with the proposed methodology is deadlock-free and provides the best performance given a set of system parameters (machines, parts, machining times, etc.). Generation of programmable logic controller (PLC) codes is greatly facilitated as the generated strategy can be mapped directly to a ladder diagram representing the PLC code. The objective of real-time optimal control could then be achieved with this type of controller. An example is provided to illustrate the methodology.     

Object-oriented approach of MCTPN for modelling Flexible manufacturing systems

Manufacturing industry is facing a stricter challenge than ever before owing to the rapid change in market requirements. Flexible manufacturing systems (FMSs) have a much greater capability than traditional fixed-type production systems for coping with the rapid change. In this paper, a modified coloured-timed Petri net (MCTPN) is developed to model the dynamic activities in an FMS. The MCTPN provides an object-oriented and modular method of modelling manufacturing activities. It includes colour, time, modular and communication attributes. The features of object-oriented modelling allow the FMS to be modelled with the properties of classes, objects, and container trees. Since the system activities can be encapsulated and modularised by the proposed MCTPN, the manufacturing systems can be easily constructed and investigated by the system developers. It makes the concept of software IC possible for modelling complex FMSs. Once all of the MCTPN objects are well defined, the developers need to consider only the interfaces and operations relating to the MCTPN objects. In order to demonstrate the capability of the proposed MCTPN, the FMS in the Manufacturing Automation Technology Research Center (MATRC) of the National Taiwan University will be stimulated and justified by using the proposed MCTPN along with the G2 expert system.     

AGV schedule integrated with production in flexible manufacturing systems

Flexible manufacturing systems (FMS) comprise, automated machine tools, automated material handling, and automated storage and automated retrieval systems (AS/RS) as essential components. Effective sequencing and scheduling of the material handling systems (MHS) can have a major impact on the productivity of the manufacturing system. The material handling cannot be neglected while scheduling the production tasks. It is necessary to take into account the interaction between machines, material handling systems and computer. In this context, this paper attempts to link the operation of automated guided vehicles (AGV) with the production schedule and suggests a heuristic algorithm that employs vehicle dispatching rules (vdr) for conflict resolution. The vdrs considered in this paper are: shortest operation time (SPT), longest operation time (LPT), longest travel time (LTT) and shortest travel time (STT). The performance of the vdrs in the proposed heuristic is compared with makespan criteria. The results show that the STT provides the best solutions compared to other vdrs.     

Modelling,simulation and scheduling of flexible assembly systems with coloured Petri nets

Scheduling in flexible assembly systems is a complicated phenomenon owing to the large variability in the operating parameters. In this paper, coloured Petri nets are shown to be useful in modelling, simulating and scheduling flexible assembly systems. Case studies from published literature are chosen to show its superiority over some of the heuristic and analytical tools. In addition, the tool is also shown to model and analyse systems with some realistic constraints.     

The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems

In a flexible manufacturing system (FMS) with multiple products, deadlocks can arise due to limited shared resources, such as machines, robots, buffers, fixtures etc. The development of efficient deadlock prevention policies, which can optimise the use of system resources, while preventing deadlocks from occurring, has long been an important issue to be addressed. In [1], an optimal deadlock prevention policy was proposed, based on the use of reachability graph (RG) analysis of the Petri net model (PNM) of a given FMS and the synthesis of a set of new net elements, namely places with initial marking and related arcs, to be added to the PNM, using the theory of regions. The policy proposed in [1] is optimal in the sense that it allows the maximal use of resources in the system according to the production requirements. For very big PNMs, the reachability graph of the PNMs becomes very large and the necessary computations to obtain an optimal deadlock prevention policy become more difficult. In this paper, we propose the use of the Petri net reduction approach to simplify very big PNMs so as to make necessary calculations easily in order to obtain an optimal deadlock prevention policy for FMSs. An example is provided for illustration.     

Material flow and control sequence specification of flexible production systems using coloured Petri nets

Starting with the specification of each resource and the whole structure of a flexible production system, in this approach a special kind of coloured Petri nets is used for performing the modelling and the validation of the coordination control structure of the systems. In a second phase, it is proposed to modify the first models to synchronised Petri net schemas to facilitate the supervision and the interaction of the coordination model with the physical components of the system as well as the development and maintainability of the discrete-event control structures. The final result is a formal specification of coloured Petri net based coordination control of resources of the system, and logic control structures for control sequencing based on the use of synchronised subPetri net structures derived from the first one by refining transitions, i.e., their occurrence. Based on the proposed approach, the coordination control model of resources and a first skeleton of the logic control structures of a flexible assembly cell located at the Institute of Manufacturing Automation and Production Systems at the University of Erlangen-Nuremberg, Germany is elaborated and then the correctness of the obtained models with regard to material flow and control sequence specifications is validated by means of the structural analysis of the coloured Petri net-based models.     

Deadlock avoidance control for manufacturing systems with multiple capacity resources

This paper addresses the problem of designing a control scheme capable of avoiding deadlock conditions for a class of manufacturing systems. The considered model for the system under control is based on Petri nets, and is formulated according to well-known modelling rules. A deadlock avoidance policy is proposed which is an extension of a previously presented one. The proofs of its main properties are briefly sketched. Finally, an example of an automated manufacturing system for which such a deadlock avoidance policy has been applied is discussed.     

An integration architecture for flexible manufacturing cells

A modern flexible manufacturing cell (FMC) usually consists of several distributed control systems, including machining centres and material handling systems. Modelling an FMC to evaluate its design and performance, and translating the resulting models into operational programs are complex, but critical steps in implementing an FMC. This paper represents an architecture for the design, integration, and implementation of an FMC. The primary focus is on defining the process and functional requirements of the system, designing the system using high-level abstraction tools that ensure system integration and effective communication with users and implementors, and using efficient algorithms and effective interfaces for implementing real-time process control.     

An expert enhanced coloured fuzzy Petri net approach to reconfigurable manufacturing systems involving information delays

In today’s competitive market, manufacturers need to quickly adapt to the changing demands of the customers. Reconfigurable manufacturing system (RMS) is a cost-effective system that can easily absorb frequent changes in product demands. In this article such a system is modelled using expert enhanced coloured fuzzy Petri net (EECFPN), which considers the demands of customers as a fuzzy parameter and vividly captures the reconfigurability aspect of RMS. A fuzzy control strategy (FCS) is proposed to deal with the information delays occurring during information transfer or decision implementation. After intensive computational experimentation, it has been found that FCS outperforms the alternative priority (AP) heuristic and it is considered an effective measure to deal with situations where considerable information delay is involved.     

An activity-based predicate/transition net model of operational control planning for a flexible manufacturing system

An effective flexible manufacturing system (FMS) relies on a hierarchy of decisions, including the control of the FMS operation. The FMS operation usually is dynamically constrained by the limited resources such as pallets, machines, tools, carts, etc. Most analytical models make many assumptions and oversimplify the complicated decision problems. This study proposes the predicate/transition (Pr/Tr) net, a high level petri net, as a model for operational control planning. Firstly, the activities (modes) and their resources usage in FMS were analysed and aggregated into activity sets. Then, the flow of parts among activities was traced to obtain the mode transition diagram, and then the Pr/Tr net model was introduced. We incrementally defined the predicates and transitions into this model. Finally, a comprehensive FMS Pr/Tr net model was derived. By implementing it into a rule-based simulation model, it is well suited for FMS operational control planning because of its inclusiveness and high flexibility.     

Modeling and analysis for a kind of flexible manufacturing system involving time factors

Time control and management are important in flexible manufacturing systems (FMS). The time to finish the machining unit is uncertain because of the uncertainties of the workpieces, so the whole time to finish the FMS is also variable. In order to reduce the time to finish for the whole FMS to improve efficiency, the modeling and analysis method for this timing kind of FMS based on standard Petri net is proposed. The modeling method is a mapping from the machining units to the component of a Petri net, and the timing factors are represented by a timing function on the place set. With the Petri net model obtained and its reachability graph, the timing factors influencing the implementation of the FMS are analysed and presented. In addition, the method is obtained to find the best state line for the implementation of the FMS.     

模糊柔性制造系统的混杂Petri网建模与调度

对模糊柔性制造系统的建模和调度进行了研究.定义了一种具有模糊区间速率的混杂Petri网模型,提出了模型的迁移使能和迁移引发语义,定义了弱使能迁移的模糊使能规则,给出了模型动态演变算法.建立了模糊柔性制造系统调度的模糊线性规划模型,并对典型的工业实例进行了分析.研究结果表明,基于所定义的混杂Petri模型能够有效地描述和分析模糊柔性制造系统.     

An FMS scheduling and control decision support system based on generalised stochastic Petri nets

This paper presents an FMS scheduling and control DSS (decision support system) using generalised stochastic Petri nets (GSPNs) for model representation and analysis. The function of the DSS is to assist the FMS operator to search for suitable control strategies that will achieve efficient performance. It can also be called upon in the event of unforeseen changes in production requirements, component failures, or other related contingencies. The GSPN modelling approach is employed because GSPNs can characterise random processing times, machine breakdown and repair rates. The GSPN employed in the proposed DSS also incorporates dispatching control at conflicting immediate transitions and can be used to determine various performance measures pertaining to scheduling and control. An application example of the DSS for the processing of two part types in a three-machine FMS is also described.     

板材FMS的修正分层控制结构研究

研究板材柔性制造系统 (FMS)控制系统结构。在比较了几种典型控制系统结构之后 ,采用修正分层结构作为板材FMS的控制系统框架 ;文章详细研究了板材FMS的物理组成以及修正分层控制系统结构形式及其实现方式。     

基于UML-OPN的可重组制造系统建模分析方法

为建立涵盖两种重组方式的系统模型,避免现有方法中模型相互转化造成的信息丢失以及动态特性的不完整,在分析了可重组制造系统重组实现方式的基础上,提出了基于统一建模语言与面向对象Petri网的建模与性能分析方法。采用模块化方法对制造资源进行划分,利用统一建模语言建立系统逻辑模型,利用面向对象Pe-tri网建立系统物理模型,分析了各自活动机理,给出了模型关联映射的触发规则。为实现模型的性能分析,对面向对象Petri网引入时间参数,提出基于随机过程理论的性能分析方法。通过实例验证了建模与分析方法的有效性。     

Deadlock-free scheduling of an automated manufacturing system using an enhanced colored time resource Petri-net model-based evolutionary endosymbiotic learning automata approach

Deadlock-free scheduling of parts is vital for increasing the utilization of an Automated Manufacturing System (AMS). An existing literature survey has identified the role of an effective modeling methodology for AMS in ensuring the appropriate scheduling of the parts on the available resources. In this paper, a new modeling methodology termed as Extended Color Time Net of Set of Simple Sequential Process with Resources (ECTS³PR) has been presented that efficiently handles dynamic behavior of the manufacturing system. The model is subsequently utilized to obtain a deadlock-free schedule with minimized makespan using a new Evolutionary Endosymbiotic Learning Automata (EELA) algorithm. The ECTS³PR model, which can easily handle various relations and structural interactions, proves to be very helpful in measuring and managing system performances. The novel algorithm EELA has the merits of both endosymbiotic systems and learning automata. The proposed algorithm performs better than various benchmark strategies available in the literature. Extensive experiments have been performed to examine the effectiveness of the proposed methodology, and the results obtained over different data sets of varying dimensions authenticate the performance claim. Superiority of the proposed approach has been validated by defining a new performance index termed as the ‘makespan index’ (MI), whereas the ANOVA analysis reveals the robustness of the algorithm.     

Simultaneous optimisation of control factors in automated storage and retrieval systems and FMS using stochastic coloured Petri nets and the Taguchi method

Automated storage and retrieval systems (AS/RS) are playing an important role in modern manufacturing systems such as flexible manufacturing systems (FMS). The integration of AS/RS systems and FMS is very complex owing to the complexity of the individual elements. Stochastic coloured petri nets (SCPN) can be used to model, simulate and analyse such a system efficiently and realistically. In this paper, SCPN based simulation, aided by the Taguchi method of design of experiments, has been used for analysing the influence of important factors on makespan, unproductive travel time, and the mean flow time, and is supported by an example.     

Heuristic solution approaches for combined-job sequencing and machine loading problem in flexible manufacturing systems

Job sequencing and machine loading are two vital and interrelated production planning problems in flexible manufacturing systems (FMSs). In this research, attempts have been made to address the combined job sequencing and machine loading problem using minimization of system unbalance and maximization of throughput as objective functions, while satisfying the constraints related to available machining time and tool slots. This research describes two heuristics to deal with the problems. Heuristic I uses predetermined fixed job sequencing rules as inputs for operation allocation decision on machines, whereas heuristic II uses genetic algorithm based approach for simultaneously addressing job sequences and operation machine allocation issues. Performance of these heuristics has been tested on problems representing three different FMS scenarios. Heuristic II (Genetic algorithm based) has been found more efficient and outperformed heuristic I in terms of solution quality.