Collaborative composition of processes in holonic manufacturing systems

Although it provides a flexible architecture to deal with changes and uncertainties, holonic manufacturing systems (HMS) also pose challenges in design and implementation. A challenge is to design a problem solving environment to guide the holons in HMS such that the decisions made by the individual holons as a whole collaboratively compose the production processes for the tasks. The objective of this paper is to propose a problem solving environment for the composition of minimal cost processes in HMS. Given a specific product type and due date, the problem is to dynamically compose a complete process in HMS to process the product by the due date. To achieve the objective, we combine multi-agent systems technology with Petri nets in this paper. We first propose architecture and a two-layer contract net protocol to describe the negotiation between order holons, product holons and resource holons in HMS. To determine whether it is feasible for a set product holons and resource holons to compose a process for an order holon, we propose Petri net models to capture the workflows and activities in product holons and resource holons, respectively. To optimize the cost in the composed manufacturing process, the concept of activity-based costing is adopted to assign the cost of the activities to Petri nets. The advantages of our design methodology include specification of workflows and resource activities with PNML to minimize the cost. To realize the two-layer contract net protocol relies on a mechanism for a holon to discover the services provided by other holons. We proposed a scheme for publication and discovery of holon services based on FIPA compliant multi-agent system platform. Based on the service publication and discovery scheme, interactions between holons with the two-layer contract net protocol can be realized. We develop a HMS system to solve the process composition problem.     

Collaborative reconfiguration mechanism for holonic manufacturing systems

Although holonic manufacturing systems (HMS) are recognized as a paradigm to cope with the changes in manufacturing environment based on a flexible architecture, development of reconfiguration mechanism is required to realize the advantages of HMS. Finding a solution from scratch to deal with changes in HMS is not an appropriate approach as it may lead to chaos at the shop floor. The objective of this paper is to propose a viable design methodology to achieve effective reconfiguration in HMS based on the cooperation of holons. We formulate and study a holarchy reconfiguration problem and define an impact function to characterize the impact of resource failures on different holons in a holarchy. A collaborative reconfiguration algorithm based on the impact function is proposed to effectively reconfigure the systems to achieve minimal cost solutions.     

Holonic coordination obtained by joining the contract net protocol with constraint satisfaction

Present manufacturing systems are facing significant challenges concerning their adaptability. Holonic manufacturing systems are among the technologies that can provide solutions to such requests, if certain conditions are met. As being included in the class of semi-heterarchical control architectures, holonic systems need appropriate coordination and planning schemes, together with validation tools to increase the beneficiaries’ trust. This paper proposes a coordination scheme for holonic systems, based on a mix between contract net protocol and distributed constraint satisfaction problems. The distinct phases of this method are explained, with details referring to the adaptation of contract net protocol. About the constraint satisfaction mechanism, a guide is provided on how a manufacturing problem can be expressed according to this formalism. To validate the introduced coordination scheme, a coloured Petri net model was developed. This allowed several simulation experiments for scenarios regarding a manufacturing system with four robots to be carried out. The obtained solutions showed that the proposed method can determine both the right holarchy related to the manufacturing goal, and optimal plans for robots. Moreover, as proven by the reachability graphs obtained for different goals, the proposed method reached correct results for all goals and diverse constraints, and it determined all possible solutions. An advantage is about how knowledge possessed by different types of holons is efficiently used, without producing an increased communication load. In conclusion, our method can ensure the right trade-off between complexity and optimality, and the attached model can constitute the required link between design and implementation, thus contributing to an easier deployment of holonic systems.     

Analysis of contract net in multi-agent systems

Application of contract net protocol requires the development of a bid evaluation procedure specific to the problem. Care must be taken to apply contract net protocol to tasks that involve precedence constraints among different operations and heterogeneous resources. The lack of a process model in the original contract net protocol makes it difficult to determine the feasibility of the resulting contracts. We propose a model to facilitate the development of the bid evaluation procedure by extending our previous results to handle tasks with more complex process structure. We formulate an optimization problem to find a minimal cost feasible execution sequence for a task.     

Model and control holonic manufacturing systems based on fusion of contract nets and Petri nets

Holonic manufacturing systems (HMS) can be modeled as multi-agent systems to which contract net protocol can be effectively and robustly applied. However, the lack of analysis capability of contract nets makes it difficult to avoid undesirable states such as deadlocks in HMS. This paper presents a framework to model and control HMS based on fusion of Petri net and multi-agent system theory. The main results include: (1) a multi-agent model and a collaboration process to form commitment graphs in HMS based on contract net protocol, (2) a procedure to convert commitment graph to collaborative Petri net (CPN), and (3) feasible conditions and collaborative algorithms to award contracts in HMS based on CPNs.     

Dynamic composition of holonic processes to satisfy timing constraints with minimal costs

The flexible architecture provided by holonic manufacturing systems (HMS) poses challenges in planning and control of production processes. The challenges are due, in part, to the loosely coupled structure of holons and also to the complex interactions among holons. Development of new methodologies is required to optimize the holonic processes in HMS to achieve the objectives. In this paper, we concentrate on the development of method for the composition of holonic processes. We consider the holonic processes composition (HPC) problem to synthesize processes with minimal costs while meeting the timing constraints in HMS. We formulate this problem based on a hybrid model in which contract net protocol is adopted as the negotiation protocol and timed Petri net is used to analyze the timing and resource constraints. To specify the costs of operations, we augment the timed Petri net with a cost function. We formulate an optimization problem to minimize the cost while meeting the timing constraints based on the Petri net models. A solution to HPC can be represented by a collaborative Petri net. Our methodologies include a condition to check whether the timing constraints can be met, a condition for the existence of an optimal solution to the HPC problem and a multi-layer contract net protocol to find the minimal cost solution.     

A Petri net-based methodology to increase flexibility in service-oriented holonic manufacturing systems

Distributed control systems such as the holonic manufacturing systems and service-oriented architectures have demonstrated to provide higher levels of flexibility, notably in the planning and scheduling functionalities, if well exploited. In scheduling, the use of fixed process plans generated by traditional planning approaches, usually leads to unrealistic schedules due to the lack of considerations of the workshop status. IPPS approaches try to break the gap between these two functionalities in favor of providing flexible plans adapting to the shop floor's state. A key element in the creation of flexible process plans is the definition of a process model capable of representing alternatives solutions to the sequencing problem and therefore increasing the potential solution space. This paper presents a methodology to increase planning flexibility in service-oriented manufacturing systems (SOHMS). The methodology introduces a Petri net service-oriented process model (SOP model) capable of computing a product's deadlock free sequential space and adapts to the fractal character of holonic architectures. A set of modeling rules, with illustrations, is presented for the automatic generation of the Petri net, based on a set of precedence conditions. To explore the solution space represented by the SOP model a holonic interaction protocol is presented. Moreover, a set of behavioral strategies is proposed in order to cope with the effects of a possible combinatorial explosion. A study case applied workshop example is presented to illustrate the modeling process of SOP models, compute the sequential solution space and demonstrate how this notably increases the number of potentially goods feasible solutions.     

Dynamic schedule execution in an agent based holonic manufacturing system

The present paper deals with the negotiation based task allocation to the resources for preparing dynamic scheduling in an agent based holonic control framework. The scheduling priority is developed by Multi Objective Optimization on the basis of Ratio Analysis (MOORA) technique under Fuzzy Multi Criteria Decision Making (FMCDM) environment considering several attributes. The well-known Contract Net Protocol (CNP) is followed for the purpose of task allocation by negotiation and cooperation, where message based communication is accomplished by eXtensible markup language (XML) using J2EE. Different Document Type Definitions (DTDs) are developed for intended applications. Necessary modifications in the scheduling arising out of changes in the volume-mix are made by a distributed cooperative problem-solving algorithm to meet the demand without violating the deadline. The algorithm is implemented using HTML code in front-end with Java Server Page (JSP) through Apache Tomcat 6.02 server. It is advocated that the cooperation based teamwork coupled with higher flexibility and agility is the key to success to remain unperturbed and provide reasonably good solution in the face of disturbances and stands superior to its hierarchical counterpart.     

Process vs resource‐oriented Petri net modeling of automated manufacturing systems

Since the 1980s, Petri nets (PN) have been widely used to model automated manufacturing systems (AMS) for analysis, performance evaluation, simulation, and control. They are mostly based on process‐oriented modeling methods and thus termed as process‐oriented PN (POPN) in this paper. The recent study of deadlock avoidance problems in AMS led to another type of PN called resource‐oriented PN (ROPN). This paper, for the first time, compares these two modeling methods and resultant models in terms of modeling power, model complexity for analysis and control, and some critical properties. POPN models the part production processes straightforwardly, while ROPN is more compact and effective for deadlock resolution. The relations between these two models are investigated. Several examples are used to illustrate them. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

A holonic approach to dynamic manufacturing scheduling

Manufacturing scheduling is a complex combinatorial problem, particularly in distributed and dynamic environments. This paper presents a holonic approach to manufacturing scheduling, where the scheduling functions are distributed by several entities, combining their calculation power and local optimization capability. In this scheduling and control approach, the objective is to achieve fast and dynamic re-scheduling using a scheduling mechanism that evolves dynamically to combine centralized and distributed strategies, improving its responsiveness to emergence, instead of the complex and optimized scheduling algorithms found in traditional approaches.     

Development of holonic manufacturing execution systems

Rapid changes of market demands and pressures of competition require manufacturers to maintain highly flexible manufacturing systems to cope with a complex manufacturing environment. To meet these requirements, this work adopts the concepts of holon and holarchy to design manufacturing systems. Holon and holarchy are derived from the studies of social organizations and living organisms and possess the properties of intelligence, autonomy, cooperation, reconfigurability, and extensibility. Moreover, advanced manufacturing systems also require the properties of security certification and failure recovery. Based on the requirements of these properties, a systematic approach is proposed to develop a holonic manufacturing execution system (HMES) for the semiconductor industry. This systematic approach starts with a system analysis by collecting domain requirements and analyzing domain knowledge. The HMES Holarchy is designed by the procedure of constructing an abstract object model based on domain knowledge, partitioning application domain into functional holons, identifying generic parts among functional holons, developing the Generic Holon, defining holarchy messages and the holarchy framework of HMES, and finally designing functional holons based on the Generic Holon. It is believed that this proposed systematic approach provides a novel and efficient way to design HMES.     

基于扩展合同网协议的无线传感器网络协作方法研究

提出一种适用于无线传感器网络协作的扩展合同网协议.该协议在传统合同网协议中引入了信任度、阈值和优先级等策略,减少了无线传感器网络的通信开销,有效均衡了节点的能量消耗.为确保扩展合同网协议的完整性、正确性和可靠性.利用面向对象Petri网对其进行建模、分析和验证.仿真结果表明,扩展合同网协议有效地延长了网络生命周期,提高了网络的能耗效率,网络完成任务数也有了显著的增加.     

A two phase optimization method for Petri net models of manufacturing systems

Optimization is a key issue in the design of large manufacturing systems. An adequate modeling formalism to express the intricate interleaving of competition and cooperation relationships is needed first. Moreover, robust and efficient optimization techniques are necessary. This paper presents an integrated tool for the automated optimization of DEDS, with application to manufacturing systems. After a very quick overview of optimization problems in manufacturing systems, it presents the integration of two existing tools for the modeling and evaluation with Petri nets and a general-purpose optimization package based on simulated annealing. The consideration of a cache and a two phase technique for optimization allows to speed-up the optimization by a factor of about 35. During the first preoptimization phase, a rough approximation of the optimal parameter set is computed based on performance bounds. Two application examples show the benefits of the proposed technique.     

Agent-based distributed manufacturing control: A state-of-the-art survey

Manufacturing has faced significant changes during the last years, namely the move from a local economy towards a global and competitive economy, with markets demanding for highly customized products of high quality at lower costs, and with short life cycles. In this environment, manufacturing enterprises, to remain competitive, must respond closely to customer demands by improving their flexibility and agility, while maintaining their productivity and quality. Dynamic response to emergence is becoming a key issue in manufacturing field because traditional manufacturing control systems are built upon rigid control architectures, which cannot respond efficiently and effectively to dynamic change. In these circumstances, the current challenge is to develop manufacturing control systems that exhibit intelligence, robustness and adaptation to the environment changes and disturbances. The introduction of multi-agent systems and holonic manufacturing systems paradigms addresses these requirements, bringing the advantages of modularity, decentralization, autonomy, scalability and re-usability. This paper surveys the literature in manufacturing control systems using distributed artificial intelligence techniques, namely multi-agent systems and holonic manufacturing systems principles. The paper also discusses the reasons for the weak adoption of these approaches by industry and points out the challenges and research opportunities for the future.     

Petri net based process scheduling: A model of the control system of flexible manufacturing systems

In this paper, we propose a class of algorithms for the sub-optimal solution of a particular class of problems of process scheduling, particularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, each formed by a number of temporally related tasks (segments). Tasks are executable by alternate resource sets, different both in performance and costs. Processes and tasks are characterized by release times, due dates, and deadlines. Time constraints are also present in the availability of each resource in resource sets. It has been proven that such a problem does not admit an algorithm for an optimal solution in polynomial time. Our proposed algorithm finds a sub-optimal schedule according to a set of optimization criteria, based on task and process times (earliness, tardiness), and/or time independent costs of resources. Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling algorithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) theautomatic synthesis of Petri net models of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose kernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-optimal multi-criteria algorithms. Furthermore, the paper defines the interaction mechanisms between the coordination and scheduling subsystems. Our approach clearly distinguishes the mechanism of the net execution from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: theexecutor and thescheduler levels. One of the outstanding differences between these levels is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distributed component, whose behavior may heavily depend on the problem class. If the scheduler fails, the executor is, in any case, able to proceed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.     

基于改进的网重写系统途径的可重构制造单元故障恢复

提出了一种用于可重构制造单元故障恢复的策略与方法, 允许故障发生时, 通过对用于正常操作控制的Petri网形式的监督控制器进行局部、临时性的修改, 实现故障的恢复. 首先, 提出改进的网重写系统, 可用于动态改变Petri网模型结构. 然后,提出了基于改进的网重写系统的故障恢复方法, 其中改进的网重写系统用于操作、引导Petri网监督控制器由错误状态进入正确状态. 故障恢复后监督控制器的结构与期望属性维持不变. 最后, 以实例演示了该故障恢复方法的应用, 证实了方法的有效性.     

基于变迁覆盖的制造系统死锁控制策略

基于系统Petri网模型,研究柔性制造系统的死锁控制问题.论文利用变迁覆盖为系统设计活性控制器.变迁覆盖是由一组极大完备资源变迁回路组成的集合,其变迁集覆盖了Petri网中所有极大完备资源变迁回路的变迁集.验证变迁覆盖的有效性,然后仅对有效变迁覆盖中的极大完备资源变迁回路添加控制位置,就得到系统的活性受控Petri网.这种受控Petri网包含的控制位置个数少,从而结构相对简单.最后通过一个例子说明了所提出的死锁控制策略的构成与特点.     

H2CM: A holonic architecture for flexible hybrid control systems

Several studies typically arise from the interaction of discrete planning algorithms or control and continuous processes, normally called hybrid control systems. It consists in three distinct levels, the controller, the plant and the interface. Hybrid control systems are conventionally modeled by switching patterns using the whole system instead of atomic resource. Therefore, the reconfiguration process is complex because it must take into account the system as a whole, making the hybrid control systems inflexible and more susceptible to uncertainties. The need for flexibility thus leads several teams to investigate the application of holonic paradigm to hybrid control systems. The objective of this paper is to demonstrate the possibility to apply almost directly a holonic discrete-event based reference architecture to hybrid control systems. A case study of industrial electricity generation process was taken, specifically a combined cycle plant (CCP) for verifying the proper operation of the proposed architecture.     

Robust design of flexible manufacturing systems using, colored Petri net and genetic algorithm

A method is presented for the robust design of flexible manufacturing systems (FMS) that undergo the forecasted product plan variations. The resource allocation and the operation schedule of a FMS are modeled as a colored Petri net and an associated transition firing sequence. The robust design of the colored Petri net model is formulated as a multi-objective optimization problem that simultaneously minimizes the production costs under multiple production plans (batch sizes for all jobs), and the reconfiguration cost due to production plan changes. A genetic algorithm, coupled with the shortest imminent operation time (SIO) dispatching rule, is used to simultaneously find the near-optimal resource allocation and the event-driven schedule of a colored Petri net. The resulting Petri net is then compared with the Petri nets optimized for a particular production plan in order to address the effectiveness of the robustness optimization. The simulation results suggest that the proposed robustness optimization scheme should be considered when the products are moderately different in their job specifications so that optimizing for a particular production plan creates inevitably bottlenecks in product flow and/or deadlock under other production plans.     

可重构制造系统的Petri网建模和分析方法

提出一种针对可重构制造系统的Petri网建模和分析方法．根据生产流程图可以得出制造系统的基本网模型,扩展基本网模型即可得到系统的Petri网模型．当生产任务发生改变并建立新的生产流程图时,可直接从原来的基本网模型构造出新构形的基本网模型．此外给出了系统重构代价的评价方法．仿真研究验证了该方法的有效性。