Vincent Pretre

Fabrice Bouquet

Christophe Lang

Frédéric Dadeau

Adrien De Kermadec

Automating UML Models Merge for Web Services Testing

Keywords: Web services, UML, model based testing, consistency 1

This paper presents a method for merging UML models which takes place in a quality evaluation framework for Web Services (WS). This framework, called iTac-QoS, is an extended UDDI server (a yellow pages system dedicated to WS), using model based testing to assess quality. WS vendors have to create UML model of their product and our framework extracts tests from it. Depending on the results of the test execution, a mark is given to WS. This mark permits to customers to have an idea about the quality of WS they find on our UDDI server. Up today, our framework was limited to WS which did not use other WS. This was justified by the fact that it is impossible for vendors to create a good model of a foreign product. Our method for model merging solves this problem: each vendor produces models of its own product, and we automatically merge the different models. The resulting model from this merging represents the composition of the different WS.

For each type of diagram present in the models (class, instance or state-chart diagram), a method is proposed in order to produce a unique model. In addition to this, a solution is proposed to merge all OCL code in the class modeling the WS under test. Unfortunately, this process introduces inconsistencies in the resulting model, that falsify the results of the subsequent test generation phase. We thus propose to detect such inconsistencies in order to distinguish inconsistent and unreachable test targets.

important place in software development. Web Services (WS) are used in many kinds of applications: web sites, widgets or more classical software. This omnipresence leads to a need of validation. That need led us to create a quality evaluation framework for WS. Until now, this framework was not able to test WS working with other WS. This paper introduces a method for model merging, which solves this lack.

The first section introduces context which led us to propose a model merging solution. First, we introduce WS and our vision of their quality. Then, we present iTac-QoS, our validation framework for WS. The merging method proposed in this paper takes place in this framework. At last, we present why model merging is a necessity for testing a particular type of web services. Second section is dedicated to related works. It is split in three parts: UML modeling of WS, test of WS and model merging. The third section introduces our method to automatically merge UML models, applied on an example. Then, the fourth section presents how to detect and solve the inconsistency problems resulting from the model merging process. At last, we conclude and introduce future work.

Web services quality

We define WS as the server part of a client-server application in which exchanged messages are written in XML [START_REF] Vogels | Web services are not distributed objects[END_REF]. Generally, WS are built upon SOAP (Simple Object Access Protocol [START_REF] Gudgin | Soap version 1.2[END_REF]). This protocol defines structure of XML messages, and uses well known protocol such as http or smtp. The first advantage of WS is their compliance with most security policies, which generally authorize http and smtp protocols. Moreover these protocols and XML bring the second main advantage of WS: portability. Almost every programming language has libraries handling XML and those protocols. This makes it possible to easily create clients for a web service in any programming language. Writing a client for a WS can be easily done using a WSDL (Web Service Description Language [START_REF] Christensen | Wsdl 1.1[END_REF]) file. This file describes everything required to communicate with a WS: address, provided operations, message format, exchange protocols . . . A second technology related to WSDL is UDDI (Universal Description Discovery and Integration [START_REF]OASIS UDDI specification TC. Uddi version 3.0.2[END_REF]). A UDDI server is a yellow pages system for WS. It permits customers to easily find WS, and vendors to spread their Figure 1: From Web service deployment to quality assessment products. We are currently working on an improvement of UDDI, in which the server provides more than the information given in the WSDL files, it also assesses the quality of results produced by WS.

There exists many criteria to describe quality of a WS: accessibility, time needed to compute a result, privacy of data and customer, quality of results . . . We consider two criteria to define quality of a WS. The first one is results correctness (is the answer given fits with the expected one ?) and the second one is result completeness (if many answers can be given, are they all provided ?). There is many reasons that can lead to quality leak of a WS. We can classify them in two categories: static or dynamic. Classification is based on reproducibility of quality leak. Reproducible problems are considered as static, the others as dynamic.

For WS, the most obvious dynamic problem is network: packets may be lost during transport, leading to a corrupted message. As this kind of problem is not reproducible, it is quite impossible to certify that a WS is free of them. There exists few static reasons for quality leak. The first one is, obviously, bugs introduced during the development phase. The second one is software on which the WS relies: web server, libraries, other applications, etc. Bugs may exist in those software, and have an impact on WS quality. The last reason is the interaction relations between WS operations.

There exists two kinds of relations between WS operations. The first kind of relation is composition. An informal definition of composition is "a WS operation acting as a client of another operation". There exists several compositions. We consider three criteria to discriminate them: synchronicity (a composition is synchronous when the composing operation uses results of the composed operation), dynamicity (a composition is dynamic when the composed operation has been found through a UDDI server) and distributivity (a composition is distributed when the two involved operations do not belong to the same WS). Due to fault propagation, synchronous compositions have an impact on quality. If an operation bases its results on wrong data, it may be false. The second kind of relation is the temporal dependency. Its informal definition is "operation a temporally depends on the operation b if it can be called only if b has been called previously". Generally, this dependency is due to shared data, on the server side (operation b writes in a database, operation a reads what has been written) or on the client side (operation b produces a list of results, the client picks up one and uses it as a parameter of a). As for composition, temporal dependency can be responsible of fault propagation. Thus, as we see in this part, there are numerous possible quality leaks in WS. This is why we set up iTac-QoS, a quality evaluation framework for WS.

iTac-QoS: using tests to asses quality

iTac-QoS (iTac Tests And Certifies Quality of Services [START_REF] Pretre | A model-based validation framework for web services[END_REF]) is a quality evaluation framework for WS. It relies on a UDDI server, and provides quality information based on tests. Figure 1 shows the evaluation process, that we now describe. First, the WS vendor deploys its product [START_REF] Benatallah | Towards patterns of web services composition[END_REF], and creates a model for test [START_REF] Bertolino | The audition framework for testing web services interoperability[END_REF]. When he registers its product on our framework (3), provides classical information (WSDL file, description . . . ) and this model. Before test production, the framework has to perform some tasks on the model (4.1) such as interaction discovery, or string replacement. If distributed compositions have been discovered, models of the different WS need to be merged (4.2). Then, tests are generated using Test Designer (TD) a commercial tool from the Smartesting company1 . (4.3) and executed [START_REF] Bouquet | Instantiation of parameterized data structures for model-based testing[END_REF]. Result of these tests are used to compute a mark for each WS operation. When a customer searches WS on the UDDI server [START_REF] Bouquet | A subset of precise UML for model-based testing[END_REF], it provides the list of corresponding WS and the mark they obtained [START_REF] Bouquet | CLPS-B: A constraint solver to animate a B specification[END_REF]. This mark helps customers to have an idea of the quality of WS found. This paper focuses on step 4.2. In order to make our method for model merging easier to understand, we will detail two important steps of the assessment process: modeling and test generation. The modeling solution chosen was UML, because of its extensibility and reputation. WS vendors are more likely to know UML than any other modeling language. UML models required by our framework contain three types of diagrams (class diagram, instance diagram and statechart diagram), completed by OCL code. Those models have to be compliant for the test generation tool we con-sider, Test Designer (TD), as described in [START_REF] Bouquet | A subset of precise UML for model-based testing[END_REF]. The first type of diagram is class diagram. Class diagram is mandatory for two different parts of the WS: interface and data used. The interface part is composed of a class representing the WS and a set of class describing exchanged messages. This part of the class diagram is needed to produce suitable test scripts (in which messages content is set before operation call). The second part of diagram class is more classical, and represents data used by the WS (for example, a model describing an online store WS will contain classes "customer", "commands", "products" . . . ). For each operation described in the class diagram, postconditions must be expressed using OCL. They describe how the model changes when the operation has been called. We do not use pre-condition (meaning that the pre-condition is always true). Our model is built upon the defensive paradigm: error cases have to be handled in post-conditions and return error codes. We chose this solution in order to be able to capture all the possible behaviors of the WS under test.

The second diagram of our model is an instance diagram. When the class diagram gives structure of data, instance diagram gives value to them. This diagram has to present real data, because our framework is fully automatic, and nobody will translate abstract data into real data. All classes declared in the model must have at least one instance in the instance diagram. It is useless to represent all data used by the WS in the instance diagram. The modeler has to choose a subset of data and integrate them in the model. Data chosen must be as representative as possible. For example, if the modeled WS handles multiple level of users, the model must contain at least one user of each level (such as admin, member, guest, etc.). The last kind of diagram is state-chart diagram. Its goal is to model the life-cycle of the web service. This is not a mandatory diagram, but it helps test generation by describing how WS has to be used. If such a diagram is made, it must represent all possibilities of WS utilization. Figure 2 synthesizes how a WS is decomposed in its model.

We then use Test Designer (TD) to generate tests. First, it extracts every behavior described in the model. A behavior can be seen as a path in the control-flow graph of an operation written in OCL (for example, an "if" statement may create two behaviors: one when its condition is satisfied and one when it is not). Behaviors may also be extracted from a state-chart diagram (when a state is reached). All those behaviors are called test targets. For each one, TD generates a sequence of operations that aims at activating it. This sequence is called a test. An oracle is associated to each test. It is given by the state of the model after test execution and/or the values returned by the last operation call. In our framework, we only consider the latter option: if the results produced by the last operation of the test are not the expected one, the test fails. Now, we present limits of this modeling solution and why it is not adapted for WS composition testing.

The necessity of model merging

The need for model merging only occurs when a WS uses other WS. To test such a WS, there are two solutions. In the first one, the vendor of the WS produces a model describing the two WS involved in the composition. The second solution is that each vendor models its own product, and our framework merges these two models. The result of this merging is a new model which described the composition of the two WS.

We consider that the first approach is not viable, since a vendor may not be able to produce a valid model of a foreign product. A "login" operation seems simple to model: if there exists a user corresponding to login and password given in parameter, he is logged in the system. If there is no such user, an error is raised. This solution would certainly fit in most cases. But if the WS has more severe security policies, tests may fail because the model does not match with implementation. For example, composed WS security policies specify that a customer can not be logged in twice in the same time. If our framework is not aware of this, it will try to run parallel tests to accelerate quality evaluation process, and tests will fail. Security policies are one of the reasons why model of the composed WS must concord to its behavior. A simple customer is aware of how the composed WS reacts in normal conditions of use, but may not precisely know all security policies. For this reason, he is not able to produce a efficient model for this WS. A second problem of modeling a foreign WS is creation of instance diagram. As we said before, this diagram must represent real data. Someone modeling a foreign WS may not know which data it uses, and so may be unable to produce a useful instance diagram. As we explained before, the instance diagram has to be representative of the system. If data is missing, the testing tool may not be able to produce some tests.

A solution could be to get model given by the vendor when he registered his WS. As we saw before, this model contains real data that may be critical. For this reason, models can not be shared. Thus, this solution can not be used. Those two reasons led us to choose the solution of model merging. Before introducing our method, we present works about WS testing and model merging.

RELATED WORKS

In order to propose an efficient solution for model merging, we had to look at existent solutions. This section is divided in three parts. First, we introduce works using UML to model compositions. Then, we take a look at works using UML to test WS, and how they handle compositions. Finally, we present works about merging UML models.

UML for modeling web services and compositions

UML-WSC is an UML extension introduced in [START_REF] Thöne | Process-oriented, flexible composition of web services with uml[END_REF]. It is presented as an alternative for BPEL2 . Another solution for composition modeling has been introduced in [START_REF] Benatallah | Towards patterns of web services composition[END_REF]. This paper presents design patterns to easily design compositions with UML. We think that these works are not relevant for our purpose. The first reason is that those models are not designed for test production. The second one is that these models represent the whole composition. We explained before why we do not think that this kind of method is suitable for our framework. UML modeling for WS was also presented in [START_REF] Marcos | Representing web services with uml: A case study[END_REF]. This modeling solution is not suitable for test generation, because behavior of WS is not modeled. A link between UML meta-models and WS standards (WSDL, BPEL) is shown in [START_REF] Staikopoulos | A comparative study of metamodel integration and interoperability in uml and web services[END_REF].

Testing web services with UML

The choice of UML for test generation can be criticized, because of its lack of formalism. For example in [START_REF] Heckel | Automatic conformance testing of web services[END_REF], UML has been set aside because authors considered that UML could not describe precisely evolution of a WS. Our modeling solution does not suffer from this lack of formalism, as it has been shown in [START_REF] Bouquet | A subset of precise UML for model-based testing[END_REF]. There also exists works that deal with UML modeling for WS testing. Some does not take composition into account, such as [START_REF] Frantzen | Towards model-based testing of web services[END_REF]. The others deal with composition in different ways. In [START_REF] Heckel | Towards contract-based testing of web services[END_REF], when the WS under test performs a composition, it does not really communicate with another WS. The test driver emulates the composed WS. In [START_REF] Bertolino | The audition framework for testing web services interoperability[END_REF], a proxy is set up between WS under test and composed WS. That allows to verify how the WS under test acts toward composed WS. In [START_REF] Foster | Model-based verification of web service compositions[END_REF], UML is combined with BPEL in order to verify if composition workflow is respected. Those solutions are really efficient for composition testing, but do not provide clues to our main problem: how to easily make a model of the composition compliant with our test tool?

According to our knowledge, there is no solutions dealing with model merging to handle WS testing. To propose a solution, we had to investigate on works about model merging.

Model merging

Composition is not a specificity of WS. Since a few years, different solutions have been proposed for creating applications from components. Having models to represent those compositions is one goal of [START_REF] Bézivin | From object composition to model transformation with the mda[END_REF]. This paper does not show solutions for model merging, but deals with the use of metamodels to handle several kinds of components (EJB, Corba . . . ). In [START_REF] Estublier | Extending uml for model composition[END_REF], a UML profile is proposed in order to help model compositions. No explanations are given on how to produce an unique model from different models using this profile.

A model merging solution is introduced in [START_REF] Clarke | Extending standard uml with model composition semantics[END_REF]. This method

MERGING UML MODELS

We saw that model merging is necessary to test a WS performing distributed compositions. In order to illustrate our method for model merging, we introduce an example. This example is composed of two WS. The first one is an online store WS, which composes a parcel service WS. The online store WS provides operations: register, login, logout, search, addToCart and validate. The parcel service WS provides three operations: login, getPrice and logout.

We now present our method for model merging, which is done in four steps: the first one is to transform statecharts into OCL code. The second one consists in merging the different class diagrams. Then, OCL code of classes are merged in class modeling the WS under test. Eventually, instance diagram are also merged to produce the final model.

State-chart

There would be two solutions to produce a final model in which specifications of the several state-charts are captured. The first one would be to produce a final state-chart that is a combination of the different one.

The second solution would be to translate the state-charts of composed web services into OCL code, and the state-chart of the composing web services is kept in its original version.

With the first solution, the final state-chart models temporal evolution of every WS involved in the composition. With the second one, the state-chart only models evolution of the WS under test. This is why we chose this solution.

The first step in the transformation of the state-chart in OCL is to create a new enumeration ("state-List"), which lists all states described in the state-chart, including initial and final state. A new attribute ("state") is added to the class describing the web service, which has for type the enumeration previously created. Then, for each operation, we list all transitions using it as a trigger. These transitions are noted as 4-tuple, in the form {lS, g, rS, op}, where "lS" is state leaved by the transition, "g" the guard of the transition, "rS" the state reached by the transition and "op" operation that may be automatically activated when "rS" is reached. This list is the base for OCL update, which permits simulation of the state-chart.

Update of OCL code is done in two steps. First, we include all the OCL code of the operation in a "if" statement. Its condition is "(((self.state = lS1) and (g1)) or ((self.state = lS2) and (g2)) or . . . or ((self.state = lSn) and (gn)))". Thanks to this condition, the operation has effects only if it Then we simulate the evolution in the state-chart diagram.

To do this, at the end of OCL code (just before closing the "if" statement previously created), we create a list of "if" statement that make the "state" attribute's value change. They look like this following code:

i f ( ( s e l f . s t a t e = l S 1 ) and ( g 1 ) ) then s e l f . s t a t e = r S 1 and s e l f . op 1 ( ) e l s e i f ( ( s e l f . s t a t e = l S 2 ) and ( g 2 ) ) then s e l f . s t a t e = r S 2 and s e l f . op 2 ( ) e l s e . . . i f ( ( s e l f . s t a t e = l S n ) and ( gn ) ) then s e l f . s t a t e = r S n and s e l f . opn ( ) e n d i f . . .

e n d i f e n d i f

There is a particular case when the reached state is a choice point. In this case, we can not write "self.state = . . . ". Each transition is transformed into imbricated "if" statements (where the guard of the transition becomes the condition of the "if" statement). The order in transformation as no importance, except if a guard of one of these transition is "[else]". In this case, the state reached by this transition is used to produce the "else" case of the last "if" statement. The code produced by this transformation is shown in code below:

i f ( g 1 ) then s e l f . s t a t e = r S 1 and s e l f . op 1 ( ) e l s e i f ( g 2 ) then s e l f . s t a t e = r S 2 and s e l f . opn ( ) e l s e . . . i f ( gn ) then s e l f . s t a t e = r S n and s e l f . opn ( ) e l s e / * i f t h e r e i s a n ' ' [ e l s e ] ' ' g u a r d * / s e l f . s t a t e = r S else and s e l f . op else ( ) e n d i f . .

. e n d i f e n d i f

Once all operations are treated, there is one step left before state-chart diagram destruction. In some cases, operation may use the "OCLisInState(x)" keyword (that permits to know the current state of the system). We replace all these use by "self.state = xS" (where "xS" is the enumerate value corresponding to the state "x"). Now the state-chart diagram can be deleted, because it do not have any interest anymore. The next step in model merging is about the class diagram.

Class diagram

Class diagram merging is a quite simple step: all classes of the models have to be merged into a single class diagram. The main problem is aliasing: if two classes have the same name, do they represent the same thing? Obviously, we can not trust classes names. Two classes named "customer" in two models of two different WS will not represent the same customers. But two classes named "getParcelPri-ceInputMsg" will represent the SOAP message used as input parameter for the getparcelPrice operation. In order to discriminate classes modeling the only thing shared by the two model (SOAP messages and interfaces of WS), we will use WSDL files. As explained before, those files describe messages used to communicate with a WS. So we use this files to discover which classes models shared messages. All other classes are renamed before merging. To rename classes, we give a number to each model. Then, for each class which do not represent a shared message, we prefix its name with the number given to the model it belongs to. Once renaming done, all classes are sent into a new class diagram.

It is possible that shared messages are not represented exactly the same way. In this case, we keep all attributes and operations from the several classes modeling those data and include them in a single class.

Figure 3 shows merging process on a sub-part of our example. For space reasons, we simplified the diagram (for example, cardinality, name and role of association are removed). Up left part represents a sub-part from the online store model, below is shown a sub-part from the parcel service model. The right side is what is obtained when merging these two sub-parts. Once this step is finished, we can merge all OCL code into the class modeling the web service under test.

OCL

We propose a solution for OCL merging because our test tool (TD) does not handle operation call. That means that the whole OCL code must be contained in the class representing the web service under test. This merging solution is only possible because TD understands OCL code as a sequential language, not as a parallel language. If we write "self.attr = 2 and self.attr = 4", this should be evaluated as false, because, in the same time, "attr" should have for value 2 and 4. For our test tool, this means "attr has for value 2, then it has for value 4". This solution does not comply with OCL specifications (in which OCL is an constraint language, not an action language). This solution has been chosen during TD design to help model design: most people know how to use action language, and some operations could not be written with parallel interpretation of OCL.

Merging OCL code is done in two phases: the first one is the references update. In OCL code, there may be many references (to an attribute of the class, to another class . . . ), that are linked to a context. For example, the operation "login" of the class "parcelService" has for postcondition "self.user = pUser". The context is the operation "login", so "self.user" refers to the attribute "user" of the class "parcelService". In order to move all OCL code in the class representing the web service under test, we have to change all those references to adapt them to their new context. This is done by changing the "self" keyword by the path linking new context to old context. In the previous example, the code will be moved to the class "onlineStore". The classes "onlineStore" and "parcelService" are linked by the association "uses", the role on the "parcelService" class side is "parcelWS". When OCL code of the operations of the "parcelService" class is moved to the operations of "onlineStore", all references to "self" will be changed to "self.parcelWS". We also have to update a second kind of references: operation's parameters. All references to parameters must be changed by the value assigned at the call.

Once this is done, OCL code of an operation is moved before its call. The next step is to link results produced by operation to call of the operation. There is two possibilities here. The first one occurs when "result" is only affected once. In this case, this affectation is deleted, and the call to the operation is replaced by the value used to instantiate "result". In the second case, "result" has multiple affectation. Here, we create a new attribute in the class under test, having the same type than the result. Each occurrence of result will be replaced by this attribute, and the call to the operation will also be replaced by this attribute.

Code below shows evolution of code in our example. We chose composition of operation login(user, passwd) from the parcel WS by operation validate from online store WS. In order to make the example more readable, we had to simplify the code (we do not use classes defining SOAP messages).

Instance diagram

Initial state merging is done by bringing all instances of class provided in the different models into a single instance diagram. As in class diagram merging, we have to change names in order to avoid conflicts between names. The same principles than in class renaming is applied, all names are prefixed by the number previously given to the model. As classes names have been changed, we must tell to instances the new names of the class they instantiate. Then, we can move all instances to a single instance diagram. Now, we have to correct impacts of class diagram update on instances. The first action is to locate classes that received new attributes during class diagram merging. For all instances of those classes, we have to instantiate every attribute to its default value (as specified in models or arbitrarily chosen by us). The next issue is to have only one instance of each web service interface. If we keep more than one instance of a web service interface, the model will not be realistic, because there exists only one web service corresponding the instantiated class. To do this, we only keep the instance given in the model describing the concerned web service. If we have two different instance of the class modeling the interface, we consider that the vendor of the web service knows his product better than everyone else. That means that his instantiation of the class can be more trusted, so it is the one that is kept. The third problem may be caused by associations between classes, and particularly associations having a cardinality of "1" or "0..1". If we take our example of online store and parcel service again, the "parcelService" class has a relation with the "newParcelResponse" class, the cardinality on the "newParcelResponse" side is "1". In the two models, we have a instance of each of these class, and a instance of the relation liking them. We saw before that we only keep the instance provided by the parcel web service vendor. If we create a link between the "parcelService" instance and the two instances of the "newParcelResponse" class, our model will not be correct, because the cardinality of the association is broken. For the same reasons than before, we only keep the instance provided by the vendor of the parcel service, and the other one is deleted. If other links were existing between the deleted instance and other instances, they are reported to the instance kept.

We have to point at the fact that, in normal conditions of modeling, only interfaces of web services and messages received and produces can be found in two different models. This explains why we mainly talk about these kind of instances.

Once the new instance diagram is created, our model is ready for test generation.

Tests generated from merged model

TD is used to generate tests. This tool is based on the extraction of every behavior of the operations described in the model. It is important to know that TD has a particular way of interpreting OCL. OCL is usually a parallel language, used to describe the states of the model before and after the each operation. TD considers OCL as a sequential action language, having the same syntax, and in which each equality is interpreted as an assignment modifying the state variables of the models. If this particularity is helpful for model interpretation and merging, we lose the commutativity and associativity of predicates.

The operation code has to be put in the SSA form (Static Single Assignment [?]), a predicative representation to keep intermediate calculus for sequential semantics. It is obtained by adding intermediate state system variables between each assignment, our changing state function.

Based on the control flow graph of the operation in the SSA form, TD extracts the behaviors, from which the test targets are issued. Thus, a behavior is the conjunction of all predicates on paths starting from the root node of the graph, until the leafs, through a depth-first search in the graph. A test target is then computed as the set of states in which the behaviors can be activated.

For each test target, TD automatically computes a sequence of operations, a preamble, from the initial state of the system, that aims at its activation. This gives the test cases, to which an oracle is associated. This latter can be defined in two ways: the state of the model after test execution, and/or values returned by the operations of the test. In our framework, we only consider this second definition, as iTac-QoS does not have access to the internal states of the WS, and, moreover, the definition of a mapping relation between abstract and concrete values would be to costly in terms of effort asked to the WS vendor. As a consequence, if the results produced by the operations of the system under test are not the expected one, the test fails. Otherwise, it succeeds.

Our method has been applied on the example, as shown in [START_REF] Pretre | Automating uml models merging: application of the method[END_REF]. When we tried to generate tests on the final model, TD found fifty-two test goals. Only twenty-three of these were about the WS, the others were about messages getters and setters. Among these twenty-three tests goals, only twelve were reached by tests. The other test goals could not be activated for two reasons: either the goal was inconsistent or the initial state is incomplete. The main problem is that some of these test goals are introduced by the model merging process. We now present how to correct the model merging process in order to filtrate these irrelevant test goals for the test generation step.

CORRECTION OF MODEL MERGING

Our goal is to correct models obtained by model merging, (1) on figure 4. This latter illustrates our method correction and it is used as reference for the section 4.1. We focus on dead code created by the model merging method and on the lack of data in the initial state from which the two problems, inconsistent test targets and incomplete initial state, originates. First, we present in 4.1 our methods for checking the correctness of the test targets. Then, we give, in 4.2, an example of the behavior computation that we use for our detections. We further explain in 4.3 how to get the inconsistent behaviors and, eventually, how to get a minimal instanciation of the initial state in 4.4.

Correction Methods

The model-based testing approach of TD aims at producing tests that cover the tests targets, [START_REF] Bertolino | The audition framework for testing web services interoperability[END_REF]. These tests are composed of sequences of operations that reach a state in which a behavior (ie. a test target) can be activated (a). If TD can not find such a sequence, the behavior is declared unreachable (2).

As test targets coverage is used to give an indication of the quality of the produced test suite, the fact that the first two cases are reported as "unreacheable" falsifies the results of the test generation, and may let the user think that this step did not fully succeed, whereas inconsistent targets introduce a disturbance in the statistics. We attempt to resolve that.

The first step of the correction (3) is to find behavior which is inconsistent (ie. incoherente) over any possible configuration of the system. This inconsistent behavior (c) is unreachable behavior because the conditions representing the states of the behavior are not sastifiable. This may be due to an incoherence of the system (invariant or constantes) and we invite the user to correct is model by classic static verification like XX. If no error exist in the system, this behavior is extracted from a dead code because of a bad modelisation of the behavior. In the model merging process, operation calls are substitued by copies of the entire operation, in-Figure 4: Correction method stead of using only the relevant part (a specific execution path of the called operation), creating inconsistent behavior (dead code), that may only be determined by evaluating the behavior conditions. As the model merging process may produce this kind of behaviors, behaviors extracted from a dead code, we invite the user to verify their origins to filtrate them on test generation process if necessary and otherwise to correct them in the model.

The second step of the correction (4) take the rest of unreachable behavior (d) and find the behaviors which is inconsistent over the system limited by a data pool. In our case the limitation is calculate with the instance diagram. In classic Model Based Testing context this limitation is done on the model before test generation, due to its complexity, by enumerate the abstract data [XX]. These kind of inconsistent behaviors (e) is due to a problem on data. Some data is missing or must not be exists because of a problem in the data pool. We give an instantiation (g) of the system providing to the user a help to verify if the data pool is correct [START_REF] Bouquet | Instantiation of parameterized data structures for model-based testing[END_REF]. The rest of behaviors (f), which are consistent over the system with the limitation data, may be due to a problem in preamble computation of test generation, its need some object instances creation but is limited in search depth computation (a bounded time), or due to an activable behavior which is really unreachable. We give as before an instantiation (g) that may help the user to help the preamble computation or to conclude on the reachability of the behavior (5) and we invite him to use reachiability test method [XX] 3 too.

We present, in the next sections, the techniques use for 3 comme les travaux de ROMEO OH MON ROMEO... the correction more precisely.

Behavior Example

In order to illustrate our method of merging correction on the validate operation in an understable manner, we translate and more simplify this operation into an imperative oriented-object programmation language (similar to Javapseudo-Java) with quantifiers, whose semantics is equivalent to the TD interpretation of OCL. The code below gives the translation in pseudo-Java of the validate operation. We can extract the control flow graph of this translated example as done in [?]. This graph is depicted in Fig. 5.

Behaviors are then computed by a depth-first search in the resulting graph. In this paper we interest of the third behavior, the path [START_REF] Benatallah | Towards patterns of web services composition[END_REF][START_REF] Bertolino | The audition framework for testing web services interoperability[END_REF][START_REF] Boronat | Formal model merging applied to class diagram integration[END_REF][START_REF] Bouquet | A subset of precise UML for model-based testing[END_REF][START_REF] Bouquet | CLPS-B: A constraint solver to animate a B specification[END_REF][START_REF] Christensen | Wsdl 1.1[END_REF][START_REF] Clarke | Extending standard uml with model composition semantics[END_REF][START_REF] Couchot | Scalable Automated Proving and Debugging of Set-Based Specifications[END_REF][START_REF] Estublier | Extending uml for model composition[END_REF], and the fourth behavior, the path (1, 2, 4, 6, 7, 8, 10, 11, 12), of 5.

Behavior b3 of the login validation (i).

The expression of the behavior b3 is given by the following set-theoretical predicate:

currentUser.login = validateMsg.login ∧ currentUser.session.sessionId = validateMsg.sessionId ∧ psloginmsg.user2 = str.onlineStore ∧ psloginmsg.password2 = str.storePassword ∧ ¬ ( ∃ c . c ∈ ps.customer ∧ c.login = psloginmsg.user2 ∧ c.password = psloginmsg.password2)) ∧ ps.psloginresponse.resCode2 = -1 ∧ psloginresponse2 = ps.psloginresponse ∧ psloginresponse2.resCode = 0 ∧ osvalidateresponse2.resCode = 0 ∧ result = osvalidateresponse2
The fourth, b4, is the same behavior as b3 except for last part,

psloginresponse2.resCode = 0 ∧ osvalidateresponse2.resCode = 0 ∧ result = osvalidateresponse2 which became ¬(psloginresponse2.resCode = 0) ∧ osvalidateresponse2.resCode = -1 ∧ result = osvalidateresponse2

Consistency of Test Targets

Behavior b3 illustrates the problem of inconsistency of declared "unreachable" behaviors. This latter describes a login validation, that requires the user not to be logged This is clearly an incoherent behavior that is introduced by the model merging process.

The consistency checking ensures that the behavior is coherent by verifying that a proof obligation, called the behavior consistency formula (BCF), is satisfiable. A BCF is the conjunction of the predicates of a behavior, it represents the minimal condition to activate the behavior, in terms of system states that in which the behavior may be activated.

To be able to verify this formula using automated tools, it is necessary to dispose of a representation of the system state in the theory used by the prover/solver that will be employed. We have chosen to employ a set-theoretic representation of the system state. As in a previous work [?], the object oriented systems we consider are represented using sets, total functions and relations, according to the following principles. The system heap is represented by an abstract set of atoms that give the addresses of the possible objects. Existing class instances are pairwise distinct subsets of this latter. Each instance attribute is a total function mapping the instance to its value in a given domain. Each binary UML association is represented by a relation from the first to the second class instances. Thus, for a given instance, it is possible (using domain or image restriction of the relation) to know to which instances it is linked. The data model is extracted from the considered UML class diagrams. The set of existing instances is given by the instance diagram considered by TD.

BCF of the login validation.

A part of the BCF expression of behavior b3 is given by the following set-theoretical predicate: The BCF is verified using satisfiability checker tools, namely SMT-provers and a set-theoretical solver. Provers use deductive techniques that make it possible to deal with infinite data, such as abstract sets whose content and size is not specified. Constraint solver manage the constraints using consistency algorithms. Unfortunately, consistency algorithms are not complete, and thus, an enumeration of the solutions, named labeling, is potentially necessary for ensuring the satisfiability of the constraints.

In our experimentation, we use the CLPS-BZ solver [START_REF] Bouquet | CLPS-B: A constraint solver to animate a B specification[END_REF] (that natively supports set theory) and the SMT provers [START_REF] Ranise | The Satisfiability Modulo Theories Library (SMT-LIB)[END_REF], in which the set theoretical structures are expressed using the array theory (suitable for representing sets and functions) as done in [START_REF] Couchot | Guiding the Correction of Parameterized Specifications[END_REF] and [START_REF] Couchot | Scalable Automated Proving and Debugging of Set-Based Specifications[END_REF].

For the BCF of behavior b3, the tools automatically conclude on the unsatisfiability of the formula. The CLPS-BZ solver give a result in XX.XXs and the SMT provers Yices answers in YY.YYs, Z3 in ZZ.ZZs and haRVey in TT.TTs.

[[FD: un petit tableau complet des 13 insatisfiables avec les temps de calcul, ca serait vraiment nickel .

..]]

Behavior b4 consistency formula is also declare unsatifiable in similar times.

With this method, we can automatically find automatically inconsistent behavior of the operations of an UM-L/OCL model.

For the example model, 39 generate tests were generated, excluding 13 "unreachable" targets. Among these, we found 8 inconsistent behaviors meaning that the remaining 5 behaviors are "real" unreachable ones.

When checking the BCF we check if the behavior is consistent for a given set of existing instances at the initial state. This point is crucial since objects can not be created dynamically when executing the UML models (requirement of TD).

We now propose to check if the inconsistency of the behaviors may possibly due to an incorrect initial state.

Computation of a Relevant Initial State

As seen before, the inconsistency of behaviors may be due to an erroneous initial state of the UML After filtrate the inconsistent behaviors, we propose a instantiation of the system parameters for a behavior. We need enough elements in our database of object, the instance diagram, to represent a state, a collection of objects. If we haven't this, we can not represent the state, and so, we can not reach it. Our method get an instanciation of parametres providing the representation of a least one state activating a behavior.

The behavior b4 illustrate the instantiation problem. This behavior describes a login validation failure, that requires the user doesn't exist but in the instance diagram this user exist. In fact for a specific instantiation we can be log or not but not both.

It clearly an unreacheable behavior due to a lack data or a bad data. We want to compute an instantiation needed to activate the behavior in the way to compare each other.

The instantiation approach represent the data structure of the system with the set theory, a set for each parameter, and use the BCF to put enough elements in them and activate the asociated behavior.

We can only instanciate consistent behavior because compute the instantiation of an inconsistent behavior is useless as it is not activable with any instantiation.

Data Structure Representation

As in the section 4.3 we get the BCF with the system representation in predicative form over set theory. Each parameter becomes a set pairwise distinct and is considering as primary sort.

We compute the graph of sort dependency [START_REF] Bouquet | Instantiation of parameterized data structures for model-based testing[END_REF], a representation of dependency between sorts. The nodes are the sorts and the edges are the dependencies. A sort s depends of others sorts s1, . . . , sn if there exists a functional symbol whose signature is s1, . . . , sn → s. Intuitively it is the case when an element transformer adds some elements of some sorts in an other sort.

At this point, we obtain the data structure of the model over the set theory and their dependencies.

Instantiation Computation

The instantiation computation gives a over-approximation of needed objects in parameters for the behaviors and reduce it.

We want to get each variables of the BCF representing a system object and put in in the appropriated sort.

We skomelize the BCF to extract these variables, that become constants of the herbrand universe, and we use informations of the behavior predicate to fill the data structure with these constants.

A simple way to do this is to duplicate and add each constants in each sort. By this way we are sure that any variable can be instantiate by any sort.

In the same time, we use the graph of sort dependency to complete the instantiation. For each dependency and each combination of constant which can be use to apply the function, we add a new fresh constants corresponding to the result of the function application over this combination.

The problem of this approach is the Herbrand universe calculus can not terminate. This is due to a cycle in the dependency graph of sort. Indeed the computation of universe Herbrand is finite if and only if the graph is acyclic.

We check the BCF on a solver with this upper approximation as parameter domain to reduce it and obtain a minimalist behavior instantiation.

We obtain for the behavior b4 and the U SER class an intantiation without an user c where the condition c.login = psloginmsg.user2 and c.password = psloginmsg.password2 is verified.

Model Instantiation

The model instantiation consists in computing an unique instantiation for all behaviors in the same time, and so the entire model.

We extend the BCF to the Most General Behavior Consistency Formula MGBCF for the over-approximation computation and the reduction.

The Most General Behavior Consistency Formula is the conjunction P ∧ (∃X i .BCF i (X i ))

where for each behavior bi, Xi is a distinct tuple of state variable and BCFi is the BCF of bi over Xi and P is the common part of each BCF, such as parameters, constants and their properties.

We get the model instantiation with the same method of behavior instantiation but we use no more the BCF but the MBCF.

In our example we can not compute the model instantiation because the MBCF is not consistent. It due to the the condition c.login = psloginmsg.user2 and c.password = psloginmsg.password2 of the user c can not be true and false in the same time.

With this method, we can find automatically a behavior instanciation of a UML/OCL model.

For the example model, which still have 5 unreachable behaviors with unkown reason. We find an instanciation of each of them.

CONCLUSION AND FUTURE WORK

In this article, we introduced a method used to merge UML models for test generation. The method takes place in a quality evaluation framework for WS: iTac-QoS. In this framework, WS vendors produce a UML model of their product. Tests are generated from this model, and result of their execution are translated into marks, allowing customers to evaluate quality of the WS. Our framework was not able to test WS which acted as client of other WS. This was due to the fact that a WS vendor is not able to produce a valid UML model of a foreign product. We solved this problem with our model merging method. This method is done in four steps. The first one is to transform state-charts into OCL code. Once done, a new class diagram is created, which includes class from the several models. To avoid any overwriting due to two classes sharing the same name, classes are renamed before the creation of the new class diagram. The third step is to merge all OCL code into a single class (the one modeling the WS under test). We have to do this because the test tool we use (TD), does not handle operation call. The solution proposed to solve this problem is based on a another specificity of the test tool. OCL code is interpreted as a sequential language, not a parallel one. The last step of model merging is to create a new instance diagram.

To the best of our knowledge, this work is an innovation in model merging. We do not know any solution allowing to automatically merge UML models for test generation. This solution is has three main advantages. The first one is its portability. Except for OCL merging, it can be applied to classical UML model which are not designed for TD. The OCL merging solution only works because of an TD specificity, but has been designed to solve a lack of this software. The other advantages are more specifics to our framework. The first one is that our framework can now evaluate quality of WS performing distributed compositions. The last one is that it simplifies work for WS vendor: they just have to model their own product, and our framework automatically produce a model describing the whole composition. They do not have to specify composition pattern for merging. Composition specification is done by describing composed WS interface in the class diagram, and to call operations in OCL code. In order to simplify description of interfaces in class diagram, we created a tool translating WSDL files in XMI (http://lifc. univ-fcomte.fr/˜pretre/itac-qos/wsdl2xmi.php.html). With this tool, describing interfaces is really simple and automated.

We are currently working on a last improvement for our method: initial state completion. As shown in section 3.5, TD was not able to generate some tests on model produced by our example. Our goal is to be able to automatically classify those test goals: do they concern inconsistent behaviour or can we add data to make this test goal activable? Once inconsistent test goals set aside, we will have to complete models to reach all test goals.

Figure 2 :

 2 Figure 2: An overview of model's structure

Figure 3 :

 3 Figure 3: Example of class diagram merge

/

  * -ORIGINAL CODE - * / / * O p e r a t i o n : v a l i d a t e * / i f ( s e l f . p a r c e l S e r v i c e . l o g i n ( " l o g i n " , " p a s s w o r d " = " o k " ) then / * b u s i n e s s c o d e , u s e l e s s f o r t h e e x a m p l e * / e n d i f / * O p e r a t i o n : l o g i n ( u s e r , p a s s w d ) * / i f ( s e l f . u s e r s ->e x i s t s ( u | u . l o g i n = u s e r and u . p a s s w o r d = pas s w d ) then s e l f . c u r r e n t U s e r = s e l f . u s e r s ->any ( u | u . l o g i n = u s e r and u . p a s s w o r d = pas s w d ) and r e s u l t = " o k " e l s e r e s u l t = " A u t h e n t i c a t i o n f a i l e d " e n d i f / * -1 -REFERENCES UPDATE - * / / * O p e r a t i o n : l o g i n ( u s e r , p a s s w d ) E v e r y r e f e r e n c e t o s e l f i s c h a n g e d t o s e l f . p a r c e l S e r v i c e * / i f ( s e l f . p a r c e l S e r v i c e . u s e r s ->e x i s t s ( u | u . l o g i n = u s e r and u . p a s s w o r d = pas s w d ) then s e l f . p a r c e l S e r v i c e . c u r r e n t U s e r = s e l f . p a r c e l S e r v i c e . u s e r s ->any ( u | u . l o g i n = u s e r and u . p a s s w o r d = pas s w d ) and r e s u l t = " o k " e l s e r e s u l t = " A u t h e n t i c a t i o n f a i l e d " e n d i f / * -2 -PARAMETERS UPDATE - * / / * O p e r a t i o n : l o g i n ( u s e r , p a s s w d ) R e f e r e n c e s t o p a r a m e t e r u s e r a r e c h a n g e d b y i t s v a l u e " l o g i n " , a n d t h o s e t o p a r a m e t e r p a s s w d t o " p a s s w o r d " * / i f ( s e l f . p a r c e l S e r v i c e . u s e r s ->e x i s t s ( u | u . l o g i n = " l o g i n " and u . p a s s w o r d = " p a s s w o r d " ) then s e l f . p a r c e l S e r v i c e . c u r r e n t U s e r = s e l f . p a r c e l S e r v i c e . u s e r s ->any ( u | u . l o g i n = " l o g i n " and u . p a s s w o r d = " p a s s w o r d " ) and r e s u l t = " o k " e l s e r e s u l t = " A u t h e n t i c a t i o n f a i l e d " e n d i f / * -3 -CODE MERGING - * / / * O p e r a t i o n : v a l i d a t e ( ) A l l c o d e f r o m o p e r a t i o n l o g i n ( ) i s b r o u g h t b e f o r e i t s c a l l i n o p e r a t i o n v a l i d a t e ( ) * / i f ( s e l f . p a r c e l S e r v i c e . u s e r s ->e x i s t s ( u | u . l o g i n = " l o g i n " and u . p a s s w o r d = " p a s s w o r d " ) then s e l f . p a r c e l S e r v i c e . c u r r e n t U s e r = s e l f . p a r c e l S e r v i c e . u s e r s ->any ( u | u . l o g i n = " l o g i n " and u . p a s s w o r d = " p a s s w o r d " ) and r e s u l t = " o k " e l s e r e s u l t = " A u t h e n t i c a t i o n f a i l e d " e n d i f and i f ( s e l f . p a r c e l S e r v i c e . l o g i n ( " l o g i n " , " p a s s w o r d " = " o k " ) then / * b u s i n e s s c o d e , u s e l e s s f o r t h e e x a m p l e * / e n d i f / * -4 -MATCHING RESULT AND CALL - * / / * O p e r a t i o n : v a l i d a t e ( ) A n e w a t t r i b u t e , c a l l e d " t m p L o g i n " , i s c r e a t e d i n t h e c l a s s m o d e l i n g t h e o n l i n e s t o r e WS . R e f e r e n c e s t o r e s u l t c o m i n g f r o m l o g i n ( ) c o d e a r e r e p l a c e d b y t h i s a t t r i b u t e . T h e s a m e t h i n g i s d o n e f o r t h e c a l l t o t h e o p e r a t i o n . * / i f ( s e l f . p a r c e l S e r v i c e . u s e r s ->e x i s t s ( u | u . l o g i n = " l o g i n " and u . p a s s w o r d = " p a s s w o r d " ) then s e l f . p a r c e l S e r v i c e . c u r r e n t U s e r = s e l f . p a r c e l S e r v i c e . u s e r s ->any ( u | u . l o g i n = " l o g i n " and u . p a s s w o r d = " p a s s w o r d " ) and s e l f . tm pLogi n = " o k " e l s e s e l f . tm pLogi n = " A u t h e n t i c a t i o n f a i l e d " e n d i f and i f ( s e l f . tm pLogi n = " o k " ) then / * b u s i n e s s c o d e , u s e l e s s f o r t h e e x a m p l e * / e n d i f

  i f ( c u r r e n t U s e r . l o g i n = v a l i d a t e M s g . l o g i n and c u r r e n t U s e r . s e s s i o n . s e s s i o n I d = v a l i d a t e M s g . s e s s i o n I d ) { p s l o g i n m s g . u s e r 2 = s t r . o n l i n e S t o r e and p s l o g i n m s g . p a s s w o r d 2 = s t r . s t o r e P a s s w o r d and / * C o d e f r o m l o g i n i s b r o u g h t h e r e * / i f ( e x i s t s ( c | c : p s . c u s t o m e r and c . l o g i n = p s l o g i n m s g . u s e r 2 and c . p a s s w o r d = p s l o g i n m s g . p a s s w o r d 2 ) ) { / * b u s i n e s s c o d e , u s e l e s s f o r t h e e x a m p l e * / } e l s e { p s . p s l o g i n r e s p o n s e . r e s C o d e 2 = -1 } and / * e n d o f l o g i n c o d e * / p s l o g i n r e s p o n s e 2 = p s . p s l o g i n r e s p o n s e and i f ( p s l o g i n r e s p o n s e 2 . r e s C o d e = 0 ) { / * b u s i n e s s c o d e , u s e l e s s f o r t h e e x a m p l e * / o s v a l i d a t e r e s p o n s e 2 . r e s C o d e = 0 } e l s e { o s v a l i d a t e r e s p o n s e 2 . r e s C o d e = -1 } } e l s e { o s v a l i d a t e r e s p o n s e 2 . r e s C o d e = -1 } and r e s u l t = o s v a l i d a t e r e s p o n s e 2

1 psloginresponse2

 1 = validateMsg.login and currentUser.session.sessionId = validateMsg.sessionId not( currentUser.login = validateMsg.login and currentUser.session.sessionId = validateMsg.sessionId) psloginmsg.user2 = str.onlineStore and psloginmsg.password2 = str.storePassword exists(c| c : ps.customer and c.login = psloginmsg.user2 and c.password = psloginmsg.password2) not( exists(c| c : ps.customer and c.login = psloginmsg.user2 and c.password = psloginmsg.password2)) /* business code, useless for the example */ ps.psloginresponse.resCode2 = -

Figure 5 :

 5 Figure 5: Control flow graph of the pseudo Java of the validate operation

  p s . p s l o g i n r e s p o n s e . r e s C o d e 2 = -1 after a successful authentication. o s v a l i d a t e r e s p o n s e 2 . r e s C o d e = 0

  c e l S e r v i c e , o n l i n e S t o r e , c u s t o m e r 2 , c u s t o m e r 2 2 l o g i n , c u s t o m e r 2 2 p a s s w o r d , s e s s i o n 2 , s e s s i o n 2 2 i d , i s L o g g e d I n 2 , knows2 , manages2 , i s L o g g e d W i t h 2 , . . . INVARIANT o n l i n e S t o r e <: INSTANCES ONLINESTORE & p a r c e l S e r v i c e <: INSTANCES PARCELSERVICE & c u s t o m e r 2 <: INSTANCES CUSTOMER2 & c u s t o m e r 2 2 l o g i n : c u s t o m e r 2 --> STR & c u s t o m e r 2 2 p a s s w o r d : c u s t o m e r 2 --> STR & s e s s i o n 2 <: INSTANCES SESSION2 & s e s s i o n 2 2 i d : s e s s i o n 2 --> STR & i s L o g g e d I n 2 : c u s t o m e r 2 <--> p a r c e l S e r v i c e & knows2 : c u s t o m e r 2 --> p a r c e l S e r v i c e & i s L o g g e d W i t h 2 : c u s t o m e r 2 <-> s e s s i o n 2 & m anages 2 : s e s s i o n 2 --> p a r c e l S e r v i c e & . . . . & ( i ) // P r e d i c a t e o f B3

  not ( e x i s t s ( c | c : p s . c u s t o m e r and c . l o g i n = p s l o g i n m s g . u s e r 2 and c . p a s s w o r d = p s l o g i n m s g . p a s s w o r d 2 ) )

www.smartesting.com

Business Process Execution Language -A language used to model compositions aims at helping subject-oriented design. An application is not designed in a big model, but by a set of small models. Each one of those models describes a subject of the application. The method proposed in this paper may not be applied to WS model merging, because composition description requires both models. In[START_REF] Boronat | Formal model merging applied to class diagram integration[END_REF], another model merging solution is proposed. This solution only applies a merging for diagram classes, and do not take into account other types of diagram. We present now our own solution for model merging.


Anne Benoit
email: anne.benoit@ens-lyon.fr

Alexandru Dobrila
email: adobrila@lifc.univ-fcomte.fr

Jean-Marc Nicod
email: jmnicod@lifc.univ-fcomte.fr

Laurent Philippe
email: lphilippe@lifc.univ-fcomte.fr

Throughput optimization for micro-factories subject to task and machine failures

In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks of different types onto a set of machines. The originality of our approach is the failure model for such applications in which not only the machines are subject to failures but the reliability of a task may depend on its type. The failure rate is unrelated: a probability of failure is associated to each couple (task type, machine). We consider different kind of mappings: in one-to-one mappings, each machine can process only a single task, while several tasks of the same type can be processed by the same machine in specialized mappings. Finally, general mappings have no constraints. The optimal one-to-one mapping can be found in polynomial time for particular problem instances, but the problem is NP-hard in most of the cases. For the most realistic case of specialized mappings, which turns out to be NP-hard, we design several polynomial time heuristics and a linear program allows us to find the optimal solution (in exponential time) for small problem instances. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput achieved with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases where the optimal throughput can be computed.

I. INTRODUCTION

In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. Microfactories are production systems composed of cells, each one performing a particular task on complex micro-components that pass through them. The probability for a fault to arise in these cells is high, so taking faults into account is mandatory when scheduling a production. In this context, faults are however not only attached to the processing unit, as it is commonly assumed for computer based distributed systems, but also to the tasks. In a production system a task may indeed be complex to perform, for instance due to some hard manipulation, with an impact on its success ratio. If the same robot is able to perform different tasks, it may generate less faults on simple tasks than on difficult ones.

To produce a micro-product, several tasks, each characterized by a task type, must be performed by the cells in an order fixed by a precedence graph. In the micro-factory, the robots that compose the cells must however be configured before being able to process a type of task. So the issue we face is to map several tasks of different types onto a set of cells, or machines, with the objective of optimizing the number of products that output the system, in spite of the faults.

In a first study [START_REF] Benoit | Throughput optimization for micro-factories subject to failures[END_REF], we have tackled the particular case in which faults only depend on the task type. In this paper we are interested in studying the impact of a fault model linked to both tasks and machines. Our specific use case is a micro-factory, more a production system than a distributed computing system, but the results presented in this paper are more generally applicable to distributed production systems or to distributed systems where the fault probability is attached not only to resources, but also to tasks.

The paper is organized as follows. The micro-factory context and related works are presented in Section II. Section III gives a more formal presentation of the micro-factories and of the failure model. Section IV presents the optimization problems tackled in the paper. The complexity study and results are given in Section V. In the rest of the paper, we focus on a particular variant of the problem, which is NP-hard: our aim is to find a specialized mapping which maximizes the throughput of a linear chain application. In Section VI, we provide several methods to solve this problem: (i) an integer linear programming formulation of the problem which allows us to find the optimal solution for small problem instances, and (ii) polynomial time heuristics for general instances. An extensive set of simulations is detailed in Section VII, and demonstrates the efficacy of our heuristics. Finally, we conclude in Section VIII.

II. CONTEXT AND STATE OF THE ART

Micro-factories are production units designed to produce pieces composed of micro-metric elements [START_REF] Tanaka | Development of desktop machining microfactory[END_REF]. Today's microfactories are composed of micro-robots able to carry out basic operations through elementary actuators as piezo-electric beams (e.g., for gripping), stick-slip systems, etc. As these robots are usually teleoperated by a human operator, only simple tasks can be done. To perform more complex operations and to improve their efficiency, micro-factories need to be automated and robots need to be grouped in cells. Then cells will be put together and they will cooperate to produce complex assembled pieces, as it is done for macroscopic productions. Due to the piece, actuator and cell sizes, it is however impossible for human operators to directly interfere with the physical system. So it needs a highly automated command. The complexity of this command makes it mandatory to develop a distributed system to support this control. So, the cell group results in a distributed system that is very similar to a distributed computing platform. However, at this scale the physical constraints are not totally controlled so there is a need to take faults into account in the automated command.

The main issue for fault tolerant systems [START_REF] Nelson | Fault-tolerant computing: Fundamental concepts[END_REF] is to overcome the failure of a node, a machine or a processor. To deal with those faulty machines, the most common method used in distributed systems is to replicate [START_REF] Cirne | On the efficacy, efficiency and emergent behavior of task replication in large distributed systems[END_REF] the data. Those models assume that failures are attached to a machine. So the probability to get one product as a result is highly increased when the task is replicated on several machines. Once all the replicated jobs are done, a vote algorithm [START_REF] Parhami | Voting algorithms[END_REF] is often used to decide which result is the right one. However, in our case the products are physical objects and therefore can not be replicated.

In real-time systems, another model called Window-Constrained [START_REF] West | Analysis of a window-constrained scheduler for real-time and best-effort packet streams[END_REF] model can be used. In this model one considers that, for y messages, only x (x ≤ y) of them will reach their destination. The y value is called the Window. The looses are not considered as a failure but as a guarantee: for a given network a Window-Constrained Scheduling [START_REF] West | Dynamic windowconstrained scheduling of real-time streams in media servers[END_REF], [START_REF] West | Dynamic window-constrained scheduling for multimedia applications[END_REF] can guarantee that no more than x messages will be lost for every y sent messages. The Window-Constrained based failure model is adapted to a distributed system, the micro-factory. But in this paper, the objective function makes us use the failure model as the ratio x/y. In any case, the issue is to guarantee the output of a given number of products. Once an allocation of tasks to machines has been given, we can compute the number of products needed as input of the system and guarantee the output for the desired number of products.

III. FRAMEWORK

We outline in this section the characteristics of the applicative framework and target platform. Finally, we describe and motivate the failure model that we use in this work.

A. Applicative framework

We consider a set N of n tasks:

N = {T 1 , T 2 , . . . , T n }. Each task T i (1 ≤ i ≤ n) is
applied successively on a set of products. We wish to produce x out products as an output, and the total number of products being processed by a task may depend on the allocation: we process more than x out products since some losses may occur because of failures, as explained later in Section III-C. Note that all products are identical. When the context is not ambiguous, we may also design task T i by i for clarity, as for instance in the figures.

A type is associated to each task as the same operation may be applied several times to the same product. Thus, we have a set T of p task types with n ≥ p and a function t : [1..n] → T which returns the type of a task: t(i) is the type of task T i , for

1 ≤ i ≤ n.
The application is a directed acyclic graph (DAG) in which the vertices are tasks, and edges represent dependencies between tasks. An example of application with n = 5 tasks is represented on Figure 1. In the top branch of the DAG, we need to finish the processing of task T 1 on one product before proceeding to task T 2 . The join to task T 4 corresponds to the merge of two products, which produces a new unit of product composed of the two. Typically one instance of product from each predecessor in the graph is required to process with the joining task. Note that forks cannot be considered in this context as the output of one task is a physical component that cannot be split in two. Unlike data that can be easily replicated at every step of a DAG, an instance of a physical component is the result of all the preceding tasks and cannot be duplicated as it is material.

B. Target platform

The platform consists in a set M of m machines: M = {M 1 , M 2 , . . . , M m }. All machines can be interconnected: the platform graph is a complete graph. A machine handles some of the tasks at a given speed: machine M u can perform the task T i onto one product in a time w i,u . We also consider that tasks of the same type have the same execution time on a given machine, since they correspond to the same action to be performed on the products. Thus, we have:

∀i, i ′ ∈ [1, n], ∀u ∈ [1, m], t(i) = t(i ′ ) ⇒ w i,u = w i ′ ,u .
We neglect the communication time required to transfer a product from one machine to another. If a communication may not be negligible, we can always model it as a particular task with a dedicated machine (the machine responsible of the transfer of the product).

We are interested in producing the desired number of products rather than producing a particular instance of a product. So we consider that products are not identified: two products, on which the same sequence of tasks has been done, are exactly similar and we can use one or the other indifferently for further operations.

C. Failure model

An additional characteristic of our framework is that tasks are subject to failure. It may happen that a product is lost or damaged while a task is being executed on this product. For instance electrostatic strength may be accumulated on the actuator, and thus the piece will be pushed away rather than caught. Indeed, we work at a scale such that these electrostatic strengths are stronger than gravity.

Due to our application setting, we deal only with transient failures, as defined in [START_REF] Jalote | Fault Tolerance in Distributed Systems[END_REF]. The tasks are failing for some of the products, but we do not consider a permanent failure of the machine responsible of the task, as this would lead to a failure for all the remaining products to be processed and the unability to finish them.

One classical technique used to deal with failures is replication [START_REF] Cirne | On the efficacy, efficiency and emergent behavior of task replication in large distributed systems[END_REF]. However, while replication is very useful for hardware failures of machines, we cannot use it in our framework since the products are not a data such as a numerical image that we need to process, but it is a physical object. The cost of these products is very low while the equipments are expensive. Thus, the only solution consists in processing more products than needed, so that at the end, the required number of finished products are brought out.

The failure rate of task T i performed onto machine M u is the percentage of failure for this task and is denoted f i,u = li,u bi,u , where l i,u is the number of lost products each time b i,u products have been processed (l i,u ≤ b i,u ).

IV. OPTIMIZATION PROBLEMS Now that the framework has been clarified, we formalize in this section the various optimization problems that we wish to solve. Our goal is to assign tasks to machines so as to optimize some key performance criteria. The solution to one problem is thus an allocation function a : [1..n] → [1..m] which returns for each task the machine on which it is executed. Thus, if a(i) = u, task T i is executed on machine M u , and the processing of one product for this task takes a time w i,u .

We first discuss the objective criteria that we want to optimize. Then we introduce the different rules of the game that can be used in the definition of the allocation function a. The complexity of these various problems is discussed in Section V.

A. Objective function

In our framework, several objective functions could be optimized. For instance, one may want to produce a mapping of the tasks on the machines as reliable as possible, i.e., minimize the total number of products to input in the system. Rather, we consider that products are cheap, and we focus on a performance criteria, the throughput. The goal is to maximize the number of products processed per time unit, making abstraction of the initialization and clean-up phases. This objective is important when a large number of products must be produced.

Rather than maximizing the throughput of the application, we rather deal with the period, which is the inverse of the throughput. First we introduce the fractional number x i , which is the average number of products required to output one product out of the system for task T i . We can compute x i recursively for any application. Let T j be the (unique) successor of T i , if it exists (remember that we do not allow forks in the application graph). For tasks with no successor, we set x j = 1, which means that T i needs to output one product. Then, if task T i is assigned to machine M u , we have

x i = 1 1 -f i,u × x j = b i,u b i,u -l i,u × x j ,
where the fraction represents the number of products needed per successful product. Starting from the nodes with no successor, we can then compute x i for each task T i .

We are now ready to define the period of a machine: it is the time needed by a machine to execute all the tasks allocated onto this machine in order to produce one final product out of the system. Formally, we have

period(M u ) = 1≤i≤n|a(i)=u x i w i,u . (1)
The period of machine M u is the sum, for each task allocated to that machine, of the average number of products (x i ) needed to output one product, multiplied by the speed (w i,u ) of that task onto that machine. The slowest machine will slow down the whole application, thus we aim at minimizing the largest machine period. The machines realizing this maximum are called critical machines. If M c is a critical machine, then period = period(M c ) = max Mu∈M period(M u ).

Note that minimizing the period is similar to maximizing the throughput.

B. Rules of the game

In this section, we classify several variants of the optimization problem that has been introduced. A task must always be processed by one unique machine (allocation function), but different rules can be enforced about what a machine can process.

1) One-to-one mappings:

In this first class of problems, a machine can compute only one single task. This rule of the game is enforced with the following constraint, meaning that a machine cannot compute two different tasks: On Figure 2, we have an application graph (a) that must be mapped on a platform graph (b). The result is shown in (c), where we can see that one machine can handle only one task. Thus this mapping is quite restrictive because we must have at least as many machines as tasks.

∀1 ≤ i, i ′ ≤ n i = i ′ ⇒ a(i) = a(i ′ ) . (a) (b) 2 (c) 1 2 3 3 1 M 2 M 4 M 3 M 2 M 1 M 1 M 4 M 3
2) Specialized mappings: We have dedicated machines that can realize only one type of tasks. But task types are not dedicated to machines, so two machines may compute different tasks of the same type.

For instance, let us consider five tasks T 1 , T 2 , T 3 , T 4 , T 5 with the following types: t(1) = t(3) = t(5) = 1 and t(2) = t(4) = 2. If machine M 3 computes task T 1 , it could also execute T 3 and T 5 but not T 2 and T 4 . As types are not dedicated to machines, T 5 could also be assigned to another machine, for instance M 1 . This situation is described on Figure 3.

The following constraint expresses the fact that a machine cannot compute two tasks of different types: 3) General mappings: A machine can compute any task regardless of its type, thus there are no constraints. An example of this case is shown on Figure 4.

∀1 ≤ i, i ′ ≤ n t(i) = t(i ′ ) ⇒ a(i) = a(i ′ ) . (b) 1 2 3 5 4 (a) (c) 3 4 5 2 1 M 2 M 2 M 1 M 3 M 4 M 1 M 4 M 3 Figure 3: Specialized mapping (task types: t(1) = t(3) = t(5) = 1 and t(2) = t(4) = 2). (b) 1 2 3 5 4 (a) (c) 3 4 1 2 5 M 2 M 1 M 2 M 3 M 4 M 1 M 4 M 3

V. COMPLEXITY RESULTS

Complexity results are classified depending on the mapping rules. We start with one-to-one mappings, then we focus on specialized and general ones.

A. Complexity of one-to-one mappings

For one-to-one mappings, we can refine the problem complexity depending on the application class. We are particularly interested in linear chain applications, as in the example of Figure 1. Indeed, the problem remains polynomial for such applications (Theorem 1), while it turns out to be NP-hard for general applications (Theorem 2).

In this section, we introduce a new notation:

F i = 1
1-f i,a(i) . Theorem 1. Given a linear chain application and a set of homogeneous machines (w i,u = w for all i, u), finding the one-to-one mapping which maximizes the throughput can be done in polynomial time.

Proof: For a linear chain application with dependencies from task T i to task T i+1 , for 1 ≤ i ≤ n -1, the average number of products x i needed to output one product out of the system and performed by the task T i can be computed thanks to the F j , with j ≥ i, see Section IV-A:

x i = F i × x i+1 = i≤j≤n F j .
(

) 2
Of course, the values of F j depend on the allocation function. Thus, the period period(M a(i) ) = period(i) of the machine M a(i) on which the task T i is assigned to is x i × w i,a(i) = x i × w. Since all F j values are greater than 1, we have x 1 = max 1≤i≤n x i , and the period is constrained by the machine on which task T 1 is executed. The goal is thus to minimize the product 1≤j≤n F j , in order to maximize the period.

Since the mapping is required to be one-to-one, we create a bipartite graph with one node per task T j (1 ≤ j ≤ n) on one side, one node per machine on the other side. The cost of an edge from task T j to machine M u is then set tolog(1-f j,u ), so as to transform the previous product into a sum.

Then, we can find in polynomial time a minimum weight matching in this bipartite graph, for instance using the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF], [START_REF] Duff | On algorithms for permuting large entries to the diagonal of a sparse matrix[END_REF]. This matching corresponds to an assignment of tasks to machines which minimizes 1≤j≤n F j , and thus it is equivalent to a one-to-one mapping which has a minimum period.

Note that this reasoning does not hold anymore with heterogeneous machines (w i , w u or w i,u ), since the bottleneck task is not necessarily T 1 in such cases. The complexity remains open for such cases.

However, if we consider general applications rather than restricting to linear chains, the problem becomes NP-hard.

Theorem 2. Finding the optimal one-to-one mapping is NPhard, even with constant processing costs w and failure rates which depend on machines (f i,u = f u for 1 ≤ i ≤ n).

Proof: We consider the following decision problem: given a period K, is there a one-to-one mapping whose period does not exceed K? The problem is obviously in NP: given a period and a mapping, it is easy to check in polynomial time whether it is valid or not.

The NP-completeness is obtained by reduction from 3-PARTITION [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF], which is NP-complete in the strong sense. Let I 1 be an instance of 3-PARTITION: given a set {z 1 , ..., z 3n } of 3n integers, and an integer Z such that 1≤j≤3n z j = nZ, does there exist n independent subsets

B 1 , • • • , B n of {z 1 , • • • , z 3n } such that for all 1 ≤ i ≤ n, zj ∈Bi z j = Z?
We build the following instance I 2 with 3n + 1 tasks and processors:

• the application consists in n linear chains of 4 tasks sharing the same final task T (4) : for 1 ≤ i ≤ n, T

→ T (2) i → T (3) i → T (4) ; • w = 1 (constant processing cost); • f 3n+1 = 0 (machine M 3n+1 never fails); • for 1 ≤ u ≤ 3n, f u = 2 zu -1 2 zu ; • K = 2 Z . (1) i
Note that the size of I 2 is polynomial in the size of I 1 . Indeed, since 3-PARTITION is NP-complete in the strong sense, we could encode I 1 in unary, and thus the size of the instance would be in O(nZ). Moreover, the values of f u can be encoded in binary and thus their size is polynomial in the size of I 1 . Now we show that I 1 has a solution if and only if I 2 has a solution. Suppose that I 1 has a solution. We construct the allocation function a such that a(T (4) ) = 3n + 1, i.e., the last task is processed by the reliable processor, and, for

1 ≤ i ≤ n, tasks T (1) i , T (2)
i , T

(3) i are allocated to the three processors such that z u ∈ B i . Since all w are equal to 1, the period of the mapping is constrained by one of the T (1) i tasks, and their period is

P i = zu∈Bi 1 1-fu . Taking the logarithm, log 2 (P i ) = zu∈Bi log 2 ( 1 1-fu ) = zu∈Bi log 2 (2 zu ) = Z = log 2 (K)
, that means P i = K for 1 ≤ i ≤ n, and I 2 has a solution. Suppose now that I 2 has a solution. The critical resource is still one of the T (1) i , since w = 1. For each of these machines, we must have log 2 P i ≤ Z, and thus u∈alloci z u = Z, where alloc i represents the set of indices of the four processors allocated to the i th chain. To minimize this quantity, we can build a solution in which the reliable processor is processing task T (4) , and then the problem amounts to 3-PARTITION the z u . Therefore, I 1 has a solution. This concludes the proof. This NP-hardness result illustrates the additional difficulty of having a failure probability which depends both on tasks and machines. Indeed, the problem can be solved in polynomial time with fully heterogeneous machines (w i,u ) when the failure rates are identical for all machines (f i,u = f i for each machine), because we are then able to compute x i for each task, independently of the mapping (see [START_REF] Benoit | Throughput optimization for micro-factories subject to failures[END_REF]).

B. Complexity of specialized and general mappings

In [START_REF] Benoit | Throughput optimization for micro-factories subject to failures[END_REF], we proved that the problem of finding the optimal specialized or general mapping is NP-hard, even for a linear chain application with constant processing costs w, and when failure probabilities are independent of the machines (f i,u = f i ). Therefore, the problem remains NP-hard when considering more general values of failure probabilities. This illustrates the additional complexity of considering more general mapping rules rather than restricting to one-to-one mappings.

VI. SOLVING THE SPECIALIZED MAPPING PROBLEM

In the practical setting of micro-factories, general mappings are not really useful because of the unaffordable reconfiguration costs. Indeed, if a machine is processing tasks of different types, one needs to reconfigure the machine between operations.

However, when the number m of machines is greater than the number p of task types, it is always possible to find a specialized mapping, since each machine is able to process all the tasks of a same type. The key point is then to find m (or less) groups of tasks of the same type to be assigned to the m machines of the platform. Even if we restrict to specialized mappings and linear chain applications, this problem is already NP-hard, as explained in Section V-B.

Thus, we present in the following a linear program and six heuristics that return a mapping, by grouping tasks of same type onto machines.

A. Linear programming for the specialized mapping

In this section, we present a linear program to solve the specialized mapping problem presented in Section IV-B2. This linear program is a Mixed Integer Program (MIP) because it uses both integer and rational variables. Solving a MIP is NPcomplete, however efficient solvers such as Cplex [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF] makes it possible to solve small problem instances in a reasonable time. The following MIP implementation allows us to validate the relevance of the scalable heuristics that we present in the next section.

In the following, the two indices i and u denote respectively a task

T i (1 ≤ i ≤ n) and a machine M u (1 ≤ u ≤ m).
The parameters of the linear program are the following: • w i,u is the time needed by the task T i to perform one product onto the machine M u ; • f i,u is the failure rate of task T i on machine M u .

The variables needed to define the MIP are the following: • x i is the average number of products that the task T i has to perform to output one product out of the system; • For any pair (T i , M u ) we denote a i,u ∈ {0, 1} as the mapping of T i onto the machine M u : a i,u = 1 if the task T i is performed by the machine M u and 0 otherwise; • For any pair (M u , j) we denote t u,j ∈ {0, 1} such as t u,j = 1 if the machine M u is specialized to perform tasks of type j and 0 otherwise; • K ∈ Q is a rational number which represents the upper bound on the period for all machines.

The objective function is to minimize the period K, but several constraints must be enforced to have a valid mapping function (a), and a correct number of product (x).

• We ensure that each task T i is performed by one and only one machine M u :

∀i u a i,u = 1 (3)
• We ensure that each machine M u is dedicated to at most one type j:

∀u j t u,j ≤ 1 (4)
• We ensure that each task T i of type j = t(i) can be performed only by one machine M u which is specialized upon the type t(i). This constraint is not in contradiction with the fact that several tasks of same type j can be performed by the machine M u :

∀u ∀i a i,u ≤ t u,t(i) (5)
• We ensure that the average number of products that the task T i has to perform depends on the mapping of T i but also on the number of products that the task T i+1 has to perform to output one product out of the system.

∀u ∀i x i ≥ 1 1 -f i,u a i,u × x i+1
This formula can be transformed into the following linear equation:

∀i ∀u x i ≥ 1 1 -f i,u x i+1 -(1 -a i,u )M AX xi (6)
where M AX xi is an upper bound of x i such that

x i ≤ M AX xi = i≤j≤n 1 1-max 1≤u≤m (fj,u) .
• The period of each machine M u depends on the mapping and its value is bounded by K:

∀u i a i,u × x i w i,u ≤ K
This non-linear formula can be transformed into the following linear inequations. In order to make the linearization possible, we define a new positive rational variable y i,u = a i,u × x i for every task T i and for every machine M u . So the previous equation can be rewritten into the equation ( 7) under the constraints (8):

∀u i y i,u w i,u ≤ K (7)    ∀i ∀u y i,u ≤ a i,u M AX xi ∀i ∀u y i,u ≤ x i ∀i ∀u y i,u ≥ x i -(1 -a i,u )M AX xi (8)
The objective is to minimize the period under the previous constraints, thus we get the following MIP: Minimize K under the constraints (3), ( 4), ( 6), ( 7), (

B. Heuristics

Since faults occur depending on the task and the machine, we are not able to compute the number of products the task T i has to perform before knowing which task is assigned to which machine. The six heuristics presented here are executed by starting with the last task of the application graph and going backward to the first one.

H1: Random heuristic. A task T i is assigned to a machine M u if M u is free or if M u is already specialized to tasks of the type t(i). If none of these conditions are fulfilled, we try the next machine M u+1 and so on until an available machine is found.

H2: Binary search heuristic 1. This heuristic aims at optimizing the potential of the machines, i.e., the goal is to assign to each machine a set of tasks for which it is efficient. Thus, we start by sorting, for each machine M u , the set of w i,u , for 1 ≤ i ≤ n, in ascending order. Then, rank i,u represents the rank of T i in the ordered set for M u .

The heuristic performs a binary search on the period between 0 (best case) and the time required to perform sequentially all the tasks on a machine (worst case). For each value of the search, all tasks are assigned greedily (from T 1 to T n ) to machines.

We try to assign the task T i to a machine such that rank i,u is minimum. If the rank equals one, this means that the potential of M u for this task is optimal. In case of equality (several machines of identical rank for T i ), machines are sorted by non-decreasing values of w i,u . Of course, the assignment can be done only if the machine was not already specialized to a type which is different from t(i), and if the fixed period is not exceeded. Otherwise we try to assign T i to the next machine, according to their priority order for this task. If no machine is able to process T i , then no assignment is found and we try a larger period. If all tasks can be correctly assigned, we try a smaller period.

H3: Binary search heuristic 2. This heuristic is the same as H2 except that, for the assignment, the machines are sorted by their heterogeneity level in descending order. The idea is to preserve homogeneous machines for the last tasks. The heterogeneity level of M u is computed as the standard deviation of its w i,u values. Each task is assigned to the most heterogeneous machine capable of handling it. Note that for this heuristic, slow machines may be used instead of powerful ones, because of their heterogeneity level.

H4: Best performance heuristic. This heuristic assign a task T i to the machine M u with the best performance value for that task. The performance value of M u for T i is computed by w i,u × f i,u × x i .

H4w: Faster machine heuristic. This heuristic is the same that H4 except that the faster machine is selected (w i,u × x i ) without taking into account the failure rate in the assignment process.

H4f: Reliable machine heuristic. This heuristic is the same that H4 except that the most reliable machine is selected (f i,u × x i ) without taking into account the speed in the assignment process.

VII. EXPERIMENTS

In this section, we compare the six heuristics that give scheduling solutions to the specialized mapping problem with w i,u and f i,u for linear chain applications. The results are computed by a simulator, developped in C++. The performance of each heuristic is measured by its period in ms.

Recall that m is the number of machines, p the number of types, and n the number of tasks. Each point in the figures is an average value of 30 simulations where the w i,u are randomly chosen between 100 and 1000 ms, for 1 ≤ i ≤ n and 1 ≤ u ≤ m. Similarly, failure rates f i,u are randomly chosen between 0.5% and 2% (i.e., 1/200 and 1/50), unless stated otherwise.

A. Specialized mappings with m and p fixed

In this first set of experiments, the number of machines m and the number of task types p are fixed, and we plot the period for each heuristic as a function of the number of tasks n.

Figure 5 shows that H1 and H4f are not very competitive. Indeed, minimizing the failure rate does not prevent from choosing a slow machine and so getting a long period. For the next experiment, only the other heuristics are plotted. In Figure 6, H4 is slightly under the others. That is explained by the f i,u factor used by H4. Two major factors are in competition here, the speed and the reliability. A large platform is set (100 machines) to see the difference between those two factors. In Figure 7, H4w shows up to be better than the others. As a conclusion of this first set of experiments, we can say that the machine speed seems to be a more important criteria than its reliability when taking assignment choices.

To study more precisely the effect of failure rates, platforms with a high failure rate (up to 10%) are used. Figure 8 shows that periods are increasing dramatically with the number of tasks. In that special case only H2 is performing well.

B. One-to-one mappings with m and n fixed

As shown in section V-A, considering the one-to-one mapping, an optimal solution can be found in polynomial time only if the failure is attached only to tasks (f i,u = f i for 1 ≤ u ≤ m). Thus, a platform with 100 machines, 100 tasks and failures defined by f i is set. We plot the period as a function of the number of types p and run 100 simulations for each dot of the figure. Figure 9 shows H2, H3, H4w and the optimal one-to-one solution (OtO). For a better visibility the other heuristics are ignored here. H4w has the best performance and is very close to the optimal when the number of types is low. We can also see that when the number of types is high, all heuristics tend to have the same performance. This is explained by the fact that with p close to m, the way of creating the groups of tasks is less crucial.

Results are very encouraging and show that H2, H3 and H4w are respectively at a factor of 1.84, 1.75 and 1.28 from the optimal solution.

C. Comparison with the linear program

This last set of experiments compares our heuristics to the mixed integer linear program (MIP) described in Section VI-A. We restrict the study to small problem instances, so that we are able to derive a solution for the linear program, and results are reported only if 30 successful experiments over 60 trials are obtained with the MIP. Those "MIP-compatible" platforms are selected and the heuristics are run on them.

In the first experiment, we use a platform with 5 machines, and the application has 4 types. We are then able to target applications with up to 15 tasks. Figure 10 shows that H4w is once again the best heuristic but H2 and H4 are close. To measure that difference, Figure 11 shows the normalization of the heuristics with the MIP solution. Results reveal that H2, H3 and H4w are respectively at a factor of 1.73, 1.58 and 1.33 from the optimal.

For the next experiment, we use a platform with 9 machines, and the application has between 5 and 20 tasks of 4 different types. For visibility reason, we discard results of H1 and H4f from the figure. Figure 12 shows that with more than 15 tasks, the MIP is not able to find solutions anymore.

VIII. CONCLUSION

In this paper, we investigate a throughput optimization problem in the context of micro-factories subject to failures. The problem consists in assigning tasks of tree-shaped application graphs to machines. The failures that occur in the system depend on both the task and the machine on which the task is assigned. We proved that the problem to find an optimal oneto-one mapping for linear chain onto homogeneous machines is polynomial while the problem becomes NP-hard for in-tree one-to-one mappings or for specialized and general mappings. Since general mappings are not usable in practice because of reconfiguration costs, we focused on specialized mappings and proposed several polynomial heuristics to solve the problem when the graph is a linear chain. Also, a mixed linear programming formulation of the problem is given to allow us to evaluate our heuristics by comparing experimental results to the optimal, considering small problem instances. These experimental results showed that the most performing solution is obtained by H4w. This heuristic focuses on the execution speed and does not take into account the failure rate. The comparison between H4w and the optimal solutions that can be found respectively for one-to-one mappings and specialized mappings (onto small platforms thanks to the linear program) showed that H4w is respectively at a factor of 1.28 and 1.33 from the optimal. This is a very promising result, but somehow expected, which means that if we produce fast enough we overcome the faults.

As future work, an interesting problem would be to consider that the instances of a same task can be computed by several machines. Thus, the workload of a task would be divided and the throughput could be improved.

Figure 1 :

 1 Figure 1: Example of application.

Figure 2 :

 2 Figure 2: One-to-one mapping.

Figure 4 :

 4 Figure 4: General mapping (task types: t(1) = t(3) = 1, t(2) = t(4) = 2 and t(5) = 3).

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: m = 50, p = 5.

Figure 8 :

 8 Figure 8: m = 10, p = 5, 0 ≤ f i,u ≤ 0.1.

Figure 9 :

 9 Figure 9: m = 100, n = 100, f i,u = f i .

Figure 10 :

 10 Figure 10: m = 5, p = 2.

Figure 11 :Figure 12 :

 1112 Figure 11: m = 5, p = 2. Normalization with the MIP.