Ben Mouldi

Azzouna

Jean-Noël Périé

Jean-Mathieu Guimard

François Hild
email: hild@lmt.ens-cachan.fr

Stéphane Roux

Jean-Noël Azzouna

Jean-Mathieu Périé

François Guimard

Stéphane Hild

Roux

Special issue on Multiscale Modeling of Ductile and Brittle Damage in Solids: Recent Progresses and New Trends (Guest editors

Keywords: Anisotropic damage law, Composite material, Digital Image Correlation, Equilibrium Gap Method, Identification

Two different mechanical tests are performed on a laminated composite coupon to induce an anisotropic damage affecting essentially shear modulus softening. The first test is a uniaxial tension loading on a straight coupon, which is used to evaluate the damage law using a conventional approach, while the second contains a notch that enhances dramatically the strain (and hence damage) heterogeneity. A global Digital Image Correlation approach is used to quantify the kinematic fields all along the loading path of the second experiment.

Displacement fields are hence evaluated based on a finite-element type discretization. A further exploitation based on the reconditioned equilibrium gap method (and without any further information) gives access to a quantitative measurement of the damage law. The latter approach makes use of a finite-element model based on the very same mesh and element shape function. This full-field based identification method compares very well with traditional techniques, up to the stage where macroscopic localization prevents their subsequent exploitations. Moreover, it is shown that neither the type of mechanical test, nor the discretization of the displacement field, affects the identification of the damage law.

Introduction

The intensive use of composite materials in the field of aeronautic structures challenges industry on its ability to predict accurately through numerical simulations the behavior of specimens and structures up to failure. In the framework of the VULCOMP project aiming at assessing and quantifying carbon fiber reinforced plastics (CFRP) damage laws [START_REF] Ladevèze | Damage modelling of the elementary ply for laminated composites[END_REF] in the dynamic loading range, the present work is a first step that proposes an alternative strategy geared towards robust identification of the behavior of a composite ply model by means of a non-conventional test and full field measurements.

The identification of the parameters of anisotropic damage laws involved in CDM models [START_REF] Voyadjis | Damage Mechanics in Engineering Materials[END_REF][START_REF] Allix | Continuum Damage Mechanics of Materials and Structures[END_REF] is usually either performed by resorting to elementary tests on coupons with numerous unloading / loading cycles (e.g., from unidirectional composites [START_REF] Barbero | An Inelastic Damage Model for Fiber Reinforced Laminates[END_REF] or from tensile tests on various stacking sequences [START_REF] Ladevèze | Damage modelling of the elementary ply for laminated composites[END_REF][START_REF] Halm | A modular damage model for quasi-brittle solids -interaction between initial and induced anisotropy[END_REF][START_REF] Payan | Damage modelling of laminated carbon/epoxy composites under static and fatigue loadings[END_REF][START_REF] Camanho | Prediction of size effects in notched laminates using continuum damage mechanics[END_REF])) or on notched samples (e.g., shear test on the so-called Iosipescu geometry [START_REF] Iosipescu | New Accurate Procedure for Single Shear Testing of Metals[END_REF][START_REF] Dickson | Selection of an in-plane shear test method based on the shear sensitivity of laminate tensile modulus[END_REF]). In the first case, central strain gauges are used in addition to a load measurement to retrieve stress-strain relationships at the ply level by using the classical laminate theory. It assumes a uniform strain field up to failure, which is a strong hypothesis that neglects strain and damage localization. In the case of Iosipescu's experiment, uniform strain distributions are assumed in the ligament, even though this is only a first order approximation [START_REF] Burr | Continuum Description of Damage in Ceramic-Matrix Composites[END_REF]. When more complex geometries are considered, or when only corrupted measurements are recorded (e.g. in dynamic loadings), inverse procedures are needed to tune material parameters [START_REF] Andrieux | The reciprocity gap: a general concept for flaws identification problems[END_REF][START_REF] Rota | An inverse approach for identification of dynamic constitutive equations[END_REF][START_REF] Allix | Identification strategy in the presence of corrupted measurements[END_REF][START_REF] Lecompte | Mixed numerical-experimental technique for orthotropic parameter identification using biaxial tensile tests on cruciform specimens[END_REF][START_REF] Avril | Overview of identification methods of mechanical parameters based on full-field measurements[END_REF]. For all these methods, the identification task results in the resolution of an ill-posed problem with constraints given by trusted experimental data. Up to now, only piecewise global data were used in these methods.

Conversely, [START_REF] Chalal | Direct identification of the damage behaviour of composite materials using the virtual fields method[END_REF] resorted to the virtual fields method to determine the parameters of a linear relationship between the damage parameter and the local shear strain.

More recently, [START_REF] Lubineau | A goal-oriented field measurement filtering technique for the identification of material model parameters[END_REF] proposed an iterative FE procedure by means of a filtering technique. It is based on building new field variables (based on simple operations and linear combinations of longitudinal and transverse strain fields) that are more sensitive to each parameter and in each local area.

An alternative route to the previous approaches is given by the equilibrium gap method that aims at identifying fields of elastic contrasts [START_REF] Claire | Identification of damage fields using kinematic measurements[END_REF]2004), which may be reinterpreted a posteriori in terms of a damage field [START_REF] Claire | Identification of a Damage Law by Using Full-Field Displacement Measurements[END_REF][START_REF] Crouzeix | An orthotropic variant of the Equilibrium Gap Method applied to the analysis of a biaxial test on a composite material[END_REF]. More recently, it was shown that the same type of formalism can be used to directly identify the parameters of the damage law in the case of an isotropic [START_REF] Roux | Digital Image Mechanical Identification (DIMI)[END_REF] and anisotropic [START_REF] Périé | Digital Image Correlation and biaxial test on composite material for anisotropic damage law identification[END_REF]) description of damage. The latter will be used herein to analyze another experiment (here a notched sample to create a heterogeneous strain field), and will be compared to results obtained by analyzing a tensile test on a coupon as an independent validation of the whole procedure. In the present case the studied composite is layered as opposed to the previously studied materials (Roux and Hild 2008; Périé et al. 2009) In the present paper, a notched sample will be used to identify the parameters of a damage law. In Section 2, the experimental conditions are described, and first analyses of kinematic data extracted from displacement measurements thanks to digital image correlation are presented. The identification procedure, namely, the equilibrium gap method is briefly summarized in Section 3, and applied to analyze the experiments on the notched sample in Section 4. The identified damage law is finally compared with that obtained by following a classical approach on a coupon specimen for validation purposes.

Description of the experiments

In the work of [START_REF] Périé | Digital Image Correlation and biaxial test on composite material for anisotropic damage law identification[END_REF], it has been shown that the Equilibrium Gap method is more powerful when one considers full-field measurements of experimental configurations that undergo non-uniform damage states (and therefore heterogeneous strain fields). Non-uniform fields enable for the activation of a large range of strain distributions at each loading step, whereas a uniform-like test requires the use of many loading steps to reach the same range.

To validate this hypothesis, the identified damage law obtained in the analysis of a tensile test on a notched sample is compared with that observed in a classical [+/-45] ns tensile test on a coupon (ASTM 1994), see Figure 1.

In the present work, the idea is to enforce geometrically the heterogeneity of strain fields. Consequently, the classical [+/-45°] ns tensile test on coupons was modified by adding a lateral notch on the specimen. Each layer of the composite is made of unidirectionally aligned carbon fibers (average diameter: 7 µm, volume fraction: 60 %) in a thermoset matrix.

The test has been performed on a tension / compression testing machine quasi-statically (stroke rate: 0.5 mm/min) with unloading / loading steps up to final failure of the specimen (Figure 2). The grips were aligned prior to the experiments as usually performed. However, no additional care was taken since the actual boundary conditions are measured for the region of interest by digital image correlation. One face was covered with a random pattern (created by spraying black and white paint). Images are recorded with a digital camera up to failure.

The later occurs for a tensile load of about 7500 N (Figure 3). Final failure follows the 45° directions, i.e., the fiber directions.

Thanks to the recorded pictures (at each 500 N step), displacement fields of the prepared face can be measured for each loading steps (Figure 3) by resorting to digital image correlation or DIC [START_REF] Sutton | Image correlation for shape, motion and deformation measurements[END_REF]). In the present case, a global correlation algorithm is used [START_REF] Besnard | Finite-element'' displacement fields analysis from digital images: Application to Portevin-Le Châtelier bands[END_REF]. It allows for the extraction of continuous displacement fields associated with a finite-element discretization. Four-noded elements are considered with a bilinear interpolation of the displacements in each element. The spatial resolution of the displacement measurement is directly given by the element size. Two element sizes are considered, namely 12 and 34 pixels. These two sizes are considered to analyze the mesh sensitivity of the identified damage law, which is a concern when damage computations are performed. The displacement maps shown in Figure 4 for the two discretizations at the maximum load level are similar. The corresponding strain fields are estimated by computing the average value in each finite element (Figure 5). The spatial resolution of the strains is thus equal to the element size l. There is a more pronounced difference in terms of spatial description of the strain fields when comparing the results obtained for the two discretizations (Figure 5). This is due to the localization of the strains in the vicinity of the highly damaged (V-shaped) zones.

The chosen element sizes lead to a standard displacement uncertainty of the order of 1.5 and 0.3 centipixel, respectively, and a standard strain uncertainty of the order of 10 -3 and 10 -4 , respectively. These results are obtained with an a priori analysis [START_REF] Besnard | Finite-element'' displacement fields analysis from digital images: Application to Portevin-Le Châtelier bands[END_REF] that consists in prescribing uniform sub-pixel displacements ranging from 0 to 1 pixel, with an 0.1-pixel increment. The root mean square of the measured displacement is estimated for each prescribed value, subsequently averaged over the whole analysis, and referred to as the standard displacement uncertainty σ u . The strain field is then calculated and the corresponding standard strain uncertainty σ ε is evaluated by following the same procedure as for the displacements. The results of the analysis are shown in Figure 6. A single power law interpolation of σ u = A / l α and lσ ε = B / l α , with α = 1.7 and B / A = 2.3 describes well the results up to element sizes of the order of 40 pixels. Last, it is to be noted that non-uniform fields are present at each step and localized in the vicinity of the initial notch (Figure 2) that may induce interpolation errors if the displacement field is not sufficiently discretized, especially in terms of strain fields (Figure 5). This result is confirmed by the equivalent shear strain maps plotted for the classical tensile test and for the test on a notched sample (Figure 7). Heterogeneity becomes significant only at the final stages of the loading. For comparison purposes, the distributions of equivalent strains in the coupon and notched sample (with two different discretizations) are shown in Figure 8. In the classical test, the range of strains is not as high as that observed in the notched sample. This is especially true for the last load levels, for which the range is quasi-constant for each cycle of the classical test. The strain histograms of the notched sample using two discretizations are also different, thereby illustrating the effect of the spatial resolution of the measurement technique in the presence of heterogeneous strain fields. In the following, an identification technique making use of the FE measured displacement fields will be utilized in the framework of the equilibrium gap method.

Equilibrium Gap Method

Damage model

In the following, a [0/90] ns stacking sequence is considered (a simple rotation leads to the actual configuration studied, see Figure 1). The composite behavior is described at the macroscopic scale for the sake of simplicity (delamination degradation does not occur in this configuration which means that the mesoscopic and macroscopic scales are similar), and only in-plane stress components are considered. It is assumed that the dominant degradation mechanism is related to shear damage modeled by a single variable D. Gibbs' free enthalpy Ψ of the composite then reads

⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - + + - = Ψ ) 1 ( 2 1 12 2 12 2 2 22 22 11 1 12 1 2 11 D G E E E σ σ σ σ ν σ (1)
where σ 11 , σ 22 , σ 12 are the in-plane stress components expressed in the material frame (1, 2).

The elastic properties are E 1 and E 2 (Young's moduli along the fiber directions), ν 12 (Poisson's ratio), and G 12 (in-plane shear modulus). The in-plane strain components are expressed as

D G E E E E - = ∂ Ψ ∂ = - = ∂ Ψ ∂ = - = ∂ Ψ ∂ = σ σ ε σ ν σ σ ε σ ν σ σ ε (2)
and the thermodynamic force Y associated with the damage variable D becomes

2 12 12 2 12 2 12 2 ) 1 ( 2 ε σ G D G D Y = - = ∂ Ψ ∂ = (3)
Equation ( 3) shows that the thermodynamic force Y is directly related to the shear strains, which are accessible thanks to kinematic measurements. The growth of the damage variable D is assumed to be driven by Y [START_REF] Herakovich | Damage evolution in [±45]s laminates with fiber rotation[END_REF]. It is worth noting that other driving forces have been proposed for fabric tapes [START_REF] Hochard | A ply scale non-local fibre rupture criterion for CFRP woven ply laminated structures[END_REF]) but for the UD laminate studied herein, this simple expression is in good accordance with microscopic observations [START_REF] Kellas | Damage and Failure Mechanisms in Scaled Angle-Ply Laminates[END_REF]. Consequently, the damage variable D becomes a function of an equivalent strain eq εˆ such that ( )

eq k k k c D ε ϕ ∑ = with ) ( max ) ( ˆ12 0 τ ε ε τ t eq t ≤ ≤ = ( 4
)
where ϕ k are functions to be specified later on, and c k are the material parameters to be tuned.

In the next section, the equilibrium gap method is summarized to identify the parameters c k .

Identification procedure

The identification procedure followed herein consists in prescribing the measured nodal displacements to a finite element model in which the mesh and the kinematic hypotheses are identical. When applying displacements to inner nodes on which no external forces are prescribed, nodal forces arise. In a finite element framework, the residual force vector { }

res f reads { } { } ( ) [ ]{ } meas res u D K f = (5)
where the stiffness matrix [ ] K depends upon the damage vector { } D , and { } meas u denotes the measured displacement vector. In the present case, it is assumed that the damage variable is uniform in each considered Q4 element. Therefore, the elementary stiffness matrix [ ]

el K is affine in D ( ) [ ] [ ] [ ] 1 0 K K K D D el - = (6)
where [ ]

( ) ( ) ∑ ∑ ∑ ∑ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - = i e e eq k je j ij k k i k g L S c u c E 2 1 ε ϕ (9)
where u i is the i-th component of the measured nodal displacements, 1 ie L the contribution of element e to the nodal force at the internal node i (

∑ = j j ije ie u K L 1 1
), and S ij the component of the operator [S] defined by [S]{L} = {u meas }. It is to be emphasized that in spite of the proposed non-linear constitutive damage law, the identification consists in solving a linear system in the unknown c k parameters (minimization of a quadratic functional). The reconditioned functional g E ~ is much less sensitive than g E to the short wavelength noise, which is inevitably present in the determination of the displacement field. Hence the proposed formulation is robust, and of very small size (the number of unknowns is typically very small). As already used in previous studies [START_REF] Roux | Digital Image Mechanical Identification (DIMI)[END_REF][START_REF] Périé | Digital Image Correlation and biaxial test on composite material for anisotropic damage law identification[END_REF], functions ϕ k are written as

( ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - - = k eq eq k ε ε ε ϕ êxp 1 ˆ ( 10
)
where the values ε k are considered in the range of experimentally observed equivalent strains, and well separated (typically, ε k+1 / ε k =2). When only one parameter c k is not equal to zero, the classical range [0;1] of a damage variable is automatically satisfied. Equation ( 4) is a constitutive law regularization. It enforces the strong condition that two regions where the equivalent strain is the same will experience an identical damage level. Let us finally note that Equation (4) can be read as a truncated Laplace transform of the damage law.

Identification and validation

Data extraction

In this study, the identification consists in estimating the damage part of all non-linear mechanisms involved in the degradation of composite materials. Since DIC yields displacement fields in the notched sample at each chosen load level (up to failure) with respect to any reference step, there are many possible choices. Classically, the reference picture is that of the initial step for which no load was applied (i.e., at the very beginning of the experiment). However, it is possible to consider the picture corresponding to each unloaded step as the reference, and the next one corresponding to the subsequent maximum load level (see Figure 3). By using the present procedure, it is therefore possible to analyze only the part of the behavior corresponding to the damage state (disregarding plastic-like components).

It is to be stressed that the actual experimental boundary conditions (even if imperfect) are taken into account from the Dirichlet conditions to be used in the identification procedure.

Hence, spurious rotations or torques that are likely to appear for the most damaged states are taken into account, making this identification procedure much more tolerant to imperfections in the loading conditions or natural breakdown of symmetries.

Identification results

By using the damage law (4), the identification results yield the unknowns c k for chosen ε k values (Table 1). The quality of the identification is first assessed globally by computing the standard deviation of the displacement difference related to that of the measured displacement.

This indicator is denoted by ρ u . Second, the field of displacement differences allows for a local analysis of the identification result. From the measurement of the equivalent strain map and the determination of the parameters of the damage law, it is possible to construct the damage maps for each of the analyzed load levels (Figure 9). From Figures 7 and8, it is to be expected that the notch enables for the exploration of higher strain levels prior to failure, and consequently for the identification of higher levels of damage. For the last considered cycle (#14), a localized damage pattern is observed with a value of d 12 approaching 1. This is in good accordance with the experimental failure pattern observed in Figure 2. For the two discretizations (12pixel and 34-pixel sizes), the best solution is obtained with only one parameter ε k for which c k is therefore close to 1. This result shows that the identified damage law given by Equation ( 4) is similar for the two discretizations.

The whole identification procedure interpreted in terms of a constitutive law is a priori only valid prior to localization. Beyond localization onset, the DIC analysis may smooth out sharp gradients. Similarly, numerical simulations are inadequate as they become mesh-dependent. However, here both DIC and simulation are performed with the same mesh, and hence they are expected to share these flaws, and yet they can be compared. At this point, the determination of the damage law is not unique. However, because of the very few parameters introduced to describe it, no indeterminacy appears, and the comparison remains quite satisfactory.

Validations

A first way of validating the identification results is to compare the computed displacement field using the damage law that was identified with the measured displacement field, and then estimate the displacement residuals (Table 1). Figure 10 shows the three maps corresponding to the two displacement components for cycles #4 and #14. A very good agreement is observed. The relative displacement residual ρ u is about 3.7 % for 12-pixel elements and 5.6% for 34-pixel elements for the final cycle, which leads to a low sensitivity to the uncertainty level (Figure 6) associated with DIC. The fact that ρ u is smaller for 12-pixel elements than the value for 34-pixel elements indicates that the discretization with 12-pixel elements better captures the damage pattern.

Another way of validation is given by the damage law itself. The latter is compared with that obtained by following the classical identification procedure [START_REF] Ladevèze | Damage modelling of the elementary ply for laminated composites[END_REF]). In the latter, only a single longitudinal strain level (Figure 1) is available per unloading / loading cycle. From 10 to 15 points are generally accessible. For example,

Figure 11 shows the result from the analysis for which only 5 points lie above the damage threshold. For the present approach, the same results are shown in Figure 11. Numerous identification points are available thanks to full-field data. It is also to be noted that the present approach allows for the identification of damage levels greater than 0.4, level at which the global method stops because of failure that occurs suddenly.

In the range over which the two results can be compared, there is a good agreement, thereby validating the approach followed herein. It is to be remembered that the damage functions (10) do not incorporate a threshold parameter. This is the main difference between the two results. However, it is believed that this value is difficult to capture with fine meshes for which the measurement uncertainty is not sufficiently small.

Summary and Outlook

This paper proposes a robust damage law identification based on full-field measurements and using a non-conventional test. It was validated against classical procedures. It is to be emphasized that the power of the proposed method comes from the exploitation of heterogeneous tests. Each element can be seen as an elementary test on its own, but in addition the equilibrium condition provides additional information on stresses being transferred from one element to its neighbors. Even if this information is relative (in the absence of external load measurements), it provides a very severe constraint on the estimation of the local damage state. The ill-posed character of the identification procedure as an inverse problem is tamed by using a law formulation rather than a stiffness field measurement.

Moreover, a reconditioned method allows for the construction of a residual based on displacement fields (as can be seen from dimensional analysis) rather than on their second derivatives (residual body forces). This approach dampened the noise sensitivity of the searched material properties.

The validation is performed on the very same mesh as the measurement itself. The fact that two mesh sizes have led to the same growth law is a validation on the mesh insensitivity prior to localization. Let us underline that the fact that measured and not assumed boundary conditions are considered makes the identification procedure more realistic.

The present analysis focused only on the damage law identification but the method is currently extended to identify the inelastic (or plastic-like) effects. This is made possible by analyzing the sequence of pictures shot at zero load with respect to the reference picture. The fact that the damage state is already known with the present approach will allow for a decoupled identification procedure. The pixel size corresponds to a physical length scale of 36 μm.

.

  are dependent upon the elastic properties of the layers. If it is assumed that the damage variable follows the same growth law in the region of interest, Equation (4) provides a unique relationship between the damage field D(x) The force residuals should be made as small as possible. This is possible by tuning the parameters of the damage law. Minimizing the equilibrium gap g E

FiguresFigure 1 :

 1 Figures

Figure 2 :

 2 Figure 2: Picture of the prepared surface at failure (left) and experimental set-up (right).

Figure 3 :

 3 Figure 3: Applied load (N) versus time (s). Each local peak data were used to measure

Figure 4 :

 4 Figure 4: Displacement maps u x (top) and u y (bottom) expressed in pixels (1 pixel ↔ 36 µm)

Figure 5 :

 5 Figure 5: Strain maps ε xx (top) and ε yy (bottom) at last step of the analysis of the notched

Figure 6 :

 6 Figure 6: A priori analysis of the standard displacement (σ u ) and strain (σ ε ) uncertainties as

Figure 7 :

 7 Figure 7: Equivalent (shear) strain maps for each step up to failure in a tensile test for the

Figure 8 :

 8 Figure 8: Probability density functions of equivalent strains in the classical geometry with a

Figure 9 :

 9 Figure 9: Identified damage maps for each analyzed cycle for two elements sizes:

Figure 10 :

 10 Figure 10: Comparison of the measured and computed displacement fields (top: cycle #4,

Figure 11 :

 11 Figure 11: Damage law identified by following the classical approach (few strain data are

Table 1 :

 1 Identification results for the two considered discretizations.

Acknowledgments

This work was funded by Agence Nationale de la Recherche under the grant ANR-2006-MAPR-0022-01 (VULCOMP Phase 1 Project).


Benoît Darties

Jean-Claude Konig

Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs

Keywords: coupled-tasks, scheduling, complexity, approximation algorithm, compatibility graph tâches couplées, ordonnancement, complexité, algorithmesd'approximation, graphe de compatibilité

We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e.coupledtasks having the same sub-tasks execution time and idle time duration. We study severals problems in frame works of classic complexity and approximation for which the compatibility graph G c is bipartite (star, chain, ...)I ns u c hc o n t e x t ,w ed esign some efficient polynomial-time approximation algorithms according to difference parameters of the scheduling problem. When G c is a k-stage bipartite graph, we propose, among other, a 7 6 -approximation algorithm when k =1 ,a n da 13 9approximation algorithm when k =2.

1I n t r o d u c t i o n

The detection of an object by a radar system generally uses thef o l l o w i n gp r o c e s s : at r a n s m i t t e re m i t sap u l s ei ns o m ed i r e c t i o nw h i c hp r o p a g a t es though the environmental medium. If the pulse encounters an object, it is reflected back to the transmitter. Using the transmit time and the direction of thep u l s e ,t h et r a n s m i tter can compute the position of the object. Formally this process is divided into three parts: (1) a first operation of duration a as e n s o re m i t st h ep u l s e ; [START_REF] Caprara | The Multiple Subset Sum Problem[END_REF]t h e n the system waits for a fixed amount of time L the propagation of the pulse and its potential reflexion; [START_REF] Caprara | A 3/4-Approximation Algorithm for Multiple Subset Sum[END_REF] then in a second operation of duration b the sensor listen to any pulse echo to conclude of the presence or not of an object and compute its position. Due to the nature of the application, the system worksi nan o n -p r e e m p t i v e mode. Varying the values of parameters a, b and L allows, among others, to adapt the detection range. On mono-processor systems, the idle processing time L can be reused to perform other operations, i.e.to schedule another object detection process using another sensor.

Scheduling issues appear when several sensors using different frequencies can work in parallel, while acquisitions using the same frequency have to be delayed in order to avoid interferences. Two acquisition processes i and j are said compatible if they can work in parallel.

We consider in this pap er a mono-pro cessor system using several sensors, some of them using the same frequencies. Given a set of data acquisitions with they duration and the list of compatible acquisitions, finding a optimal schedule which minimizes the makespan is a problem hard to solve in general, even under restricted hypothesis on the values of a, b, L and/or on the list of compatible acquisitions. We study the variation of the complexity when for any acquisition i,t h ed u r a t i o n so f each of its operations and the idle time between them are equal. We propose exact and approximation results according to different hypothesisw em a d eo nt h el i s to f compatible acquisitions.

This article is organized as follows: first we present the general coupled-task model, a natural way to model such a data acquisition process,andtherelatedw ork. In the next section we introduce the stretched coupled-tasksm o d e la n ds u m m a r i z e the contribution of this paper. The computational complexity results are detailed in Section 4, while Section 5 focuses on polynomial-time approximation algorithms with performance guarantee for NP-Hard instances

2P r e s e n t a t i o n o f c o u p l e d -t a s k s a n d r e l a t e d w o r k

An a t u r a lw a yt om od e ld a t aa c q u i s i t i o np r oc e s sp r e s e n t e di nintroduction is to use coupled-tasks,introducedfirstbyShapiro [START_REF] Shapiro | Scheduling coupled tasks[END_REF]: eachacquisitiontaskisacoupled-task A i =(a i ,L i ,b i ) composed by two sub-tasks of processing time a i and b i ,respectiv ely dedicated for wave transmission and echo reception. Betweent h e s et w os u b -t a s k s there is a fixed idle time L i which represents the spread of the echo in the medium. We work in a non-preemptive mo de: once started, a sub-task cannot be stopped and then continued later. A valid schedule implies here that for any task started at t,the first sub-task is fully executed between t and t+a i ,andthesecondbetw eent+a i +L i and t + a i + L i + b i .W en o t eA = {A 1 ,...,A n } the collection of coupled-tasks to be scheduled. Two tasks A i and A j are said compatible if they use different wave frequencies; any sub-task of A i may be executed during the idle time of A j or reciprocally. A valid schedule implies here that for any tasks A i and A j ,i fe i t h e rt h efi r s ta n d / o r the second sub-task of A i is scheduled during the idle time of A j ,t h e nA i and A j must be two compatible tasks. For clarity we say that A i and A j are executed in parallel in such a schedule. The parallel execution of A i and A j may exist under to configurations, according to the values of a i , L i , b i , a j , L j , b j .Ag r a p hG =(A,E) is used to model such this compatibility, where edges from E link any pair of compatible coupled-tasks.

Due to the combinatory of the parameters of the problem, we uset h eG r a h a m ' s notation scheme α|β|γ [START_REF] Graham | Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey[END_REF] (respectively the machine environment, job characteristic and objective function) to characterize the problems related to coupled-tasks. The job characteristics summarizes the conditions made on the values of a i , L i , b i (independent between tasks, or equal to a constant), and the shape of the compatibility graph G.T h ec o u p l e d -t a s k ss c h e d u l i n gp r o b l e m su n d e rc o m p a t i b i l i ty constraints has been studied in the framework of classic complexity and approximation (see Table 1 -only main results are retained).

(a i ,L i ,b i ) Complexity Approximation Ref. (a i ,a i ,a i ) NPC 3/2 [13] (p, L, p) NPC 7/4+ L 4p [15] (a, L, b) NPC if L ≥ a + b else Poly 3a+2b 2a+2b [12] (1, 2, 1) NPC 10 9 if G c is triangle free else 13 12 [14] (p, p, b i ) or (a i ,p,p)
Poly [START_REF] Simonin | Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph[END_REF] Table 1: Computational complexity and p olynomial-time approximation algorithms for 1|(a i ,L i ,b i ),G c |C max according to the triplet (a i ,L i ,b i ).

3S t r e t c h e d c o u p l e d -t a s k : m o d e l a n d c o n t r i b u t i o n

Model

This paper focuses on stretched coupled-tasks, i.e.coupled-tasks for what the durations of the first sub-task, the second sub-task and the idlet i m ea r ee q u a lt oa stretch-factor applied to an original task

(a i ,L i ,b i )=(1, 1, 1).F o r m a l l y ,as t r e t c h e d coupled-task A i is a task such that a i = L i = b i = α(A i ),w h e r eα(A i )
is the stretch factor of the task. In the rest of the paper, coupled-tasks area l w a y ss t r e t c h e d coupled-tasks, and noted A i when we need to refer to the values a i , b i and L i ,o r with a single identifier, i.e. x,o t h e r w i s e . I ns u c hc o n fi g u r a t i o n ,f o rt w oc o m p a t i b l e tasks A j and A j to be scheduled in parallel, one of the following conditions must hold:

1. either α(A i )=α(A j ):t h e nt h ei d l et i m eo fo n et a s ki sf u l l ye x p l o i t e dt o schedule a sub-task from the other (i.e. b i is scheduled during L j ,a n da j is scheduled during L i ), and the completion of the two tasks is done without idle time.

2. or 3α(A i ) ≤ α(A j ):t h e nt a s kA i is fully executed during the idle time L j of A j .F o rs a k eo fs i m p l i f y ,w es a yw epack A i into A j .

To p o l o g y

Complexity Approximation uug(G c )=Star graph NP -C (Theorem 2) FPT AS (Theorem 6) uug(G c )=Chain graph O(n 3 ) (Theorem 3) G c = 1-stage bipartite, ∆(G c )=2 O(n 3 ) (Theorem 4) G c = 1-stage bipartite, ∆(G c )=3
NP -C (Theorem 5) NP -C (see [START_REF] Simonin | Complexity and approximation for scheduling problem for coupled-tasks in presence of compatibility tasks[END_REF]) PT AS (Theorem 7) G c =c o m p l e t e1-stage bipartite NP -C (see [START_REF] Simonin | Complexity and approximation for scheduling problem for coupled-tasks in presence of compatibility tasks[END_REF]) PT AS (Theorem 7) with constraint α(x)=α(y), ∀x, y ∈ X 1 From this observation, one can deriver from the compatibility graph G =(A,E) ad i r e c t e dc o m p a t i b i l i t yg r a p hG c =( A,E c ) by assigning a direction to each edge E from the task with the lowest stretch factor to the task with the highest one. If two compatible tasks x and y have the same stretch factor, then E c contains both the arc (x, y) and the arc inverted (y, x).R e m a r kt h a ti ff o ra n yp a i ro fc o m p a t i b l e tasks x and y we have α(x) ̸ = α(y),t h e nG c is a directed acyclic graph.

Note that when the job characteristics refer to an undirectedt o p o l o g yf o rt h e compatibility graph (i.e. star, chain), we consider in fact ag r a p hG c such that their undirected underlying graph uuc(G c ) correspond to the given class.

Given a valid schedule σ and a task A i ,w en o t eσ(A i ) the date when A i is being executed, i.e.the first (resp. second) sub-task is executed between σ(A i ) and σ(A i )+a i (resp. between σ(A i )+a i + L i and σ(A i )+a i + L i + b i ). We also denote by seq(W ) the sum of the processing time of the tasks in any set W :

seq(W )=3 x∈W α(x)
Remark that, when W is an independent set for G c ,t h ec o s to fa n yo p t i m a l schedule is at least seq(W ).W en o t eN G (v) the neighborhood of v in G.W en o t e d G (v)=|N(x)| the degree of v in G,a n d∆ G the maximum degree of G.

As we focus our work on bipartite graphs, we recall that a k-stage bipartite graph

is a digraph G =(V 0 ∪•••∪V k ,E 1 ∪•••∪E k )
where V 0 ...V k are disjoint vertex sets, and each arc in E i is from a vertex in V i to a vertex in V i+1 .T h ev e r t e xo fV i are said to be at rank i,a n dt h es u b g r a p hG i =(

V i-1 ∪ V i ,E i ) is called the i-th stage of G,andw ewriteG = G 1 + •••+ G k .N o t et
h a tG is acyclic, and that vertices from V 0 are always source in G (nodes only incident to outgoing arcs) , while vertices from V k are sink (nodes only incident to ingoing arcs). For clarity, a 1-stage bipartite graphs may be referred as triplet (X, Y, E).

Contribution

We define the main problem of this study as 1|a i = L i = b i = α(A i ),G c |C max ,s tu d y the variation of the complexity when G c or uug(G c ) varies, and propose approximation results for instances hard to solve. The results proved in this article are summarized in Table 2.

Prerequisites

We use in this pap er known complexity results on four packing-related problems:

1. The subset sum (ss)p r o b l e m i s a k n o w n p r o b l e m i n w h i c h , g i v e n a s e t S of n positive values and v ∈ IN ,o n ea s ki st h e r ee x i s t sas u b s e tS * ⊆S such that i∈S * i = v.T h i sd e c i s i o np r o b l e mi sw e l l -k n o w nt ob eNP-complete (see [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF]). The optimization version problem is sometimes view as a knapsack problem, where each item profits and weights coincide to a value in S,t h ek n a p s a c k capacity is v,a n do n et r yt ofi n dt h es e to fp a c k a b l ei t e m sw i t hm a x i m u m profit.

2. The multiple subset sum (mss)p r o b l e m i s a v a r i a n t o f w e l l -k n o w n bin packing in which a number of identical bins is given and one would like to maximize the overall weight of the items packed in the bins such that the sum of the item weights in every bin does not exceed the bin capacity.T h ep r o b l e mi s also a special case of the Multiple knapsack problem in which all knapsacks have the same capacities and the item profits and weights coincide. Caprara, and al. [START_REF] Caprara | The Multiple Subset Sum Problem[END_REF] proved that mss admits a PT AS,b u td o e sn o ta d m i taFPT AS even for only two knapsacks. They also proposed a 3 4 -approximation algorithm in [START_REF] Caprara | A 3/4-Approximation Algorithm for Multiple Subset Sum[END_REF].

multiple subset sum with different knapsack capacities (mssdc)

[1] is an extension of mss considering different bin capacities. mssdc also admits a PT AS [START_REF] Caprara | A PTAS for the Multiple Subset Sum Problem with different knapsack capacities[END_REF].

As a generalization of mssdc, multiple knapsack assignment restriction (mkar)p r o b l e m c o n s i s t s t o p a c k s w e i g h t e d i t e m s i n t o n o n -i d e n t i c al

capacity-constrained bins, with the additional constraints that each item can be packed in some bins only. Each item as a profit, the objectiveh e r ei st o maximize the sum of profits of packed items. Considering the profit of each item equals its weight, [START_REF] Dawande | Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions[END_REF] proposed a 1 2 -approximation. We also use a known result concerning a variant of the NP-complete problem 3SAT [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF], denoted subsequently by one-in-(2,3)sat(2, 1):t h i sp r o b l e ma i mt oa s k is there exists an assignment of n boolean variables, with n mod 3 ≡ 0,w h i c h satisfies a set of n clauses of cardinality 2 and n/3 clauses of cardinality 3 such that:

• Each clause of cardinality 2 is equal to (x ∨ ȳ) for some x, y ∈V with x ̸ = y.

• Each of the n literals x (resp. of the literals x)f o rx ∈V belongs to one of the n clauses of cardinality 2,t h u st oo n l yo n eo ft h e m .

• Each of the n (positive) literals x belongs to one of the n/3 clauses of cardinality 3,t h u st oo n l yo n eo ft h e m .

• Whenever (x ∨ ȳ) is a clause of cardinality 2 for some x, y ∈V,t h e nx and y belong to different clauses of cardinality 3. Question: Is there a truth assignment I : V→{ 0, 1} whereby each clause in C has exactly one true literal?

Example: The following logic formula is a valid instance of one-in-(2,3)sat(2, 1):

(x 0 ∨ x 1 ∨ x 2 ) ∧ (x 3 ∨ x 4 ∨ x 5 ) ∧ (x 0 ∨ x 3 ) ∧ (x 3 ∨ x 0 ) ∧ (x 4 ∨ x 2 ) ∧ (x 1 ∨ x 4 ) ∧ (x 5 ∨ x 1 ) ∧ (x 2 ∨ x 5 ).
The answer to one-in-(2,3)sat(2, 1)is yes.I ti ss u ffi c i e n tt oc h o o s ex 0 =1(1 for true), x 3 =1and x i =0(0 for false) for i = {1, 2, 4, 5}.T h i sy i e l d sat r u t h assignment that satisfies the formula, and there is exactly one true literal for each clause. The proof of the NP-completeness is given in [START_REF] Giroudeau | Complexity and approximation for the precedence constrained scheduling problem with large communication delays[END_REF].

4C o m p u t a t i o n a l c o m p l e x i t y

We present severals NP-complete and polynomial results. We first show the problem is NP-hard even when the compatibility graph is a star (Theorem 2),b u tt h e n show it is solvable with a O(n 3 ) time complexity algorithm when G is a chain (Theorem 3). Then we focus our analysis when G c is a 1-stage bipartite graph. We prove the problem is solvable with a O(n 3 ) polynomial algorithm if ∆ G =2(Theorem 4), but becomes NP-hard when ∆ G =3(Theorem 5).

Theorem 1 The problem 1|a

i = L i = b i = α(A i ),G = star|C max is polynomial if the central node admits at least one outcoming arc.
Proof If it exists a least one outgoing arc from the central node x,t h e nt h eo p t imal solution consists in executing the central node in one coupled-task y such that (x, y) ∈ G c .T h er e m a i n i n gt a s k sa r ep r o c e s s e ds e q u e n t i a l l ya f t e rt h ec ompletion of the y-task. 1. For each value i ∈S we introduce a coupled-task x with α(x)=i.L e tT be the set of these tasks.

Theorem 2 The problem 1|a i = L i = b i = α(A i ),G = star|C max is NP-hard if the central node admits only incoming arc. Proof It is easy to see that 1|α(A i )=a i = L i = b i ,G = star|C max is in NP.
2. We add a task y with α y = a y = L y = b y =3v.

3. We define a compatibility constraint between each task x ∈T and y.

Clearly the compatibility graph G is a star with y as the central node. The transformation is clearly polynomial. It easy to see that 1|α

(A i )=a i = L i = b i ,G = star|C max is NP -hard as following:
• Considering the characteristics of the instance when G c is a star, any (optimal) valid scheduling consists in scheduling sequentially a subset T ′ ⊆T of task during the idle time of y,a n di ns c h e d u l i n ga f t e rt h i st h eo t h e rt a s k sf r o m T sequentially. Then the optimal schedule would consist in maximizing w = 3 t∈T ′ α t under the constraint w ≤ L y ,a n di np r o d u c i n gas c h e d u l ew i t ha total length equal to the time to schedule y (i.e. 3α y )plusthetimetosc hedule tasks not executed during L y the idle time of y (ie. • Conversely, if one can exhibit a subset S * ⊆Sthus that i∈S * i = v,t h e n one can produce an optimal schedule by executing sequentially tasks x with α x = i,w h e r ei ∈S * ,d u r i n gt h ei d l et i m eL y =3v of task y,a n db ye x e c u t i n g sequentially tasks z ∈S/S * immediately after the execution of y.

Theorem 3 The problem 1|a i = L i = b i = α(A i ),G = chain|C max admits a polynomial-time algorithm.
Proof When the compatibility graph is a chain, compatibility constraints require tasks to be executed either alone, by pair only, or two consecutively tasks in another big one. The last case occurs only when a vertex x of degree two, called peak, has its two neighbor y and z which can be entirely executed in the inactivity time of x.

Thus if 3α y +3α z ≤ α x ,th e non ec ane x e c u tey and z during the idle time of x;T h e schedule length for this block is exactly 3α x .W ec a no b s e r v et h a tt h ep e a k sc a nn o t be executed in another tasks. Therefore, w.l.o.g. we can assume that there exists an optimal solution where the peak tasks and their neighbors aree x e c u t e dt o g e t h e r .

From this result, we can in p olynomial time mo dify G in G m where all peak vertices, their neighbors and the associated edges are removed. Thus G m is a collection of chains and the best scheduling associated to this graph requires tasks to be executed either alone or by pair.

Given x and y two compatibles tasks, only the two following configurationsallo w them to be scheduled pairwise (by blocks):

1. if α x = α y ,t h e no n ec a ne x e c u t ea y during the idle time of x and b x during the idle time of y.T h em a k e s p a nf o rt h i sb l o c ki se x a c t l y4α x .

2. if α x ≤ αy 3 ,t h e no n ec a ne x e c u t ee n t i r e l yx during the idle time of y,t h e makespan for this block is exactly 3α y ,includinganinactivityperiodofα y -2α x .

By weighting each edge of the graph G m with the sequential time of the overlap of the two tasks which form the edge, our problem has a solution ifw efindamatc hing that minimizes the weight of the matching edges and the isolated vertices.

This problem can be solved in a polynomial-time by reducing the problem to the search for a minimum weighted perfect matching. This problemcanbepolynomially solved in O(n 2 m) time complexity [START_REF] Edmonds | Maximum matching and a polyhedron with 0, 1 vertices[END_REF]. In order to obtain a graph with even number of vertices and such that finding a perfect matching is possible, we construct a graph H c =(V H ,E H ,w) and define a weighted function w : E → IN as follows:

1. Let I 1 be an instance of our problem with a compatibility graph G m =(V m ,E m ), and I 2 an instance of the minimum weight perfect matching problem ing r a p h constructed from I 1 .W ec o n s i d e rag r a p hH c ,consistingoftwocopiesofG m denoted

G ′ m =(V ′ m ,E ′ m ) and G ′′ m =(V ′′ m ,E ′′ m ).T h ev e r t e xc o r r e s p o n d i n gt ox ∈ V m is denoted x ′ in G ′ m and x ′′ in G ′′ m .
M o r e o v e r ,∀i =1,...,n,a ne d g e{x ′ ,x ′′ } in E H is added and we state w({x ′ ,x ′′ })=3α ′

x .T h i sw e i g h tr e p r e s e n t st h es e q u e ntial time of the task alone 2 . In order to provide a polynomial-time algorithm solving our problem, we will prove firstly the following proposition.

x ′ .W eh a v eH c = G ′ m ∪ G ′′ m =(V ′ m ∪ V ′′ m ,E ′ m ∪ E ′′ m ), with |V ′ m ∪ V ′′ m |
Proposition 1 For a minimum weight perfect matching C,w ec a na s s o c i a t ea schedule of minimum processing times C and vice versa.

A2 A1 A3 x ′ 1 x ′ 2 x ′ 3 x ′′ 1 x ′′ 2 x ′′ 3 3 × 2 3 × 8 3 × 8 Gm G ′ m G m ′′ Hc α1 =2 α3 =8 α2 =8 3×8 2 3×8 2 4×8 2 4×8 2

Proof

By construction H c contains an even number of vertices, and the fact that each vertex of G ′ c is connected to an equivalent vertex in G ′′ c ,findingaperfectmatchingon the graph H c is possible. This means that there exists a schedule such thateachtask is executed only once time. Note that the matching in G ′ c is not necessarily identical to the one in G ′′ c ,b u tt h e ys t i l lh a v et h es a m ew e i g h t . T h em a k e s p a no b t a i n e d is equal to the sum of the processing times of the obtained blocks and those of isolated tasks. And since each block has an execution time equal to the weight of the equivalent edge in the perfect matching, we have the sum ofe d g e sw e i g h t so f the matching which is equal to the blocks sum of the schedulingo b t a i n e d .

Thus, for a minimum weight perfect matching C,w ec a na s s oc i a t eas c h e d u l eo f minimum length C and vice versa. This ends the proof of the Proposition 1.

Proof continuation of Theorem 3

The proposition 1 shows the relationship between a solution to our problem with G m and a solution of a minimum weight perfect matching in H c .H o w e v e r , t h e Edmonds algorithm can find a minimum weight perfect matching in O(n 2 m) [START_REF] Edmonds | Maximum matching and a polyhedron with 0, 1 vertices[END_REF]. So the optimization problem with G m is polynomial, and if one adds the execution of the blocks created by removed vertices, this leads to the problem

1|a i = L i = b i = α(A i ),G = chain|C max is polynomial.
In following, we study the variation of the complexity in the case of the compatibility graph is oriented in presence of a 1-stage bipartite graph according to the different values.

Theorem 4 The problem of deciding whether an instance of 1|a

i = L i = b i = α(A i ),G c =1-stage bipartite, ∆ Gc =2|C max is polynomial.
Proof Let G c =( X, Y, E) be a 1-stage bipartite compatibility graph. Y -tasks will always be scheduled sequentially. The aim is to fill their idlet i m ew i t ham a x i m u m of tasks of X,w h i l et h er e m a i n e dt a s k sw i l lbee x e c u t e da f t e rt h eY -tasks. We just have to minimize the length of the remained tasks. Note that d Gc (y) ≤ 2.T h e algorithm use three steps :

1. for each task y ∈ Y such that 3α(x 1 )+3α(x 2 ) ≤ α(y) where x 1 and x 2 are the only two neighbors of Y ,w ea d dy to the schedule and execute x1 and x 2 sequentially during the idle time of y.T h e nw er e m o v ey, x 1 and x 2 from the instance.

2. Each remaining task y ∈ Y admits at most two incoming arcs (x 1 ,y) and / or (x 2 ,y).W ea d d aw e i g h tα(x) to the arc (x, y) for each x ∈ N(y),t h e n perform a maximum weight matching on G c in order to minimize the length of the remained tasks of X.T h u s ,t h em a t c h e dc o u p l e d -t a s k sa r ee x e c u t e d ,a n d these tasks are removed from G c .

3. Then, remaining tasks from X are allotted sequentially after the other tasks.

The complexity of an algorithm is O(n 3 ).

Theorem 5 The problem of deciding whether an instance of

1|a i = L i = b i = α(A i ),G c =1-stage bipartite, ∆ Gc =3
|C max has a schedule of length at most 54n is NP-complete with n the number of tasks.

Proof It is easy to see that 1. For all x ∈V,weintroducefourv ariable-tasks: x, x ′ , x and x′ with (a i ,L i ,b i )= (1, 1, 1), ∀i ∈{x, x ′ , x, x′ }.T h i sv a r i a b l e -t a s k ss e ti sn o t e dVT .

1|a i = L i = b i = α(A i ),G c =1-stage bipartite, ∆ Gc = 3|C max =54n ∈NP.O u rp
2. For all x ∈V ,w ei n t r o d u c et h r e el i t e r a l -t a s k sL x ,C x and Cx with L x = (2, 2, 2); C x = Cx =(6, 6, 6).T h es e to fl i t e r a l -t a s k si sd e n o t e dLT .

3. For all clauses with a length of three, we introduce two clause-tasks C i and Ci with C i =(3, 3, 3) and Ci =(6, 6, 6).

4. For all clauses with a length of two, we introduce one clause-task C i with C i =(3, 3, 3).T h es e to fc l a u s e -t a s k si sd e n o t e dCT .

The following arcs model the compatibility constraints:

(a) For all boolean variables x ∈V,w ea d dt h ea r c s(L x ,C x ) and (L x , Cx ) (b) For all clauses with a length of three denoted C i =(y ∨ z ∨ t),w ea d dt h e arcs (y, C i ), (z, C i ), (t, C i ) and (ȳ ′ , Ci ), (z ′ , Ci ), ( t′ , Ci ). (c) For all clauses with a length of two denoted C i =(x ∨ ȳ),w ea d dt h ea r c s (x ′ ,C i ) and (ȳ, C i ). (d) Finally, we add the arcs (x, C x ), (x ′ ,C x ) and (x, Cx ) and (x ′ , Cx ). x x′ ȳ′ z′ In follows, we say that a task x is merged to a task y,i fi te x i s t sac o m p a t i b i l i t y constraint from x to y; i.e.the coupled-task x may be executed during the idle of coupled-task y.

L x C x Cx (x, y, z) (x, y, z) C C ′ C ̸ = C ′ two clause-tasks of lenght two (a i ,L i ,b i ), =(1, 1, 1), ∀i ∈{x, x ′ , x, x′ }, ∀x ∈V L x =(2, 2, 2); C x = Cx =(6, 6, 6),x∈V C (x,y,z) =(3, 3, 3) C (x,y,z) =(6, 6, 6) C C = C C ′ =(3, 3, 3)
• Let us first assume that there is a schedule with length of 54n at most. We prove that there is a truth assignment I : V→{ 0, 1} such that each clause in C has exactly one true literal (i.e. one literal equal to 1). We make some essentials remarks:

1. The length of the schedule is given by an execution time of the coupledtasks admitting only incoming arcs, and the value is

54n =3 α CT |CT | + α LT (|LT | -|{L x ,x ∈V} | )=9 |{C i ∈CT of length 2 and 3}| +18|{ Ci ∈ CT }| +18|{C
x and Cx ∈LT}|=9× 4n 3 +18× n 3 +18× 2n. Thus, all tasks from VT ∪ {L x ,x ∈V}must be merged with tasks from CT ∪ (LT -{L x ,x ∈V}).

2. By the construction, at most three tasks can be merged together.

3. L x is merged with C x or Cx . 4. The allocation of coupled-tasks from CT ∪ (LT -{L x ,x ∈V } ) leads to 18n idle time. The length of the variable-tasks VT and L x equals 18n (in these coupled-tasks there are 6n idle times). 5. If the variable-tasks x and x ′ are not merged simultaneously with C x , i.e.only one of these tasks is merged with C x ,s o ,b yw i t ht h ep r e v i o u sd i scussion, it is necessary to merge a literal-task L y ,w i t hx ̸ = y one variabletask (ȳ or ȳ′ )w i t hC y or Cy .I ti si m p o s s i b l eb ys i z eo fc o u p l e d -t a s k s .I n the same ways, the variable-tasks x et x′ are merged simultaneously with Cx .

6. Hence, first x and x ′ are merged with C x or with clause-task where the variable x occurs. Second, x and x′ are merged with Cx or a clause-task.

So, we affect the value "true" to the variable l iff the variable-task l is merged with clause-task(s) corresponding to the clause where the variable l occurs. It is obvious to see that in the clause of length three and two we have one and only one literal equal to "true".

• Conversely, we suppose that there is a truth assignment I : V→{ 0, 1},s u c h that each clause in C has exactly one true literal.

-If the variable x = true then we merged the vertices L x with C x ; x with the clause-task C i corresponding to the clause of length three which x occurs;

x ′ with the clause-task C i corresponding to the clause of length two which x occurs; and x, x′ with Cx .

-If the variable x = false then we merged the vertices L x with Cx ; x with the clause-task corresponding to the clause of length two which x occurs; x′ with the clause-task Ci corresponding to the clause (C)o fl e n g t ht h r e e which x occurs; and x, x ′ with C x .

For a feasible schedule, it is sufficient to merge vertices which are in the same partition. Thus, the length of the schedule is at most 54n.

5P o l y n o m i a l -t i m e a p p r o x i m a t i o n a l g o r i t h m s

Star graph Theorem 6

The problem

1|a i = L i = b i = α(A i ),G = star|C max admits a FPT AS.
Proof The central node admits only incoming arcs (the case of the central node admits at least one outcoming arc is given by Corollary 1). Therefore, we may use the solution given by the subset sum (ss)( s e e [START_REF] Ibarra | Fast approximation algorithms for the Knapsack and Sum of Subset problems[END_REF]a n d[ 1 0 ] ) ) . I n d e e d ,t h es c h e d u l e is follows: the central node is executed first with the coupled-tasks chosen by an FPT AS algorithm, the remaining tasks are processed after the completion of the central node.

1-stage bipartite graph

Scheduling coupled-tasks during the idle time of others can be related to packing problems, especially when the constraint graph G c is a bipartite graph. In the following, we propose several approximation when G c is a 1-stage bipartite graph.

Lemma 1 Let P be a problem with mkar mssdc, mss} such that P admits a ρ-approximable then the following problems

1. 1|a i = L i = b i = α(A i ),G c =1-stage bipartite|C max , 2. 1|α i = a i = L i = b i ,complete bipartite|C max 3. 1|α i = a i = L i = b i ,complete bipartite|C max
where the constraint graph is a complete bipartite G=(X,Y), and al l the tasks from Y have the same α(y).

is approximable to a factor In such instance, any valid schedule consists to find for each task y ∈ Y asubset of compatible tasks X y ⊆ X to pack into y ∈ Y ,e a c ht a s ko fx being packed at most once. Let X p = ∪ y∈Y X y be the union of tasks of X packed into a task from Y .L e tX p the set of remaining tasks, with X p = X/X p .O b v i o u s l y ,w e have: seq(X p )+seq(X p)=seq(X )

1+ (1-ρ) 3 . Proof 1. Let consider an instance of 1|α i = a i = L i = b i ,G c =1-stage bipartite|C max such that G c =(X, Y, E),
As Y is an independent set in G,tasksfromY have to be scheduled sequentially in any (optimal) solution. The length of any schedule S is then the time to execute entirely tasks from Y plus the length to schedule sequentially the tasks from X p.F o r m a l l y :

C max (S)=seq(Y )+seq(X p) (2)
From Eq. ( 1) and (2) we have:

C max (S)=seq(Y )+seq(X) -seq(X p ). (3)
We use here a reduction to mkar:e a c ht a s kx from X is an item having a weight 3.α(x),e a c ht a s kf r o mY is a bin with capacity α(y),a n de a c hi t e mx can be packed on y if and only if the edge {x, y} belong to the bipartite graph. Using algorithms and results from the literature, one can obtain an assignment of some items into bins, and note X p the set of packed items. The cost of the solution for the mkarproblem is seq(X p ).I fmkar is approximable to a factor ρ,t h e nw eh a v e:

seq(X p ) ≥ ρ × seq(X * p ), (4)
where X * p is the set of packable items with the maximum profit. Combining Eq. ( 3) and (4) , we obtain a solution for 1|α i = a i = L i = b i ,bipartite|C max with a length:

C max (S) ≤ seq(Y )+seq(X) -ρ × seq(X * p ) (5)
As X and Y are two fixed sets, a optimal solution S * with minimal length C max (S * ) is obtained when seq(X p ) is maximum, i.e.when X p = X * p .T h e length of any optimal solution is here:

C max (S * )=seq(Y )+seq(X) -seq(X * p ) (6)
Using Eq. ( 5) and ( 6), the ratio obtained between our solution S and the optimal one S * is :

C max (S) C max (S * ) ≤ seq(Y )+seq(X) -ρ × seq(X * p ) seq(Y )+seq(X) -seq(X * p ) ≤ 1+ (1 -ρ) × seq(X * p ) seq(Y )+seq(X) -seq(X * p ) (7
seq(X * p ) ≤ 1 3 seq(Y ) (8)
Combined to Eq. ( 7) , we obtain the following upper bound:

C max (S) C max (S * ) ≤ 1+ (1 -ρ) 3 . (9)
We obtain the desired result.

2. For the problem 1|α i = a i = L i = b i ,complete bipartite|C max ,t h ep r o o fi s identical keeping in mind that mssdc is a special case of mkar where each item can be packed in any bin.

3. For the problem 1|α i = a i = L i = b i ,complete bipartite|C max where the constraint graph is a complete bipartite G =(X, Y ),andallthetasksfromY have the same α(y),theproofisiden ticalaspreviouslysincemssdc is a generalization of mss.

Theorem 7

The following problems admits a polynomial-time approximation algorithms:

1. The problem 1|a i = L i = b i = α(A i ),G c =1 -stage bipartite|C max is approximable to a factor 7 6 .

The problem 1|a

i = L i = b i = α(A i ),G c = complete 1-stage bipartite|C max
admits a PT AS.

The problem 1|a

i = L i = b i = α(A i ),G c = complete 1-stage bipartite|C max ,
where all the tasks from Y have the same stretch factor α(y):

(a) is approximable to a factor 13 12 . (b) admits a PT AS. Proof 1. Authors from [START_REF] Dawande | Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions[END_REF] proposed a ρ = 1 2 -approximation algorithm for mkar.R e u s i n g this result with Lemma 1, we obtain a 7 6 -approximation for

1|a i = L i = b i = α(A i ),G c =1-stage bipartite|C max .
2. We know that mssdc admits a PT AS [START_REF] Caprara | A PTAS for the Multiple Subset Sum Problem with different knapsack capacities[END_REF], i.e.ρ =1-.U s i n gt h i sa l g o r i t h m to compute such a PT AS and Lemma 1, we obtain an approximation ratio of 1+ 3 for this problem.

The problem 1|a

i = L i = b i = α(A i ),G c = complete 1-stage bipartite|C max ,
where all the tasks from Y have the same stretch factor α(y):

(a) Authors from [START_REF] Caprara | A 3/4-Approximation Algorithm for Multiple Subset Sum[END_REF] proposed a ρ = 3 4 -approximation algorithm for mss. Reusing this result with Lemma 1, we obtain a 13 12 -approximation for 1|α i = a i = L i = b i ,complete bipartite|C max . (b) They also proved that mss admits a PT AS [START_REF] Caprara | The Multiple Subset Sum Problem[END_REF] , i.e.ρ =1-.U s i n g the algorithm to compute such a PT AS and Lemma 1, we obtain an approximation ratio of

1+ 3 for 1|a i = L i = b i = α(A i ),G c = complete 1-
stage bipartite|C max when nodes from Y have the same stretch factor.

2-stage bipartite graph

Theorem 8 The problem

1|a i = L i = b i = α(A i ),G c =2
-stage bipartite|C max is approximable to a factor 13 9 . Proof Reusing the notation introduced for k-stage bipartite graph(seeSection5.3), we consider an instance of

1|a i = L i = b i = α(A i ),G c =2 -stage bipartite|C max where G c =(V 0 ∪ V 1 ∪ V 2 ,E 1 ∪ E 2 ) ,w h e r ee a c ha r ci nE i is from a vertex in V i to a vertex in V i+1 ,f o ri ∈ 1, 2.
Definition 1 We note V ip (p=packed), (resp. V ia (a=alone) ) i =0 , 1 the set of tasks merged (resp. remaining) in any task from y ∈ V i+1 in a solution S.M o r e o v e r , V ib (b=box), i =1 , 2 the set of tasks scheduled with some tasks from V i-1 merged into it.This notation is extended to a optimal solution S * by adding a star in the involved variables.

Considering the specificities of the instance, in any (optimal) solution we make some essential remarks:

1. Tasks from V 0 are source nodes for G c ,a n dc a nb ee i t h e rs c h e d u l e da l o n e ,o r merged into some tasks from V 1 only. Given any solution S to the problem on G c , {V 0p ,V 0a } is a partition of V 0 .

2. Tasks from V 1 can be either scheduled alone, merged into some tasks from V 2 , or scheduled with some tasks from V 0 merged into it. Given any solution S to the problem on

G c , {V 1p ,V 1a ,V 1b } is a partition of V 1 .
3. Tasks from V 2 form an independent set for G c ,a n dh a v et ob es c h e d u l e ds equentially in any schedule, either alone, or with some tasks from V 1 merged into it. Given any solution S to the problem on G

c , {V 2a ,V 2b } is a partition of V 2 .
Any solution would consist to schedule first each task with at least one task merged into it, then to schedule the remaining tasks (alone). Given an optimal solution S * , the length of S * is given by the following equation:

S * = seq(V 1 * b )+seq(V 2 b)+seq(V 0 * a )+seq(V 1 * a )+seq(V 2 * a ) (10)
or, more simply

S * = seq(V 2 )+seq(V 1 * b )+seq(V 0 * a )+seq(V 1 * a ) (11)
Note that V 0 * p and V 1 * p are not part of the equation, as they are scheduled during the idle time of

V 1 * b and V 2 * b .
The main idea of the algorithm is divided into three parts:

1. First we compute a part of the solution with a 7 6 -approximation on G 0 thanks to Theorem 7, where

G 0 = G c [V 0 ∪ V 1 ] is the 1-th stage of G c .
2. Then we compute a second part of the solution with a 7 6 -approximation on G 1 thanks to Theorem 7, where

G 1 = G c [V 1 ∪ V 2 ] is the 2-th stage of G c .
3. To finish we merge these two parts and resolve potential conflicts between them.

Let consider an instance restricted to the graph G 0 .N o t et h a tG 0 is a 1-stage bipartite graph. Let S * [G 0 ] be an optimal solution on G 0 .L e tu sn o t eV 0 *

p [G 0 ] the set of tasks from V 0 packed into tasks from V 1 in S * [G 0 ],a n dV 0 * a [G 0 ] the set of remaining tasks.
Obviously, we have:

S * [G 0 ]=seq(V 1 )+seq(V 0 * a [G 0 ]) (12)
Given any solution S[G 0 ],l e tu sn o t eV 1b [G 0 ] the set of tasks from V 1 with at least one task from V 0 merged into them, and V 1a [G 0 ] the remaining tasks. Let us note V 0p [G 0 ] the set of tasks from V 0 merged into V 1 ,a n dV 0a [G 0 ] the set of remaining tasks. We use Theorem 7, Lemma 1, and the demonstration presented in their proof from [START_REF] Dawande | Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions[END_REF], to compute a solution S[G 0 ] such that:

seq(V 0p [G 0 ]) ≥ 1 2 seq(V 0 * p [G 0 ]) (13)
Note that we have

seq(V 0p [G 0 ]) + seq(V 0a [G 0 ]) = seq(V 0 * p [G 0 ]) + seq(V 0 * a [G 0 ]) = seq(V 0 ) (14)
As

V 0 * a [G 0 ] represents the set of tasks not packed into V 1 in an optimal S * [G 0 ] such that seq(V 0 * a [G 0 ]) is minimal, we know that seq(V 0 * a [G 0 ]) ≤ seq(V 0 * a )
.Combining Equation [START_REF] Simonin | Complexity and approximation for scheduling problem for coupled-tasks in presence of compatibility tasks[END_REF] and Equation ( 14), one obtain:

seq(V 0a [G 0 ]) ≤ seq(V 0 * a [G 0 ]) + 1 2 seq(V 0 * p [G 0 ]) ≤ seq(V 0 * a )+ 1 2 seq(V 0 * p [G 0 ]) (15)
We use an analog reasoning on an instance restricted to the graph G 1 .L e tS * [G 1 ] be an optimal solution on G 1 .L e tu sn o t eV

1 * p [G 1 ] the set of tasks from V 1 packed into tasks from V 2 in S * [G 1 ],a n dV 1 * a [G 1 ]
the set of remaining tasks. Given any solution S[G 1 ],l e tu sn o t eV 2b [G 1 ] the set of tasks from V 2 with at least one task from V 1 merged into them, and V 1a [G 1 ] the remaining tasks. One can compute a solution S[G 1 ] based on a set of tasks V 1p [G 1 ] packed in V 2 such that:

seq(V 1p [G 1 ]) ≥ 1 2 seq(V 1 * p [G 1 ]) (16)
and

seq(V 1a [G 1 ]) ≤ seq(V 1 * a [G 1 ]) + 1/2seq(V 1 * p [G 1 ]) ≤ seq(V 1 * a )+1/2seq(V 1 * p [G 1 ]) (17) as we know that seq(V 1 * a [G 1 ]) ≤ seq(V 1 * a ).
We design the feasible solution S for G c as follows:

• We compute a solution S[G 1 ] on G 1 ,t h e nw ea d dt oS each task from V 2 and the tasks from V 1 merged into them (i.e. V 1p [G 1 ])i nS[G 1 ].

• Then we compute a solution S[G 0 ] on G 0 ,t h e nw ea d dt oS each task v from V 1b [G 0 ]/V 1p [G 1 ] and the tasks from V 0 merged into them.

• The tasks V 1a [G 1 ]/V 1b [G 0 ] and V 0a [G 0 ] are added to S and scheduled sequentially.

• We note V conf lict the set of remaining tasks, i.e. the set of tasks from V 0 which are merged into a task v ∈ V 1 in S[G 0 ],t h u st h a tv is merged into a task from

V 2 in S[G 1 ].
Remark that:

seq(V 1b [G 0 ]/V 1p [G 1 ]) + seq(V 1a [G 1 ]/V 1b [G 0 ]) = V 1a [G 1 ]) (18)
Thus the cost of our solution S is

S = seq(V 2 )+seq(V 1a [G 1 ]) + seq(V 0a [G 0 ]) + seq(V conf lict ) (19)
It is also clear that:

seq(V conf lict ) ≤ 1 3 seq(V 1p [G 1 ]) ≤ 1 3 seq(V 1 * p [G 1 ]) (20)
Using Equations ( 15), ( 17) and (20) in Equation (19), we obtain

S ≤ seq(V 2 )+seq(V 1 * a )+ 5 6 seq(V 1 * p [G 1 ]) + seq(V 0 * a )+ 1 2 seq(V 0 * p [G 0 ]) (21)
Using Equations ( 11) and (21), we obtain

S ≤ S * + 5 6 seq(V 1 * p [G 1 ]) + 1 2 seq(V 0 * p [G 0 ]) (22)
We know that S * ≥ seq(V 2 ).W ea l s ok n o wt h a tt a s k sf r o m(V 1 * p [G 1 ]) must be merged into tasks from V 2 and cannot exceed the idle time of V 2 ,i m p l y i n gt h a t seq(

V 1 * p [G 1 ])) ≤ 1
3 seq(V 2 ).O n ec a nw r i t et h ef o l l o w i n g:

5 6 seq(V 1 * p [G 1 ]) S * ≤ 5 6 × 1 3 seq(V 2 ) seq(V 2 ) ≤ 5 18 (23)
We know that tasks from (V 0 * p [G 0 ]) must be merged into tasks from V 1 and cannot exceed the idle time of V 1 ,i m p l y i n gt h a tseq(V 0 * p [G 0 ])) ≤ 1 3 seq(V 1 ).W ea l s ok n o w that S * ≥ seq(V 1 ),a sV 1 is an independent set of G c .O n ec a nw r i t et h ef o l l o w i n g:

1 2 seq(V 0 * p [G 0 ]) S * ≤ 1 2 . 1 3 seq(V 1 ) seq(V 1 ) ≤ 1 6 (24)
Finally, with Equations ( 22), ( 23) and (24) the proof is finished:

S S * ≤ 13 9 (25)
6C o n c l u s i o n

The results proposed in this paper are summarized in Table 2. New presented results suggest the main problem of coupled tasks scheduling remains difficult even for restrictive instances, here stretched coupled-tasks when the constraint graph is ab i p a r t i t eg r a p h . W h e nw ec o n s i d e rs t r e t c h e dc o u p l e d -t a s k s, the maximum degree ∆ G seems to play an important role on the problem complexity, as the problem is already NP-Hard to solve when the constraint graph is a star. Approximation results presented in this paper show the problem can be approximated with interesting constant ratio on k-stage bipartite graphs for k =1or 2.T h ep r e s e n t e d approach suggests a generalization is possible for k ≥ 3.T h i sp a r tc o n s t i t u t e so n e perspective of this work. Other perspective would consists to study coupled-tasks on other significant topologies, including degree-bounded trees, or regular topologies like the grid.

7 6 -

 6 APX (Theorem 7) G c =c o m p l e t e1-stage bipartite

13 12 -

 12 APX (Theorem 7) G c = 2-stage bipartite NP -C (Theorem 5) 13 9 -APX (Theorem 8)

  W e propose a reduction to ss problem. From an instance of ss composed by a set S of n positive values and v ∈ IN (with v ≥ x, ∀x ∈ S), we construct an instance of 1|star, α i = a i = L i = b i |C max in the following way:

Figure 1 :

 1 Figure 1: Example of the transformation

  r o o fi sb a s e do nar e d u c t i o nf r o mone-in-(2,3)sat(2, 1): given a set V of n boolean variables with n mod 3 ≡ 0,as e to fn clauses of cardinality two and n/3 clauses of cardinality three, we construct an instance π of the problem 1|a i = L i = b i = α(A i ),G c =1-stage bipartite, ∆ Gc =3|C max =54n in following way (Figure 2 illustrates the construction):

Figure 2 :

 2 Figure 2: A partial compatibility graph for the NP-completeness of the scheduling problem 1|bipartite of depth one, d(G c ) ≤ 3,α i = a i = L i = b i |C max

  whereX ∪Y are coupled-tasks, and by a stretch factor function α : X ∪ Y → IN ,andarcsfromE model the constraints between tasks.

  ) By definition, X * p ⊆ X.M o r e o v e r ,a st h ep r o c e s s i n gt i m eo fX * p cannot excess the idle time of tasks from Y ,w eo b t a i n :

Table 2 :

 2 Complexity and approximation results.

  of even size. 2. For two compatibles tasks x ′ and y ′ with 3α x ′ ≤ α y ′ or 3α y ′ ≤ α x ′ ,w ea d d the edges {x For two compatibles tasks x ′ and y ′ with α x ′ = α y ′ ,w ea d dt h ee d g e s{x ′ ,y ′ } and {x ′′ ,y ′′ } in E,a n dw es t a t ew({x ′ ,y ′ })=w({x ′′ ,y ′′ })=

	4×α x ′

′ ,y ′ } and {x ′′ ,y ′′ } in E and we state w({x ′ ,y ′ })=w({x ′′ ,y ′′ })=

3×max{α x ′ ,α y ′ } 2 .

3.

Acknowledgment

This work has been funded by the regional council of Burgundy.