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.     

Formal verification of negotiation protocols for multi-agent manufacturing systems

Formal verification is an important means of tackling behavioural problems such as deadlocks in multi-agent systems. This paper is concerned with the role played by formal verification in the simulation-based performance analysis of multi-agent manufacturing systems. A discrete-event simulation case study is presented to show how varying certain timing parameters of the agent negotiation protocol affects the performance of a multi-agent manufacturing system as well as the chance of getting deadlocks among the software agents. When one tries to determine the optimal values of these timing parameters based on the simulation results, formal verification can help refine the results by confirming whether deadlocks among software agents are indeed possible for particular parameter values. This involves modelling the system's real-time behaviour according to the simulation model and applying the techniques and tools of model checking.     

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.     

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.     

Agent-based distributed scheduling for virtual job shops

Nowadays, market globalisation and stiff world-wide competition require flexible, demand-driven, and reconfigurable production systems that can adapt to the requirements of the increasing reduction in product life cycle and rapid changes in market demand. The advent and development of network technology (especially the Internet) and distributed computing technology make it possible for geographically dispersed manufacturing resources to be integrated and deployed effectively and efficiently. In addition, manufacturing enterprises can expand their throughput within a short time and rapidly reduce the production cycle via transferring certain jobs to other available manufacturing resources in the globalised manufacturing environment, viz., manufacturing enterprises can expand their throughput through the dynamic formation of virtual job shops according to the production requirements. Owing to more open manufacturing environments and rapid changes of market demands, the traditional centralised scheduling approaches are not suitable for this open distributed manufacturing environment. This paper proposes a distributed scheduling approach in which a multi-agent solution towards a ‘task-machine’ assignment is presented. The main points of discussion are the formation of a virtual job shop that is based on market mechanism and the distributed scheduling approach based on negotiation.     

Novel collaborative optimization framework with a negotiation model for satellite system design

This article proposes a novel collaborative optimization (NCO) framework that uses a persuasive multi-agent negotiation method for satellite system design. Satellite system design is a typical multi-disciplinary design optimization problem. The traditional collaborative optimization (CO) is a competitive method but has the disadvantage of inefficient convergence caused by the interdisciplinary compatibility constraints in system-level optimization. By introducing the multi-agent negotiation method, an NCO framework is proposed, in which the system-level and subsystem-level variable negotiations replace the system-level compatibility constraints in traditional CO. The negotiation introduces a modification for candidate values that do not satisfy the compatibility constraints, ensures that an alternative compatible candidate will be obtained and has high convergence efficiency. Two numerical benchmark functions and a multi-disciplinary satellite system design are used to analyse the performance of the proposed NCO. The simulation results show that NCO can efficiently ensure parameter interdisciplinary matching and advanced convergence performance.     

Multi-agent systems applications in manufacturing systems and supply chain management: a review paper

This paper offers a review of the development and use of multi-agent modelling techniques and simulations in the context of manufacturing systems and supply chain management (SCM). The objective of the paper is twofold. First, it presents a comprehensive literature review of current multi-agent systems (MAS) research applications in the field of manufacturing systems and SCM. Second, it aims to identify and evaluate some key issues involved in using MAS methods to model and simulate manufacturing systems. A variety of different MAS applications are reviewed in three different classified research areas: production design and development, production planning and control, and SCM. In presenting a detailed taxonomy of MAS applications, the paper describes MAS application domains from five different perspectives. The review suggests the MAS approach represents a feasible framework for designing and analysing real-time manufacturing operations, since the approach is capable of modelling different levels of agent behaviour and dynamical interactions. The paper also highlights a number of key issues which have to be taken into account in attempting to design MAS-based research paradigms for future applications in manufacturing systems.     

Effect of information sharing in supply chains with flexibility

Coordination plays a pivotal role in successful design and implementation of supply chains, especially for those that are formed by independent and autonomous companies. More specifically, information sharing has widely been regarded as an essential tool to coordinate supply chains activities in order to overcome supply chains dynamics. A major contribution of this paper is to analyse the effects of negotiation-based information sharing in a distributed make-to-order manufacturing supply chain in a multi-period, multi-product types environment, which is modelled as a multi-agent system. Information can only be exchanged through negotiation in the agent-based framework with delivery quantity and due date flexibility, which is significantly different from the past reported literature that shared information is available anytime. Four schemes, namely, stochastic model (STO), flexibility in delivery quantity and due date without information sharing (FLEX_NI), flexibility in delivery quantity and due date with partial information sharing (FLEX_PI), and flexibility in delivery quantity and due date with full information sharing (FLEX_FI), are considered. Simulation results indicate that FLEX_PI in the system has comparable performance in terms of total cost and fill rate against FLEX_FI, while both systems outperform STO and FLEX_NI. Considering the associated costs and limitations to achieve full information sharing, partial information sharing may be more practical in real-life applications. Nevertheless, the proposed agent-based framework with delivery quantity and due date flexibility but without information sharing (i.e. FLEX_NI) is not that worse as compared with the two schemes of information sharing (FLEX_PI and FLEX_FI). Therefore, by taking the difficulties of implementing information sharing into account, flexibility in delivery quantity and due date that could be introduced may be a more feasible solution.     

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.     

Sensor economy principles and selection procedures

Integrating multiple sensors into manufacturing systems enables adaptive and flexible automation and increases process adaptivity and quality control. The design of an optimum configuration must be based on a systematic analysis relative to operational and economic considerations. This design should include an evaluation of sensor performance, a decision on how many sensors, of which type they should be, and where to locate them, modes of sensor interaction, and the influence on overall performance based on a cost/benefit analysis. In most real-world applications it is impossible to develop an accurate model to predict sensor performance and therefore, performance must be derived empirically but in a systematic manner. This paper presents research and development of integrated sensor economy principles and selection procedures in addition to a performance assessment model. A systems engineering approach is applied for empirical investigations for assessment of alternative guidance systems. The outcome of this research is a set of general design guidelines for integrating multiple sensors into robotic manufacturing systems.     

Spatial econometrics models for congestion prediction with in-vehicle route guidance

The congestion dependence relationship among links using microsimulation is explored, based on data from a real road network. The work is motivated by recent innovations to improve the reliability of Dynamic Route Guidance (DRG) systems. The reliability of DRG systems can be significantly enhanced by adding a function to predict the congestion in the road network. The application of spatial econometrics modelling to congestion prediction is also explored, by using historical traffic message channel (TMC) data stored in the vehicle navigation unit. The nature of TMC data is in the form of a time series of geo-referenced congestion warning messages, which is generally collected from various traffic sources. The prediction of future congestion could be based on the previous year of TMC data. Synthetic TMC data generated by microscopic traffic simulation for the network of Coventry are used in this study. The feasibility of using spatial econometrics modelling techniques to predict congestion is explored. The results are presented at the end.     

基于消息的协同设计中的冲突

在由消息通信实现的协同设计中，认识和理解其内在的冲突，是CAD模型数据通信和维持数据一致的关键性问题。协同设计系统必须对协同水平和冲突的理解具有自适应能力，通常强协同对应的是强冲突，而弱协同对应的是弱冲突。对于强协同设计，为了协调强冲突，应该保证协同主体互斥地访问和操作协同客体，在此过程中可以采用协商、仲裁和模式等方式对协同中的冲突加以解决。     

A multi-agent model for the reasoning of uncertainty information in supply chains

In order to simulate the real world effectively, this paper proposes a multi-agent model that integrates a price negotiation support system based on the use of intelligent agents capable of processing information uncertainty. The certainty factor is integrated in expert systems to support the decision of agents. In the model, each agent is integrated with an expert system to deal with the uncertainty information. A real example of supply chains is chosen to show the validity of the proposed multi-agent model. Virtual companies can use the uncertainty information to support decisions. Multiple experiments are conducted to work on the coordination of the supply chain. The selling and purchasing prices in the supply chain are proposed in the experimental results. These prices are similar with the data in a real supply chain and are the optimal price strategy for the supply chain. The model was programmed using Jess and Swarm, which was run on Windows XP. The multi-agent model in the paper is beneficial to the reasoning of uncertainty information in multi-agent systems.     

Synchronization in manufacturing systems: quantification and relation to logistics performance

The term ‘synchronization’ in manufacturing refers to the provision of the right components to the subsequent production steps at the right moment in time. It is widely assumed that synchronization is beneficial to the logistics performance of manufacturing systems. However, it has been shown that synchronization phenomena can be detrimental to systems in which they emerge. To study if synchronization phenomena also occur in and affect manufacturing systems’ performance, a formal quantification and holistic understanding of the types of synchronization phenomena emerging in manufacturing are needed. This article aims to fill this research gap by developing synchronization measures for manufacturing systems, applying these measures to real-world production feedback data and utilising them to test the assumption about synchronization’s beneficial effect on logistics performance. We identify two distinct synchronization types occurring in manufacturing systems, logistics and physics synchronization, and show that they are negatively correlated. Further, we show that logistics synchronization and due date performance exhibit anti-correlation and thus question the assumption that synchronization leads to higher efficiency in manufacturing systems. This article aids production managers in designing and optimising production systems, and supports further empirical research in production planning and control and production system design.     

Modelling,measurement and evaluation of sequencing flexibility in manufacturing systems

Sequencing flexibility refers to the possibility of interchanging the order in which required manufacturing operations are performed. In this paper, we address several issues related to the modelling, measurement and performance evaluation of this flexibility in manufacturing systems. In particular, we introduce several representation and measurement schemes for sequencing flexibility and discuss the usefulness and limitations each. We then propose a new performance-based approach for quantifying the value of flexibility. To this effect, we study the relationship between flexibility and system performance under a variety of design assumptions and operating conditions. These relationships are used to identify key characteristics of a measure of flexibility that is reflective of system performance. This measure is to allow system designers and managers to predict performance based on existing levels of flexibility and/or determine the amount of flexibility required to achieve a certain level of performance. This measure is shown to be easier to calculate than traditional performance measures and to be possible to use as a substitute for these measures in estimating the effect of flexibility on performance.     

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.     

Intercell scheduling: A negotiation approach using multi-agent coalitions

Intercell scheduling problems arise as a result of intercell transfers in cellular manufacturing systems. Flexible intercell routes are considered in this article, and a coalition-based scheduling (CBS) approach using distributed multi-agent negotiation is developed. Taking advantage of the extended vision of the coalition agents, the global optimization is improved and the communication cost is reduced. The objective of the addressed problem is to minimize mean tardiness. Computational results show that, compared with the widely used combinatorial rules, CBS provides better performance not only in minimizing the objective, i.e. mean tardiness, but also in minimizing auxiliary measures such as maximum completion time, mean flow time and the ratio of tardy parts. Moreover, CBS is better than the existing intercell scheduling approach for the same problem with respect to the solution quality and computational costs.     

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.     

Analysis of automated guided vehicle configurations in flexible manufacturing systems

Automated guided vehicle (AGV) systems complement the operation of flexible manufacturing systems (FMS) by providing integrated automated material handling that capitalizes on the system's flexibility. Previous research considering AGV systems for use in FMS installations has focused on complex control strategies to reduce the congestion problem often encountered in these systems. Recently, attention has been given to tandem system configurations that reduce congestion and simplify system control. The present study uses the simulation methodology to compare the performance of three AGV configurations under a variety of experimental conditions. The results indicate that system size, load/unload time, and machine failure rate factors have significant impacts on the operation of the systems considered. In general, with respect to due date performance, it is recommended to use the traditional configuration in small systems while using the tandem/loop configuration in larger systems. Furthermore, it is shown that the addition of the loop to the tandem configuration mitigates the sensitivity of the tandem configuration to the load/unload time factor as well as significantly improving its performance under high load/unload times. Thus, if tandem configuration is desired to reduce congestion and simplify system control, investments must be made to directly reduce the load/unload times or to construct a loop to avoid the load/unload time penalty.     

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.