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.     

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.     

Oscillator analogy for modelling the manufacturing systems dynamics

The purpose of this paper is to present an approach of modelling and analysis of the dynamic behaviour of manufacturing systems. The manufacturing system is considered to be responding to an excitation, namely a demand that varies over time, by producing a number of parts over time. This resembles a mechanical system that displaces its mass responding to a varying input force. Based on this analogy, this paper establishes a manufacturing system's modelling method. A system identification technique is used for deriving inertia, damping and stiffness from the manufacturing system's response to different excitations. Based on these attributes, the response of a manufacturing system to any given input can be estimated. Furthermore, a definition for assessing manufacturing flexibility, based on this approach, is being discussed.     

Virtual fusion: a hybrid environment for improved commissioning in manufacturing systems

Efficiency and quality are major factors contributing to profits in manufacturing systems. Production downtime occurs during commissioning of a new system, adoption of new processes, system faults, or (un)planned maintenance; all of which result in reduced production and profit loss. Current techniques for evaluating change to a manufacturing system rely on simulation and modeling to verify processes, but ignore the physical interactions of the work parts on the system. Implementation techniques to evaluate commissioning focus on identifying issues with the cyber interfaces, ignoring the physical interfaces. To validate the cyber and physical interfaces simultaneously, physical work are sent through the system, resulting in significant costs from scrapped work parts and loss of production time. This research proposes a virtual fusion environment where the physical interfaces between a virtual work part and a manufacturing system can be investigated in real-time, on the physical system, without the expenses associated with physical work parts. The virtual environment includes a virtual fusion filter to monitor discrepancies between the physical and virtual systems, and generate a hybrid virtual-physical input signal to the system level controller for virtualisation of a work part onto a physical system. Experimental demonstrations validate the feasibility of the proposed approach.     

Balancing of manufacturing systems with complex configurations for delayed product differentiation

In response to increasing product variety, manufacturing systems with complex asymmetric configurations have often been used for delayed product differentiation. Balancing these types of manufacturing systems, however, is a challenge, since existing line balancing methods usually have been developed for symmetric configurations, such as serial lines with parallel machines at some stages. This paper proposes a novel binary integer programming (BIP) model for task-machine assignment and workload balancing in complex asymmetric configurations for mixed-model production. The new model includes (1) mathematical representations of task relations and system configurations, (2) constraint equations for task precedence relations in asymmetric configurations, and (3) constraint equations for parallel/serial relations among tasks. This study extends the area of line balancing and task-machine assignment problems to asymmetric system configurations, and helps to select a configuration from alternatives.     

Analysis of sequential failures for assessment of reliability and safety of manufacturing systems

Assessment of reliability and safety of a manufacturing system with sequential failures is an important issue in industry, since the reliability and safety of the system depend not only on all failed states of system components, but also on the sequence of occurrences of those failures. Methods that are currently available in sequential failure analysis always start with given sequences of the failures in the system, which is not the case in real life situations; therefore, the sequences of the failures should be identified and the probability of their occurrence should be determined. In this paper, we represent a methodology that can be used for identifying the failure sequences and assessing the probability of their occurrence in a manufacturing system. The method employs Petri net modeling and reachability trees constructed based on the Petri nets. The methodology is demonstrated on an example of an automated machining and assembly system.     

Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings.     

Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.     

Reconfiguration: a key to handle exceptions and performance deteriorations in manufacturing operations

During a manufacturing operation, exceptions may occur dynamically and unpredictably. Their occurrence may lead to the degradation of system performance or, in the worst case scenario may interrupt the production process by causing errors in the schedule plan. This paper classifies three families of exceptions: (1) out-of-order events such as machine breakdowns, (2) operational out-of-ordinary events such as rush orders and (3) deteriorations of manufacturing resource performance such as reductions of machines’ utilization. In all cases, in order to maintain an adequate level of system performance, it is necessary to detect exceptions, to diagnose them quickly and to recover them by taking corrective actions to avoid fault propagations. Decisions concerning how to deal with exceptions, i.e. which strategy to implement, depend on the manufacturing environment (dedicated line, flexible system, reconfigurable system or a mix of them) and the advantages arising from using a certain exception handling policy vary from one production system to another. The activity of reconfiguring manufacturing resources has been demonstrated to be a powerful operation strategy to handle machine breakdowns. This paper extends the concept of ‘reconfiguration for exception handling’ to other families of exceptions and proposes reconfiguration for their recovery. The reconfiguration process is handled by an agent-based control system that implements four negotiation processes among manufacturing resource agents.     

An aggregation method of Markov graphs for the reliability analysis of hybrid systems

To meet always increasing safety requirements in car industry, design and safety assessment methods are developed in order to fit the complexity of new embedded mecatronic systems. Hybrid (discrete/continuous) and dynamic features, specific to these systems, require choosing a suitable formalism. These features should also be considered in safety studies made all through the system design. The aim of this paper is to propose a quantitative analysis method based on the construction of an aggregated Markov graph, which allows a limitation of the combinatorial expansion. This graph is directly deducted from the Petri net modelling of the system. It is composed by a set of functional modes and a set of transitions to which statistical information regarding the system dynamics has been added.     

The tool transporter movements problem in flexible manufacturing systems

We consider a job sequencing and tool transporter movements problem on a single flexible machine with limited tool magazine capacity. A tool transporter having limited capacity is used in transporting the tools between the machine and tool crib area. Our aim is to minimize the number of the tool transporter movements. We present several lower and upper bounds, propose a Branch-and-Bound algorithm and a Beam Search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized instances with 25 jobs and 25 tools. For large-sized problem instances, Beam Search provides high quality solutions very quickly. Finally, we address the problem of minimizing the total flow time.     

A hybrid multi-agent negotiation protocol supporting supplier selection for multiple products with synergy effect

Supplier selection is an important problem in supply chain management. In practice, it is common for a purchasing company to procure a bundle of products simultaneously. In this regard, synergy effect could exist between products and hence affect the final choice of suppliers. It is therefore necessary to incorporate the synergy effect between products in supplier selection process. Agent-based negotiation models are applied to automate supplier selection process. Negotiation protocol is an essential component should be considered when building an effective agent negotiation model. The objective of this research is to propose a negotiation protocol special for multi-product supplier selection problem. The negotiation protocol is a hybrid multi-agent protocol of combinatorial procurement auction protocol and multi-bilateral bargaining protocol. The negotiation protocol is able to support the purchasing company and suppliers negotiate on the concrete commitments of multiple products simultaneously, and select suppliers for multiple products. In addition, both the purchasing company and suppliers can express their preferences on the synergy effect between products in negotiation process by adopting the negotiation protocol. Simulation is conducted to demonstrate the effectiveness and efficiency of the negotiation protocol.     

New reliability modeling methods for structural systems with hybrid uncertainty

The present study investigates the hybrid reliability modeling of structures in which the inputs contain both random variables and interval variables. Hybrid uncertainty is divided into three categories, including random variables mixed with random variables, interval variables mixed with interval variable, and random variables mixed with interval variables. In order to perform the reliability analysis of structural systems, first, the Bayes method is proposed in the present study to obtain distribution parameters of random variables. Moreover, the self-sample method is introduced to obtain the interval boundaries based on the least available measuring data. Then, the reliability models are established for three situations and the reliability indices are defined and derived accordingly. The abovementioned three types of reliability indices outline the general situation of structural systems. Finally, the specific calculation process is described in details through different examples. Furthermore, the accuracy and efficiency of the proposed method is discussed by comparing the results obtained from the Monte Carlo simulation and those of other methods. The obtained results indicate that the performance of the proposed model in solving reliability modeling problems is better.     

Scheduling of deadlock and failure-prone automated manufacturing systems via hybrid heuristic search

This work focuses on the scheduling problem of deadlock and failure-prone automated manufacturing systems, and presents a new scheduling method by combining a robust supervisory control policy and hybrid heuristic search. It aims to minimise makespan, i.e. the completion time of the last part. Based on the extended reach ability graph of the system, it establishes a new heuristic function and two dispatching rules to guide the search process for a schedule. By embedding a robust supervisory control policy into the search process, it develops a polynomial robust dynamic window search algorithm. Failure and repair events of unreliable resources may occur during the execution of a schedule obtained by the proposed algorithm and may make the schedule infeasible. To reduce the influence caused by them and ensure all parts to be finished, this work proposes two event-driven strategies. The first one suspends the execution of the parts requiring failed resources and those to be started until all failed resources are repaired and permits only those parts that have already been processed on working machines to be completed. The second one invokes the proposed algorithm to obtain a new schedule at the vertex generated after a resource failure or repair event and executes the new schedule. Both strategies are effective while the latter performs better at the expense of more computation.     

Machine cell formation for production management in cellular manufacturing systems

The formation of machine-part families is an important task in the design of cellular manufacturing systems. Manufacturing cell grouping has the effect of reducing material handing cost and work in process. Among the many methods utilized in machine cells formation, the similarity coefficient method is most widely used. Production sequence and product volumes, if incorporated properly in determining the machine cells, can enhance the quality of solutions and reduce the number of intercellular movements. Measures for cell formation based on operations sequence utilizing ordinal production data are few and have many limitations, such as counting the number of the trips for each individual part instead of counting the weights of the batches. A new ordinal production data similarity coefficient based on the sequence of operations and the batch size of the parts is introduced. Furthermore, a new clustering algorithm for machine cell formation is proposed. The new similarity measure showed more sensitivity to the intercellular movements and the clustering algorithm showed better machine grouping.     

Integrated design approach for virtual production line-based reconfigurable manufacturing systems

Reconfigurable manufacturing systems (RMSs) have been recognized as a new manufacturing paradigm. In light of their enhanced flexibility and responsiveness, RMSs are considered to be mostly applicable to the very dynamic and unpredictable marketplaces of the near future. However, systematic approaches to the design and ramp-up of an RMS have not been well addressed. This paper presents a virtual production line-based (VPL) approach to the design and operation of a reconfigurable manufacturing system. Shop floor attributed finite-capacity automaton and VPL attributed finite-capacity automaton are proposed for modelling the control of an RMS, which leads to ease of control software development. Algorithms for balancing VPLs to maximize the productivity of an RMS are discussed. The results of simulation runs of the proposed methodology and algorithms applied to simplified back-end semiconductor manufacturing are provided.     

A genetic scheduling methodology for virtual cellular manufacturing systems: an industrial application

Effective solutions to the cell formation and the production scheduling problems are vital in the design of virtual cellular manufacturing systems (VCMSs). This paper presents a new mathematical model and a scheduling algorithm based on the techniques of genetic algorithms for solving such problems. The objectives are: (1) to minimize the total materials and components travelling distance incurred in manufacturing the products, and (2) to minimize the sum of the tardiness of all products. The proposed algorithm differs from the canonical genetic algorithms in that the populations of candidate solutions consist of individuals of different age groups, and that each individual's birth and survival rates are governed by predefined aging patterns. The condition governing the birth and survival rates is developed to ensure a stable search process. In addition, Markov Chain analysis is used to investigate the convergence properties of the genetic search process theoretically. The results obtained indicate that if the individual representing the best candidate solution obtained is maintained throughout the search process, the genetic search process converges to the global optimal solution exponentially.

The proposed methodology is applied to design the manufacturing system of a company in China producing component parts for internal combustion engines. The performance of the proposed age-based genetic algorithm is compared with that of the conventional genetic algorithm based on this industrial case. The results show that the methodology proposed in this paper provides a simple, effective and efficient method for solving the manufacturing cell formation and production scheduling problems for VCMSs.     

Multi-agent-based workload control for make-to-order manufacturing

Workload control is a production planning and control concept designed to meet the need of the make-to-order industry. In this paper, a multi-agent workload control methodology that simultaneously addresses due date setting, job release and scheduling is proposed. To be consistent with just-in-time production, the objective of minimizing weighted job earliness and tardiness is used. Two new rules are developed, by introducing a feedback mechanism, to set job due dates dynamically. These two new rules implicitly include job pool times and, thus, eliminate the need to estimate job pool times in the presence of workload control. At the critical norm defined in this paper job release control can reduce average job flowtime and work-in-process inventory, without worsening earliness and tardiness, and lead-time performances. The proposed methodology is implemented in a flexible job shop environment. The computational results indicate that the proposed methodology is very effective for production planning and control in make-to-order companies. In addition, the proposed methodology is extremely fast and can be implemented in real time.     

制造质量记录信息管理系统的总体设计与开发

本文首先论述了质量记录在计算机辅助质量管理（ＣＡＱＭＳ）中的作用及地位，随后阐述制造质量记录信息管理系统的总体设计方案，以上工作在计算机集成制造系统（ＣＩＭＳ）应用中将得到体现。     

Dynamic restructuring process for self-reconfiguration in the fractal manufacturing system

To meet the rapidly changing customer needs in the manufacturing environment, future manufacturing systems must be dynamically and flexibly reconfigured. The fractal manufacturing system (FrMS) is one of the new manufacturing paradigms that can meet such requirements. The basic component of the FrMS is referred to as a fractal. Consisting of self-similar agents, each fractal autonomously cooperates and negotiates with others to coordinate its tasks. Dynamic restructuring process (DRP) supports reorganization of the system configurations so that the FrMS can be adapted to dynamically changing environments. Although traditional approaches have endeavoured to demonstrate reconfigurability of a manufacturing system, they are not accurate enough to meet the requirements of circumstances such as high-level autonomy in reconfiguring the system architecture. In this paper, therefore, the DRP, which embodies self-reconfigurability of a system, is proposed focusing on the FrMS. To check the effectiveness of the DRP, we have developed the FrMS test bed and conducted the experimentation on the DRP. A simulation study has been conducted to show the effectiveness of the DRP under an illustrative situation.