Jorge E Hernández

Raúl Poler
email: rpoler@cigip.upv.es

Josefa Mula
email: fmula@cigip.upv.es

David De

La Fuente

Collaborative tactical planning in multi-level supply chains supported by multiagent systems

Keywords: Collaborative planning, supply chain management, negotiation, multiagent systems

In the supply chain modeling context, the agent-based model aims to represent not only each node, but also the information sharing process among these nodes. Despite the complexity of the configuration, the agent-based model can be applied straightforwardly to support the collaborative planning process. This allows the parties to achieve common goals effectively. Thus by sharing accurate, action-based information, collaboration among the nodes will emerge to improve the decision-making process in supply chain planning processes. Therefore, this paper presents a novel collaborative planning model in multilevel supply chains that considers a multiagent system modeling approach to carry out the iterative negotiation processes which will support the decisionmaking process from a decentralized perspective.

Introduction

The decisions linked to the supply chain management process can affect three decisional levels: strategic, tactical and operational. The first relates with long-term decisions, which include design processes. The second implies decisions at the midterm level, which will influence planning activities at the operational level. Finally, the third mainly involves the execution of planned activities, where a decision has to be made from a short-term perspective. Thus, high uncertainty in the planning horizon will have a significant effect at this level because, in most cases, there is not enough reaction time to meet the new requirement. Thus, the system will need to consider high inventory levels to cover this uncertainty, which will imply and increase cost rates. This impact may be stronger if the system is composed of a multi-level supply chain where suppliers, warehouses, 3PL, retailers, etc., are directly affected by strategic and tactical decisions. Hence, a system should be studied from three viewpoints in relation to its products, information and decision flows [START_REF] Mula | A reference model for conceptual modeling of production planning processes[END_REF]. Therefore, the on-time and right decisions in the tactical planning process might avoid, and also optimize, these unnecessary levels and rates. Furthermore, [START_REF] Ouhimmou | Furniture supply chain tactical planning optimization using a time decomposition approach[END_REF] established that tactical planning covers those planning decisions in which short-term decisions are defined, such as synchronized planning policies for procurement, production, distribution and sales. In a supply chain context, it is possible to state that the planning process takes into account the coordination and integration of the key business activities which are normally undertaken by enterprises, ranging from the procurement of raw materials to the distribution of final products to end customers [START_REF] Gupta | Managing demand uncertainty in supply chain planning[END_REF]. In addition, lead times are one of the important factors to be considered in the supply chain planning process, as suggested by [START_REF] Chaharsooghi | LT variance or LT mean reduction in supply chain management: Which one has a higher impact on SC performance[END_REF]. Thus, it is important to consider lead times at the tactical level because lead times vary in terms of environmental uncertainties, which is precisely one of the serious factors that challenge suppliers and buyers in a supply chain when it comes to defining the mean and variance. In this context, supply chain management offers new opportunities for conducting operations strategy research [START_REF] Zhao | Developments and emerging research opportunities in operations strategy and supply chain management[END_REF]. Nevertheless, supply chain management at the information system level is becoming a high core competency, and enterprise resource planning systems are expected to become an integral component of supply chain management. Moreover, installing such systems is expensive and risky, and managers must decide how to use their limited resources and how to invest in the right products [START_REF] Su | Why are enterprise resource planning systems indispensable to supply chain management?[END_REF].

Therefore, this paper is set out as follows: Section 2 briefly reviews the relevant literature on collaborative planning and multi-agent systems in a supply chain management context. Section 3 establishes the formal formulation for the novel collaborative planning proposal in multi-level supply chains. Section 4 provides a brief example of the proposal application. Finally, Section 5 offers the main conclusions drawn and also briefly describes our future work.

Background

Despite the complexity of these systems, there are significant benefits at the collaborative level from a supply chain perspective, where the information exchanging process occupies a relevant place in supporting the planning processes among the nodes. Hence, as defined by [START_REF] Mula | A reference model for conceptual modeling of production planning processes[END_REF], collaborative activities also imply a distributed decision-making process which involves several supply chain nodes. So in relation to the collaboration that may exist among these supply chain nodes, planning will consider the answers that customers send to the manufacturer which, in turn, will be sent to suppliers; thus, messages will flow effectively. The planning process is then supported by considering more effective answers in relation to demand/orders, and the agreement processes may also be supported by considering the corresponding negotiation processes [START_REF] Alemany | SCAMM-CPA: A Supply Chain Agent-Based Modelling Methodology That Supports a Collaborative Planning Process[END_REF].

In addition, this collaborative process can be seen from two perspectives: centralized and decentralized. From the centralized perspective, a virtual node controls the supply chain information process to support the planning processes. An example of this is highlighted in [START_REF] Ortiz | V-Chain: Migrating From Extended To Virtual Enterprise Within An Automotive Supply Chain[END_REF]. Then, from the centralized viewpoint, however, collaborative planning (among supply chain partners) can be achieved by simple coordinated upstream planning by providing the collaboration partners an opportunity to modify the suggested order/supply patterns iteratively [START_REF] Dudek | Negotiation-based collaborative planning between supply chains partners[END_REF]. Meanwhile from a decentralized collaboration viewpoint, each node will consider its collaborative and non collaborative partners (customers and suppliers) to carry out its planning processes [START_REF] Poler | Collaborative forecasting in networked manufacturing enterprises[END_REF]. This last perspective leads to a more realistic current supply chain process. In addition, examples of this decentralized perspective relating to logistic supply chain planning, supply chain coordination, a collaborative supply chain decision-making model and a supply chain coordination under demand uncertainty, can be found in [START_REF] Jung | Decentralized supply chain planning framework for third party logistics partnership[END_REF], [START_REF] Gaudreault | Distributed search for supply chain coordination[END_REF], [START_REF] Poler | The reverse logistic process of an automobile supply chain network supported by a collaborative decision-making model[END_REF] and [START_REF] Xiao | Coordination of a supply chain with consumer return under demand uncertainty[END_REF], respectively.

Consequently, and as mentioned earlier, information technology systems must be set up irrespectively of the collaborative approach that the supply chain possibly considers to support such aspects as the information flow among the nodes in order to support supply chain planning and the communication processes. In the same context, and by considering the robustness presented by the multi-agent system, [START_REF] Nahm | A hybrid multi-agent system architecture for enterprise integration using computer networks[END_REF] proposed a novel architecture to support the inter-enterprise functions/resources integration and collaboration in a networked context. Moreover, [START_REF] Gomez-Gasquet | A Scheduler for extended supply chains based on combinatorial auctions[END_REF] present auctions experiments, supported by multiagent systems, to view the impact at the operative level. To support this, modeling methodologies like MASCOT [START_REF] Sadeh | MASCOT: An Agent-Based Architecture for Coordinated Mixed-Initiative Supply Chain Planning and Scheduling[END_REF] or SCAMM-CPA [START_REF] Alemany | SCAMM-CPA: A Supply Chain Agent-Based Modelling Methodology That Supports a Collaborative Planning Process[END_REF] can be considered where a full literature review has been contemplated. Thus, the aim of multiagent proposals is to support the development of a system with a collaborative purpose by exchanging information without sharing a common system, but one that also considers the related ontology's with a view to supporting the communication process, hence leading to collaborative behavior. Therefore, this technology has been considered to support the following proposal.

The collaborative tactical planning formulation in multi-level supply chains

The proposed planning process is about to consider the right and on-time information to support the decision-making process. Thus, the decision-making process is supported by a manufacturing requirement planning (MRP) system which, like the main information for all the n periods, considers inputs such as demand (D), inventory level (IL), the sell price (SP) and capacity (CAP). On the other hand, the main MRP outputs are the following: planned orders (PO), Delay on Demand (DoD), Profit and SP. Then, each node considers its own MRP mechanism (M).

The collaborative perspective of this proposal, as seen in Fig. 1, establishes communication at the multi-level area of the supply chain by considering the customer node's PO, which will be contemplated as D in the directly relating tier suppliers, as will the PO relating with the CAP information that the customer owns. So the main idea is support a negotiation process by incrementing the SP with an increased P factor. In fact, if no agreement is reached among the nodes, the proposal will be improved by raising the SP.

Hence from the decentralized and collaborative perspectives, each node in the multi-level decision-making process considers its own database (or information repository) to link the communication process. This kind of communication is considered decentralized and collaborative because. In addition, Fig. 2 shows how the information system structure is composed of five main tables. These tables aim to collect the inputs and outputs generated by the MRP mechanism. In this case, the Releases table is about demand information. The Master_I table includes the information related to holding costs (HC), unitary costs UC, delay on demand costs (DoDC) and the sell price (SP). The OUT_MRP table collects information relating to the final level of the IL, P and DoD. This table holds information that will support the decision-making process of the planning process.

MRP systems also consider that information relating to ShopFloor activities, which mainly relate to CAP, ETC and ITC. Then, each answer the system generates will be restricted by the information in this table. Thus given the collaborative planning proposal, this information will consider the answer from the tier supplier to evaluate the planning proposal's level of profit. Then along with the OUT_MRPII table, the supply chain will be able to evaluate its decision by considering the right and on-time information in an iterative decentralized negotiation process.

Finally, the profit level (8) will lead not only to the negotiation process, but also to the decisions relating to the planning process in each n period of the planning horizon. The calculus of this profit consider the following information for each period: inventory costs at each period (1), production costs (2), delay on demands costs (3), extra time costs (4), costs of the idle time of resources (5) and sell revenues (6 and 7). Thus by considering the answers from suppliers, the customer node will evaluate renegotiation by taking the new profit value which is directly affected by the raised product's sell price. The negotiation process will finish when new price changes no longer have an impact on the profit level or when no DoDc for the suppliers exist. Hence, an example of the application of this novel proposal to a multi-level supply chain is briefly provided in the following section.

A multiagent-based system to support collaborative tactical planning in multi-level supply chains

The collaborative planning model (Fig. 3) for supply chain networks which considers a multiagent system modeling approach is supported by MPL/CPLEX, JADE 3.6 and ECLIPSE. The communication process among agents is supported by behaviors that aim to generate demands and firm orders, and to also send and receive the corresponding messages, by considering the FIPA standard communication protocols, which are mainly supported by the Contract-Net protocol. The system has been tested in a real concurrent environment, thus each agent considers its own thread. As Fig. 3 illustrates, each node considers its own planning mechanism, as well as its own database (DB) repository. In addition, each agent is independently governed by its own behaviors, including its wishes and beliefs. Next, the multi-level supply chain is composed of the customer agent (CA), the first-tier supplier agent (FTSA1) and two second-tier supplier's agents (STSA1 and STSA2). Then, each node will validate its proposals by obtaining the related values at the profit level. Then, the negotiation process supported by the profit algorithm calculus [START_REF] Poler | The reverse logistic process of an automobile supply chain network supported by a collaborative decision-making model[END_REF] is presented in its technical JAVA-SQL approach (see Fig. 4). Fig. 5 presents the communication process which considers the main planning decision relating to the negotiation process (supported by the profit level). Therefore from a decentralized perspective, the system implementation, as Fig. 5 highlights, considers that each agent in the collaborative planning supported by the multi-agent system is in its own machine; that is, in its own container. Thus, each thread is composed of sub-threads that are supported by the relating FIPA contract-net protocols. Every agent belonging to the highest level will wait for the negotiated answers from the lower levels, and each node will evaluate its profit evolution.

Conclusions

A novel multiagent-based collaborative planning model for multi-level supply chains has been proposed. The modeling basis is supported by the fact that each node considers its own information repository from a decentralized viewpoint, hence its own databases. In addition, the MRP mechanism supports the decision-making processes. The main idea is that these mechanisms will consider some inputs from the lower levels of the supply chain (suppliers) to, in turn, consider their answers about their profit calculus. Hence, the negotiation process will be composed of both the inputs and outputs relating to the decision, and the answers from all the supply chain levels; and all this from a decentralized perspective. In addition, a prototype has been developed that offers a good possibility of establishing the multi-agent system.

In future research, the proposed model will be applied to a real supply chain network in the automobile supply chain sector with a view to implementing the mobility agent by scaling the platform prototype and by considering real demand data. Furthermore, this novel proposal will also be compared with other negotiation mechanisms to test its suitability.

Fig. 1 .

 1 Fig. 1. Collaborative planning mechanism.

Fig. 2 .

 2 Fig. 2. Structure of the database supporting decentralized collaborative planning.

Fig. 3 .

 3 Fig. 3. A Multi-Tier Supply Chain example.

Fig. 4 .

 4 Fig. 4. JAVA -Extract of the SQL profit calculus code.

Fig. 5 .

 5 Fig. 5. Sniffer agent. Validation of the collaborative planning process.

Acknowledgments. This research has been supported by the EVOLUTION project (Ref. DPI2007-65501) which is funded by the Spanish Ministry of Science and Education, www.cigip.upv.es/evolution.


Rubén Fuentes-Fernández

José M Galán
email: jmgalan@ubu.es

Samer Hassan

Juan Pavón
email: jpavon@fdi.ucm.es

Felix A Villafañez
email: villafafelix@eis.uva.es

Metamodelling for Agent Based Modelling: An Application for Continuous Double Auctions

Agent-Based Modelling is gaining wider acceptance as a paradigm for social research. However, it still present limitations in the management of the process to generate the simulations from the initial conceptual models. Thus, it is difficult to reuse the knowledge from available models and adapt it to different hypotheses. This paper proposes the use of metamodels in order to define explicitly the core concepts of a problem and to differentiate the aspects involved in the process. A case study for continuous double auctions shows how to define the related metamodel and use it to address alternative situations in these auctions. The case study drives the discussion on the advantages and limitations that metamodelling can bring to social simulation.

Introduction

Agent-Based Modelling (ABM) has become over the past years a widely used technique for research in Social Sciences [START_REF] Gilbert | Simulation for the social scientist[END_REF]. One of its key advantages lies on its core abstractions for modelling, i.e. agents and their societies. Agents are intentional and social entities, which are capable of rational and complex individual behaviour. As they share these features with humans, they are expected to facilitate the specification of the human target systems. Besides, these abstractions can be refined with concepts closer to the target simulation platforms, bridging the gap between the conceptual models and the simulation ones.

The actual use of agent-based models still has a lot of room for improvement [START_REF] Edmonds | The Use of Models -Making MABS More Informative[END_REF]. The situation in which agents constitute general and reusable modelling primitives for ABM, with standardise processes to translate them to simulation models has not been reached. In fact, researchers in ABM have different perspectives on what agents are. Moreover, they do not tend to follow a clear translation of those perspectives in their formal agent models, frequently adopting ad-hoc translations of them in the simulation code.

In order to address these limitations, some researchers [START_REF] Hassan | Mentat: A Data-Driven Agent-Based Simulation of Social Values Evolution[END_REF][START_REF] Sansores | Agent-Based Simulation Replication: A Model Driven Architecture Approach[END_REF] have proposed the use of metamodelling techniques. Metamodels define modelling languages, which describe the modelling primitives available to describe a problem. Researchers create their models instantiating these primitives. If required, they can use extension mechanisms to modify the language in a controlled way, introducing new elements.

This approach has several advantages. Firstly, metamodels can be processed by software tools. This allows, for instance, the building of graphical editors for these models, and to provide automated transformations that partly carry out the propagation of information from abstract formal models to actual simulations. This tool support reduces the probability of making unintended mistakes when modelling and provides the basis for comparison (and thus replication) among works.

The main obstacle to apply this approach is to define suitable metamodels. There is an inherent difficulty in capturing the knowledge to describe complete domains of problems with a formal definition. A metamodel must be rich enough to capture all the variability of a domain, but also to constrain modellers to produce correct models that can be translated to simulation code in a semi-automated way.

Our work attempts to provide guidelines, intermediate languages for metamodelling in ABM and software tools that facilitate the definition of these metamodels. In order to illustrate this approach, this paper discusses the formalisation of the well-known problem of continuous double auctions.

The rest of the paper is organised as follows. Section 2 provides a brief introduction on ABM. Section 3 considers how our approach use metamodels in ABM and Section 4 applies such approach to model auctions. Finally, Section 5 discusses the implications of the process together with some concluding remarks.

Related Work

ABM describes models for social analysis using agents as the key abstraction. The complete process entails different stages of designing, implementing and using agentbased models. Initial steps usually begin with non-formal conceptualizations of the target system that successively are refined to shape a formal model that can be computationally implemented. This process is often got around in literature and only few works explore the migration from conceptualisations to formal models.

[12] considers the problems emerging from the usual lack of background in software programming of social researchers and the difficulties to compare similar models implemented over different platforms. They propose adapting the modeldriven engineering methodology INGENIAS [START_REF] Pavón | The INGENIAS Methodology and Tools[END_REF], which focuses on the development of Multi-Agent Systems (MAS). Their approach extends the INGENIAS modelling language with additional primitives for specific problems. It also uses the INGENIAS process to generate the simulation source code. The main limitation of this work is its use of predefined extension mechanisms of the INGENIAS language, with concepts with an inherent software bias, which are not very appropriate for social researchers.

[7] defines a MDE approach for ABM. Its language has as core concept the Mentat, an agent skeleton with mental properties that researchers can extend for their models. The main issue of this work is that it is constrained to data-driven simulation, which complicates its application for other kind of problems.

Looking to overcome these limitations, our approach tries to achieve a MDE approach for ABM with two main features: it must be adaptable to different agentoriented approaches and support alternative uses of models and their reuse.

INGENIAS Metamodels for ABM

INGENIAS [START_REF] Pavón | The INGENIAS Methodology and Tools[END_REF] is a software development methodology for MAS. It adopts a MDE approach with two basic components: a modelling language and software tools.

A metamodel specifies the INGENIAS modelling language. It defines the available concepts and relationships, together with their properties and constraints. As it is aimed for modelling MAS, it includes the concepts of agent and group. An agent is characterised in terms of its goals and the capabilities it has to accomplish them. Groups include agents and external resources, coined environment applications, that agents can use. Agents participate in interactions with other agents to achieve global goals. Models can also include code components to specify low-level details that depend on the platform, such as formulas about preference policies or location algorithms.

The INGENIAS Development Kit (IDK) software tool allows processing models with their modules. Standard modules available with the distribution support model auto-completion for certain tasks, documentation and code generation. Both of them require the availability of templates. A template gives a general description of a primitive available for modelling with slots that are instantiated with information of specific elements in models. For instance, researchers building a simulation for the MASON platform [START_REF] Luke | MASON: A Multiagent Simulation Environment[END_REF] specify a general template for a MASON agent; when generating code, the IDK instantiates that template with the information of every agent in the specification, generating the source code for those specific agents. The IDK allows the development of new modules that access and change its models, so automated transformations can be adapted to the researcher needs.

The approach of this work uses these elements to provide domain-specific modelling languages and tools, with guidelines for their use [START_REF] Hassan | Reducing the Modeling Gap: On the use of metamodels in agent-based simulation[END_REF]. It modifies the INGENIAS metamodel in order to include more flexible extension mechanisms. In particular, inheritance relationships are allowed for any concept, so it can be tailored with additional properties and constraints in common models, without changes in the metamodel. Inheritance implies that a concept acquires all the features of its superconcept. Moreover, it adopts a more declarative approach concerning the tool. It specifies transformations with transformation languages instead of code, which provides a definition closer to the artefacts (i.e. metamodels, models, grammars, code...) that these transformations manipulate. Besides, it proposes developing model transformations (i.e. those that only involve models) with a Model Transformation by Example (MTBE) approach. MTBE [START_REF] García-Magariño | A Tool for Generating Model Transformations By-Example in Multi-Agent Systems[END_REF] defines transformations through prototype pairs of source and target models compliant with certain metamodels. A MTBE tool processes these pairs and automatically generates the resulting transformation. The final component of the approach is a process to guide researchers in the application of this framework [START_REF] Hassan | Reducing the Modeling Gap: On the use of metamodels in agent-based simulation[END_REF]. The case study chosen here illustrates this to show the advantages and current limitations of the work.

These decisions are expected to increase the autonomy of social researchers. The final goal is that they mostly develop their models autonomously, requiring only the support of engineers to address new and not-considered features of the domain.

Case Study: Continuous Double Auction

Case Study: Continuous Double Auction

In order to illustrate the exposed approach, this paper considers an auction as paradigmatic case in Economics, in particular the Continuous Double Auction (CDA). As CDA is one of the institutions used more often for real trading, it has been thoroughly analyzed from the experimental and computational point of view [START_REF] Posada | How to choose the bidding strategy in continuous double auctions: Imitation versus take-the-best heuristics[END_REF]; it is also complex enough to exemplify the capabilities of metamodelling. CDA fixes the Institution in the triplet IEA (Institution x Environment x Agent's behaviour) that defines any market [START_REF] Smith | Microeconomic Systems as an Experimental Science[END_REF]. This study takes into account the other two dimensions from the classical work of Gode and Sunder [START_REF] Gode | Allocative Efficiency of Markets with Zero-Intelligence Traders -Market as a Partial Substitute for Individual Rationality[END_REF][START_REF] Gode | Lower Bounds for Efficiency of Surplus Extraction in Double Auctions[END_REF] where zero-intelligence agents interact in using a single unit per trader. The main features of this CDA are described below.

The CDA considers buyers and sellers. All the sellers are endowed with a unit of a good that is indistinguishable from any other; the buyers want to obtain a unit of this good. The decisions of sellers and buyers depend on certain private values. Each buyer agent is informed of a redemption value v according to a demand function unknown for the other players. The profit obtained by a buyer that buys the good at a price p is v-p. Similarly, each seller agent is endowed with a cost c for the unit of the good. The profit obtain by a seller that sells the good at price p is p-c.

From the point of view of the institution, the auction runs as follows. Any buyer can send a "bid" for a single unit by stating its identity and price. Any buyer can raise this bid. Correspondingly, any seller can "ask" (offer) by stating its identity and price. If asks and bids match or cross, a transaction takes place and both, buyer and seller, leave the market cancelling any unaccepted bids and asks. In the case that a bid and ask do not match but cross, the transaction price is equal to the earlier of the two. After this, the process begins again with the remaining agents. The whole procedure is run several periods of specified duration.

The agents considered in this version [START_REF] Gode | Lower Bounds for Efficiency of Surplus Extraction in Double Auctions[END_REF] are zero-intelligence traders subject to a budget constraint (ZI-C agents). This implies that after a certain amount of time, either a buyer or seller randomly forms a bid or an ask. A seller forms an ask price between its cost and a maximum value (usually the maximum redemption value). A buyer forms a bid price between its redemption value and 0. These constraints suppress the possibility for agents to have losses.

In the game dynamics, each buyer compares its bid with the current state of the market. If its bid is above the best ask, it accepts the best ask and the transaction occurs, while the state of the market is updated. If the buyer's bid is below the best ask and above the best bid or there is not any ask yet, that bid becomes the current best bid; otherwise, in the case that the buyer's bid is below the best bid and according to the auction rules, the agent does not send the bid. The asking process is analogous in the case of sellers.

Metamodelling

The process proposed in [START_REF] Hassan | Reducing the Modeling Gap: On the use of metamodels in agent-based simulation[END_REF] comprehends two main stages: the identification of the core concepts of the domain and the description of their standard interactions. The metamodel for the problem describes these elements as extensions of the primitives available in INGENIAS [START_REF] Pavón | The INGENIAS Methodology and Tools[END_REF].

INGENIAS has two main components that can perform tasks: agents are proactive entities able to initiate tasks following their own and explicit agenda; applications are usually reactive (i.e. used by agents), though they can raise events in case of changes in the environment. Agents that share an application belong to the same group, and when they also share knowledge, procedures and rules, to the same organisation. Fig. 1 illustrates part of the hierarchies of elements proposed for the modelling language of CDA. Following [START_REF] Smith | Microeconomic Systems as an Experimental Science[END_REF], the basis of the hierarchies is the market that determines the institutions, the environments and the agents. Agents in market can play two roles, buyer and seller, which are not exclusive. The auction is a particular type of market. The diagram shows this through the InheritRelationship between these concepts. The auction is characterised for its institution, the auction house. A ruler governs this house and implements the common rules for auctions (e.g. turns between buyers and sellers, transactions, availability of goods, or relationships between bids and asks). The most specific market in this hierarchy is the CDA. Following [START_REF] Gode | Lower Bounds for Efficiency of Surplus Extraction in Double Auctions[END_REF], this auction uses a particular type of agents (i.e. ZI_C agents) to play the two roles in the group agents of the market. The CDA also adds a specific CDA organiser agent to play the ruler role and tailor the institutional behaviour to the norms of CDA.

In this case, there is no need to identify external entities. In order to keep the model simple for this discussion, this metamodel does not explicitly represents the units of goods. These are represented as attributes of the traders. The internal values of these agents (i.e. the redemption and cost value) are also represented as a unique limit value attribute. These attributes appear in Fig. 3 as the components good units and value limit of the internal state of the ZI_C agent.

The next step is refining the agents and roles in Fig. 1. This refinement implies defining their goals and the capabilities they have available in order to achieve them. Roles define the general features of these elements, which agents implement with specific policies. Fig. 2 shows them for the buyer role. It pursues the goal acquire good, which requires stating bids and accepting some of the asks when they are suitable according to its internal demand function. These goals are achieved through two tasks, generate bid and accept ask respectively. Besides specifying the involved goals and tasks, roles need to describe when they initiate the tasks and when the goals are satisfied according to the current system state. Fig. 3 shows an example of these specifications. The trigger condition ask is an instance of the internal state of the ZI_C agent that indicates when the task accept ask can be initiated. The condition states that the agent must be playing the role buyer and there must be a bid. The specific condition involving the bid and the limit value of the agent would be recorded in the acceptable ask. It can be specified, for instance, as formulae or code. The metamodel could include additional primitives to describe this condition, although it is not advisable: there must be a trade-off between the expressiveness of the language and its value to present a synthesised vision of the problem. Adding primitives to the low-level details would make specifications too verbose, losing their abstraction value.

The final element of the specifications is the interactions describing how agents and roles participate in the global activity of the system. Fig. 4 shows an excerpt involving the previous element and also showing the participation of the ruler.

Conclusion and Discussion

This paper has presented the definition of a metamodel that defines a modelling language for CDA. This metamodel illustrates our vision that ABM can benefit from an explicit definition of its modelling languages in several ways: facilitating the specification of problems, their translation to code and the analysis of their results.

Several classical works on CDA have been the basis to identify the key concepts present in this kind of auctions, the attributes that determine their behaviour and their interaction. These elements have been structurally formalised as roles and agents, their goals and capabilities, and groups and organisations. The dynamic behaviour of these elements in auctions has been established through satisfaction relationships between tasks and goals, together with particular conditions, as those used for triggering a task. This metamodel shows the common participants in auctions with the components that researchers need to specify and test different hypotheses. For instance, CDA does not require their agents being zero-intelligence traders; if other traders are going to be tested, researchers may need to add new attributes. Those would participate in conditions or change specific tasks, but the defined roles, interactions and groups would remain unchanged. Besides, the metamodel can define the well-formedness rules for models, allowing the checking of modelling mistakes. For instance, if the model does not include the participation of the buyer proposing bids, it should be revised and corrected.

As stated in sections 1 and 2, the formal models of auctions facilitate applying standardised transformations. Transformations are used to check complex errors, generate documentation, translate them to another modelling language, generate source code, or output result data from models. For instance, a transformation could check that all the traders are going to participate in at least two different auctions if researchers decide so. These transformations are developed and refined over different projects, fixing the potential errors and simplifying the processing.

These advantages are expected to make researchers more autonomous and productive in ABM. These are two necessary conditions to mitigate the main drawbacks of the approach: the high costs of development models and the difficulties to guarantee that the simulation models are a close translation of the original conceptual models.

Fig. 1 .

 1 Fig. 1. Partial metamodel for the structural components of the CDA. Stereotypes (i.e. names between guillemets) denote types of entities and relationships.

Fig. 2 .

 2 Fig. 2. Goals and tasks for the buyer role and their relationships.

Fig. 3 .

 3 Fig. 3. Mental states for the buyer.

Fig. 4 .

 4 Fig. 4. Metamodel for interactions. Roles execute the activities that trigger the communications represented by the arrows.


Juan José Lavios Villahoz

Ricardo Del Olmo Martínez

Alberto Arauzo Arauzo
email: arauzo@insisoc.org

Price-setting Combinatorial Auctions for Coordination and Control of Manufacturing Multiagent Systems: Updating Prices Methods

Keywords: Multiagent Systems, Combinatorial Auction, Lagrangian Relaxation

Combinatorial auctions are used as a distributed coordination mechanism in Multiagent Systems. The use of combinatorial auctions as negotiation and coordination mechanism is especially appropriate in systems with interdependencies and complementarities such as manufacturing scheduling systems. In this work we review some updating price mechanisms for combinatorial auctions based on the Lagrangian Relaxation Method. We focus our research to solve the optimization scheduling problem in the shop floor, taking into account the objectives of resource allocation in dynamic environments, i.e. -robustness, stability, adaptability, and efficiency-.

Introduction

Scheduling is a decision-making problem devoted to allocate resources on tasks to optimize one or several objectives. Manufacturing and production systems are some of the most known fields of application of this problem. In this context, operations of a given production process are considered as tasks and the different machines in a workshop are considered the resources [START_REF] Pinedo | Scheduling 2º ed[END_REF]. This problem is characterized by its highly combinatorial and dynamic nature and its practical interest for industrial applications [START_REF] Shen | Distributed manufacturing scheduling using intelligent agents[END_REF].

Multiagent Systems (MAS) have been proved to be an appropriate paradigm to model complex systems and they constitute a useful framework to define distributed decision-making processes. In this specific domain, agents are used to encapsulate physical and logical entities or even autonomous functionalities of the production systems. The ability of MAS to perceive and react to changes in their environment justifies their use as adaptive systems in manufacturing (some recent reviews in the field can be found in [START_REF] Shen | Applications of agent-based systems in intelligent manufacturing: An updated review[END_REF], [START_REF] Lee | Multi-agent systems applications in manufacturing systems and supply chain management: a review paper[END_REF] or [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF].

Market Based Coordination Mechanisms and Combinatorial auctions

Distributed decision making through MAS are considered an alternative to centralized scheduling systems. They facilitate to take into account local objectives, preferences and constraints of each resource in the decision making process [START_REF] Kutanoglu | On combinatorial auction and Lagrangean relaxation for distributed resource scheduling[END_REF]. Combination of individual problem-solving and coordination/negotiation schemes is one of the research challenges in this area [START_REF] Shen | Applications of agent-based systems in intelligent manufacturing: An updated review[END_REF].

Market based allocation mechanisms are one of the most active branches of decentralized scheduling research. The underlying idea is to allocate resources among tasks by designing an ad-hoc market and setting prices iteratively to find the equilibrium. The process involves the creation of a production schedule based on the prices emerging from the bids sent by tasks. The goal is to design a bid structure and a selling mechanism that leads to an optimal scheduling of resources on a shop floor.

According to [START_REF] Wellman | A Market-Oriented Programming Environment and its Application to Distributed Multicommodity Flow Problems[END_REF], the main features of a decentralized scheduling problem are: First, each individual decision-maker follow its own objectives, but coordination will be enabled by prices. Second, decision-makers may have their own private information, such as their valuations of objects, and have no access to the private information of others (objectives, preferences and constraints). Third, complex calculations are distributed among the participating agents, so that the problem is divided into several easier problems which can be solved in parallel, and hence calculations can be sped up. Fourth, the communication overhead is low since it is limited to the exchange of bids and prices between agents and the market mechanism.

Combinatorial auctions have been used as a market mechanism to create schedules. One of the earliest works in this area has been developed by [START_REF] Rassenti | A Combinatorial Auction Mechanism for Airport Time Slot Allocation[END_REF]. Combinatorial auction is a type of auction in which participants can place bids on combinations of items rather than just individual items or continuous quantities. Economic efficiency is enhanced if bidders are allowed to bid on bundles of different items when there are complementarities between the different items, [START_REF] De Vries | Combinatorial Auctions: A Survey[END_REF]. The use of combinatorial auctions as negotiation and coordination mechanism is appropriate in problems in which the value of interdependent items needs to be considered.

Manufacturing scheduling problem presents complementarities. For instance, jobs are required to bid for continuous time slots on a resource (non-preemption constraints) and each job is required to participate in multiple auctions for its different operations, however all these operations have precedence constraints. We use a combinatorial auction-based mechanism to coordinate agents.

Combinatorial auctions can be divided into single round and iterative combinatorial auctions. In single round auctions participants send their valuations over the combinations of products just one time and the auctioneer allocate the items in such a way that the global objective is maximized. On the contrary, in iterative combinatorial auctions prices are fixed after multiple rounds. There are some advantages of using iterative combinatorial auctions instead of single round ones. First, participants do not have to make bids over the set of all possible combinations of bids. Second, participants reveal in each iteration their private information and preferences. Third, iterative auctions are well-suited for dynamic environments (e.g. manufacturing environments) where participants and items get in and out in different moments.

Price-setting Combinatorial Auctions for Coordination and Control of Manufacturing MAS: Updating Prices Methods

3 There are two kinds of iterative combinatorial auctions: quantity-setting and pricesetting. In the fist one, bidders send their valuation over every possible combination of the items sold. The auctioneer makes a provisional allocation that depends on the submitted prices. Bidders adjust the prices at every iteration. In the second one, pricesetting, (or demand query) auctioneer sets the prices for each of the items of the auction. Bidders submit the bundle of items they want to get at the given price. Auctioneer adapts the prices to balance the supply and demand [START_REF] De Vries | Combinatorial Auctions: A Survey[END_REF].

Combinatorial Auctions and Lagrange Relaxation Techniques

The updating methods used in the Lagrangian Relaxation Method to solve the dual problem can be used to update prices in iterative combinatorial auctions, since they share the same structure in their protocols [START_REF] Dewan | Auction-based distributed scheduling in a dynamic job shop environment[END_REF]. Auction protocols can be implemented in a non-adaptive standard Walrasian fashion, or as an adaptive tâtonement (price adjustment process). The subgradient optimization can be viewed as a particular version of the tâtonement proccess. While the subgradient optimization tries to penalize infeasibility of dualized constraints and the auctioneer updates the resource prices as to discourage conflicts on the demanded objects, the subgradient algorithm adjusts the prices proportional to the amount of infeasibility and the auction algorithm updates the prices proportional to the excess of demand [START_REF] Kutanoglu | On combinatorial auction and Lagrangean relaxation for distributed resource scheduling[END_REF]. Lagrangian relaxation technique relaxes the complex constraints of an optimization problem (i.e. those constraints which make the problem hard to solve), making the problem easier to optimize. The group of relaxed constraints is incorporated to the objective function in such a way that the restrictions that are not fulfilled are penalized. The new objective function is called Lagrangian function. The Lagrangian problem solution is always lower or equal to the solution of the original problem [START_REF] Fisher | The Lagrangian Relaxation Method for Solving Integer Programming Problems[END_REF]. The iterative process will approach the solution of the Lagrangian problem to the solution of the original problem.

Price setting iterative combinatorial auction

The task scheduling problem can be modeled as an auction where time horizon is divided into slots that are sold through the auction. Tasks participate in the auction as bidders, trying to get the time slots of the resources that they need to perform the operation [START_REF] Dewan | Auction-based distributed scheduling in a dynamic job shop environment[END_REF](See Fig. 1). We will relax the constraints that relies on variables belonging to different jobs. Our aim is to divide a complex problem into several easier ones. If we eliminate the restriction of capacity of the resources, we will be able to split the problem into N job subproblems. The mechanism will follow the main principles of distributed systems since the relevant information of the bidders (i.e. due date of the jobs, penalty for the delays, resources needed) will be hidden to the rest of agents [START_REF] Duffie | Synthesis of heterarchical manufacturing systems[END_REF]. None of the agents knows which other agents belong to the system nor what are the goals of those agents. Prices show the preferences of other agents, providing information to the agent to act consequently. This mechanism have been used to solve different kind of task scheduling problem, e.g. job shop problem [START_REF] Kaskavelis | Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems[END_REF], [START_REF] Sun | Lagrangian relaxation for complex job shop scheduling[END_REF], flow shop problem [START_REF] Tang | A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time[END_REF], or project management [START_REF] Ni | An Optimization-Based Approach for Design Project Scheduling[END_REF], [START_REF] Arauzo | Gestión eficiente de carteras de proyectos. Propuesta de un sistema inteligente de soporte a la decisión para oficinas técnicas y empresas consultoras= efficient projet porfolio management. And intelligent decision system for engineering and consultancy firms[END_REF].

Fig. 1. Auction-based scheduling mechanism

It can be described as follows: There exists a central pool of resources (Resourceagent). Each resource has different abilities. The planning horizon of the resource is divided into time slots. These time slots are sold in an auction. Several jobs have to be completed (Job-agents). The jobs need to get the necessary resources to be finished before their due date. Job-agents bid for the time slot of the resources. They try to minimize their cost function. An agent acts as a central node (Auctioneer-agent). The bids sent by Job-agents are received by the Auctioneer-agent, who will update the prices of the slots. Once known the new prices, the Job-agents will remake their bids. This iterative process continues until prices are stabilized or a stop condition is fulfilled. (See fig. 2)

Job-agents are price-takers in the model (See fig. 3). Price is fixed by an iterative process. The prices of the slots are raised or lowered by a walrasian mechanism. The auctioneer compares the demand over a time slot of a resource with the capacity of the resource in this time slot. if there is an excess demand, the auctioneer raises prices. On the other hand, if there is an excess of capacity he lowers them.



      n n 1

Fig. 2. Price-setting iterative combinatorial auction

There are many ways to update prices (e.g. constant increase or decrease of prices, proportional to the demand, proportional to the excess of demand).

Updating Prices Methods

Subgradient method [START_REF] Geoffrion | Lagrangean relaxation for integer programming[END_REF], [START_REF] Fisher | The Lagrangian Relaxation Method for Solving Integer Programming Problems[END_REF], [START_REF] Guignard | Lagrangean relaxation[END_REF]: It is the method most commonly used to solve the relaxed (dual) problem. Each bidder sends the bundle of time slots that maximizes its utility. Auctioneer computes the excess demand (subgradient) and updates time slots prices along the subgradient. A lower bound of the optimal scheduling cost can be obtained from the dual problem resolution process. Although it is used by many practitioners for its simplicity and low computational overhead, it has many drawbacks: Multipliers zigzag along ridges (intersection of several facets) of the dual function. It suffers from slow convergence, and it can be difficult to solve all the suproblems in big size problems.

Aiming to improve the performance of the subgradient method, [START_REF] Camerini | On improving relaxation methods by modified gradient techniques[END_REF] developed the conjugate gradient method, also used in [START_REF] Crowder | Computational Improvements for Subgradient Optimization[END_REF], [START_REF] Brännlund | A generalized subgradient method with relaxation step[END_REF] or [START_REF] Wang | An optimization-based algorithm for job shop scheduling[END_REF] by following a modified gradient step direction that is calculated as a linear combination of the actual vector of excess demand and the precedent modified gradient step direction. It reduces zigzagging with respect to subgradient method.

The surrogate gradient method [START_REF] Zhao | The surrogate gradient algorithm for Lagrangian relaxation method. Decision and Control[END_REF], [START_REF] Chen | An alternative framework to Lagrangian relaxation approach for job shop scheduling[END_REF] is based on the idea that it is not necessary to get the best directions to reach the optimum of the dual function. Good directions can be obtained with much less effort. The bundles of time slots sent by the bidders do not have to maximize its utility; they just have to improve the utility of the

Acknowledgements. This work has been partially supported Caja de Burgos through Projects 2009/00199/001 and 2009/00148/001

INFORMATION TECHNOLOGY FOR BALANCED AUTOMATION SYSTEMS

bidder with respect to the previous bids at the given prices. This method is useful for large problems having many complicated subproblems. The main disadvantage of this method is that the surrogate dual cost is not always a lower bound to the optimal scheduling cost.

The interleaved subgradient is a special case of the surrogate method [START_REF] Zhao | Surrogate Gradient Algorithm for Lagrangian Relaxation[END_REF], [START_REF] Kaskavelis | Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems[END_REF], [START_REF] Zhao | The surrogate gradient algorithm for Lagrangian relaxation method. Decision and Control[END_REF]. Only one subproblem per iteration is solved to obtain a direction and to update the multipliers. The method is called random interleaved subgradient if this process is done in a non predefined order. This idea is attractive for real dynamic environments, where real time dynamics have to be considered. The directions obtained are also smooth for large problems, leading to better performance.

The fuzzy subgradient [START_REF] Zhao | Fuzzy gradient method in Lagrangian relaxation for integer programming problems[END_REF] aims to make use of all the information generated in the job sub-problem resolution. It takes not only optimal solutions of the job subproblems, but also near optimal solutions combining them to generate "fuzzy gradients". This method reduces the solution zigzagging without much additional computational requirements. We search an updating price method for combinatorial auction that meets the requirements of scheduling manufacturing systems in dynamic environments, i.e. they are intended to offer robustness, stability, adaptability, and efficient use of available resources through a modular and distributed design [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF]. To the best of our knowledge, currently there is no work which compares the updating prices methods of combinatorial auctions for Job Shop problem.. In our work we will use a specific problem as Job Shop scheduling problem, but we want to extend the conclusions that we will obtain to other problems of the same nature. Our objective is to compare the different methods of updating prices based on those that update the Lagrangian problem.

We will define and implement a distributed task scheduling system based on the Job Shop Problem [START_REF] Pinedo | Scheduling 2º ed[END_REF]. We want to compare the different methods of updating prices using as criteria convergence, stability and other points to study in a real case implementation as asynchronous computation. We will use different benchmark as we can find in [START_REF] Demirkol | Benchmarks for shop scheduling problems[END_REF] and the modifications suggested in [START_REF] Kreipl | A large step random walk for minimizing total weighted tardiness in a job shop[END_REF].

Price-setting Combinatorial Auctions for Coordination and Control of Manufacturing MAS: Updating Prices Methods

7


Pedro Gomez-Gasquet

Francisco Cruz

Lario Esteban

Ruben Dario

Franco Pereyra

Victor Anaya Fons

The Design of an Agent-Based Production Scheduling Software Framework for Improving Planning-Scheduling Collaboration

Keywords: Production Scheduling, Agent, Collaboration Planning-Scheduling

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The design of the system that is proposed is initiated once the analysis of the requirements has been completed. In this case, the requirements have been obtained by applying CIMOSA [START_REF] Fons | CIMOSA -Open System Architecture for CIM[END_REF][2] [START_REF] Zelm | The CIMOSA business modelling process[END_REF]. It provides optimal, desired images.

The reader should consider the proposed system to be the structural element on which the algorithms, methods, and other resources that are oriented to the scheduling in changing environments will subsequently be placed or where it is necessary to apply rescheduling of the previously established schedules. The functional coordination between the environment of the planner and the scheduler, in this type of environment, is based on cooperation. Communication is the fundamental objective of this software element.

From a technical point of view, the system's design is based on the agent-based paradigm that offers some interesting advantages [START_REF] Wooldrige | Intelligent Agents: Theory and Practice[END_REF]. Therefore, its design itself includes the employee methodological proposal INGENIA [START_REF] Pavon | Agent Oriented Software Engineering with INGENIAS. Multi-Agent Systems and Applications II[END_REF], which facilitates the development of systems that are based on agents and multi-agents. Although the design is closely linked to the Technology of Information and Communication (TIC), a vision of the employed methodology is provided in order to connect it with the most conceptual levels of the process of production scheduling.

The remainder work is divided according to the following form: the second paragraph analyzes the conditions in which the process of collaboration between planner and scheduler should occur. In the third paragraph, INGENIAS methodology is deployed in order to obtain the framework of the proposed software. The fourth paragraph is dedicated to commentary about the practical use of the proposed software. The report concludes with a summation of the aforementioned information.

Process Analysis of Collaborative Planning-Scheduling Operations

To proceed in the phase of requirement analysis, CIMOSA methodology has been selected. It provides the advantage of offering a vision of the problem to analyze that is structured according to various views (i.e., functional, organizational, resourcebased, and informational) that enrich the final analysis. Figure 1 presents the functional point of view that production scheduling is defined like a domain; that is, directly related to the domains of the planning (i.e., tactical), the design of processes and products (i.e., strategic) and the operations control (i.e., operating). The objective that is defined inside the production scheduling domain is to obtain production schedules in which the average of productivity that is reached in the different periods is the highest that is possible. This aspect is fundamental and, from our point of view, implies that the quantitative methods are suitable to give solutions to the corresponding combinatorial problems as well as fundamentally promoting the contribution among the planner. The planner decides the lots that one must carry out in each period. The scheduler manages the capable manufacturing system that offers the service in question. In this sense, one must emphasize that the suitable adjustment of the capacity to the needs of each moment will be the one that facilitates the attainment of the greatest productivity average. Inside the production scheduling domain, only the domain process has been defined (DP-production schedule management) as being responsible for managing the allocation, sequencing, and timing of the lots that the planner has requested be manufactured in a determined period. Such management implies that the initial schedule is obtained by means of a business process (BP-predictive PS) that employs some algorithm that is adjusted to the characteristics of the problem in function of the known data to priori (e.g., static or predictive schedule). At the beginning of the period, the initial schedule will become the schedule in process. A new business process will run (BP-REVIVE PS) to detect events and, in that case, to try those that can affect the schedule in process (EV-upset, EV-new period, EV-restart) and imply the execution of some method to readjust the schedule in process to the current reality.

The proposed system is focused on a make-to-stock management, although other type of management will be tackled easily. Algorithms and methods should be adapted to each problem. What is provided is an architecture that enables the coordination between the planner and the scheduler to adjust the lot number and its volume of each period by means of an iterative process to carry out the major number of possible units. For example, consider the following in the case of:

Predictive scheduling (i.e., initial schedule). Normally an upset among the employed times for the calculation in the environment of planning exists and the available time in the environment of scheduling once generated the schedule (e.g., the variable times of process and setups, dependence of the sequences, etc.).

Reactive scheduling (i.e., schedule in process) consists of detecting the possibility of incorporating some new lot if the schedule in process advances faster than predicted. In other cases, it consists of canceling some lot that is included on the schedule in process if some delay that impedes the ability to carry out the predicted schedule occurs inside the current period. One must remember that is possible that the initial schedule include some idle time that provides a solution to some small incident that is not predicted without modifying the initial selection of lots. This situation is normal, in order to avoid a high number of cancellations or incorporations of lots in each period.

The views of information and resources indicate that they have established the type of data and capacities that are necessary to manage the productive schedule.

The Jade-Based Production Scheduling System

Complex manufacturing systems consist of a number of related subsystems that are organized in a hierarchical fashion. At any given level, subsystems work together to achieve the functionality of their parent system. Each component can be thought as achieving one or more objectives. Thus, entities should have their own thread of control (i.e., they should be active), and they should have control over their own actions (i.e., they should be autonomous). Given this fact, it is apparent that the natural way to modularize a complex system is in terms of multiple autonomous components that act and interact in flexible ways to achieve their objectives. Therefore, the agent-oriented approach is simply the best fit.

In next sections, we present the agent-oriented models and methodology that we have used in the development process of the scheduling problem of production.

Description of the Modeling Process

INGENIAS methodology employs several meta-models and a meta-model language for constructing models. All meta-models are based on objects, attributes, and relationships. INGENIAS methodology also integrates its meta-models into the Rational Unified Process (RUP) for developing software systems and offers a graphical development tool called the INGENIAS Development Kit (IDK).

During analysis and the design phases, five different meta-models are used: (i) an organization meta-model, which defines how agents are grouped and identifies the system functionality and the existing constraints in the agents' behavior; (ii) an agent meta-model, which describes the particular agents to be used and their internal mental states; (iii) an interaction meta-model, which details how agents are coordinated and interact; (iv) an environment meta-model, which defines the types of resources and applications that are used by the system; and (v) a tasks and objectives meta-model, which relates the mental state of each agent with its tasks. This paper focuses on the analysis phase of the production. In the following subsections, we will show analysis diagrams of a distributed, flexible, and autonomous production scheduling system. This system could be easily connected with the other subsystems in order to implement the agile manufacturing enterprise.

Use Case Diagrams

A use case diagram provides a snapshot model of a set of system behaviors that meets a user goal. Thus, this description represents a functional requirement that shows what happens, but not how it is achieved by the system. As previously mentioned, our study is focused on the scheduling system, in which four main use cases can be identified (Figure 2). In the "calculate predictive scheduling" use case, a feasible initial schedule to be carried out in the following days is created. This schedule is developed according to the manufacture lots that are defined in the master plan which is included in the planner set of use cases (not shown) but that is available with the "get periodic plan" use case. In the "reactive production adjustment" use case, previous schedules in which problems developed during execution are modified. Therefore, those schedules are reconfigured in order to adjust to factory changes. The schedule execution monitoring data is included in the last use case.

Organization Model

The organization model is defined by the organizational goals and tasks, the workflows that determine associations among tasks and general information about their execution; groups, which may contain agents, roles, resources or applications; and social relationships.

Several roles are distinguished in the organization model for the scheduling process (Figure 3): (i) planner, which is responsible for selecting the lots in a period; (ii) coordinator, which maintains information about all plants' configuration and knows all restrictions and features of each machine and plant element; (iii) scheduler, which has the ability to schedule tasks and resources and supervises actual execution of a schedule in a specific plant; and (iv) worker, which oversees the schedule execution at the plant.

Interaction Model

An interaction model consists of identifying, for each use case, interaction goals, its members (i.e., the initiator and collaborators), nature, and specification (by means of collaboration diagrams). Table 1 shows the defined interactions, the involved agents, and the interaction unit (i.e., message) that is used.

Agent Model

In an agent model, a specific agent has been assigned to each role that is identified in the organization model. The goals, tasks, and mental states have to be associated for each agent. Figure 4 shows the scheduler agent model. The scheduler agent plays the scheduler role and this example has two main goals (e.g., set a schedule and increase the production rate average) and a set of tasks (e.g., check and load data, parameter adjustment, calculate predictive/reactive scheduling, tuning the schedule, validate/reject the results, notify a new schedule). They are achieved by means of a set of mental states. In the same way, a planner and a worker agent model exists. The first one plays the role of planner and coordinator, and the second plays the role of worker. Figure 4 shows how a scheduler agent could be in a different mental state ("AHasMS"). For example, "waiting" for a proposal/message, "scheduling" a batch of jobs, "ask for modifying" a batch of jobs, etc. From a specific mental state, the agent scheduler must reach his goals by using the available functions and tools.

Task/Goals Model

This model attempts to answer the questions of why, who, and how throughout the analysis process. "Why" refers to the goals that are defined for the system; "who" refers to the agents which are responsible for the goal fulfillment; and "how" refers to the set of tasks which are defined to achieve the goals.

Two major goals have been established: "predictive scheduling" and "scheduling adjustment or rescheduling".

Predictive scheduling comes from the functional view of the production scheduling domain, which is carried out in CIMOSA analysis. Figure 5 shows how this workflow must satisfy three main goals (i.e., satisfy planning, efficient use of resources, and set production scheduling). The "conversation" items that represent interactions between two agents (e.g., scheduler-planner and scheduler-worker) could be highlighted in the figure. These conversations are the core of the negotiation process that occurs in almost all functional processes. Regarding our analysis, the decomposition of the schedule creation workflow is shown in figure 6 as an example of the tasks/goals model. The associated tasks are the different steps of this workflow which are accomplished according to concrete roles. Scheduling adjustment comes from the functional view of the production scheduling domain, which is carried out in CIMOSA analysis that is named "reactive scheduling." Figure 6 shows how this workflow adds one additional goal, "keep a stable scheduling," and displays what is relevant and characteristic about this function. This task maintains "conversations" as core elements in the process.

Environment Model

The environment model of the production scheduling organization is shown in order to consider that an internal application is managed by the planner to store and update executed plans that are created by the organization.

Using Proposed Software in a Ceramic Tile Factory

The resulting proposed framework software has been transformed in a prototype in order to be used in a typical make-to-stock industry, such as a ceramic tile enterprise. The software programming and deployment has been carried out by using the JADE platform (http://jade.tilab.com/) and JAVA language. The methods and algorithms have been developed in order to solve a hybrid flow-shop problem with sequencedependent setup times [START_REF] Gomez-Gasquet | Dynamic Hybrid Flow-Shop Scheduling with Due Dates and Sequence Dependent Setup Times[END_REF] [START_REF] Gupta | Flowshop Schedules with Sequence Dependent Setup Times[END_REF]. Comparing the current processes at the selected enterprise and the new options that are provided by the prototype, one could observe that, as the top productivity rate is attained (i.e., 10%-25%, depending on the scenario) in the second case, it can be attributed to the overall reduction of idle time. These times have reduced as much for the relocation/sequencing of the lots in process as they have for the incorporation of new lots. This paper presents a methodological development, based on multi-agent technology, of an application with which to overcome the scheduling production problem in a make-to-stock factory. It has been designed according to the actual dynamic production processes needs that allow the selling process to be realized in an online platform. Our approach is based on a medium-time project. This proposal is based on the system capability that offers the most suitable product alternative, even though it could involve scheduling changes if the global quality is improved.

In order to satisfy that goal, it is necessary to integrate the various distributed production steps in a flexible, adaptable, versatile, robust, and natural way. Agent/multi-agent systems technology has been used in the resolution of this problem, since it provides the required characteristics for manufacturing systems. We have currently centred our analysis on the scheduling problem, due to its critical importance in the whole process. The resulting software has been tested in the ceramic tile industry.

Fig. 1 .

 1 Fig. 1. Main Elements of Functional View of Production Scheduling Domain.

Fig. 2 .

 2 Fig. 2. Use Cases for the Schedule of Production Tasks.

Fig. 3 .

 3 Fig. 3. Scheduling Process Organization Model.

Fig. 4 .

 4 Fig. 4. Scheduler Agent Model.

Fig. 5 .

 5 Fig. 5. Predictive Scheduling Tasks/Goals Model.

Fig. 6 .

 6 Fig. 6. Scheduling Adjustment Tasks/Goals Model.

Table 1 .

 1 Interactions Between Agents and Interactions Units.

	Interaction	Agent Actors	Interaction Unit
	Get	Periodic	Planner-	Ask for Factory Capacity
	Planning		Scheduler	Notify Factory Capacity
				Notify Factory Planning
	Notify		Scheduler-	Notify	Infeasibilities	of
	Infeasibilities		Planner	Planning
	Notify Planning	Planner-	Reject Lot
			Scheduler	Get allocating options
				Notify Capacity available
				Modify Planning
				Ask for a lot
				Allocating new lot
	Notify Scheduling	Scheduler-	Notify new schedule
			Worker
	Notify problems	Worker-	Notify the problem
			Scheduler


Pierre I Dussarrat

Maxime I Perrier

Almazbek Imanaliev

Raphael Lopes

Alain Aspect

Marc Cheneau

Denis Boiron

Chris Westbrook

Two-Particle Four-Mode Interferometer for Atoms (poster)

come

• We present a free-space interferometer to observe two-particle interference of a pair of atoms with entangled momenta.

• The source of atom pairs is a Bose-Einstein condensate subject to a dynamical instability, and the interferometer is realized using Bragg di raction on optical lattices. • Our observations rule out the possibility of a purely mixed state at the input of the interferometer.

• Our current setup can be extended to enable a test of a Bell inequality on momentum observables.

Bragg mirror and splitters

  100 µs pulse (π-pulse) • Splitter: 50 µs pulse (π/2-pulse) • The lasers imprint their phase on the atomic modes (φ A,B ) • Spectral broadening induced by the short interaction time: → the same lattice addresses (p,-p') and (-p, p') → addition of a velocity-dependent phase away from the energy resonance • Correlation coefficient: E = V cos(φ A -φ B -2δτ) driven by moving optical lattice → emission of atom pairs with opposite momenta • Broad resonance → several pairs of modes are coherently populated • Filtering the data reduces the state to the desired form: center-of-mass frame • Analysis of 3 di erent sets of modes → access to 3 di erent phases (φ A -φ B -2δτ) • Joint detection probabilities correlated 2-by-2 • Correlation coe cient di erent from zero for one data set → E = 0.51(20) for set 3 • Rules out the possibility for a totally mixed state • Proof of entanglement? → need separate Bragg splitters to control the phase → work 1D geometry (vertical) • Pair emission driven by a moving optical lattice (vertical) • Interferometer realized in free fall • Bragg mirros and splitters • Detection after 300 ms time of ight → single-atom detection (25% det. e .) → 3D resolution (x-y position + time) This project has received funding from: • the European Union's FP7 and Horizon 2020 research and innovation programme • the French National funding Agency • Churchill College, Cambridge

  Two-Particle Four-Mode Interferometer for Atoms Pierre Dussarrat , Maxime Perrier , Almazbek Imanaliev , Raphael Lopes Alain Aspect , Marc Cheneau , Denis Boiron , Chris Westbrook Laboratoire Charles Fabry, Institut d'Optique Graduate School, CNRS, Université Paris-Saclay, 91120 Palaiseau, France LNE-SYRTE, Observatoire de Paris, PSL Research University, CNRS, Sorbonne Universités, UPMC Université Paris 06, 75014 Paris, France Cavendish Laboratory, University of Cambridge, Cambridge CB3 0HE, United Kingdom


S N Khalil

R H Weston

Modelling Human Resource Systems in Support of Efficient Production

Keywords: Human system, manufacturing enterprise, simulation modelling, process-oriented enterprise modelling

Resource systems in manufacturing businesses need to be managed innovatively particularly when a range of products and services needs to be realized with minimum investment in resource systems. In this research, the primary form of active resource system, namely people, will be modelled with a view to facilitating efficient production. Humans play the key role in organising manufacturing businesses and contribute greatly towards competitive production performance. Enterprise Modelling is use to create static models that capture key organisational relationships in a manufacturing business and transformed into equivalent structures within Simulation Models that enable dynamic analysis. This provides both graphical and computer executable models of people and facilitates quantitative analysis and comparison of different human system configurations that suit various manufacturing workplaces. The paper illustrates the application of the modelling approach and observes advantages gained through using coherent sets of enterprise and simulation models.

Introduction

To be able to design an efficient production system, designers and managers of Manufacturing Enterprises (MEs) need to be able to reason about the assignment of persons to production activities such that key performance measures (like lead-time, quality and cost targets) are met. Typically in industry this is done implicitly with regard to 'abilities' (of alternative candidate resources (including people, semiautomated machines and supporting IT systems) to fulfill a given set of product realising roles with respect to specific case performance measures. When assigning production operatives to roles, production system designers and managers use their experience and knowledge about abilities of the people involved and makes judgments about their individual and collective abilities to accomplish predicted patterns of upcoming work. However often production systems, and/or the products they make, can be complex. Indeed when production systems need to share human and technical (machine and IT) resources amongst a changing mix of multiple value streams, frequently designers/managers may make poor people and machine assignment decisions, which will lead to poor attainment of production targets that causally may result in poor competitive performance of the manufacturing business as a whole. In such case managers/designers can gain significant competitive advantage from the ongoing re-use of an effective decision-support tool which will help them make better informed decisions about how and when to allocated a finite production resource in response to any given customer induced dynamic. This paper researches a new means satisfying this requirement for decision support. The approach taken is to deploy a synergistic combination of:

Enterprise Modelling, which explicitly describes organisational structures related to a particular parent manufacturing business; so that process-oriented structural relationships inter-connecting production systems are uniquely defined, and Simulation Modelling, which is capable of simulating time-based behaviours of alternative production system configurations of people and technical resource; thereby potentially enabling production system designers and managers, in a virtual environment, to experiment within systematic changes to organisational structures and production system parameters so as to predict changes in production system behaviours and therefore performance outcomes in respect of new work scenarios.

The modelling approach taken has potential within dynamic production systems environments to much improve the deployment of a constrained set of people and machine resources and further by predicting change outcomes prior to making physical production system change the costs and benefits of changes trial can be assessed, thereby protecting risk associated with production system investments and potentially extending the economic life-time of production systems. This paper describes how an enterprise model can be used to capture a big picture of the organisational structures of a case study Manufacturing Enterprise (ME). The approach being researched has potential to form the basis of a decision support tool, which can repetitively, quantitatively and explicitly inform production system designers/manager about the suitability of different assignments of human and technical resources, given a set of changing work. Therefore this paper is design to aid the efficient deployment of human systems in MEs by: Proposing a human system modelling technique which can be used on an ongoing and systematic basis to model, understand and engineer human systems that satisfy dynamic production system requirements;

Analyzing key aspects of human system dynamics by developing static and dynamic models of human systems. The paper will discuss the background of the research work. It will also explain how Enterprise (static) and Simulation (dynamic) modelling can be used in a complementary fashion to visualise and computer executes alternative possible human system deployments.

Manufacturing Complexity

Over many years great interest has been placed in managing complexity in manufacturing organizations. Siemieniuch and Sinclair [START_REF] Siemieniuch | On complexity, process ownership and organisational learning in manufacturing organisations, from an ergonomics perspective[END_REF] defined manufacturing complexity from an organisational perspective. They state that if interactions between entities of an organisation give rise to unpredictable organisational performance then that organisation is complex. Common entities in manufacturing organisations comprise human resources, electromechanical and IT machines which typically are organised to realise customer related processes and infrastructure services [START_REF] Pandya | Towards the manufacturing enterprises of the future[END_REF] When seeking to manage complexity, various approaches and manufacturing paradigms have been introduced. For example the Group Technology (GT) has widely been used in industry to improve manufacturing processes by means of grouping and coding. GT types of activities are also referred as classification and clustering: of parts that are similar in nature; or parts that require operations of similar machinery and processes [START_REF] Kusiak | Group technology[END_REF]. Advantages of deploying GT philosophy are (1) to simplify the flow of parts and tools, (2) to reduce set-up times, (3) reduce throughput time, (4) reduce work-in-process inventory and ( 5) maximize design and manufacturing efficiencies. However according to name Kusiak and Heragu, the use of a clustering method may not be efficient because of constraints from needed information flows in the processes; such as if data related to material, geometry and tolerances is not available.

The average lifetime of products has shortened dramatically in the last 10 years. Product variations have increased and this requires MEs to be more flexible and responsive towards their customer demands. But current trends in global demand mean that more products are now produced in low quantities, with high variety amongst demand patterns. This is because increasingly products are highly customised and/or their underlying technologies and components are subject to increased rates of change. Richards states that being responsive and agile is as being able to respond to sophisticated customer requirements when subject to persistently changing competitive processes and success factors [START_REF] Richards | Agile manufacturing beyond lean[END_REF].

Trends and Needs to Model Human Systems

Currents Trends in Manufacturing Industry

The new millennium has seen rapid change in many aspects and segments of manufacturing industries. Some factors contributing towards this change are:

Intense global competition. Mass markets fragmenting into niche markets. Customers expecting low volume, high quality, custom products. Seemingly ever shortening product life-cycles, development times, and production lead times are required. Customers want to be uniquely treated, i.e. as individuals In an attempt to address these factors, organisations need much more frequently to be re-configured. This for example may require some form of change in human oriented organisational structures. Manufacturing organisations, basically comprise human resources, and electromechanical and IT machines; and in general systematic use of these 'active' resources (i.e. resources that can perform required ME actions) are commonly organised so that they systematically achieve value adding processes and related infrastructure support and engineering developmental activities [START_REF] Pandya | Towards the manufacturing enterprises of the future[END_REF]. Earlier in this paper, the literature focussed on the paradigms and approaches that industry is adopting to improve manufacturing processes. However these paradigms were mainly discussed in respect of their mechanistic aspects rather than their behavioural aspects and how such behaviours can impact on MEs. However the functional aspects of human-related processes still requires further study. As the prime ME resource, there is a great need for humans to know about the 'how', 'what' and 'do' (BS ISO 14258:1998) activities in a given ME and the related roles that they and other humans can play with respect to manufacturing activities. The literature reviewed in this paper illustrates that there is a gap in quantitative understandings about potential roles of technical (electromechanical and IT) resources and related roles that human resources can play with respect to engineering, infrastructural and direct value adding manufacturing activities.

Needs to Model Human System

As yet there is no widely accepted (by industry or academia) systematic way to qualitatively and quantitatively model ME process oriented roles; and how such roles may function over time under differing production demand patterns should they be resourced by humans and machines or by humans or machines. In general it is observed that addressing this deficiency requires effective models of relationships between human/human and human/machine, which may be uncertain in nature. Therefore it is observed that great advantage could be gained by having a 'simulation tool' to model alternative combinations of resource entities; so as to inform 1) managerial aspects of human/machine resource allocation, by providing support for planning decisions and determining suitable resource system reconfigurations based on predictions about organisational behaviours and 2) design aspects of production systems, associated with mid to long term investment decision making.

Human System Modelling in Manufacturing Enterprise

Humans are unique and their behaviour can be difficult to predict. Thus it may be almost impossible to model the unconstrained human due to these complexities. On the other hand, potentially human systems can be modelled from more constrained viewpoints. Example viewpoints include: psychology, physiology, culture, structure, dynamic, roles and attribute. Researchers in the MSI (Manufacturing System Integration Institute) have focused their human systems modelling efforts on modelling people roles (i.e. organised sets of activities that people perform) and to consider how the abilities and behaviours of potential human role holders impact on achieving production targets. The approach being taken is therefore based in process oriented modelling. One thread of top-down modelling followed is centered on ME process decomposition into hierarchy/levels for action taking and information sharing. Here processes are explicitly and graphically modelled as related sets of enterprise activities (EAs) which identify possible sets of explicitly defined roles that can be resourced by alternate groups of people competent to perform the role sets defined. Here role sets essentially specify a process oriented organisational structure. This is illustrated by figure 1. The activities are defined in terms of unitary functional operations (FO) that require unitary functional entities (FE) which can be possessed by human and/or machine holders of those roles. In a second thread of modelling candidate human (and machine) holders of roles are described in a tabular fashion, in terms of the competencies they can bring to bear on defined role sets Fig 1 . Human system entities (which can be matched to FE) and likely behavioural performances they can achieve (which can be linked to FO sequence models). A third thread of modelling is centered on simulation of alternative candidate configurations of roles and role holders, which provides a tool for comparing throughputs, utilisation, cost and value generation abilities of those alternative configurations.

Modelling Concepts and Research Methods

MSI researchers have been using enterprise engineering and simulation modelling technique to aid decision-making. Enterprise modelling is used primarily to [START_REF] Siemieniuch | On complexity, process ownership and organisational learning in manufacturing organisations, from an ergonomics perspective[END_REF] externalizing enterprise knowledge about case study MEs, and can add value to the enterprise by enabling knowledge sharing and (2) to provide a process-oriented decomposition mechanism, so that high levels of complexity can be handled and it becomes possible to break down the barriers in organization that hinder productivity by synergizing the enterprise to achieved better understandings about how business goals can be achieved in an efficient and productive way [START_REF] Vernadat | Enterprise Modelling and Integration[END_REF].

The enterprise modelling (EM) technique used in this study is known as CIMOSA. CIMOSA is an acronym derived from CIM Open System Architecture and this acronym was introduced by the AMICE consortium. In CIMOSA the user representation and system representation, and related function information and control perspectives are decomposed. The associated decomposition and isolation of different modelling concepts and viewpoints enables an organization to be represented in a flexible fashion, so as to realise changing requirements for functional and facilities integration. Generic graphical representation of CIMOSA models is illustrated in figure 2. CIMOSA modelling enables ME decomposition into the following: Domains (DM) Domain Processes (DP) Business Processes (BP) and Enterprise Activities (EA) Functional Operators (FO) Functional Entities (FE) This case study modelling is supported by simulation models (dynamic models) that are in part derived from (and hence are consistent with) selected segments of the CIMOSA static model. CIMOSA graphical models are static in the sense that they only encode relatively enduring properties of MEs and cannot be computer executed to show ME behaviours over time. The simulation models are capable of modelling Fig. 2. CIMOSA static model queues, stochastic events, product flows, process routes, resource utilisation, breakdowns and absence, exception flows and etc. Enterprise and simulation modeling (SM) techniques can mutually support analysis of human system roles in a manufacturing enterprise.

Research Domain, Integration of Enterprise & SM

Chosen case study company is an air conditioning company, LS a privately owned Chinese manufacturing company located in Shun De in the Guangdong province of South China. Since 1988 when it came privately owned, it has expanded its manufacturing and supply scope and is currently specialised in the 'engineering to order' of customised industrialised air conditioners. Their unique expertise is demonstrated in their competence in meeting varying customer needs. On the average LS employs about 1000 staff of which 60 are mainstream Engineers. Most of the staff is young graduates from universities and colleges and hence the company exhibits high level of exuberance in terms of its personnel. The assembly shop 2 has been chosen as the case study for this research. The shop floor assembly held in five stages:1)general assembly, 2)pipes and tubing and hydraulic tests, 3)electronic control installation and side panels assembly, 4) testing and lastly 5)packaging. Each stages of the assembly work is supported by 66 staff that is grouped into 5 sets of different teams. Each team are trained and specialised in each stages. The process that took place during the assembly is described in CIMOSA enterprise activity diagram BP 6.3.1 as referred in figure 3.

The simulation modelling (SM) of these workstations is as described in figure 5. The simulation modelling is held using Teknomatix Plant Simulation Modelling software tool. The software is a custom made tool for users that specifically designed to model the performance of a manufacturing plant. The SM is capable of modelling human resources hierarchically. The broker or acting as supervisor worked by assigning workers in the workpool to perform activities/processes at the workstations. Workstations are the places where worker is assigned to do their work assigned at each stage and the performance is affected by i.e. workers efficiency, dynamic input etc. In this case the efficiency of the workers are set to 60% efficient in the first experiment and the other is set 80% efficient in the second experiment. Thus is done to compare the performance of the production line when workers efficiency is changed. The chart of the overall performance of the work centers is shown in figure 4. The column in the chart shows the pattern of working and blocked processes taking place during the simulation is done. The simulation throughput results showed that there is a 30% increase of production throughput i.e. from 1 AC unit per day to 1.3 AC units per day when the efficiency of workers increased from 60% to 80%. When the number of workers in Team 1 is reduced by half, the simulation results showed that the throughput remained to 1 per day when the resource efficiency is set to 80%. The results showed there is potential for the production system design to reduce the amount of workers when the workers are working at higher efficiency.

Further Work in Human System Modelling in Manufacturing Enterprise

Current modelling is based on the 'as is' model, i.e. the current process carried out in the particular bearing manufacturing system. Improvements that will be performed in later stages include: 1) Improving matching roles to role holders in Static Model for modelling and allocating the right worker for the right processes according to different competency levels of workers. 2) Enhancing the current team with abilities to perform multiple processes and able to work in cross-team assembly work. This will improve the throughput of the process line due to increase of shared-knowledge and information flow in the assembly line.

Summary and Conclusions

This approach has developed new understandings about different types of model that can be used to characterize human system dynamics. This characterization is based on a job order specification at which influenced by multiple variances i.e. product specification variances. At this stage of experimentation the author has not yet been able to find out whether these models can usefully predict the impact of the overall performance of manufacturing enterprise due to product variance. But early results are encouraging.

Fig. 3 .Fig 4 .

 34 Fig. 3. Activity Diagram-Assembly shop 2

Acknowledgments

The principal researcher is currently a PhD researcher in Loughborough University and sponsored by the Malaysian Ministry of Higher Education/ Universiti Teknikal Malaysia Melaka.