A coordination strategy for distributed multi-agent manufacturing systems

This paper proposes a distributed multi-agent approach for dynamic part routing in automated manufacturing systems. In particular, each part in the system is associated to an intelligent software agent that must select its next destination autonomously (i.e. ignoring the actions of the other agents) and in real time (i.e. at each time it completes an operation on a workstation). Differently from other existing approaches, we overcome the typical myopia of negotiation algorithms based on dispatching rules by allowing the part agents to take decisions not only about the imminent operation, but also for the subsequent ones. The anticipated decisions are transmitted to workstation agents, which are also designated to detect and resolve conflicts by modifying part agents’ decisions. To describe the single agents and their interaction schemes in a formal way, we take advantage of DEVS discrete-event modelling tools, which also allow us to develop a detailed simulation platform for our multi-agent system. The simulation experiments obtained on a detailed model of a manufacturing system derived from the literature confirm the effectiveness of the proposed approach.     

Agent-based manufacturing control based on distributed bid selection and publish-subscribe messaging: a simulation case study

Bidding-based negotiation schemes play a major role in multi-agent manufacturing systems research. Despite some concerns with message congestion, researchers have been proposing and studying negotiation schemes based on the contract net protocol (CNP). On the other hand, research in robotics has considered a variant of CNP based on publish-subscribe messaging designed for multi-robot coordination. A distinct feature of this variant involves distributing the bid evaluation and selection functions among robot agents. This paper discusses our adaptation of this design variant for multi-agent manufacturing systems and examines its performance implications. Using discrete-event simulation, we study how the adapted CNP design can help address the message congestion problem by cutting down on negotiation slack time. Our case study results show that it can enhance the resilience of the agent negotiation process to message congestion, thereby contributing to the overall performance of a multi-agent manufacturing system.     

Performance evaluation of an auction-based manufacturing system using coloured Petri nets

The next generation of manufacturing systems is assumed to be intelligent enough to make decisions and automatically adjust to variations in production demand, shop-floor breakdowns etc. Auction-based manufacturing is a control strategy in which various intelligent entities in the manufacturing system bid themselves, accept bids and make selections among the bids available based on a heuristic. This paper deals with the simulation modelling and performance evaluation of a push-type auction (negotiation) based manufacturing system embedded in a pulltype production system using coloured Petri nets. Three different models of an auction-based manufacturing system have been discussed. This methodology helps in developing systems for real-time control, anticipation of deadlocks, and evaluation of various performance metrics like machine utilization, automated guided vehicle (AGV) utilization, waiting times, work in process (WIP) etc. Various decision-making rules were identified for the real-time control of auction-based manufacturing systems.     

A review of “Advances in Computer-Integrated Manufacturing.” Edited by Peter J. Sacket (JAI Press Ltd., 1990) [pp. 188]. Price £ 48, US $ 81·95.

Global competition and rapidly changing customer requirements are forcing major changes in the production styles and configuration of manufacturing organizations. Traditional centralized manufacturing systems are not able to meet such requirements. This paper proposes an agent-based approach for dynamically creating and managing agent communities in such widely distributed and everchanging manufacturing environments. After reviewing the research literature, an adaptive multi-agent manufacturing system architecture called MetaMorph is presented and its main features are described. Such architecture facilitates multi-agent coordination by minimizing communication and processing overheads. Adaptation is facilitated through organizational structural change and two learning mechanisms: learning from past experiences and learning future agent interactions by simulating future dynamic, emergent behaviours. The MetaMorph architecture also addresses other specific requirements for next generation manufacturing systems, including scalability, reliability, stability, maintainability, flexibility, real-time planning and scheduling, standardized communication, fault tolerance, and security. The proposed architecture is implemented as a multi-agent virtual manufacturing system, in simulation form, which incorporates heterogeneous manufacturing agents within different agent-based shop floors or factories. The experimental results have shown the potential of the agent-based approach for advanced manufacturing systems.     

Development of a parallel processing multi-agent architecture for a virtual CIM system

Global manufacturing enterprises tend to rely on fully integrated manufacturing systems to satisfy constantly changing market requirements. In addition, small to medium enterprises are in a dilemma when competing with large organizations. Virtual computer-integrated manufacturing (VCIM) is a realistic concept that can provide the integration requirements for the globally distributed manufacturing resources and it has the potential to satisfy the market requirements of small to medium enterprises. The vision of the VCIM is to improve the efficiency and effectiveness of manufacturing enterprises by seamlessly integrating globally distributed manufacturing resources as much as possible. Meanwhile, intelligent agent technology provides a better means to implement distributed components as integrated application systems. The paper provides a parallel processing multi-agent architecture to support a global integrated manufacturing system in the form of the VCIM. In this architecture, a three-layered structure is proposed to accommodate all the agents no matter where they are located. Multiple Facilitator agents are proposed with similar functionalities to smooth the information flow across the integrated system in a parallel connection manner. In addition, a multi-agent VCIM model that describes the agent identification approaches for VCIM, Java environment implementation approaches and a simulation system to demonstrate the parallel processing multi-agent architecture are also discussed.     

Markovian models for deadlock analysis in automated manufacturing systems

Deadlocks constitute a major issue in the desing and operation of discrete event systems. In automated manufacturing systems, deadlocks assume even greater importance in view of the automated operation. In this paper, we show that Markov chains with absorbing states provide a natural model of manufacturing systems with deadlocks. With illustrative examples, we show that performance indices such as mean time to deadlock and mean number of finished parts before deadlock can be efficiently computed in the modelling framework of Markov chains with absorbing states. We also show that the distribution of time to deadlock can be computed by conducting a transient analysis of the Markov chain model.     

Using Extended Timed Petri Nets to evaluate and validate timing performance of hard real‐times software

Abstract

An important issue in real‐time systems development is to check the satisfaction of timing requirements. In this paper, we propose a formal model of the Extended Timed Petri Nets (ETPN) to model real‐time software systems. Some basic types of transitions are used to model the structures among software processes. The general equations for evaluating the performance in firing the basic transitions of ETPN are presented. The timing performances of a modelled software system can be evaluated using the corresponding ETPN. The evaluated results are validated with the corresponding timing constraints for checking the satisfaction of the results. The systematic procedure for evalution and validation are also discussed.     

A structured approach to deadlock detection,avoidance and resolution in flexible manufacturing systems

Production scheduling models that determine part mix ratios and detailed schedules do not usually account for deadlocks that can be caused by part flow. Deadlocks must be prevented for operational control (especially in automated systems). The major thrust of this paper is in developing a structured model for deadlock detection, avoidance and resolution caused by part flow in manufacturing systems. A system status graph can be constructed for the parts currently in the system. Deadlock detection amounts to determining deadlocks in the system status graph. On the other hand, deadlock avoidance amounts to restricting parts movement so that deadlocks are completely avoided in the future. While deadlock detection is a one-step look ahead procedure, deadlock avoidance is a complete look ahead procedure. Deadlock resolution or recovery amounts to judiciously using a limited queue to recover from deadlocks. Deadlock detection and avoidance are absolutely crucial to uninterrupted operation of automated manufacturing systems. A model based in graph theory has been formulated to detect and avoid deadlocks in automated manufacturing systems.     

Deadlock detection and resolution for discrete-event simulation: multiple-unit seizes

This paper develops an automatic scheme to detect and resolve deadlocks in discrete-event simulation systems with entities capable of requesting multiple units of a resource. The research extends earlier deadlock work on discrete simulation systems with unit resource requests. The purpose of the deadlock handling scheme is to provide for additional capabilities in discrete simulation systems. This is accomplished by endowing the simulation system with appropriate data structures and algorithms. The algorithms presented are based on a graph model of deadlocks in the simulation system. The proposed algorithms identify different categories of permanent and transient deadlocks in the simulation system. A deadlock resolution scheme is also developed in the case of group-processing for permanent deadlocks.     

A multi-agent virtual enterprise model and its simulation with Swarm

Virtual enterprise (VE) is a considerably complex organization in the world. More efforts have been made to establish such organization, among which multi-agent modelling and simulation are regarded as a promising approach. In this paper, MAS theory and technology are briefly reviewed. A novel multi-agent VE model is provided with a comparison with related work. Swarm as an outstanding multi-agent simulation programming tool is introduced. A modelling and simulation platform is developed with Swarm. The framework and main components of the platform are illustrated. The procedure of modelling VE on this platform is proposed. A case study using the platform on VE establishment in manufacturing domain is presented, and several common formulae to measure the performance of manufactures are developed in this case study.     

Optimal resource assignment through negotiation in a multi-agent manufacturing system

Research studies on multi-agent systems have been recently boosted by manufacturing and logistics with deep motivations like the presence of independent human deciders with individual goals, the aspiration to dominate the complexity of decision-making in large organizations, the simplicity and robustness of self-reacting distributed systems. After a survey of the multi-agent paradigm and its applications, the paper introduces the notion of hybrid holonic system to study the effect of supervision on a system whose elements negotiate and cooperate in a rule-settled environment to obtain resources for system operation. The supervisor can spur or disincentive agents by assigning/denying resources to them. A simple single-decider optimization model referred to a real application is described, and solution methodologies for optimal resource allocation fitting different scenarios (centralized, distributed, multi-agent) are discussed, identifying ranges of autonomy, quantifying rewarding and defining a negotiation protocol between the agents and the supervisor. Aim of the paper is to describe through an example a general methodology for quantitative decision-making in multi-agent organizations.     

Development of a hybrid negotiation scheme for multi-agent manufacturing systems

A hybrid inter-agent negotiation mechanism based on currency and a pre-emption control scheme is proposed to improve the performance of multi-agent manufacturing systems. The multi-agent system considered consists mainly of four types of agents: machine, clone, part and mediator. The machine agent controls the scheduling and the execution of a task. The clone agent aims to maximize the utilization rate by attracting relevant work to the machine. The part agent communicates with the machine agent or clone agent to acquire necessary production resources in order to get the required processing done, and the mediator agent contains the status of the part that will be processed by the subcontracting machine agent. The primary objective is to design decentralized control protocols for discrete part manufacturing systems to enhance the efficiency of the system and to allocate dynamically the resources to critical jobs based on the dynamic search tree. This research incorporates both the currency and the pre-emption schemes within a common framework. Currency functions are used to help the agents meet their individual objectives, whereas the pre-emption scheme is used to expedite the processing of parts based on their due dates. A dynamic search algorithm for the best route selection of different operations based on the job completion time is also proposed and it is implemented on a small manufacturing unit.     

Feasibility of online collaborative voltage stability control of power systems

The authors present the results of feasibility study of a novel concept of power system online collaborative voltage stability control. Online collaboration between power system controllers is proposed in order to enhance their overall performance and efficiency to cope with the increasing operational uncertainty of modern power systems. The framework of the proposed online collaborative voltage stability control is first presented, which is based on the deployment of multi-agent systems and real-time communication for online collaborative control. Then, two of the most important issues in implementing the proposed online collaborative voltage stability control are addressed: (1) Error-tolerant communication protocol for fast information exchange among multiple intelligent agents; (2) Deployment of multi-agent systems by using graph theory to implement power system post-emergency control. Results of testing the proposed online collaborative voltage stability control in the case of the 10-machine 39-node New England power system are presented. Results of a feasibility study by means of a simulation are given that take into consideration low-probability cascading faults in the power system.     

Performance-based dynamic scheduling model for flexible manufacturing systems

A performance-based dynamic scheduling model for random flexible manufacturing systems (FMSs) is presented. The model is built on the mathematical background of supervisory control theory of discrete event systems. The dynamic FMS scheduling is based on the optimization of desired performance measures. A control theory-based system representation is coupled with a goal programming-based multi-criteria dynamic scheduling algorithm. An effectiveness function, representing a performance index, is formulated to enumerate the possible outputs of future schedules. Short-term job scheduling and dispatching decisions are made based on the values obtained by optimizing the effectiveness function. Preventive actions are taken to reduce the difference between actual and desired target values. To analyse the real-time performance of the proposed model, a software environment that included various Visual Basic Application® modules, simulation package Arena®, and Microsoft Access® database was developed. The experimentation was conducted (a) to determine the optimum look-ahead horizons for the proposed model and (b) to compare the model with conventional scheduling decision rules. The results showed that the proposed model outperformed well-known priority rules for most of the common performance measures.     

Using a multi-agent system to optimise resource utilisation in multi-site manufacturing facilities

Due to cost economies and better serving the global market, many enterprises expanded their manufacturing environment from a localised, single-site facility to more globalised, multi-site facilities. In order to take advantage of operating multi-site facilities, it is vital to make optimisation decisions of resource utilisation as if these facilities situated across different geographical locations are one integrated facility and take into account of the extended multi-site constraints and variables. This paper proposes a multi-agent system, using its characteristics of autonomy and intelligence, to integrate process planning and production scheduling across different facilities, so as to secure the most efficient and cost-effective plan and schedule to meet the demand. A currency-based agent iterative bidding mechanism is developed to facilitate the co-ordination of agents to achieve the goal. A genetic algorithm is employed to tune the currency values for agent bidding. In this paper, a case study is used for simulation in order to demonstrate the effectiveness and performance of the proposed agent system.     

Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach

In real-world manufacturing, disruptions are often encountered during the execution of a predetermined schedule, leading to the degradation of its optimality and feasibility. This study presents a hybrid approach for flexible job-shop scheduling/rescheduling problems under dynamic environment. The approach, coined as ‘HMA’ is a combination of multi-agent system (MAS) negotiation and ant colony optimisation (ACO). A fully distributed MAS structure has been constructed to support the solution-finding process by negotiation among the agents. The features of ACO are introduced into the negotiation mechanism in order to improve the performance of the schedule. Experimental studies have been carried out to evaluate the performance of the approach for scheduling and rescheduling under different types of disruptions. Different rescheduling policies are compared and discussed. The results have shown that the proposed approach is a competitive method for flexible job-shop scheduling/rescheduling for both schedule optimality and computation efficiency.     

Operating system verification—An overview

This paper gives a high-level introduction to the topic of formal, interactive, machine-checked software verification in general, and the verification of operating systems code in particular. We survey the state of the art, the advantages and limitations of machine-checked code proofs, and describe two specific ongoing larger-scale verification projects in more detail. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council.     

Development of a safety critical software requirements verification method with combined CPN and PVS: a nuclear power plant protection system application

Safety-critical software systems such as certain nuclear instrumentation and control (NI&C) systems should be developed with thorough verification. This study presents a method of software requirement verification with a case study for a nuclear power plant (NPP) protection system. The verification introduces colored petri net (CPN) for system modeling and prototype verification system (PVS) for mathematical verification. In order to aid flow-through from modeling by CPN to mathematical proof by PVS, an information extractor from CPN models has been developed in this paper. In order to convert the extracted information to the PVS specification language, a translator has also been developed. This combined method has been applied to the functional requirements of the Wolsong NPP Shut Down System #2 (SDS2); logical properties of the requirements were verified. Through this research, guidelines and a tool support for the use of formal methods have been developed for application to NI&C software verification.     

Formal verification of functional properties of a SCR-style software requirements specification using PVS

Industrial software companies developing safety-critical systems are required to use rigorous safety analysis techniques to demonstrate compliance to regulatory bodies. In this paper, we describe an approach to formal verification of functional properties of requirements for an embedded real-time software written in software cost reduction (SCR)-style language using PVS specification and verification system. Key contributions of the paper include development of an automated method of translating SCR-style requirements into PVS input language as well as identification of property templates often needed in verification. Using specification for a nuclear power plant system, currently in operation, we demonstrate how safety demonstration on requirements can be accomplished while taking advantage of assurance provided by formal methods.     

Guidelines for selection of manufacturing simulation software

Manufacturing systems have become progressively complex and costly. Simulation is increasingly being used as an analysis and evaluation method in the design and operation of these systems. The practical use of simulation in the manufacturing environment has resulted in an increase in the number of available software tools for manufacturing simulation. This paper provides guidelines for selecting manufacturing simulation software according to the intended purpose of software use. The basic criteria to be examined in the software evaluation process are listed together with the level of their importance for particular types of users.