François Hild

published or not. The documents may come

Ultimate tensile strength during fatigue of fiber-reinforced ceramic-matrix composites


François Hild

René Billardon

Anne-Sophie Béranger

Fatigue failure maps of heterogeneous materials

come


François Hild

Didier Marquis

Olivier Kadouch

Jean-Pierre Lambelin

Analysis of the Failure of Ceramics Due to Subcritical Crack Growth

come   L'archive ouverte pluridisciplinaire


Guillaume Cantin

M A Aziz-Alaoui

Nathalie Verdière

Valentina Lanza

MULTIPLE HOPF BIFURCATIONS IN COUPLED NETWORKS OF PLANAR SYSTEMS

Keywords: Limit cycle, Hopf bifurcation, Hamiltonian system, Melnikov coefficients, coupled network

In this communication, we study coupled networks built with non-identical instances of a dynamical system exhibiting a Hopf bifurcation. We first show how the coupling generates the birth of multiple limit cycles. Next, we project those coupled networks in the real plane, and construct a polynomial Hamiltonian system of degree n, admitting O(n 2 ) non-degenerate centers. We explore various perturbations of that Hamiltonian system and implement an algorithm for the symbolic computation of the Melnikov coefficients.

Sequence of Hopf bifurcations in a directed chain of oscillators

Let us consider a directed chain of oscillators, built with the normal form of a Hopf bifurcation ρ = ρ(λ -ρ 2 ), θ = 1,

where (ρ, θ) denote the polar coordinates of a generic point (x, y) in R 2 . The whole coupled network is given by

     ρ1 = ρ 1 (λ 1 -ρ 2 1 ) -ερ 1 ρk = ρ k (λ k -ρ 2 k ) + ερ k-1 -ερ k , 2 ≤ k ≤ n -1 ρn = ρ n (λ n -ρ 2 n ) + ερ n-1 .
(

) 2
We consider that the cells have the same angular velocity, that is θ = 1, so we omit it in the equations of the network. For n = 3 and λ 3 < 0 < λ 1 < λ 2 , in absence of coupling (ε = 0), cells 1 and 2 each admit one unstable equilibrium point, and one stable limit cycle whose respective radius ρ1 , ρ2 satisfy ρ1 < ρ2 . Cell 3 admits a unique stable equilibrium point. If the coupling strength ε weakly increases, we observe the appearance of a second cycle in cell 2, and simultaneously the appearance of two different cycles in cell 3. If ε keeps increasing, the cycle of greater radius first vanishes, and finally the other cycle vanishes too. Finally, the three cells present the same * Laboratoire de Mathématiques Appliquées du Havre, Normandie University, Le Havre, France. E-mails: guillaumecantin@mail.com, aziz.alaoui@univ-lehavre.fr, nathalie.verdiere@univ-lehavre.fr, valentina.lanza@univ-lehavre.fr dynamic only for quite large values of ε. The bifurcation diagrams for cells 2 and 3 are depicted in Figure 1. This shows that a very simple network can also generate new limit cycles. In order to prove that the chain exhibits this sequence of Hopf bifurcations, we can make a local analysis based on the calculation of the first Lyapunov coefficient in the Poincaré normal form of the Hopf bifurcation [START_REF] Hassard | Bifurcation formulae derived from center manifold theory[END_REF][START_REF] Kuznetsov | Elements of Applied Bifurcation Theory[END_REF]. After basic computations, the first Lyapunov coefficient is given by

1 (µ) = - (2δ + 3µ) 2 (λ 1 -µ) 2 , (3)
where δ = λ 2 -λ 1 measures the difference of the dynamics of each node, and µ = λ 1 -ε is a translation of the coupling strength introduced in order to lighten the computations. In particular, we have

1 (0) = -4δ 2 λ 2 1
, thus the Hopf bifurcation that occurs in the network is supercritical, and degenerates into a Bautin bifurcation point if

λ 1 = λ 2 .
A longer chain can present a greater number of Hopf bifurcations. Such coupled networks have been applied to the study of neural networks or electric circuits networks [START_REF] Zhang | Multiple hopf bifurcations of three coupled van der pol oscillators with delay[END_REF]. It is remarkable that the number of limit cycles increases, but the degree of the polynomial involved in the system (2) is constant. In the following, we investigate the effect of projecting such a coupled network in the real plane.

2 Near-hamiltonian planar polynomial systems of degree n admitting n 3 limit cycles

In this section, we consider a Hamiltonian system admitting n 2 centers, and build a perturbation of that system. We show some examples for which the perturbed system admits n 3 limit cycles. To that aim, we introduce the following Hamiltonian system:

(Σ n,m ) ẋ = E y ẏ = -E x , ( 4
)
with n, m ∈ N * ,

E = m k=1 E k m l=1 l =k (x 2 + y 2 -ρ 2 l ) 2 , ( 5
)
where

ρ 1 < ρ 2 < • • • < ρ m , E k = 1 2 n i=1 (x -x i,k ) 2 + (y -y i,k ) 2 , ( 6
)
with x i,k = ρ k cos 2iπ n and y i,k = ρ k sin 2iπ n . Proposition 2.1. For any n, m ∈ N * , the system (Σ n,m ) is Hamiltonian, invariant under rotation of center (0, 0) and angle 2π n . Furthermore, it is polynomial of degree O(n + m), and it admits n × m non-degenerate centers at Now the difficult question is to find a polynomial perturbation of (Σ n,m ), of low degree, so that each center bifurcates into a given number a limit cycles. Thus we introduce for ε > 0 and r ∈ N * the near-Hamiltonian system:

(x i,k , y i,k ), 1 ≤ i ≤ n, 1 ≤ k ≤ m.
Σ ε n,m,r ẋ = E y + εP (x, y, δ) ẏ = -E x + εQ(x, y, δ), (7)
with

P (x, y, δ) = m k=1 P k (x, y, δ) m l=1 l =k (x 2 + y 2 -ρ 2 l ), (8)
where

P k (x, y, δ) = n i=1 -sin 2iπ n p k -sin 2iπ n x + cos 2iπ n y × n j=1 j =i -sin 2jπ n x + cos 2jπ n y , and p k (u) = r s=0 δ k,s u 2s+3 for 1 ≤ k ≤ m.
Proposition 2.2. For any n, m, r ∈ N * , the near-

Hamiltonian system Σ ε n,m,r is polynomial of degree O(n + m + r).
Finally, we present some examples for which we have computed the Melnikov coefficients [START_REF] Han | Hopf bifurcations for near-hamiltonian systems[END_REF] at each nondegenerate center, in order to show that Σ ε n,m,r can admit n × m × r limit cycles (see Table 1). It is a work in progress to prove it in the general case. Such a general theorem would constitute a new lower bound for Hilbert's number, that is H(n) ≥ O(n 3 ) (see [START_REF] Ilyashenko | Centennial history of hilbert's 16th problem[END_REF] and the references therein).

Table 1: Some examples of system Σ ε n,m,r admitting n × m × r limit cycles.

Figure 1 :

 1 Figure 1: Bifurcation diagrams for a three non identical cells directed chain.

Figure 2 :

 2 Figure 2: Energy levels of (Σ 5,3 ) .


Alexander Smirnov

Tatiana Levashova

Nikolay Shilov

Context-Driven Decision Support in Flexible Networked Organisations

Keywords: Operational decision support, service network, ontology, context

The paper proposes a context-driven approach to decision making in flexible networked organisations for the purpose of selecting partners for a specific task. The main idea of the approach is to represent the members of the networked organisation by services they provide. This makes it possible to replace the configuration of the networked organisation with that of services constituting it. Such representation benefits from the principles of the serviceoriented architectures, such as service autonomy, abstraction, standardisation, and reusability. For the interoperability purposes the services communicate in terms of a common ontology. To improve the flexibility of the operational decision support each particular situation is described by a narrow context that contains only information that is relevant to the situation.

Introduction

Global climate changes and globalization of the world economy set new goals for the manufacturing companies. One of such new requirements is sustainability. There are several definitions for this term (e.g., [START_REF]Sustainability in Manufacturing[END_REF]) but all of them refer to being environment friendly and as a result aiming at long-term competitive advantage. One of such definitions is given in [START_REF] Allwood | What is sustainable Manufacturing[END_REF]: sustainable manufacturing is developing technologies to transform materials without emission of greenhouse gases, use of non-renewable or toxic materials or generation of waste.

The author of [START_REF] Allwood | What is sustainable Manufacturing[END_REF] also identifies five major means helping to make manufacturing more sustainable. These means include: 1. Use less material and energy. 2. Substitute input materials: non-toxic for toxic, renewable for non-renewable. 3. Reduce unwanted outputs: Cleaner production, Industrial symbiosis. [START_REF] Dey | Understanding and Using Context[END_REF]. Convert outputs to inputs: recycling and all its variants. 5. Changed structures of ownership and production: product service systems, supply chain structure. The first four means require technological advances and fall beyond the scope of this paper. Instead, the paper concentrates on structural changes in production. A context-driven service-oriented approach to decision support in flexible networked organisations is proposed for the purpose of selecting partners for a specific task. The approach also relies at profiling, which is important for determining members capable of carrying out a specified task with the given level of sustainability.

The paper is structured as follows. The context-driven service-oriented architecture is described in sec. 2. The application of the profiling technology is described in sec. 3. Major results are summarised in conclusions.

Approach

This work is a development of the idea presented in [START_REF] Smirnov | Fusion-based Intelligent Support for Logistics Management[END_REF] aimed at knowledge management in production networks. The main idea of the developed approach is to represent the members of the flexible networked organisation by services they provide (Fig. 1). This would make it possible to replace the modelling of the networked organisation with that of services constituting it. The flexibility assumes efficient management of information and taking into account the dynamic environment. For this purpose the approach proposed actualises information in accordance with the current situation. An ontological model described by the Application Ontology (AO) is used in the approach to solve the problem of service heterogeneity. This model makes it possible to enable interoperability between heterogeneous information services due to provision of their common semantics [START_REF] Dey | Understanding and Using Context[END_REF]. Depending on the considered problem the relevant part of the application ontology is selected forming the abstract context that, in turn, is filled with values from the sources resulting in the operational context. Application of the context model makes it possible to reduce the amount of information to be processed. This model enables management of information relevant for the current situation [START_REF] Uschold | Ontologies: Principles, methods and applications[END_REF]. The operational context represents the constraint satisfaction problem that is used during configuration of services for problem solving. The access to the services, information acquisition, transfer, and processing (including integration) are performed via usage of the technology of Webservices.

The service-oriented architecture has a number of advantages resulting from its principles [START_REF] Cadrc | KML Sandbox: An Experimentation Facility Based on SOA Principles[END_REF]. Among these the following once should be mentioned (the specifics related to flexible supply network modelling are indicated with italic): 1. Service Autonomy. Services engineered for autonomy exercise a high degree of control over their underlying run-time execution environment. Autonomy, in this context, represents the level of independence which a service can exert over its functional logic. With regard to networked organisations the autonomy also reflects independence of the network members, which in real life are independent companies. 2. Service Abstraction. Further supporting service autonomy, service-oriented architecture advocates that the scope and content of a service's interface be both explicitly described and limited to that which is absolutely necessary for the service to be effectively employed. Beyond the service interface, abstraction applies to any information, in any form, describing aspects of the service's design, implementation, employed technologies, etc. This principle helps to abstract from real services provided by the networked organisation members and concentrates on their modelling via Web-services. 3. Service Standardisation. As services are typically distributed throughout networks, they must be easily accessible by other entities in terms of discoverability and consequential invocation. Given this requirement, serviceoriented architecture recommends that services adhere to standards, including, for example, standards for the language used to describe a service to prospective consumers. In the proposed approach the standardisation is achieved via usage of the common standards such as WSDL and SOAP as well as common terminology described by AO. As a result the services constituting the network are fully interoperable and can communicate with each other without any problems. 4. Service Reusability. Reusability is a central property of any successful service. It denotes the capacity of a service to be employed in support of not just one but rather a variety of business models. Service-oriented architecture promotes such functional reuse through stipulations for service autonomy and interface abstraction. With these features, the same service can be invoked by multiple consumers, operating in various business domains, without requiring the service provider to re-code service internals for each application domain. Service reusability significantly facilitates the modelling process and decreases the amount of work required for model building. Besides, the existing services of flexible supply network members can be used.

In [START_REF] Cadrc | KML Sandbox: An Experimentation Facility Based on SOA Principles[END_REF] two more service-oriented architecture principles are defined, namely service composability and service discovery. However, they are out of the scope of the presented approach.

Service-Oriented Architecture

In the proposed service-oriented architecture (Fig. 2) two types of Web-services are distinguished: core Web-services and operational Web-services.

The core Web-services are intended to create the abstract context and to monitor the business environment. The core Web-services comprise:

MonitoringService monitors the environment, identifies the types of problems arising, and produces corresponding messages.

ManagementService manages Web-services to create the abstract context. It operates with the service registry where the core services are registered.

AOAccessService provides access to the AO; AbstractContextService creates, stores, and reuses abstract contexts;

The operational Web-services organize a service network. To make the Webservices active components capable to negotiate an agent-based service model is used. Agents are intended to negotiate services' needs and possibilities in terms of the AO and "activate" Web-services when required. The services' needs and possibilities are respectively input and output arguments of the functions that the Web-services implement. The set of operational Web-services comprises:

InformationSourceService -a set of Web-services responsible for interactions with information sources of different types and for processing information provided by these sources. The following main types of information sources are distinguished: sensors, databases, Web-sites, and humans. ProblemSolvingService -a set of Web-services responsible for problem solving. MemberProfileService creates, modifies, and updates profiles of the acting resources or, in other words, the members of the networked organisation; provides access to these profiles; collects information about the members; in a context-based way accumulates information about the member activities; reveals preferences of MemberInteractionService -a set of Web-services responsible for support of and interactions with the members. They communicate between the system and the members (i) providing system messages, context-sensitive help, pictures of the current situation, results of problem solving to the members, and (ii) delivering information from the members to the system.

Profiling in Flexible Networked Organisation

Choosing the right partner in sustainable production network is essential and should be based on the potential partners' competences and sustainability. For this purpose application of the profiling technology is proposed. The structure of the networked organisation member profile is given in Fig. 3. Member competence is determined by capabilities, price-list and quickness. The network member profile comprises: General Information, Member Information, Request History, Member Preferences.

The General Information part contains information about the member organisation, i.e. name of organisation, organization identifier in the system, date the organization was founded, and URL to the organization web page. Member Information is a set of tuples describing information about the member. Each tuple has the following properties: o Member Name -the name of the member; o Location -current geographical location of the member, it can be taken into account for estimating the speed and quality of request processing in a particular situation. o Time -time zone of the member; o List of Languages -languages for contacting the member; o Rights -knowledge area that the member can access; o Group -the member can be part of a group, based on its capabilities; o Phone Number, E-mail -contact information; o Network Member Competence includes the following properties:

Capabilities -types of operations that the member can implement; Capacities -capacity of the member; Prices -prices for implementing operations by the member; Velocity -velocity of implementation operation by this member. o Member Sustainability describes sustainability properties of the member with regard to particular operations it can perform [START_REF]Sustainability in Manufacturing[END_REF]. Request History is a set of tuples. Each tuple possesses the following properties: o Request -a request to the member; o Context -is used to analyze the performance of the member (other members can see solutions generated in particular situations) and to identify detectable member preferences; o Member Preferences -stores member preferences at the moment of request initiation. They contain a snapshot of all the properties of the category "Network Member Preferences";

o Member Information -stores specific information about the member at the moment of request initiation. It contains a snapshot of all the properties of the category "Member Information". The Member Preferences part consists of Explicit Preferences and Tacit Preferences. Explicit Preferences describe member preferences that are manually introduced by a member. These preferences are used for choosing a member for a particular situation, and contain the member preference for arrival time, volume of work, and capability constraints. The latter stores several capabilities and logical restrictions from a list of all the capabilities for the domain. Tacit Preferences describe the automatically detectable member preferences. The paper describes an approach to decision support in flexible networked organisations. The approach is aimed at achieving a higher sustainability level due to maximisation of the flexibility and taking into account the sustainability properties of the organisation members. The members are proposed to be represented via Webservices. As a result the configuration of the flexible networked organisation can be replaced with that services. Usage of context makes it possible to reduce the search space since it narrows the domain. Profiling is important for determining, which member is capable of carrying out a specified task with the given level of sustainability and, hence, can be chosen as a team member.

Member

Fig. 1 .

 1 Fig. 1. Generic scheme of the approach

Fig. 2 .

 2 Fig. 2. Service-oriented architecture

Fig. 3 .

 3 Fig. 3. Networked organisation member profile

Acknowledgments.

Some of the results are due to research carried out as a part of the project funded by grants # 09-07-00436-a, 08-07-00264-a, and 09-07-00066-a of the Russian Foundation for Basic Research, and project # 213 of the research program "Intelligent information technologies, mathematical modeling, system analysis and automation" of the Russian Academy of Sciences.


Jiří Hodík
email: hodik@labe.felk.cvut.cz

Creation of Robust Schedule for Profit Based Cooperation

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

Introduction

In the domain of profit based cooperation, the cooperators are motivated to join (and to stay in) the team (e.g. Supply Chain and some types of Virtual Organizations) by expected profit. We concentrate to teams with one leader subcontracting the other partners mutually independently. Sometimes the leader has to conclude contracts with the others without having prepared whole schedule; it is to be prepared online during the negotiation about involvement the partners. Contrary to the intra-organizational scheduling, this scheduling adds requirements and constraints to scheduling methodologies. Together with complexity of the scheduling problem it is too hard to prepare valuable estimation of schedule until it is negotiated with the partners. Moreover, the leader has limited access to information about the partners' resources and such information may be distorted either by intention of partners to improve impression about their competencies, or by inexperienced guess of them.

When any already concluded due-date is not kept and if there is not enough slack, the processing of consequent tasks is delayed. It is critical mainly when it is not possible to reschedule the consequent tasks either because of high utilization of facility, or because of high penalties for not keeping the concluded due-dates.

The targeted domain relates to the supply chain planning and scheduling models class, which includes medium planning models mainly on an entire network level (e.g., project planning and scheduling or lot sizing models), as well as detailed scheduling models mainly on work-centers levels (e.g., job shop scheduling). The features crucial for the top level schedule creation are:

Members. They may be autonomous, self-oriented and distributed. Limited access to information. Nobody has direct access to the partners' internal information, neither the team leader. Partners with limited reliability. Presumption about partners' trustworthiness may be helpful in negotiation about resources allocation. Concluded contracts. Withdrawing from a contract or changing it is limited by the concluded rules and the affected partner's willingness.

There are several scenarios for team creation phase; all of them provide the plan and schedule for further team operations. The schedule is pre-negotiated with the partners before its conclusion, or involvements of the partners are being concluded continuously during the scheduling process. Reasons for continuous concluding are: (i) partners provide an expected completion time of the task but they do not share knowledge about available resources; and (ii) partners' resources may be shared within the partner; once dedicated for a task they cannot be used for the other one.

The scheduling algorithm is interlinked with a protocol for negotiation about tasks processing commitments. Often, it is possible to pre-negotiate involvement of the members, or mechanisms for its update according to current state of the team exist. There are several works extending basic negotiation protocols by non-bounding offers and commitments to improve quality of the consortium and its schedule like LAP [START_REF] Perugini | Distributed deliberative planning with partial observability: Heuristic approaches[END_REF], C-CNP [START_REF] Vokřínek | Competitive contract net protocol[END_REF], RC-CNP [START_REF] Bíba | Renegotiable competitive contract net protocol[END_REF], and RBVO formation protocol [START_REF] Vokřínek | RBVO formation protocol[END_REF]. Although any such mechanism for involvement modification may be implemented, there is a condition of available resources. Without resources, the schedule update is excluded although the negotiation protocols would support the updating process.

Scheduling Methods

Many scheduling methods for (not only hard) scheduling problems are based on priority rules comparing tasks priorities from attributes of tasks, machines, and actual state of the world. The rules are static, or dynamic (time is important as well). There are several schedule measures and objectives. Example of a schedule objective is the makespan, which is defined as the latest completion times of mutually related tasks.

Critical Path Method

The Critical Path Method (CPM) is a common method for scheduling set of tasks with defined precedence constraints. The objective to be optimized is the makespan. The method concentrates to finding and optimization of critical path under these constraints: (i) the processing time of a task is fixed, (ii) no other resource than machine time is required, and (iii) there are enough of parallel machines. The CPM inspired for Critical Path dispatching rule, which employs precedence constraints and processing times of tasks. From them the strings of processing times are counted and the head of the longest one is given the highest priority.

Robustness of Schedule

The robust schedule is required when any rescheduling may negatively influence the schedule objectives (e.g., too expensive, late, or no alternate resources). The robust schedule has "the ability to satisfy performance requirements predictably in an uncertain environment" (Pape in [START_REF] Pape | Constraint propagation in planning and scheduling[END_REF] in [START_REF] Davenport | Slack-based techniques for robust schedules[END_REF] by Davenport et al.). Pinedo presents four examples how to create a more robust schedule [START_REF] Pinedo | Planning and Scheduling in Manufacturing and Services[END_REF]:

Inserting idle/slack times. Depending on a rule, the idle times may be equal or depending on size/priority of foregoing task. Scheduling less flexible jobs/tasks first. Each task may be influenced by aggregated perturbations of its predecessors, for the less flexible ones this risk should be minimized.

Postponing the processing of an operation only if really needed. Contrary to the inventory cost point of view it is better to start as soon as possible. Bottleneck machine utilization optimization. As the bottleneck has high impact on facility capacity and makespan, is should not wait for a task.

We suggest extending the Pinedo's list of potentials to increase the robustness by: Reliable partners. The ones with higher probability to keep concluded dates should be preferred.

Various method for computation of idle times is explored e.g. by Davenport et al., who concentrate to using robustness technique for scheduling of job-shops with totally ordered tasks in domain with full access to control over the machines [START_REF] Davenport | Slack-based techniques for robust schedules[END_REF].

To evaluate robustness of the schedule, the measure must be defined. The robustness may be counted from the schedule as it is prepared, or evaluated after the scheduled tasks (real or simulated) execution. Pinedo defines a concept, which evaluates robustness of the original schedule. The measure is based on the amount of weighted slacks between the tasks' completion times and due-dates [START_REF] Pinedo | Planning and Scheduling in Manufacturing and Services[END_REF]. Kouvelis and Yu suggest criteria to evaluated schedule robustness from simulated performance [START_REF] Kouvelis | Robust Discrete Optimization and Its Applications[END_REF]: Absolute robustness. The worst scenario performance is the key. Robust deviation. Each scenario performance is evaluated against the optimal one to get the deviation. The worst deviation got is the key. Relative robustness. Similar to the robust deviation but the percentage deviation from the optimal case for the scenario is used.

Scheduling Process

The presented scheduling algorithm is based on CPM. The makespan and schedule robustness are the optimized objectives. The idea is that the critical tasks should be preferred during scheduling. Contrary, as the expected processing times are known after their negotiation, they may differ from the nominal ones. Therefore the critical path is not known until the whole schedule is prepared. It is being estimated and modified during the scheduling process. Simultaneously, keeping the negotiated times is not guarantied and therefore there is a request for robust schedules to be able to process whole job of the team.

Formal Description of the Scheduling Problem

From the task definition a nominal processing time is known. Actually, due to various capabilities and available resources, the processing times negotiated with the machines 1 may differ. While the capabilities are supposed to be constant during the lifecycle of the VO, the resources may vary in time.

The nominal processing time of the task 2 j is j p . For starting time j S , the nominal completion time is

j j j p S C
. For processing of task j on machine i the concluded completion and processing times are ij C and ij p . There may be also an expected completion time ij C' , which is delayed by ij . The expected processing time

is ij ij ij ij S C p ' ' ; relation ij ij p p' may be expected.
For estimation of the delay, only following is available: the task and its complexity (represented by j p ), concluded processing time ij p , and confidence in machine (given as some reputation model i R ). The expected delay for the task j is

i ij j ij R p p f , ,
. As the concluded processing time ij p is counted from the machine's available resources, j p may be omitted and therefore

i ij ij R p f , .

Algorithm Overview

Estimation of the critical path in any scheduling step is based on already concluded tasks processing (on the expected completion times), and nominal processing times (for scheduled yet part of the schedule). The following is defined:

JOB is a list of all tasks, n t t JOB ,..., 1 , where j t for n j 1 is a task from the list, and n is number of tasks in the list. For any couple of tasks the finish-tostart transitive precedence constraint ) from the ' OPEN list. We have adopted following ones:

Any ready task rule, by that any task ready to be scheduled is chosen. Nominal critical path rule, the next task is chosen according to the critical path counted from nominal processing times. Current critical path rule, the next task is chosen according to the critical path, which is updated according already existing schedule fragments. Longest chain of successor rules, the next task is chosen as the head of the longest chain of not scheduled tasks yet.

When the

NEXT t

is defined, the negotiation about its assignment and completion time is performed. We consider basic negotiation protocol which for defined starting time provides a set of completion times proposed by the interested machines. The decision process for determination of the winning proposal takes into account the proposed completion time and (if applied) reputation model of the proposer. We have adopted two rules for winning offer determination:

The basic rule for offer determination:

hj C C min
, where

hj C is by machine h proposed completion time for task j . The reputation rule for offer determination:

hj C C ' ' min
, where

hj C' is the expected completion times counted from reputation models of the proposers (

hj hj C C'
).

Next step to increase the schedule robustness is adding the idle time to the concluded completion time. The idle time j idle of the task j postpones earliest time for starting consequent tasks (

k j j ij k t t idle C S  ; '
). In this work, the rules for idle time determination do not consider whether the task is the earlier one or the latter one (such information could be also beneficial as described in [START_REF] Davenport | Slack-based techniques for robust schedules[END_REF]). Our rules are:

No idle time rule, 0 j idle .

The nominal processing time rule based on requested robustness and nominal processing time,

j j p f idle .
The concluded processing time rule is based on requested robustness and concluded processing time of the task,

ij j p f idle .
The expected processing time rule is based on requested robustness and expected processing time of the task, Formal description of process of preparation robust schedule preparation is presented by Algorithm 1¡Error! No se encuentra el origen de la referencia.. In the algorithm, the JOB S is the starting time of whole operation, the JOB C is its completion time.

Experiments

Several configurations of the algorithm were used; each configuration was run 20 times. In all of them simple CNP is used as a negotiation mechanism and 10 machines with limited resources shared across all tasks is involved, their capabilities vary from 70% to 90%. Each machine is able to process any task. Requested robustness is 5%. Number of tasks is counted as square of numbers from 1 to 7. For each task, its resources requirements are equal to 10 times the number of tasks IDs. Three different workflow structures (see Figure 1¡Error! No se encuentra el origen de la referencia.) defined by precedence constraints are used:

Single string, all the tasks are in one string, which is a critical path. All priority rules provide the same NEXT t .

Fig. 1. Applied workflow structures

All tasks in parallel, each parallel string consists of one task. The critical path consists of the longest task(s). "Any task" priority rule provides random NEXT t , the other rules provide the same one.

Parallel strings, all parallel strings consist of same number of tasks and have the same starting date. The tasks are distributed by rule that the following task is added to the tail of the next string. Each of priority rule may provide different NEXT t .

Results

Example of simulation runs is presented on Figure 2. The set of graphs presents makespan, robustness and scheduling order for number of tasks from 1 to 49 for parallel strings workflow structure and the priority rule of "Any task". The reputation is not assumed; no extra idle times are added.

In most of the results (not just this one), there is a break in results at position between 9 (=3 2 ) and 16 (=4 2 ) tasks. It is due to number of tasks that is higher than number of machines; the machines may be overloaded by already scheduled tasks.

The Table 1 presents selected results of simulations for 9 (maximum number of tasks, which is less then number of machines) and 49 tasks (maximum number of tasks in experiments, machines are overloaded). In all simulations the requested robustness was kept. The slack reserves were mainly in parallel structure on noncritical tasks if the priority rule was "Any task". For the linear-parallel structure, there is space for post-processing negotiation with partners about redistribution of slacks on the end of non-critical chains among their tasks. Also it is clear that assuming any information about the future tasks is better than scheduling any task of the ready ones. The average makespans does not differ significantly although the order of tasks scheduling varies, the main difference is in variances of robustness mainly when the reputation models are applied (not in scope of this paper). CP nominal 1.12 1.17 1.11 1.17 CP current 1.12 1.17 1.11 1.17 Longest successors 1.12 1.17 1.12 1.17

Fig. 2 .

 2 Fig. 2. Example of simulation results

  To be consistent with common terminology, the work-centers of the members are called machines.2 In the definitions j, k are indexes of tasks, and h, i indexes of responsible machines.

			For	t k		OPEN	the earliest possible starting time is denoted by the latest
	completion time from set of completion times of all predecessors:
	S	'	max	C	:	t		t	. If	t	t		t	t	CLOSE	then	t may be scheduled with
		j		k		k		j		k	k		j	k				j
	starting time	S' , otherwise	S' denotes that final	S	S	' .
						j					j					ij		j
			There are various priority rules for selection of the next task to be scheduled
	(
			2 CLOSE is a list of already scheduled tasks. For every k 1 t t  may be defined. The precedence graph must be acyclic. t its starting time, and concluded and (if applied) expected completion times are known. OPEN is a list of not yet scheduled tasks. Let ' OPEN denote a subset of tasks from OPEN having their precedential tasks scheduled.

1 NEXT t

  to select t NEXT from OPEN' use negotiation mechanism to get offers for of C ij , where t j = t NEXT and i are machines able to process t j use reputation model to get C ij ' select C j ' = min( C ij ) insert idle time to increase robustness move t j from OPEN' to CLOSE until OPEN' is empty C JOB = max(C j '; j, t j CLOSE)

	Algorithm 1 Process of Robust Schedule Preparation
	OPEN and CLOSE are empty
	copy t j from JOB to OPEN
	for t j	OPEN do
	setup S j to S JOB
	end for
	repeat
	for t j		OPEN do
	for t k , where t k takes precedence over t j do
	if t k	CLOSE then
	setup S j to max( C k '; t k takes precedence over t j )
	move t j to OPEN'
	end if
	end for
	end for
	use priority rule
			idle	f	p	' .
			j		ij

Table 1 .

 1 Selected simulation results

			Scheduled makespan (No. of tasks):
	Average robustness based	9		49
	on processing time:	(more machines than tasks)	(more tasks than machines)
	Structure:	Priority rule: Nominal	Concluded	Nominal	Concluded
	Linear	Any task	1.12	1.18	1.11	1.17
	Parallel	Any task	1.21	1.25	11.89	12.68
		CP nominal	1.11	1.56	14.74	16.13
	Linear-	Any task	1.12	1.17	1.21	1.28
	parallel