Erik Saule
email: erik.saule@imag.fr

Denis Trystram
email: denis.trystram@imag.fr

Multi-Users Scheduling in Parallel Systems

Keywords: Multi-objective optimization, Multi-users scheduling, approximation algorithms

We are interested in this paper to study scheduling problems in systems where many users compete to perform their respective jobs on shared parallel resources. Each user has specific needs or wishes for computing his/her jobs expressed as a function to optimize (among maximum completion time, sum of completion times and sum of weighted completion times). Such problems have been mainly studied through Game Theory. In this work, we focus on solving the problem by optimizing simultaneously each user's objective function independently using classical combinatorial optimization techniques. Some results have already been proposed for two users on a single computing resource. However, no generic combinatorial method is known for many objectives.

The analysis proposed in this paper concerns an arbitrarily fixed number of users and is not restricted to a single resource. We first derive inapproximability bounds; then we analyze several greedy heuristics whose approximation ratios are close to these bounds. However, they remain high since they are linear in the number of users. We provide a deeper analysis which shows that a slightly modified version of the algorithm is a constant approximation of a Pareto-optimal solution.

Introduction

Context and Motivation

High performance computing systems such as clusters and computational grids are generally not dedicated to a single user but they are shared among many users that each execute many jobs. These users compete to perform their respective jobs on the common resources. In such systems, the resource allocation problem is handled by a scheduler whose mechanism is rather simple: the jobs are submitted by users into queues and they are scheduled by batches. To our knowledge, the most elaborated cluster scheduler is MAUI [START_REF] Jackson | Core algorithms of the maui scheduler[END_REF]. It uses queue parameters to take into account various parameters related to the jobs' characteristics. MAUI can be used in such a way that each user has a dedicated queue. Tuning its queue's parameters enables the user to express his/her needs. However, theoretical properties of such a scheduler have not been studied from the users' point of view. Notice that most existing schedulers are centralized, which means that a single program is responsible for scheduling the jobs.

In this work, we are interested in studying the problem of scheduling jobs belonging to different users optimizing simultaneously the needs (or wishes) of each user. The users have no decision to make, they only submit their jobs to the scheduler and choose an objective function among some existing classical objectives. Our goal is to propose and analyze policies for sharing the resources taking into account the objectives of the users.

Related approaches

Several attempts have been proposed for optimizing simultaneously several objectives. We mainly distinguish between two approaches for solving the multi-users scheduling problem, namely, Game Theory and classical Multiobjective Combinatorial Optimization.

Game Theory is a very useful framework for studying systems where many agents (users in our context) interact [START_REF] Osborne | A Course in Game Theory[END_REF]. In computing systems, we distinguish two classes of problems. On the first hand, a centralized arbiter constructs a solution depending on users' decisions. In such cases, the problem is often considered under an economic perspective where prices are associated to time slots, and can be solved using auctions or division protocols. On the second hand, the users construct the solution in a distributed way. For instance, Pascual et al. address the load bal-ancing problem involving multiple organizations and show that cooperation between organizations can always been achieved for improving the global behavior [START_REF] Pascual | Cooperation in multi-organization scheduling[END_REF]. Legrand and Touati study a simple master-slave system where many non-cooperating users submit their own divisible jobs [START_REF] Legrand | Non-cooperative scheduling of multiple bag-of-task applications[END_REF].

Multi-objective Combinatorial Optimization received recently a great interest [START_REF] Billaut | Multicriteria Scheduling[END_REF]. Most investigations have been conducted as bi-objective optimization problems and sometimes involved three simultaneous objectives. Such results are based on sophisticated algorithms, however, they are difficult to extend to a larger number of objectives. And as far as we know, no generic combinatorial method is known for many objectives. Two papers that can serve as a basis for optimizing many objectives in the multi-users scheduling problem [START_REF] Baker | A multiple-criterion model for machine scheduling[END_REF][START_REF] Agnetis | Scheduling problems with two competing agents[END_REF]. Both of them address the restricted problem of two users that submit jobs to a single machine. We analyze in detail the content of both papers in Section 2.

Multi-users problems can also be considered by optimizing non-classical objective functions. User objective functions can be aggregated within a fairness function. An infinite number of fairness functions can be defined, all of them have their advantages and none can be easily discarded [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. However, the aggregation technique only makes sense when all the users' objectives are the same.

Contributions

We address in this work the problem of scheduling independent sequential jobs belonging to k different users on m processors where each user selects an objective function among a list of classical well-studied objectives, namely, makespan, sum of (weighted or not) completion times. Our main contribution is to provide algorithms that schedule the jobs of k users with different and mixed objectives with the best achievable theoretical guarantee. More precisely:

First, we show that if all users are interested in the makespan, the problem can not be approximated with a ratio better than (1, 2, . . . , k). We use here the natural extension of the approximation ratios notation where the i-th number corresponds to the approximation ratio on the i-th user objective. If all users are interested in the sum of completion times, the problem can not be approximated with a ratio better than (k, . . . , k).

Then, we propose an algorithm (called MULTICMAX) for the case where all the users are interested in the makespan and prove that it is a (ρ, 2ρ, . . . , kρ) approximation where ρ is the approximation ratio of an algorithm for the singleuser case (notice that a PTAS is known for this problem). Then, we propose an algorithm (called MULTISUM) for the case where all users are interested in the sum of completion times and prove that it is a (k, . . . , k)-approximation. Both algorithms are optimal in the sense that no algorithm achieves better approximation ratios. These ratios may appear disappointing since they depend on the number of users. However, the ratios are high because they take as a reference a non valid solution, namely the one that achieves the best objective value for each user as if he/she was the only one using the system. We show for the makespan case that an adaptation of MULTICMAX is a constant approximation of a Pareto-optimal solution.

Finally, we tackle the mixed case where k users are interested in the sum of completion times and k users are interested in the makespan. We propose for this problem an algorithm (called MULTIMIXED) that is a (k, . . . , k)approximation for the sum of completion times and a ( k k ρ, 2k k ρ, . . . , kρ)-approximation for the makespan.

Organization

The rest of the paper is organized as follows. Section 2 is devoted to the formal description of the problem and notations. It contains a brief description of two related papers and a discussion on how to extend their results to a more general framework. Section 3 states the complexity and approximability of the general problem and of all subproblems. Section 4 deals with the sub-problem where all the users are interested in the makespan. The MULTICMAX algorithm is given and analyzed. Then, a modification of this algorithm is provided and its distance to the Pareto set is computed. Section 5 describes and analyzes MULTISUM, an approximation algorithm for the sub-problem where all users are interested in the sum of completions times or the sum of weighted sum completion times. Finally, in Section 6, previous results are used to derive MULTIMIXED, an approximation algorithm for the mixed case where users may be interested in both the makespan and the sum of completion times.

Model and Preliminaries

Problem Definition and Notations

Let us consider k independent users (indexed by u) competing for the resources on a parallel platform composed of m identical resources (processors). Each user u owns n (u) jobs (denoted by

J (u) i , 1 ≤ i ≤ n (u)
). The jobs are submitted to a centralized scheduler.

Let n = k u=1 n (u) be the total number of jobs. Job J (u) i belongs to user u and has a processing time of p (u) i . A schedule is defined by the starting times of all the jobs: σ(J

(u) i ). The completion time of J (u) i is C (u) i = σ(J (u) i ) + p (u)
i . The usual constraints of scheduling must hold: each job is scheduled without interruption and no more than m jobs can run at a time.

2

The makespan of jobs belonging to u is

C (u) max = max J (u) i C (u)
i . The average completion times of jobs belonging to u is

C (u) i (the weighted variant is w (u) i C (u) i ).
In general f * denotes the optimal value of objective f . The value of f achieved in a given schedule S is denoted by f (S).

The multi-objective problem where each objective is the one chosen by each user is called M U SP (for Multi-Users Scheduling Problem). However, we will consider subproblems where the users' choice are fixed in the problem. For example, we will denote by M U SP (k :

C i ; k : C max ) the sub-problem where k users are interested in the sum of completion times and k = k -k users are interested in the makespan.

Analysis of basic related works

We recall in this section the results of two recent papers dealing with the same problem with restricted hypotheses. They can serve as a basis for solving the general multi-users scheduling (allocation) problem. Both papers (Baker and Smith [START_REF] Baker | A multiple-criterion model for machine scheduling[END_REF] and Agnetis et al. [START_REF] Agnetis | Scheduling problems with two competing agents[END_REF]) consider two users competing for the execution of their jobs on a common single resource.

In the first paper [START_REF] Baker | A multiple-criterion model for machine scheduling[END_REF], the problem is to optimize a linear combination of two of the three following objectives : makespan, sum of completion times (weighted or not) and maximum lateness. They proved that the combination of any pair of objectives can be solved in polynomial time except for the combination of maximum lateness and sum of weighted completion times. Moreover, on a single machine, if a user wants to optimize the makespan of his-her own set of jobs, then they can be merged into a single job.

These results can be extended to several users (more than 2) as long as the objective function remains a linear combination of users' objective functions: two users optimizing the makespan of their jobs can be seen as a single user that wants to optimize the sum of weighted completion times of two jobs, each one being the merge of the original jobs. Moreover, a user interested in the makespan is seen has a single task of a sum of completion time interested user. However, optimizing a linear combination of users' objectives does not seem to be a good idea. Let us consider the instance involving two users where the first one is interested in minimizing the makespan of several jobs which are merged into one big job with processing time p (1) , while the second one wants to minimize the sum of completion times of Kp (1) unitary jobs (where K is an integer). By optimizing the sum of both objectives, the system will schedule all the jobs of the second user before scheduling the job of the first one. This behavior is unfair because the jobs of the first user can be arbitrarily delayed by jobs of the second user when K goes to infinity. Moreover, the first user has incentive to lie: he/she would have obtained a better performance if he/she declared to be interested by the sum of completion times instead of the makespan... In the terminology of Game Theory, this method does not guarantee the truthfulness [START_REF] Archer | An approximate truthful mechanism for combinatorial auctions with single parameter agent[END_REF].

A second argument against using similar approaches based on linear (weighted) combinations of objectives is that in the objective space, the Pareto set1 of such a problem is not always convex or all Pareto optimal solutions may be aligned. Thus, it is possible to achieve only a few interesting solutions by such a technique.

The second paper of Agnetis et al. [START_REF] Agnetis | Scheduling problems with two competing agents[END_REF] also concerns the optimization of the objectives of two users (among the makespan, the sum of completion times and the sum of weighted completion times) on a single common resource. They distinguish between two questions: First, they are interested in Constrained Optimization Problems where one objective is fixed as a constraint and the second objective is optimized. The authors show that when both users are interested in the makespan, the problem can be solved in polynomial time. If they are both interested in the sum of completion times, the problem becomes binary NP-hard and they provide a pseudo-polynomial dynamic program to solve it. With mixed objectives, if one user is interested in the weighted sum of completion times, the problem is binary NP-hard. Other cases are polynomial.

Secondly, they are interested in Pareto Optimization

Problems in which the output of the algorithm is all Pareto optimal schedules. The main issue is the cardinality of the Pareto set. When one user is interested in the makespan, if the other one is interested in the makespan or in the sum of completion times, the cardinality of the Pareto set is polynomial. If the second one is interested in the weighted sum of completion times, the problem is open. If both users are interested in the sum of completion times, the cardinality of the Pareto set can be exponential.

All those results are interesting from a theoretical point of view. For instance, the constrained version of a multiobjective problem helps to construct an approximation of the Pareto set for this problem [START_REF] Angel | Approximation results for a bicriteria job scheduling problem on a single machine without preemption[END_REF]. They help to determine the frontier between easy and hard problems. However, they can not be directly used to deal with the multimachine/multi-users case. They do not provide a generic way to optimize different objective functions.

Discussion on Objective Functions

In this section, we give another point of view about this multi-user optimization problem by showing how to reduce the optimization of a fairness function to the problem we are addressing.

In the literature, when scheduling individually important jobs of different sizes, the problem of fairness arises. It can be tackled using the stretch objective function which is defined as the time the task spent in the system normalized by its processing time. Stretch optimization was studied on non-preemptible independent tasks [START_REF] Bender | Improved algorithms for stretch scheduling[END_REF]. In a sense, the stretch of a job is a degradation factor it obtains by not being the only job in the system. The stretch is also used in bagof-task applications [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF] which is comparable to our setting. In bag-of-tasks, the application is composed of small jobs (possibly infinitely small jobs), whereas in MUSP the user submits a set of jobs.

Thus, the idea is to optimize a stretch-like function derived from the user objective function. If f (u) is the objective function of user u, the degradation of u in schedule S is

d (u) (S) = f (u) (S) f (u) * where f (u) * is the minimum value of f (u) .
Stretch of applications needs an aggregation function to ensure fairness. Three of them are usually considered which corespond to the standard norms L ∞ , L 1 , L 2 : minimizing the maximum of stretches, the sum of stretches and the product of stretches. Thus, optimizing the sum (or maximum, ...) of degradations seems the logical extension, in the following let L be the considered norm.

Such an objective function would be NP-hard to optimize and approximation algorithms would be needed. However, no non-trivial lower bound on such functions is known which is a pre-request to design approximation algorithms.

The point is that L is decreasing and monotone function of the degradations according to the Pareto order and the degradation of user u is an increasing function of f (u) . Thus, in the multi-objective problem of minimizing the tuple (f (1) , . . . , f (k) ), if S Pareto-dominates S , then L(S) ≤ L(S ). In other words, solving the multi-objective optimization problem will solve the problem of optimizing L since the minimum of L is reached by a Pareto optimal solution.

Complexity and Inapproximability

We first study the complexity of all sub-problems (all possible combinations of objectives). Then, we focus on bounding the performance of the best achievable approximation algorithms.

Optimizing the makespan of a single set of jobs (i.e. one objective) on an arbitrary number of processors is strongly NP-hard [START_REF] Garey | Computers and Intractability[END_REF]. Thus, as soon as one user wants to optimize the makespan, the problem becomes strongly NP-hard. Let us now concentrate on the case where all the users are interested in the sum of completion times which is a sub-case of the weighted sum of completion times problem. Recall that the decision problem restricted to two users interested in the sum of completion times on a single machine is binary NP-complete [START_REF] Agnetis | Scheduling problems with two competing agents[END_REF]. Thus, on an arbitrary number of processors, the problem is harder. In conclusion, all optimization sub-problems we are interested in are NP-hard.

As all sub-problems are NP-hard, it is likely that no optimal polynomial-time algorithms can be designed. Thus, we are interested in polynomial approximation algorithms. In the reminder of this section, we are looking for lower bounds on best achievable approximation vector-ratios of a single solution. Formally, a scheduling algorithm algo has a performance vector-ratio (ρ 1 , . . . , ρ k ) if for all valid schedules S and for all users u, f (u) (algo) ≤ ρ u f (u) (S) where f (u) is the objective of user u. First, let us remark that the optimal value of one particular objective function is obtained by scheduling optimally the jobs of one user like if he/she was the only user of the machine. Thus, all known bounds on the best approximation ratios for the single user case are still valid.

We now examine two sub-problems successively, each one is for an arbitrary fixed number of machines that serve for establishing inapproximability bounds. These results are summarized in Propositions 3.1 and 3.2. They are expressed as "The problem can not be approximated with a performance vector ratio better than (ρ 1 , . . . , ρ k )" where 'better than' stands for the component wise relation. This means that there is no (ρ 1 -, ρ 2 . . . , ρ k ) or even (ρ 1 , . . . , ρ i-1 , ρ i -, ρ i+1 . . . , ρ k )-approximation algorithm ( > 0). However, this formulation does not prevent a (ρ 1 , . . . , ρ i-1 , ρ i -, ρ i+1 , . . . , ρ j-1 , ρ j + , ρ j+1 , . . . , ρ k )-approximation algorithm from existing.

Proposition 3.1 M U SP (k : C max ) can not be approximated with a performance vector-ratio better than (1, 2, . . . , k).

Proof. In this case, all the users are interested in the makespan. Let us consider the following instance. Each user has only m jobs. All the jobs have the same unit length. Obviously, for all the users independently, the best makespan that can be achieved is 1. In any efficient schedule, one user will have a makespan of 1, another one will have a makespan of 2, and so on. Thus, it is impossible to obtain an algorithm that guarantees a vector-ratio better than (1, 2, . . . , k). Moreover, remark that any permutation of this vector-ratio can be obtained. However, the vector-ratio (1, 2, . . . , k) is not achievable in all instances. For example, consider the instance where the k -1 last users have m jobs of unit length and the first one has m jobs of processing time k. In such an instance, if the first user gets a performance ratio of 1, all other users will get a performance ratio worse than k.

In conclusion, the best achievable vector-ratio is valid for a permutation depending on the instance. Therefore, if the scheduler aims at obtaining a performance vector-ratio of (1, 2, . . . , k), then it is impossible to guarantee that a given user will get a performance ratio better than k without having a look at other users' jobs. Proposition 3.2 M U SP (k :

C i ) can not be approximated with a vector-ratio better than (k, . . . , k).

Proof. Let us consider the instance with k users who are interested in the sum of completion times. Each user owns n (u) = mx unitary jobs (∀u, ∀i, p

(u) i = 1).
The optimal schedule for one user is straightforward since all tasks have the same length i.e, x tasks per processor. The optimal value for each user u is

C (u) * i = m x i=1 i = m x(x+1)

2

. Whatever the order of the tasks, the optimal sum of completion times of all the tasks is given by any well balanced schedule :

C * i = m kx i=1 i = m kx(kx+1) 2 .
Remark that the sum of completion times of all the tasks is the sum of the objective values of all the users :

C i = u C (u)
i . Thus, all the values of the C (u) i that lead to

C * i = u C (u) i
are Pareto-optimal (supposing the solution is feasible). In particular the tion that distributes C * i equitably between the k users is Pareto-optimal. In such a solution, the objective values are ∀u, C

(u) i = P C * i k = m kx 2 +x 2
and the associated performance vector-ratio is

P C (u) i P C (u) * i = m(kx 2 +x)/2 m(x 2 +x)/2 = k -k-1
x+1 . This ratio tends to k when x goes to infinity.

The existence of an approximation algorithm with a ratio better than (k, . . . , k) would produce a solution which is better than a Pareto-optimal solution on the instance described in this proof for a well chosen value of x.

Notice that the previous inapproximability results have been obtained from the non existence of a solution reaching a given performance vector. Thus, they are not complexity results i.e, approximation algorithms with better bounds would not exist even if P = N P .

M U SP (k : C max )

Absolute Approximation

We proved in the last section that M U SP (k : C max ) is unary NP-hard. It is even true for a single user. Moreover, no algorithm can guarantee a constant performance vectorratio better than (1, 2, . . . , k) over all permutations of objective functions. If the number of processors is fixed, the single user case can be approximated by a PTAS proposed by Hochbaum and Shmoys using dual approximation [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems: Pratical and theoretical results[END_REF]. Other approximation algorithms exist for the case of arbitrary number of processors. For instance, List Scheduling where the jobs are ordered by decreasing processing times (also called LPT order) is a 4 3 -approximation algorithm with low cost complexity [START_REF] Leung | Some basic scheduling algorithms[END_REF]. A better 5 4 -approximation algorithm has been proposed in [START_REF] Kellerer | Algorithms for multiprocessor scheduling with machine release times[END_REF].

Consider the following algorithm called MULTICMAX. For each user u, compute a schedule S (u) with a ρapproximation algorithm. Then, sort the users by increasing values of C (u) max (S (u) ). Finally, schedule jobs of user u according to S (u) between u <u C (u ) max (S (u ) ) and

u ≤u C (u ) max (S (u ) ).
The following theorem states the theoretical guarantee of this algorithm. Proof. There are two properties to check. First, the schedule is valid. Indeed, the jobs of each user u are scheduled in disjoint intervals of length C (u) max (S (u) ) according to S (u) . Secondly, the performance vector-ratio is (ρ, 2ρ, . . . , kρ). Indeed, C A straightforward corollary is that if an exact algorithm is used (ρ = 1), the vector-ratio obtained is (1, 2, . . . , k) which ensures the tightness of the bound given in Proposition 3.1. Using the PTAS proposed by Hochbaum and Shmoys, the algorithm is a (1 + , 2 + 2 , . . . , k + k )approximation algorithm.

The permutation of objectives problem pointed out in Section 3 also holds in Theorem 4.1: the theorem is valid for a given unknown permutation of users. Remark that one user can not know in advance his/her rank in the algorithm.

Distance to the Pareto Set

The performance vector-ratio of MULTICMAX depends on k and it has been shown to be tight (using an exact algorithm for computing S (u) ). One could argue that such a solution is inefficient and thus it is not interesting. However, the performance vector-ratio represents the distance between the proposed schedule and the solution that reaches the absolute best makespan for every users which is not feasible (in the general case). In this section, we present a class of solutions List, which are a MULTICMAX with ρ = 2, and which contains efficient schedules that are close to the Pareto set. We will prove this result for a restricted class of instances where each user submits a reasonable number of jobs, namely ∀u, p

(u) i > mC (u) * max 2
(Remark that such instance are not trivial : the instance that provided the approximability lower bound respects this property and the instance used to proove the NP-completeness of the makespan minimization problem also respects it). Our purpose is to show that a constant approximation of a Pareto optimal solution can be constructed while keeping the absolute bound.

List Scheduling is a mechanism that greedily schedules jobs as soon as possible in any given order [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF]. It is well-known that List Scheduling is a 2-approximation algorithm. More precisely, if the jobs are sorted according to the given order, we have the following property: ∀i, C i ≤

P i ≤i p i m + (1 -1 m )p i .
We denote by List the schedules obtained by List Scheduling using any order such that all the jobs of user u are scheduled after each job of user u < u where the users are sorted in non-decreasing order of C (u) * max . One can easily see that each solution of List can be worsened to be a solution of MULTICMAX with ρ = 2. Thus, any solution of List is a (ρ, 2ρ, . . . , kρ)approximation algorithm of M U SP (k : C max ).

We need a reference solution on the Pareto set for computing the distance between the solutions of List and the Pareto set. Let us define a set of schedules Lex that are optimal for the lexicographical order of the users. Formally, Lex is defined as: ∀S ∈ Lex, C Proof. Recall first that in an efficient schedule, all the idle time are at the end of the schedule since all the jobs are released simultaneously.

Let J (u ) i be the latest job to complete in any S ∈ Lex(u). p

(u ) i ≤ C (u) * max since p (u ) i ≤ C (u ) * max ≤ C (u) * max (for u ≤ u) . By contradiction, if Idle(Lex(u)) ≥ mC (u) *
max , there exists a processor that is idle for more than C (u) * max units of time. This processor could have schedule J (u ) i sooner. Thus, schedule S does not belong to Lex(u).

If the previous hypothesis ∀u, p

(u) i > mC (u) * max 2
does not hold, one can construct an instance where a user with a single job should be scheduled at time 0. Any solution of List does not schedule it that soon. We can derive the following lemma from the hypothesis.

Lemma 4.3 ∀u > 2, if C (u-1) max (Lex) < C (u-2) max (Lex) then C (u) max (Lex) > C (u-2) max (Lex) Proof. If C (u-1) max (Lex) < C (u-2) max (Lex) then Idle(Lex(u -1)) = Idle(Lex(u -2)) -p (u-1) i . Recalling that Idle(Lex(u -2)) < mC (u-2) * max (from Property 4.2) leads to Idle(Lex(u -1)) < mC (u-2) * max - p (u-1) i . Since p (u-1) i > mC (u-1) * max 2
(from the hypothesis) and

C (u) * max ≥ C (u-1) * max ≥ C (u-2) * max
(from the order of the users), we obtain Idle(Lex(u -1)) <

mC (u) * max 2
. Thus, all the jobs of user u can not fit in the idle time before C (u-2) max (Lex). At least one job of user u finishes after this value.

Corollary 4.4 ∀u > 2, C (u) max (Lex) > C (u-2) max (Lex)
The proof of the corollary comes directly from the previous lemma.

The next theorem proves that any solution of List is a 3-approximation of Lex.

Theorem 4.5 ∀u, C (u) max (List) ≤ (3 -1 m )C (u) max (Lex) Proof. Let p (u) max = max i p (u)
i . From the standard analysis of List Scheduling [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF], we derive:

C (u) max (List) ≤ P u ≤u P i p (u ) i m + (1 -1 m )p (u)
max which can be rewritten as:

C (u) max (List) ≤ P u ≤u-2 P i p (u ) i m + P i p (u) i m + P i p (u-1) i m + (1 -1 m )p (u) max
The first term of this expression is less than C Finally, we obtain the following expression:

C (u) max (List) ≤ C (u) max (Lex) + (2 -1 m )C (u) * max . As C (u) * max ≤ C (u)
max (Lex), we obtain the bound.

In the previous analysis, it is required to know the optimal makespan of each user for constructing a solution in List. However, if only an ρ-approximation of the makespan of each user is known, the approximation of a solution in List remains constant.

M U SP (k : C i )

We are now interested in the case where all the users want to optimize the sum of completion times of their jobs. Recall that for a single user, this problem can be solved in polynomial time by scheduling the tasks in non decreasing order of their processing time. This algorithm is called SPT [START_REF] Leung | Some basic scheduling algorithms[END_REF]. However, for more than one user, this problem is NP-hard. Moreover, no algorithm can guarantee a constant vector-ratio better than (k, . . . , k) over all permutations of objective functions.

To solve this problem, we first study the single processor case and we analyze its performance vector-ratio. Finally, we extend the analysis to an arbitrary number of processors.

Preliminary analysis for m = 1

Similarly as in Section 4, we compute the final schedule of all users' jobs from schedules of each user's jobs. Let us consider S (1) , . . . , S (k) independent schedules for the jobs of each user. We construct schedule S using the following greedy algorithm called AGGREG: schedule jobs in nondecreasing order of C (u) i (S (u) ). This simple algorithm ensures that the completion times are not degraded by a factor greater than k. This is stated by the following proposition.

Proof.

Let us consider job

J (u) i . Notice first that C (u) i (S) ≤ C (u ) i (S) implies C (u) i (S (u) ) ≤ C (u ) i (S (u ) ).
Thus, for each user u , the set of job J (u ) scheduled before

C (u) i (S) in S is such that J (u ) i ∈J (u ) p (u ) i ≤ C (u) i (S (u) ).
There is one such set per user. J (u) i completes when all the jobs of ∪ u J (u ) are completed. Thus,

C (u) i (S) = u J (u ) i ∈J (u ) p (u ) i ≤ kC (u)
i (S (u) ) which proves the proposition.

The previous algorithm considers each user with the same priority. We can derive another algorithm that does not give the same priority to the users. Let λ 1 , . . . , λ k be real positive values such that u λ u = 1. We construct schedule S λ using the following greedy algorithm called AGGREG λ : schedule the job in non-decreasing order of

C (u) i (S (u) ) λu . Remark that if ∀u, λ u = 1
k then S = S λ . The completion times in S λ of jobs belonging to user u are not degraded by a factor greater than 1 λu . This is stated by the following proposition. The proof is similar to the proof of Proposition 5.1 and thus it is omitted.

Proposition 5.2 Schedule S λ is such that ∀u, ∀i ≤ n (u) , C (u) i (S) ≤ C (u) i (S (u) ) λu .
Using AGGREG, it is possible to mix k schedules and ensure that the completion time of each job in each schedule is not degraded by a factor greater than k. In particular, if a schedule is a ρ-approximation on the sum of (weighted or unweighted) completion times then by mixing it with the k -1 other schedules, the final schedule is a (kρ)approximation for this user. C i ) on one processor.

The proof of this lemma comes directly from the optimality of SPT for one user and from Proposition 5.1.

Extension to m processors

The previous lemma states an interesting result for the single machine case. In this section, we show that the general framework can be easily extended to m processors.

We now describe the MULTISUM algorithm. Let S (1) , . . . , S (k) be k SPT schedules on m processors. Each schedule S (u) can be seen as m independent schedules denoted S (u) 1 , . . . , S (u) m . For each processor j, schedules S (u) j of each user u are mixed by AGGREG into S j . Then, a global schedule on m processors is constructed by executing S j on processor j (1 ≤ j ≤ m).

Theorem 5.4 MULTISUM is a (k, . . . , k)-approximation algorithm for M U SP (k : C i ).

The proof of Theorem 5.4 comes directly from Lemma 5.3 and from the independence of processors.

Optimizing the sum of weighted completion times case is NP-hard even for a single user. However, there exist approximation algorithms such as the one proposed by Hall et al. that reaches a performance ratio of (4 -1 m ) [START_REF] Hall | Scheduling to minimize average completion time: Off-line and on-line algorithms[END_REF]. Using a ρ-approximation algorithm instead of SPT leads to the following MULTIWEIGHTEDSUM algorithm. 6 Mixed objectives

Multi-objective optimization

In this section we are interested in the mixed objective case where k users are interested in the sum of completion times and k users are interested in the makespan :

M U SP (k : C i ; k : C max ) with k = k + k .
Remark that the technique presented in the last sectionfor the sum of completion times also works for the makespan objective. Every user will get a performance of k. However, it is possible to improve this result. Indeed, if no users are interested in the sum of completion times, we can obtain a performance ratio of (1, . . . , k). While if one user is interested in the sum of completion times, the ratio of each user interested in the makespan is worsened to k.

The idea in this section is to incorporate techniques presented in Section 4 and 5 into a single scheduling algorithm called MULTIMIXED.

Consider the sub-instance of the k users interested in the makespan. Let S (cmax) be the schedule generated by MULTICMAX (using any ρ-approximation algorithm) on this sub-instance. For each user u interested in the sum of completion times, let S (u) be a SPT schedule of jobs belonging to u on m processors. Let S (u) j be the sub-schedule of S (u) on the j-th processor (S (cmax) j is similarly defined).

For each processor j, mix all the schedules S (u) j (∀u ≤ k ) and S (cmax) j into S j using AGGREG λ with λ u = 1 k , ∀u ≤ k and λ cmax = k k . Construct the final global schedule S by executing S j on processor j.

The theoretical guarantee of MULTIMIXED is stated by the following theorem.

Theorem 6.1 MULTIMIXED is a (k, . . . , k, k k ρ, 2k k ρ, . . . , kρ)-approximation algorithm for M U SP (k : C i ; k : C max ).
Proof. All the users interested in the sum of completion times get a performance ratio of k. The corresponding proof is similar to the one of Theorem 5.4 and it is omitted.

Consider now user u interested in the makespan. Without loss of generality, we have C

Optimizing the fairness on degradations

In Section 2.3, we introduced a related problem, that is the optimization of a fairness (in fact a norm) objective function of degradations. By using the monotony of norms according to the Pareto order, we show that solving the multi-optimization problem solves the norm optimization problem. The minimum of the objective function is reached by a Pareto optimal solution. The algorithms we proposed do not generate all the Pareto set. However, several interesting properties can be derived.

First, the vector-approximation ratio of an algorithm implies an approximation for the norm optimization problem. For instance, consider the maximum of degradation (L ∞ norm), a (ρ, ρ, . . . , ρ)-approximation algorithm is a ρapproximation of the norm.

Second, all the algorithms we proposed have parameters that can be tuned in order to generate different guaranteed trade-offs. Thus, it is possible to scan the solution space by changing those parameters and keep the solution that optimizes the norm function. For instance, on the L ∞ norm case, the following iterative process can be used. Generate a solution using the algorithm. Sort users in decreasing order of their degradation. Increase the priority of the first user by decreasing the priority of the last ones. This will probably not generate an approximation algorithm (in terms of worst case bounds) but should give good results in practice.

Conclusion

In this paper, we analyzed the Multi-Users Scheduling Problem with many users interested in optimizing objectives among the most popular existing objectives on m processors. For the cases where all the objectives are the same, we derived some inapproximability results and we proposed algorithms that are very close or equal to the inapproximability bounds. In the case of mixed objectives, we lack an inapproximability bound but we proposed an algorithm with not-straightforward vector-ratio. Indeed, its restrictions to the cases where all the users share the same objective function have the same performances than the dedicated algorithms.

This analysis leads us to the following discussion. The approximation vector-ratios are linear in the number of users which may appear disappointing. Indeed, the vectorratios are computed relatively to a absolute best solution which is usually unfeasible. However, it ensures the performance degradation of each user is always reasonable. Using a deeper analysis for the makespan case, we showed that a modification of the algorithm provides a solution close to the Pareto set. This ensures that the solution is efficient.

Theorem 4. 1

 1 MULTICMAX is a (ρ, 2ρ, . . . , kρ)approximation algorithm of M U SP (k : C max ).

  max (S(u ) ). The users are ordered by increasing values of C (u) max (S (u) ). Thus, C (u) max ≤ uC (u) max (S (u) ). Moreover, S (u) was generated by a ρapproximation algorithm. Thus, C (u) max ≤ uρC (u) * max .

  max (S) = min S |∀u <u,C (u ) max (S )=C (u ) max (S) C (u) max (S ). In the following, Lex(u) denotes the set of Lex solutions of the problem restricted to the first u users i.e., the jobs of other users are not scheduled. Remark that all solutions in Lex have the same objective values. Thus, it makes sense to define C (u) max (Lex). Let us also define Idle(Lex(u)) = mC max (Lex(u))u ≤u i p (u ) i , the idle area in schedules of Lex(u).

Property 4 . 2

 42 Idle(Lex(u)) < mC (u) * max

  4.4). The second one is less than C (u) * max since it is a lower bound of C (u-1) * max and since the users are sorted in non-decreasing values of their optimal makespan. p (u) max is a lower bound of C (u) * max .

Proposition 5 . 1

 51 Schedule S is such that ∀u, ∀i ≤ n (u) , C (u) i (S) ≤ kC (u) i (S (u) ).

Lemma 5 . 3

 53 AGGREG (SP T (1), . . . , SP T (k)) is a (k, . . . , k)-approximation algorithm of M U SP (k :

Corollary 5 . 5 1 m

 551 MULTIWEIGHTEDSUM is a (ρk, . . . , ρk)approximation algorithm for M U SP (k :w i C i ).Using Hall et al.'s algorithm leads to a ((4 -)k, . . . , (4 -1 m )k)-approximation algorithm.

  max (S (cmax) ) ≤ uρC (u) * max (from Theorem 4.1) which means that ∀i ≤ n (u) , C (u) i (S (cmax) ) ≤ uρC (u) * max . Due to Proposition 5.2, all the jobs of the users interested in C max are not degraded by a factor greater than k k . Thus, ∀i ≤ n (u) , C (u) i (S (cmax) ) ≤ k k uρC (u) * max which concludes the proof.

The set of Pareto optimal solutions, i.e. solutions where no objective value can be improved without degrading another objective value.


Blal Nawfal
email: nawfal.blal@univ-montp2.fr

-Daridon Loïc
email: loic.daridon@univ-montp2.fr

Monerie Yann
email: yann.monerie@irsn.fr

-Pagano Stéphane
email: stephane.pagano@univ-montp2.fr

On mesh-size to cohesive zone parameters relationships

A micromechanical model is proposed for a collection of cohesive zone models embedded between each mesh of a finite element-type discretization (cohesive-volumetric approach). The corresponding model concerns isotropic and elastic bulk behaviours and can be applied whatever the cohesive zone model, the mesh type and the triaxiality loading ratio. The overall elastic behaviour is derived using a variational approach Hashin and Shtrikman (1963); Suquet (1995) and is obtained as function of local parameters, bulk properties of relevant material and mesh density. For an isotropic discretization, a bound is obtained on the cohesive stiffnesses: the additional compliance inherent to intrinsic cohesize zone models is bounded by lower value. Others criteria on cohesive parameters (critical opening, cohesive energy, peak stress, etc.) can be obtained trough inverse analysis.

Introduction

The cohesive approaches had emerged as one of the most efficient methods to simulate numerical fracture processes from crack initiation to overall failure. However, their numerical implementation exhibits a strong mesh sensitivity which is still an issue of concern: it is shown in [START_REF] Tijssens | Numerical simulation of quasi-brittle fracture using damaging cohesive surfaces[END_REF] that the fracture paths depend on the mesh geometry and size. Despite this path sensitivity, the authors show that the overall force-displacement response is not very sensitive to the mesh size and can be predicted with reasonable accuracy. Another aspect of this mesh sensitivity concerns the intrinsic Cohesive Zone Models (CZM), i.e. traction-separation laws with initial slope: embedding cohesive zone models along each element boundaries leads to an additional compliance since the density of the cohesive interfaces increases as the mesh is refined. 1 Following [START_REF] Song | A bilinear cohesive zone model tailored for fracture of asphalt concrete considering viscoelastic bulk material[END_REF], this artificial compliance can be illustrated on a simple 1D example (see Figure 1). In that case, the equilibrium condition reads: F/S = E M ε = C N [[u]], where F is the applied force, ε the strain in the bulk elements (mesh size L mesh , section S), E M the Young modulus used in the bulk element constitutive behaviour, C N the initial cohesive stiffness of the intrinsic model and [[u]] is the displacement jump across the cohesive zone. From the definition of the overall strain ε = F/S E M + F/S C N L mesh , one can deduce the normalized apparent Young modulus:

E E M = F/S E M ε = ξ 1 + ξ with ξ = C N L mesh E M . ( 1
)
According to this last equation, the ratio ξ seems to be the key parameter of controlling the mesh sensitivity in intrinsic CZMs. More precisely, the added compliance vanishes ( E → E M ) when ξ → +∞, see Figure 1 right. In other words, the overall elastic behaviour is not affected by the introduction of intrinsic CZMs between bulk elements and therefore the mesh sensitivity effect vanishes. Following the same type of ideas, various authors have proposed semi-empirical bounds for the ratio C N L mesh E M in order to define 'invisible' CZMs at the scale of a structure. Performing numerical tension and shear tests, [START_REF] Espinosa | A grain level model for the study of failure initiation and evolution in polycrystalline brittle materials. Part I: Theory and numerical implementation[END_REF] have noticed that the elastic wave speeds are unchanged across a cohesive line between two elastic and isotropic media when

!"#$%&'$()"*$ % + , $ + ! # -./0 F [u] L mesh S ! " E/E M C N L mesh E M
C N L mesh E M
≥ 10. Estimating the added compliance for cross-triangle elements arranged in quadrilateral pattern submitted to uniaxial tension, biaxial uniform tension and pure shear, [START_REF] Tomar | Bounds for element size in a variable stiffness cohesive finite element model[END_REF]

obtain: C N L mesh E M ≥ √ 2+1
κ(1-ν M ) with κ = 1 for plane stress and κ = 1/(1 -(ν M ) 2 ) for plane strain, where ν M is the Poisson ratio of the bulk material.

In this note, these criteria are generalized to three dimensional situations and to any type of loadings. On the other hand, the extension of the study to non linear damageable cohesive laws allows to derive an elliptic micromechanical damage model for brittle materials and exhibits others criteria on the cohesive parameters: critical opening, peak stress, cohesive energy, etc. The derived damage model does not use 1D damageable cohesive interfaces [START_REF] Daridon | Solving fracture problems using an asymptotic numerical method[END_REF]); nor is it limited to particular cohesive law [START_REF] Li | On damage theory of a cohesive medium[END_REF]).

Linear micromechanical model 2.1 Cohesive-volumetric discretization as a 'matrix-inclusion' composite

Consider a cohesive-volumetric finite element discretization: each volumetric element is connected to each other using CZMs as boundary conditions. The main idea is to replace this discretization by a continuous matrix containing penny-shaped cohesive inclusions (Figure 2). The matrix has the same behaviour as the bulk finite element one whereas the penny-shaped

! "

n inclusions have a cohesive behaviour defined by a traction-separation law. The spatial distribution of the cohesive inclusions corresponds to those of the edges of the underlying mesh and has the same spatial density, denoted by Z. In particular, in the case of a statistical isotropic mesh, e.g. a Delaunay-type mesh, the inclusions are randomly distributed in space and in orientation.

The shape of the inclusions is assumed to be of penny-shaped type, which corresponds to no thickness wiskers in two dimensions. The aim is to obtain the overall equivalent behaviour of such composite material using a Hashin-Shtrikman estimate [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF].

Phases properties

In the sequel, we limit ourselves to linear elastic behaviours. Moreover, the matrix phase is considered as isotropic and its constitutive relation reads:

σ = C M : ε with C M = 3k M J + 2µ M K, (2)
where σ (resp. ε) is the stress (resp. strain) field, C M is a fourth order stiffness tensor, k M and µ M are the bulk and the shear modulus respectively. The symmetric tensors J and K define the generic basis of the fourth order isotropic symmetric tensors: J = (1/3)i ⊗ i, K = I -J, 2I ijkl = (i ik i jl + i il i jk ), i being the second order identity tensor. Initially, the cohesive constitutive law is supposed to be elastic (intrinsic model). The traction-seperation law corresponds to a linear relation between the cohesive stress vector R coh and the opening vector [[u]], in a local normal-tangent basis oriented by the normal vector n to the cohesive inclusion:

R coh = K • [[u]] with K = C N n ⊗ n + C T u T ⊗ u T u T • u T , (3)
where

C N (resp. C T ) is the normal (resp. tangential) initial 'stiffness' of the cohesive law, u N (resp. u T ) is the normal (resp. tangential) component of [[u]] = u N n + u T .
The cohesive stress tensor is given combining (3) and R coh = σ coh • n (Acary and Monerie ( 2006)):

σ coh = (C N E l + C T K l ) ([[u]] ⊗ s n) , (4)
where ⊗ s is the symmetric dyadic product (2a ⊗ s b = a i b j + a j b i for any vector a and b) and E l , K l are two components of the fourth order transversely isotropic and symmetric tensors:

E l = n ⊗ n ⊗ n ⊗ n and K l = 2(j s ⊗ j s + j t ⊗ j t ) with j s = n ⊗ s s and j t = n ⊗ s t
, where s and t are two orthogonal vectors defining the transversal plane (n, t, s define the local orthogonal basis of the cohesive inclusion). The rescaling requires to define the strain over the cohesive phase through a fictitious thickness e intended to tend toward to 0 [START_REF] Michel | Une modélisation du rôle des interfaces dans le comportement des composites à matrice métallique[END_REF]:

ε coh = [[u]] ⊗ s n e . ( 5
)
and therefore to construct a fourth order stiffness tensor C coh leading to the following constitutive relationship for inclusions:

σ coh = C coh : ε coh with C coh = e (C N E l + C T K l ) . (6)
Again, the parameter e is a fictitious thickness that should tend to zero. Since oblate ellispoids tend to penny-shaped inclusions when their thickness tends to zero, the cohesive inclusions are now considered as oblate ellipsoids and their volume fraction f is the product of the density Z (inversely propotional to a length: the mesh size L mesh ) and the fictitious thickness e: f = eZ (cylindrical hypothesis instead of oblate one without any consequence when e → 0).

Hashin-Shtrikman estimate

A Hashin-Shtrikman estimate [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF] is used to establish an analytical expression of the overall elastic stiffness C hom . This variational representation is based on the use of polarization fields related to a homogeneous reference medium (stiffness C 0 ). In the case of a biphasic medium, the Hashin-Shtrikman estimate can be expressed as:

C HS (C 0 ) = f C coh : T + (1 -f )C M : [f T + (1 -f )I] -1 . ( 7
)
where the fourth order tensor T is given by T = (C * + C coh ) -1 : (C * + C M ) with C * being the Hill influence tensor which depends on the shape of the inclusions and on the reference medium

C 0 .
3 Effective overall moduli for the elastic problem

The final expression of the Hashin-Shtrikman estimate depends on the choice of the reference medium (C 0 ) and an appropriate average over mesh orientations (see [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] for details). Assuming that the orientations of inclusions have the equi-probability property, which corresponds to the case of isotropic meshes (e.g. Delaunay-type meshes), the expression ( 7) is reduced to [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF]):

C HS (C 0 ) = eZ C coh : T + (1 -eZ)C M : eZ T + (1 -eZ)I -1 (8)
where . indicates the average over all orientations. Following [START_REF] Gatt | Elastic behavior of porous ceramics: application to nuclear fuel materials[END_REF], this orientational average is calculating as D = (J :: D)J + (1/5)(K :: D)K for any fourth order tensor D, and the overall stiffness tensor is obtained: C hom = lim e→0 C HS (C 0 ). According to the choice of the reference medium C 0 , different bounds and estimates can be derived. Since, in a quadratic sense, the tensor C coh is smaller than C M when e tends to 0, the lower bound of the Hashin-Shtrikman estimate is obtained for the case C 0 = C coh :

C hom = lim e→0 C HS-C coh = lim e→0 eZ C coh : T + (1 -eZ)C M : eZ T + (1 -eZ)I -1 . (9)
Thus, after passage to limit e → 0, the overall bulk and shear moduli are:

k hom k M = ξ k ξ k + 1 with ξ µ = C N Zk M and µ hom µ M = ξ µ ξ µ + 1 with ξ µ = 15 4(1 + 3C N /C T ) C N Zµ M ,
(10) more practically in terms of Young modulus and Poisson ratio:

E hom E M = ξ E 1 + ξ E
where

ξ E = 5 1 + (4/3)(C N /C T ) × C N E M Z , (11)
ν hom ν M = E M Z(-1 + 2C N /C T ) + 15C N ν M E M Z(3 + 4C N /C T )ν M + 15C N ν M . ( 12
)
These lower bounds (10) give indication on the lost of global stiffnesses, e.g.:

k hom /k M ≥ 0.95 is insured for ξ k ≥ 20 , µ hom /µ M ≥ 0.95 is insured for ξ µ ≥ 20 . ( 13
)
Using the software XPER [START_REF] Perales | Two field multibody method for periodic homogenization in fracture mechanics of nonlinear heterogeneous materials[END_REF], the accuracy of these bounds is tested for the particular case C N = C T in Figure 3. As shown in Figure 3, relations (10) are lower bounds for isotropic meshes (Delaunay) and can be considered as convenient estimate for regular meshes. Moreover, it is clearly shown that criteria ξ k ≥ 20 and ξ µ ≥ 20 (dashed lines) ensure that the overall elasticity is disturbed by less than 5%.

4 Extension to the damage problem

Problem formulation

In this section, the overall behaviour for the damage part is studied (non linear damageable cohesive zone models). The macroscopic associated stress Σ is obtained via the constitutive law: Σ = C hom : E. The homogeneous stiffness tensor C hom is estimated using the modified secant method [START_REF] Suquet | Overall properties of nonlinear composites : Secant moduli theory and its link with Ponte Castañeda's variational procedure[END_REF], which is equivalent to the Ponte Castañeda variational approach Ponte [START_REF] Castañeda | Nonlinear composites[END_REF]. Focusing on the case of isotropic local damage, the non linear damageable cohesive law is defined introducing a surface damage parameter β in (3) (β = 1 the cohesive zone is undamaged, 0 < β < 1 cohesive zone is partially damaged and β = 0 the cohesive zone is fully damaged), namely:

R coh = β × C N n ⊗ n + C T u T ⊗ u T u T • u T [[u]]. (14)
We assume that the parameter β depends only on the norm of the displacement jump vector

[[u]] (β = β( [[u]] ))
. Hence, equation ( 14) leads to the non linear stiffness of the inclusions given by the secant modulus:

C coh sct = β( [[u]] ) × C coh . ( 15
)
The secant stiffness C coh sct replaces the cohesive tensor C coh in Hashin-Shtrikman estimate (9). Using the strain definition (5), the norm of the displacement jump [[u]] can be linked to the fourth order tensor = (1/2)ε ⊗ ε as:

[[u]] 2 = 2e 2 (-J + 2K) :: . ( 16
)
On the other hand, the second moment of the strain in the inclusion phase I can be linked to the overall elastic energy by (see [START_REF] Kreher | Residual stresses and stored elastic energy of composites and polycrystals[END_REF]):

I = 1 2eZ ∂(E : C hom : E) ∂C coh sct . (17)
Hence, substituting ( 17) into ( 16), the quadratic average of the displacement jump reads:

[[u]] 2 I = e Z (-J + 2K) :: ∂(E : C hom : E) ∂C coh sct ( 18
)
which may be also written involving the hydrostatic part of the strain load E m = (1/3) tr(E) and the equivalent part E eq = (2/3)E dev : E dev (with E dev being the deviatoric strain tensor:

E dev = E -E m i): [[u]] 2 I = E 2 eq (1 + ν) 2 (2 + ν) + 20E 2 m 23 + 17ν -44ν 2 -164ν 3 1 2 × F, (19)
where the scalar F depends on the damage parameter, the cohesive stiffnesses, the material properties and the mesh size (its expression is too complicated to be given here in a closedform). Finally, the expression of the secant modulus is given by:

       C coh sct = β × (C N E l + C T K l ), β = β   E 2 eq (1 + ν) 2 (2 + ν) + 20E 2 m 23 + 17ν -44ν 2 -164ν 3 1 2 × F   . ( 20
)
Given the expression of the damage function β, one can obtain the solution of the non linear problem (20) using a numerical method, e.g. fixed point schemes. The obtained result defines therefore a micromechanical damage model applicable whatever the triaxiality loading ratio. The case of a bilinear cohesive law will be discussed in the next section.

Application: bilinear cohesive law

Focusing on the case of brittle fracture in elastic materials, a bilinear cohesive damageable law is studied hereafter (see Figure 4). An elliptic damage model is thus derived (Figure 6 left). For that specific case of cohesive law, the effective yielding surface at failure is given the hydrostatic and equivalent strain by the equation:

u N R N (u N , 0) R max N δ a δ c βC N C N u T R T (0, u T ) R max T δ a δ c βC T C T            R N = βC N u N ; R T = βC T u T β(u) = δa δa-δc 1 -δc u R coh max = (R max N ) 2 + (R max T ) 2 1/2 R max N = C N δ a ; R max T = C T δ a
Ψ(E m , E eq ) = E 2 eq E eq 2 + α E 2 m E eq 2 -1 = 0 ( 21
)
where E eq = √ 10(1 + ν M )Zδ c /3( 23 + 63ν M + 82(ν M ) 2 is the equivalent macroscopic strain at failure under pure deviatoric load. The coefficient α is equal to the square of the ratio between equivalent strain E eq and hydrostatic one E m at failure, and depends only on the Poisson ratio of the matrix ν M (Figure 5 illustrates the effect of the Poisson ratio on the triaxilaty ratio at the failure: the more incompressible the material is, the larger the coefficient α becomes). It gives an idea about the triaxiality ratio effect associated to our model. For a material with ν M = 0.3, α is about 3.94, in other words, the equivalent strain which leads to total failure, in the case of deviatoric load, is nearly twice the hydrostatic strain for a 3D traction: E eq 2E m (Figure 6). Obviously, the model depends on the Poisson ratio and deals with any type of triaxiality. Therefore, it extends to the brittle case Gurson-like model [START_REF] Gurson | Continum theory of ductile rupture by void nucleation and growth. Part 1 . yield criteria and flow rules for porous ductile materials[END_REF] (where no dependence to Poisson ratio can be predicted) and Li-Wang model [START_REF] Li | On damage theory of a cohesive medium[END_REF] (restricted to hydrostatic loads). Moreover, equation ( 21) and Figure 5 show that the cohesivevolumetric finite element method predicts that: 1) it is easier to break a material under purely hydrostatic loadings than under purely deviatoric ones, when -0.27 ≤ ν M < 0.5, 2) it is easier to break a material under purely deviatoric loadings than under purely hydrostatic ones, when -1 ≤ ν M < 0.27. Figure 6 (right) illustrates the evolution of the macroscopic behaviour associated to the bilinear cohesive law. Results are given for the case of a pure deviatoric load and shows a dependence on the mesh size L mesh . This mesh sensitivity could be avoided according to rigorous calibration of the cohesive parameters. This point is developed in details in section 5.2. The material properties and cohesive parameters are given in Table 1.

E M (GPa) ν M R coh max (MPa) δ c (mm) C N (= C T )(MPa/
5 Inverse identification and rigorous criteria on cohesive parameters

Lower bounds on cohesive stiffness

The inverse study of the results obtained in the elastic part allows to derive an a priori estimate of the overall elastic reduction as function of the cohesive stiffnesses, and therefore to suitably calibrate them. Practical criteria are proposed following [START_REF] Acary | Nonsmooth fracture dynamics using a cohesive zone approach[END_REF] from the previous micromechanical model. Denoting by R = E hom /E M the overall reduction of the Young modulus (R = 1 corresponds to 'invisible' intrinsic CZMs) and according to equation ( 11), an 1 and the overall stiffness reduction is tolerated at 5%, i.e. we admit that cohesive zone models disturb the overall Young modulus for less than 5%: E hom /E M = 0.95.

implicit lower bound on C N /(E M Z) is obtained involving the density Z and the ratio C N /C T :

C N E M Z ≥ 1 5 R 1 -R 1 + 4 3 C N C T . (22)
To complete the criterion ( 22), we suggest to ensure that the overall Poisson ratio stays equal to the matrix one: ν hom = ν M . This condition leads to a restriction on the ratio C N /C T :

ν hom = ν M ⇒ C N C T = 1 2 1 + 3ν M 1 -2ν M . (23)
Equations ( 22) and ( 23) give a lower bound on the normal cohesive stiffness as function of the elastic reduction R: C N ≥ k M ZR/(1 -R). Since the density Z is inversely proportional to the mesh size L mesh , one obtains with ( 22) and ( 23):

C N L mesh E M ≥ γ R 1 -R 1 3 -6ν M , (24)
where γ depends on the spatial distribution of the considered isotropic mesh. For Delaunay meshes, γ can be represented as a mean value and a variance [START_REF] Stoyan | Stochastic geometry and its applications[END_REF]. For nonisotropic meshes (as regular ones), we claim that the bound (24) can be considered as an accurate estimate: interestingly, the two dimensional case of 'cross-triangle quadrilateral' mesh (each square element is subdivided into four isosceles triangles) corresponds to γ = 2(1 + √ 2) [START_REF] Acary | Nonsmooth fracture dynamics using a cohesive zone approach[END_REF]. The bound (10) and the condition (23) allow to define a '5% criteria' (R = 0.95) in terms of bulk and shear moduli for 2D regular meshes:

C N L mesh k M ≥ 92 and C T L mesh µ M 15 - µ M k M L mesh ≥ 1104, ( 25
)
and a 'practical 5% criterion' (R = 0.95):

C N L mesh E M ≥ 30 1 -2ν M with C T C N = 2 1 -2ν M 1 + 3ν M . ( 26
)

Criteria on damageable cohesive parameters

The identification of the other cohesive parameters follows from the damage part: critical opening δ c and cohesive peak value R coh max . Without loss of generality, interest is made for the case of overall deviatoric loads. The linearised constitutive law Σ = C hom : E gives the evolution of the macroscopic equivalent stress as function of the macroscopic equivalent strain: Σ eq (E eq ). The macroscopic stress is maximum when the macroscopic strain reaches the strain E eq corresponding to:

∂Σ eq ∂E eq | Eeq = 0,

hence, one can obtain an explicit relationship between the maximum cohesive stress R coh max and the material tensile yielding stress Σ = Σ eq ( E eq ):

R coh max = √ 2 23 + 17ν M + 71(ν M ) 2 + 151(ν M ) 3 + 410(ν M ) 4 1 2 3 (1 -2ν M ) |1 + 3ν M | Σ. (28)
In order to guarantee that the proposed model does not predict complete failure before the initiation of fissure opening, an additional condition concerning the choice of the critical separation δ c is needed. For the case of regular meshes, we have:

δ c L mesh = 3 -1 + √ 2 23 + 63ν M + 82(ν M ) 2 1 -2ν M + 5(ν M ) 2 1 2 √ 10 (1 + ν M ) (23 + 17ν M + 71(ν M ) 2 + 151(ν M ) 3 + 410(ν M ) 4 ) 1 2 × W Σ , (29)
where W denotes the material fracture energy. The results issue from equations ( 23), ( 24), ( 28) and ( 29) give practical rules to suitably calibrate the cohesive parameters, namely the cohesive stiffnesses C N and C T , the maximal cohesive stress R coh max and the critical separation δ c (equivalently the cohesive energy) as function of the macroscopic material properties (E M , ν M ) and the mesh size L mesh given a user-defined stiffness reduction R. Even though these results include a dependence of the cohesive parameters on the mesh size (except the case of R coh max ), this way to calibrate the damageable cohesive law leads to a mesh-independent overall behaviour: the macroscopic behaviour stays invariant regardless of the mesh size. Taking into account the previous relationships, the homogenized secant moduli are given as function of the overall load E, where it is clearly shown that the overall macroscopic behaviour has no dependence on the mesh size:

     k hom sct (E) = R (Eeq Σ-2W ) Eeq( Σ2 -6RW µ M ) k M Σ µ hom sct (E) = R (Eeq Σ-2W ) Eeq( Σ2 -6RW µ M ) µ M Σ ( 30
)
Similar results can be obtained for the case of hydrostatic loads.

Concluding remarks

The overall constitutive behaviour of an elastic medium with embedded cohesive inclusions has been studied. The equivalent 'matrix-inclusions' composite is considered as a representation of a cohesive-volumetric finite element modelling. As result of this micromechaical model, the following points can be highlighted:

• Rigorous lower bounds on normal, C N , and tangential, C T , cohesive stiffness have been obtained for isotropic meshes as well as convenient criteria for regular meshes. The accuracy of this result has been numerically checked for both Delaunay and cross-triangle quadrilateral meshes.

• The specific case of a bilinear shape cohesive zone model leads to an overall elliptic damage model for brittle materials. The approach is valid for any macroscopic triaxiality ratio and thus extends previous partial results of the literature. The proposed model is able to estimate the influence of Poisson ratio in material damage.

• All the local cohesive parameters can be linked to the overall fracture material properties at any given mesh size. One merit of the cohesive parameters inverse identification is its ability to derive an overall behaviour avoiding mesh dependency of mesh size. This result gives rigorous explications of the previous empirical results proposed in the literature.

Figure 1 :

 1 Figure 1: Illustration of the relationship between apparent Young modulus and mesh size in 1D-case: (left) a representative part of 1D finite element mesh with embedded cohesive zone model, (right) overall Young modulus normalized by bulk modulus vs mesh size.

Figure 2 :

 2 Figure 2: Principle of the approach: a cohesive-volumic finite element mesh is replaced by a continuous matrix corresponding to bulk elements and a collection of penny-shaped cohesive inclusions corresponding to the edges of the underlying mesh; (left) 2-D illustration, (right) 3-D illustration.

Figure 3 :

 3 Figure 3: Normalized overall elastic modulus of a cohesive-volumetric formulation with intrinsic CZMs (case C N = C T ): lower bounds (10) (thick gray line), numerical results for Delaunay meshes (closed symbols with variance) and for cross-triangle quadrilateral meshes (open symbols); bulk modulus (left) and shear moduls (right).

Figure 4 :

 4 Figure 4: Cohesive bilinear law

Figure 5 :

 5 Figure 5: Triaxialty dependence on the Poisson ratio.

Figure 6 :

 6 Figure 6: The elliptic damage model (21) (left) and the normalized overall behaviour for a deviatoric applied loading given different values of the mesh size L mesh (right). The material and cohesive parameters are given in Table1and the overall stiffness reduction is tolerated at 5%, i.e. we admit that cohesive zone models disturb the overall Young modulus for less than 5%: E hom /E M = 0.95.

Table 1 :

 1 Material and cohesive parameters

	mm)