Azeddine Cheref
email: cheref@laas.fr

Alessandro Agnetis
email: agnetis@dii.unisi.it

Christian Artigues
email: artigues@laas.fr

Jean-Charles Billaut
email: jean-charles.billaut@univ-tours.fr

Fixed-sequence single machine scheduling and outbound delivery problems

In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time and transportation times between customers are taken into account. Since the sequence is given, the problem consists to form batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NP-hardness of the general problem is established and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which complexity proofs or polynomial time algorithms are given.

Introduction

This paper deals with a model for coordinating production and delivery schedules. In many production systems, finished products are delivered from the factory to multiple customer locations, warehouses, or distribution centers by delivery vehicles. An increasing amount of research has been devoted, during the last twenty years, to devise integrated models for production and distribution. These models have been largely analyzed and reviewed by [Chen, 2010], who proposed a detailed classification scheme. The models reflect the variety of issues, including systems structure, vehicle/transportation system characteristics, delivery modes, various types of time constraints. In the large majority of the models in the literature, the coordination of production and distribution is achieved through the creation of batches, i.e., several parts are shipped together and delivered to their respective destinations during a single trip. When forming batches, one must therefore take into account both production information (such as processing time, release dates etc) and delivery information (such as customer location, time windows etc). Most of the models presented in the literature explicitly take into account transportation times to reach the customers' location, but there are no proper routing decisions, since the number of distinct customers is typically very small. Hence, the focus of the analysis is often on scheduling and batching.

1 Many studies consider delivery as a separate step after production, but do not model it in details, e.g. assuming that a sufficiently large number of vehicles is available to deliver the products at any time or assuming that it has only one customer. We briefly discuss some works related to integrated scheduling and delivery decisions. [Li et al., 2005] analyze the joint problem of production sequencing and batch formation, in order to minimize total delivery time, given that delivery is performed by a single vehicle. Total delivery time is a meaningful indicator of the overall efficiency of the delivery process. They show that in general the problem is NP-hard, and then give polynomial time algorithms for the problem with a fixed number of distinct destinations. In [START_REF] Chen | Logistics scheduling with batching and transportation[END_REF], there are various destinations but a batch can only contain jobs of the same destination. [START_REF] Fan | Integrated scheduling of production and delivery on a single machine with availability constraint[END_REF], consider a non availability time interval on the machine, several vehicles without capacity constraint and only transportation costs (no vehicle routing problem associated to the delivery). A single vehicle with a storage area and one or two customers is considered in [START_REF] Chang | Machine scheduling with job delivery coordination[END_REF]. The authors show that the problem is NP-hard for the makespan objective. Other complexity results are provided as well as polynomial time algorithms for special cases. For the same objective function, [START_REF] Li | Machine scheduling with pickup and delivery[END_REF] study the pickup and delivery problem in which a single vehicle travels between the machine and the warehouse, whereas [START_REF] Wang | Production scheduling with supply and delivery considerations to minimize the makespan[END_REF]] study a similar problem in which three different locations and two vehicles are considered. The first vehicle transports unprocessed jobs between the warehouse and the factory and the second one transports finished jobs between the factory and the customer. [START_REF] Hall | Scheduling with fixed delivery dates[END_REF] consider the problem in which the delivery dates are fixed in advance. In order to minimize the makespan, [START_REF] Gao | Integrated batch production and distribution scheduling with limited vehicle capacity[END_REF] consider the problem on a single machine scheduling and a unique capacitated vehicle with a no wait constraint, i.e., the batch must be delivered as soon as it is completed. They show that the problem is NP-hard, and then give polynomial time algorithms for the special case with constant travel times.

The cases where the delivery problem is between machines (inbound delivery) are reported by [START_REF] Lee | Machine scheduling with transportation considerations[END_REF]] and [START_REF] Hurink | Makespan minimization for flowshop problems with transportation times and a single robot[END_REF], where the authors consider multiple machines and transportation time between them. [START_REF] Lee | Machine scheduling with transportation considerations[END_REF]] consider also the case where the finished jobs are delivered to one customer location. Some complexity results are given. In [START_REF] Agnetis | Coordination of production and interstage batch delivery with outsourced distribution[END_REF], [START_REF] Agnetis | Two faster algorithms for coordination of production and batch delivery: A note[END_REF] there are two machines and the transportation is made between these machines, various cases are treated and the objective is to minimize the total transportation cost.

Using the terminology of [Chen, 2010], the models presented in this paper concern batch delivery with routing, i.e., orders going to different customers can be delivered together in the same shipment (batch).

However, a distinctive feature of the problems is studied. We consider a fixed sequence of production and delivery, i.e. the jobs must be delivered in the same order in which they are produced. Examples of situations in which the customer sequence is fixed are reported by [START_REF] Armstrong | A zero-inventory production and distribution problem with a fixed customer sequence[END_REF] and [START_REF] Viergutz | Integrated production and distribution scheduling with lifespan constraints[END_REF]. For maximizing the total satisfied demand in a single round trip, the authors consider that the products expire in a constant time after their completion time and that a delivery time window exists for each product. In [START_REF] Lenté | Problème de livraison a séquence fixée[END_REF], the authors search for a batching of jobs where a single capacitated vehicle is used for the delivery. Polynomial time algorithms are proposed for minimizing the makespan, the maximum lateness and the number of tardy jobs but the sum of delivery times is not treated. [START_REF] Tsirimpas | Single vehicle routing with a predefined customer sequence and multiple depot returns[END_REF] minimize the overall distance traveled for the single vehicle routing with a predefined customer sequence. This problem can be seen as one of the problems treated in [START_REF] Lenté | Problème de livraison a séquence fixée[END_REF] for the makespan minimization with zero processing times (no scheduling problem). In [START_REF] Agnetis | Coordination of production and interstage batch delivery with outsourced distribution[END_REF] and [START_REF] Agnetis | Two faster algorithms for coordination of production and batch delivery: A note[END_REF] and [START_REF] Li | Machine scheduling with pickup and delivery[END_REF], special cases with a predefined sequence are addressed and for each of them, polynomial time algorithms are given.

Here we will mainly focus on the problem of deciding how to form batches with a given production sequence (problem P1). The more general problem in which the sequence is not fixed and has to be decided (proved NP-hard in [Li et al., 2005])) is denoted by P2.

Our contributions are as follows. We completely characterize the complexity of Problem P1, showing that when the objective function Z is to minimize the total delivery time, it is NP-hard in the ordinary sense, and that it can be solved in pseudopolynomial time for any sum-type function of the delivery times. Then, we focus on the special case in which all transportation times are identical (constant travel times), and we show that when Z is the total delivery time minimization, both problems P1 and P2 can be solved in polynomial time. The paper is organized as follows. In Section 2 we present the problem formally and show that the problem is NP-hard when Z is the total delivery time, and that it can be solved in pseudopolynomial time when Z is any sum-type objective function. In Section 3, we study two particular cases that remain NP-hard: the case where preemption is allowed and the case where the number of locations is smaller than the number of jobs. In Section 4 we study two polynomially solvable cases: the case where the number of locations is fixed and the case where travel times are constant. Finally, some conclusions and future research directions are presented in Section 5.

Problem definition and complexity

Problem definition and notation

The problem considered in this paper can be described as follows. A set of n jobs is given and their production sequence is known. Each job J j , j = 1, . . . , n, requires a certain processing time p j on a single machine, and must be delivered to a certain location site. For the sake of simplicity, when it does not create confusion, we use j to refer to the destination of job J j . We denote by t i,j the transportation time from destination i to destination j. For analogy with vehicle routing problems, we refer to the manufacturer's location as the depot. We use M to denote the depot (manufacturer), hence t M,j = t j,M is the transportation time between the depot and destination j. Unless otherwise specified, we assume that transportation times are symmetric and satisfy the triangle inequality.

Deliveries are carried out by a single vehicle. The vehicle loads a certain number of jobs that have been produced and departs towards the corresponding destinations. Once all the jobs have been delivered, it returns to the depot, hence completing a round trip. The set of jobs delivered during a single round trip constitutes a batch. The capacity c of the vehicle is the maximum number of jobs it can load and hence deliver in a round trip. The jobs must be delivered in the order in which they are produced, hence the production sequence also specifies the sequence in which the customers have to be reached.

The problem consists in deciding a partition of all jobs into batches, i.e., a batching scheme. Each batch will be routed according to the manufacturing sequence.

In general, the performance of the system depends on all the concurrent decisions: production scheduling, batching and vehicle routing. This requires therefore an integrated model, allowing one to coordinate all these aspects. A solution to our problem with fixed sequence, is the specification of a batching scheme.

Given a solution, we denote by C j the completion time of job J j on the single machine, which is also the time at which the job is released for delivery, i.e., the batch including job J j cannot start before C j . We denote by D j the delivery time of J j , i.e., the time at which the job J j is delivered at its destination.

The performance measures we consider in this paper depend on such delivery times. In particular, denoting with Z the performance measure, in this paper we consider:

• the total delivery time, i.e., Z = n j=1 D j • a general sum-type performance index, i.e., Z = n j=1 f j (D j ), where f j (D j ) is a general, nondecreasing function of D j , j = 1, . . . , n.

Note that the latter case includes total (weighted) delivery time, total (weighted) tardiness, etc.

We consider the following problem:

Problem P 1(Z). Given n jobs of length p j , j = 1, . . . , n, transportation times t i,j for all i, j, and a sequence σ, find a batching scheme B such that Z is minimized.

Complexity

Since the production sequence is given, and since jobs are delivered to the respective customers in the same given order, we assume that the job sequence is σ = (J 1 , J 2 , ..., J n ). Only travel times t j,j+1 are relevant, as well as times t j,M = t M,j , representing the travel time between customer j and the manufacturer and vice-versa. Let us first consider the problem where the objective function is the total delivery time, i.e., problem P 1( n j=1 D j ). For our purposes, we introduce the following problem. Even-Odd Partition (EOP). A set of n pairs of positive integers (a

1 , b 1 ), (a 2 , b 2 ), . . . , (a n , b n ) is given, in which, for each i, a i > b i . Letting K = n i=1 (a i + b i ), is there a partition (S, S) of the index set I = {1, 2, . . . , n} such that i∈S a i + i∈ S b i = K/2? (1)
EOP is NP-hard in the ordinary sense [START_REF] Garey | One-processor scheduling with symmetric earliness and tardiness penalties[END_REF]. In the following, we will actually use the following slightly modified version of the problem.

Modified Even-Odd Partition (MEOP). A set of n pairs of positive integers (a

1 , b 1 ), (a 2 , b 2 ), . . . , (a n , b n ) is given, in which, for each i, a i > b i . Letting Q = n i=1 (a i -b i ), is there a partition (S, S) of the index set I = {1, 2, . . . , n} such that i∈S (a i -b i ) = Q/2?
(2)

Note that the two problems are indeed equivalent. In fact, suppose that EOP has a partition (S, S). The corresponding instance of MEOP also admits the same partition. In fact, subtracting

n i=1 b i = i∈S b i + i∈ S b i from both sides of (1), one obtains i∈S (a i -b i ) = K/2 - n i=1 b i (3)
Now, from the definitions of K and Q it turns out that

Q = K -2 n i=1 b i
and hence (3) is indeed (2). We next show the following result.

Theorem 2.1 P 1(

n j=1 D j ) is NP-hard.
Proof. The problem is obviously in NP. Given an instance of MEOP, we build an instance of P1 as follows. There are 3n + 3 jobs. The processing times of the jobs are defined as follows:

p 1 = 0, p 2 = 0, p 3 = 0 p 3i+1 = 1, p 3i+2 = 1, p 3i+3 = 4x i + b i -2 for all i = 1, . . . , n -1, p 3n+1 = 4x n + b n + Q/2, p 3n+2 = 0, p 3n+3 = 0
where the x i are defined as.

x i = (3a i -2b i + 3(n -i)(a i -b i ))/2 for all i = 1 . . . n (4)
and x n+1 = 0.

In the following, we refer to the set of jobs (J 3i+1 , J 3i+2 , J 3i+3 ), i = 0, . . . , n, as the triple

T i+1 .
For what concerns the travel times, we let:

• for each i = 0, 1, . . . , n -1, one has -t M,3i+1 = t 3i+1,M = t M,3i+2 = t 3i+2,M = t M,3i+3 = t 3i+3,M = x i+1 , -t 3i+1,3i+2 = a i+1 , t 3i+2,3i+3 = b i+1 , t 3i+3,3i+4 = x i+1 + x i+2 . • t M,3n+1 = 0, t 3n+1,M = 0, t M,3n+2 = 0, t 3n+2,M = 0, t M,3n+3 = 0. • t 3n+1,3n+2 = 0, t 3n+2,3n+3 = 0.
Finally, vehicle capacity is c = 2. The problem consists in determining whether a solution exists such that the total delivery time does not exceed

f * = n i=1 (3C 3i + 7x i + b i ) + C 3n+1 + C 3n+2 + C 3n+3 -Q/2.
(5)

For shortness, we call feasible a schedule satisfying (5). The proof has the following scheme.

1. We first establish via Lemma 2.2 that if a feasible schedule exists, then there is one having a certain structure, called triple-oriented, 2. We analyze some properties of this structure, 3. We show that a triple-oriented schedule of value f * exists if and only if MEOP is a yesinstance.

Lemma 2.2 If a feasible schedule exists, then there exists one satisfying the following property: for all i = 1, . . . , n, jobs J 3i and J 3i+1 are NOT in the same batch.

Proof. Suppose that a feasible schedule exists in which, for a certain i (1 ≤ i ≤ n), jobs J 3i and J 3i+1 are in the same batch. Since c = 2, the batch contains no other job. As a consequence, after delivering J 3i+1 , the vehicle must go back to M in order to load the next jobs and start a new trip. If we denote by τ the start time of the round trip of jobs J 3i and J 3i+1 , job J 3i is delivered at time

D 3i = τ + t M,3i and job J 3i+1 is delivered at time D 3i+1 = τ + t M,3i + t 3i,3i+1 . Therefore we have D 3i = τ + x i and D 3i+1 = τ + x i + (x i + x i+1
). The vehicle is back at M at time τ + 2x i + 2x i+1 . Now, if we replace this batch with two batches of one job each, the delivery times of both jobs as well as the time at which the vehicle is back at M are unchanged. Therefore, there is an equivalent solution where J 3i and J 3i+1 are not in the same batch. We call triple-oriented a schedule satisfying Lemma 2.2. The reason of this name is that the schedule is decomposed according to triples. More precisely, since c = 2, for each triple T i+1 = (J 3i+1 , J 3i+2 , J 3i+3 ), i = 0, . . . , n -1, A consequence of Lemma 2.2 is that there are exactly two batches, and only two possibilities, namely:

• either the first batch is {J 3i+1 , J 3i+2 } and the second is {J 3i+3 },

• or the first batch is {J 3i+1 } and the second is {J 3i+2 , J 3i+3 }.

We call these two possibilities option A and option B respectively (see Fig. 1). Namely, let us view option B as the Base option, and A as a variant to it.

Round trip length. Letting M A i and M B i denote the round trip length of the jobs of T i in the two cases. One has:

M A i = 4x i + a i (6) M B i = 4x i + b i (7)
Since a i > b i , option A implies a longer round trip length than the Base option. The difference between the two (i.e., the additional time with option A with respect to B) is precisely a i -b i .

Lemma 2.3 In any triple-oriented schedule, the vehicle is never idle, except possibly before loading J 3n+1 .

Proof. Let consider the first triple T 1 . The vehicle starts at time 0 (to deliver batch {J 1 } or {J 1 , J 2 }), and is back at time 4x 1 +b 1 or at time 4x 1 +a 1 . The completion time of T 2 is precisely equal to same reasons, the delivery of the jobs of T i cannot be smaller than, the duration of the jobs of T i+1 , and the vehicle will be able to start immediately the delivery of the jobs of T i+1 . This reasoning does not hold for the last triple T n+1 because the duration of J 3n+1 is different.

C 6 = 3(i-1)+1 3(i-1)+2 3(i-1)+3 b i 3(i-1)+1 3(i-1)+2 3(i-1)+3 a i 3i+1 3i+2 3i+3 3i+1 3i+2 3i+3 option A option B a i -b i
In view of Lemma 2.3, one can compute the total delivery time in the Base scenario, i.e., when option B is always chosen. From ( 7), one has that the vehicle delivering the last 2 jobs of T i always returns to M exactly at time C 3i (see Fig. 2). Therefore, the last time the vehicle arrives at M (before delivering the jobs of T n+1 ) is C 3n + 4x n + b n . Because of the definition of p 3n+1 , and because J 3n+1 starts at time C 3n , we have

C 3n + 4x n + b n = C 3n+1 -Q/2.
In this case, the vehicle will stay idle from C 3n+1 -Q/2 to C 3n+1 , when job J 3n+1 can be finally loaded and delivered at time C 3n+1 . The 3 jobs of T n+1 have zero travel times and the last 2 jobs have also zero durations, so all jobs of T n+1 can be delivered at C 3n+1 = C 3n+2 = C 3n+3 . Finally, recalling that C 1 = C 2 = C 3 = 0, the first job of each triple T i , for i ≥ 1, is delivered at C3i + x i , the second job is delivered at C 3i + 3x i and the last job at time C 3i + 3x i + b i + x i , as illustrate in Fig. (2). Hence, we have:

f BASE = n i=1 (3C 3i + 7x i + b i ) + C 3n+1 + C 3n+2 + C 3n+3 (8)
...

3(i-1)+1 3(i-1)+2 3(i-1)+3 b i 3i+1 3i+2 3i+3 x i x i x i x i T i+1 T i Figure 2:
The base schedule (i.e., B is always chosen).

Contribution to total delivery time. Before computing the contribution of a certain triple to the total delivery time, let us consider schedules in which the delivery of the the last three jobs J 3n+1 , J 3n+2 and J 3n+3 start exactly at their release time, i.e., at time C 3n+1 = C 3n+2 = C 3n+3 (options A and B are equivalent). Let us call regular a schedule in which such a condition holds.

Expression (8) refers to the scenario in which for all triples, the option B is chosen. We want now to compute the objective function of an arbitrary solution. Let us first consider the contribution of triple T i to the objective function in the Base schedule, i.e., assuming that the delivery of T i started at time C 3i , and let us denote this contribution as T DT A i and T DT B i 6 depending of the selected option for T i .. One has:

T DT A i = (C 3i + x i ) + (C 3i + x i + a i ) + (C 3i + 3x i + a i ) = 3C 3i + 5x i + 2a i T DT B i = (C 3i + x i ) + (C 3i + 3x i ) + (C 3i + 3x i + b i ) = 3C 3i + 7x i + b i Note that T DT B i -T DT A i = 2x i + b i -2a i (9) = (3a i -2b i + 3(n -i)(a i -b i )) + b i -2a i = a i -b i + 3(n -i)(a i -b i )
which is positive, remembering that a i > b i . This means that choosing option A over B brings a benefit in terms of total delivery time. However, such favorable situation for option A is mitigated by the fact that, with option A, one has a longer round trip time than with option B, by the amount (a i -b i ) (Fig. 3). In a regular schedule, such increased round trip time will be "paid" by all subsequent jobs, except the last jobs J 3n+1 , J 3n+2 and J 3n+3 . Hence, in a regular schedule the total effect (in favor of option B) on the subsequent jobs of choosing option A for T i is given by

3(n -i)(a i -b i ) (10)
In conclusion, the net benefit of choosing option A over B for T i in terms of objective function value is obtained subtracting (10) from ( 9), and in view of the definition of x i (4), one has therefore that

N etBenef it i = (2x i + b i -2a i ) -3(n -i)(a i -b i ) = a i -b i (11)
...

a i -b i 3(i-1)+1 3(i-1)+2 3(i-1)+3 a i x i x i x i x i T i+1 T i 3i+1 3i+2 3i+3
Figure 3: T i is the first triple choosing option A.

In conclusion, it turns out that, when A is chosen over the Base option, one has a larger round trip time, by (a i -b i ), but also a smaller contribution to total delivery time (also by the amount (a i -b i ))(see Fig. 4). So, given any regular triple-oriented schedule in which the last three jobs depart at their completion time, let T A be the set of triples for which the option A is chosen. Then, from the above considerations, the value f of the objective function is given by

f = f BASE - i∈T A (a i -b i ) (12)
On the other hand, the time at which the vehicle returns to M before loading the last three jobs (J 3n+1 , J 3n+2 and J 3n+3 ) is given by

C 3n + 4x n + b n + i∈T A (a i -b i ) (13)
Now, in a regular schedule the delivery of job J 3n+1 (and also J 3n+2 and J 3n+3 ) starts at time C 3n+1 = C 3n + 4x n + b n + Q/2. Hence, from (13), in a regular schedule, it must hold: On the other hand, comparing ( 5), ( 8) it turns out that

i∈T A (a i -b i ) ≤ Q/2 .... .... Ti+1 3(i-1)+1 3(i-1)+2 3i b i .... .... Ti+1 i j=1 aj -bj 3(i-1)+1 3(i-1)+2 3i a i T2 1 2 3 a 1 T2 1 2 3 b 1 3n+1, 3n+2, 3n+3 3(n-1)+1 3(n-1)+2 3n an Q/2 3n+1, 3n+2, 3n+3 3(n-1)+1 3(n-1)+2 3n bn Q/2 a1 -b1
f * = f BASE -Q/2
and hence, from (12), a regular schedule is feasible precisely if a subset T A of indices exists such that i∈T A (a i -b i ) = Q/2, i.e., if and only if a feasible partition exists in the instance of EOP. To conclude the proof, it is left to show that f * can be attained only by a regular schedule. In fact, if a schedule is not regular, the departure time of the last batch is delayed by the amount ( i∈T A (a i -b i ) -Q/2) with respect to C 3n+1 . As a consequence, the expression of f in ( 12) must be modified to take account of such delay of the last three jobs, i.e. it comes

f = f BASE - i∈T A (a i -b i ) + 3( i∈T A (a i -b i ) -Q/2) = f BASE + 2 i∈T A (a i -b i ) -3Q/2 (14) Since, in a nonregular schedule, i∈T A (a i -b i ) > Q/2, from (14) one has f = f BASE + 2 i∈T A (a i -b i ) -3Q/2 > f BASE + Q -3Q/2 = f BASE -Q/2
and hence it cannot be feasible.

Pseudopolynomial time algorithm for

P 1( j f j (D j ))
Theorem 2.1 implies that no optimal polynomial time algorithm can be found for P 1( n j=1 D j ), and hence for more general objective functions, unless P=NP. In what follows, we show that P 1( j f j (D j )) can be solved in pseudopolynomial time, hence settling the complexity status of P1.

We denote by {i, j} the batch consisting of jobs J i , . . . , J j . As usual, C j is the completion time of job J j (known because σ is known), and hence the release time for delivery. We denote by M (i, j) the duration of the round trip of batch {i, j}, and, if the batch starts at time t, we call K(i, j, t) its contribution to the objective function. Also, we assume that at the beginning, the vehicle is at the manufacturing location.

We denote by F (i, j, t) the value of the optimal solution of the problem restricted to the first j jobs, in which the first job of the last batch is J i , and such that the delivery of the batch starts at time t. Then, F (i, j, t) can be computed by means of a simple recursive formula. In the optimal solution of the subproblem, if the second last batch is {p, i -1}, and if it starts at time s, then we have:

F (i, j, t) = F (p, i -1, s) + K(i, j, t)
Note that, if the vehicle starts at time s, it must be back before or at time t, i.e., the following constraint must hold:

C i-1 ≤ s ≤ t -M (p, i -1)
In conclusion, the problem is solved by means of:

F (i, j, t) = min max(i-c,1)≤p≤i-1 Ci-1≤s≤t-M (p,i-1) {F (p, i -1, s)} + K(i, j, t) (15)
Let T be an upper bound on the latest possible departure time for the last batch. As long as the triangle inequality holds, this is given, for instance, by:

T = max max 1≤i≤n-1 {C i + 2 n-1 h=i t hM }, C n
The optimal solution is given by:

z * = min n-c+1≤i≤n,Cn≤t≤T F (i, n, t)
A few boundary conditions must be imposed:

F (i, j, t) = +∞ for all j < i (16) F (1, j, t) = K(1, j, t) for all j, t (17)
Condition ( 16) is obvious. Condition (17) allows to initialize the algorithm.

Let us turn to complexity. First, consider the computation of values M (i, j) and K(i, j, t). Both can be simply computed adding the contribution of the next job in the batch either to the round trip time (for M (i, j)) or to the objective function (for K(i, j, t)). More precisely, the delivery time d h of job J h with respect to the departure time of the batch is simply given by:

d h = d h-1 + t h-1,h , if i < h ≤ j t M,h , if h = i (
in this case the vehicle starts from the manufacturer location)

Hence, M (i, j) is simply given by d j + t j,M . Note that M (i, j + 1) = M (i, j) -t j,M + t j,j+1 + t j+1,M . This means that all M (i, j) can be computed in O(nc) assuming j ≤ i + c -1. Similarly, if batch {i, j} starts indeed at time t, the contribution of job J h to the objective function is given by:

f h (t + d h ), ∀i ≤ h ≤ j K(i, j, t
) is given by j h=i f h (t+d h ). Again, assuming that f j (•) can be computed in constant time, note that d j+1 = d j + t j,j+1 and K(i, j + 1, t) = K(i, j, t) + f j+1 (d j+1 ). So, all values K(i, j, t) can be computed in O(ncT ).

Once all values M (i, j) and K(i, j, t) are known, one can compute formula ( 15) for all feasible triples (i, j, t). Each such computation requires comparing nT values. Finally, O(cT ) values are compared to find the optimal solution. Since the feasible triples are O(ncT ), the computation of all values F (i, j, t) clearly dominates the other phases, and the following result is proved.

Theorem 2.4 Problem P 1( j f j (D j )) can be solved in O(nc 2 T 2 ).

More NP-hardness results

In this section we address the special case in which the number of locations is limited for the problem P 1( j D j ), this problem is denoted by P 3( j D j ). We denote by l j the location of job j and consider that we have K successive locations, i.e., two successive jobs j and j + 1 are whether in the same location then l j+1 = l j or in the successive locations then l j+1 = l j +1 (figure 5). Note that this problem is NP-hard and is equivalent to P 1( j D j ) if the number of locations K = n. In Sect. 3.1 we completely characterize the complexity of P 3( j D j ), showing that when the objective function is the total delivery time minimisation with the number of locations lower than n, the problem remains NP-hard. For this purpose, we use a similar reasoning to that employed to characterize the complexity of P 1( j D j ). Then we focus in Sect. 3.2 on the case where delivery preemption is allowed, and we establish the NP-hardness of this case.

3.1 Problem P 3( j D j ) with limited number of locations Proof. Given an instance of MEOP, we build an instance of P3 as follows. There are 3(n + 1)l jobs, 3(n + 1) locations, l jobs for each location and the vehicle capacity is c = 2l. We denote by J k the sequence of jobs (J k 1 , J k 2 , . . . , J k l ) corresponding to location k (k = 1, . . . , 3(n + 1)). The job J k j is at a position l(k -1) + j in the schedule. Since the reasoning is similar to that employed to prove the complexity of P 1 ( j D j ), we do not recall the global structure of the proof but we rather detail how the reduction used is extended to the limited number of location case.

1 n 1 n 1 + 1 n 2 n n K-1 + 1 - - - location
The processing times of the jobs are defined as follows: where the x i are defined by:

p 1 j = 0, p 2 j = 0, p 3 j = 0, ∀j =
x i = (a i -b i )/l -b i + 2a i + 3(n -i)(a i -b i ) /2, ∀i = 1, . . . , n (18)
and

x n+1 = 0. Notice that l j=1 (p 3i+1 j + p 3i+2 j + p 3i+3 j ) = 4x i + b i , ∀i = 1, . . . , n -1.
The travel times are those used in Sect. 2.2, but now the triple T i+1 , i = 0, . . . , n, corresponds to the set of sequences of l jobs (J 3i+1 , J 3i+2 , J 3i+3 ).

Finally, the problem consists in determining whether a solution exists, such that the total delivery time does not exceed

f * = l n i=1 (3C 3li + 7x i + b i ) + 3l j=1 C 3n+j -Q/2. ( 19
)
For shortness, we call "feasible" a schedule satisfying (19).

Lemma 3.2 If a feasible schedule exists, then it satisfies the following property: for any k, k = 1, . . . , 3(n + 1), all the jobs J k j with j = 1, . . . , l are in the same batch.

Proof. Suppose that a feasible schedule exists. We denote by k the first location where there exists jobs J k i and J k i+1 (i < l) which are not delivered in the same batch. All jobs of the triple T k/3 -which contains the l jobs of J k -have been completed when the vehicle starts to deliver the first i jobs of J k . We distinguish two cases. First, suppose that the capacity of the vehicle allows to take J k i+1 . If we denote by τ the delivery time of J k i , job J k i+1 cannot be delivered before time τ + 2x k/3 . The total delivery time cannot decrease if J k i+1 is delivered in the same batch as J k i at time τ , therefore J k i+1 is assigned to the same batch and the schedule remains feasible. Second, suppose that the capacity of the vehicle does not allow to take J k i+1 . This case is not possible because before location k, the vehicle only delivered multiples of l jobs (either l or 2l jobs). So either the vehicle cannot take any job of J k , or it can take all the jobs of J k . By applying this reasoning each time there exists a split of jobs that have to be delivered to the same location, we finally obtain a feasible schedule satisfying the lemma.

In view of Lemma 3.2, we can consider the set of jobs J k , k = 1, . . . , 3(n + 1), as a single job and the rest of the proof is similar to that given for problem P 1.

Problem P 4( Dj) with delivery preemption

In this section, we consider a case where preemption is allowed during the delivery: one can deliver a part of a job, come back to the depot, and take the reminder part of the job for another delivery. We remark that in this case, this problem is equivalent to the NP-hard problem P 1( Dj).

Remark 3.3 The problem P 4( Dj) with delivery preemption is NP-hard.

Proof. Consider that the preemption is allowed on the instance used to prove the complexity of P 1( Dj). One can see that each time the vehicle returns to the depot, the number of jobs already completed and ready for delivery is higher than the capacity c. Therefore, delivering a job in two successive trips has no interest and always increases the value of the objective function.

The result can be extended to the case where the number of sites is fixed to K < n.

Polynomial cases

In this section, we investigate two particular cases. First, the case where travel times are constant between successive locations. Then, we consider the case where the number of locations is bounded (problem NP-hard, see Section 3.1) and fixed. For both cases, we propose dynamic programming algorithms.

A particular case: constant travel times

In this section we address the special case in which all travel times are identical. More precisely, we will deal with the following problems:

• problem P 5( j D j ), which consists of problem P 1( j D j ) with constant travel times,

• problem P 6( j D j ), which consists of problem P 2( j D j ) with constant travel times.

For both problems we propose polynomial time algorithms.

4.1.1 Problem P 1( j D j ) with constant travel times

In the following, we investigate the problem of minimizing a general sum-type objective function when the sequence is fixed for both production and delivery and when travel times are constant. We start by analyzing some properties of the optimal solution. Clearly, every time the vehicle is back at the depot, it can restart immediately with a new batch consisting of jobs already completed, or it can wait for the completion of some jobs to be delivered (see Fig. 6).

.

.... ..... J 1 J j J j J n C j j + 1 - M - j - - M j -1 M - .... .... .... ..... - t Figure 6: Start of a new tour
Following Li et al.(2005), we call N SS (Non Stop Shipment) a sequence of consecutive round trips during which the vehicle is never waiting at the depot (see Fig. 7), followed by a waiting time. We denote by N SS[i, n i , j] a N SS starting at time C i , i.e. J i is the last job of the first round trip of the N SS containing n i jobs and ending before C j (when another N SS will start). Suppose that a vehicle starts a round trip at a certain time τ . Let J be the set of jobs completed before τ (or at time τ ) and not delivered. The round trip starting at time τ is called maximal if either (i) the batch contains c jobs of J , or (ii) it contains all the jobs of J . The following proposition gives a key feature of the optimal solutions. Proposition 4.1 There exists an optimal solution in which all round trips are maximal.

Proof. Let us denote by R q the round trip starting at τ . Let J i , . . . , J j be the jobs completed at or before τ and not yet delivered. The round trip R q is maximal if it contains min{c, j -i+1} jobs. Suppose that R q is not maximal, i.e. |R q | = k -i + 1 < min{c, j -i + 1}, i.e., the last job in R q is job J k , k ≤ j -1 (see Fig. 8(a)). This means that job J k+1 is delivered in the next batch R q+1 . One can move job J k+1 from R q+1 to R q because R q is not maximal. As a consequence, the delivery time of job J k+1 decreases by t, without changing the delivery times of all the subsequent jobs (see Fig. 8(b)). Hence, the new solution is better than the previous one. Suppose that R q is maximal, then we are done. One can repeat the whole process for k + 2, . . . , min{c, j -i + 1}, and the proposition follows.

From this, we can see that a solution of the problem is composed by successive N SS. However, a round trip may have to wait for some additional jobs, before starting its route. Let consider the following example.

Example: Let consider an instance with n = 4 jobs, processing times equal to p = (1, 1, 10, 6), a travel time equal to 5 and a capacity of 2. The solution without waiting times where the vehicle starts after job J 1 has a total delivery time of 79, the solution without waiting times where the vehicle starts after job J 2 has a total delivery time of 73. The optimal solution consists in waiting for the completion of J 4 and in delivering {J 1 , J 2 } in the same batch and {J 3 , J 4 } in the same batch too.

From the previous properties, one can propose a polynomial time algorithm to build the different N SS.

... ...

J j J i - - - - - t t J k ... ... τ J j+1 i M M k k + 1 k + 2 ... ... ... ... J j J i J k ... ... J j+1 - - - - - t t i M M k k + 1 k + 2 ... ... τ Figure 8: Maximal round trips
We denote by F (i, n i , j) the contribution to the objective function of the jobs J i+1 , . . . , J (j -c ≤ < j) delivered as follows: an N SS denoted N SS[i, n i , j] starts exactly at time C i , delivers the n i jobs of the batch of J i in the first trip, then the jobs J i+1 to J in consecutive maximal round trips, where J is the last job that can be delivered, so that the vehicle is back at the depot before or at C j . Notice that once J i , n i and J j are known, J is unique and we denote by ν i,ni,j the number of undelivered jobs from J +1 to J j , i.e. ν i,ni,j = j -. At time C j , another N SS starts in which the first round trip delivers the undelivered jobs J +1 to J j (see Fig. 7). We denote by B i,j the number of round trips of N SS[i, n i , j]. The number of jobs delivered by the round trip number k (1 ≤ k ≤ B i,j ) is denoted by n k (we have n 1 = n i ). The starting time of the delivery of the first round trip of N SS[i, n i , j] is equal to C i . It delivers the jobs in a single tour and J i is delivered last. The starting time of the delivery of the second round trip of N SS[i, n i , j] is equal to C i + t(n i + 1), of the third round trip is equal to C i + t(n i + 1 + n 2 + 1), the starting time of the round trip number k is equal to

C i + t k-1 k =1 (n k + 1).
Then, we have:

F (i, n i , j) = Bi,j k=2 n k r=1 C i + t k-1 k =1 (n k + 1) + rt = Bi,j k=2 n k C i + t k-1 k =1 (n k + 1) + t n k (n k + 1) 2 (20)
When n i , the number of jobs in the first round trip starting at C i is known, and according to proposition 4.1, we can construct in polynomial time N SS[i, n i , j] for any j > i, and it follows that F (i, n i , j) can be calculated in polynomial time.

We define F (0, n 0 , j) (∀j, 1 ≤ j ≤ c) as the contribution to the objective function of the first n 0 jobs J 1 , . . . , J j such that these jobs are delivered in the same first round trip, starting at time C j . We have:

F (0, n 0 , j) = j l=1 (C j + lt), ∀j, 1 ≤ j ≤ c, n 0 = j = ∞, otherwise
Two particular cases are identified, where an NSS cannot exist between two jobs J i and J j :

1. C i +t(n i +1) > C j : in this case, the round trip delivering job J i finishes after the completion time of C j and thus N SS[i, n i , j] cannot exist.

2. ν i,ni,j > c: job J j cannot be delivered in the first tour of the next NSS starting at time C j .

In both cases, we set:

F (i, n i , j) = +∞ (21)
We define now f (j, n j ) the minimum total cost of the jobs {J 1 , ..., J j } where the batch delivering J j contains n j jobs and starts at time C j .

We have:

f (j, n j ) = min 0≤i<j 1≤ni≤c νi,n i ,j =nj f (i, n i ) + F (i, n i , j) + nj r=1 (C j + rt) (22) with f (0, n j ) = 0, if n j = 0 = ∞, otherwise
Because in the optimal solution, the last round trip does not necessarily start at time C n , we introduce a dummy job J n+1 at the last position with C n+1 = C n + 2tn and t M n+1 = t. Clearly, this implies that there exists an optimal solution in which the last round trip delivers only this dummy job at time D n+1 = C n+1 + t.

Finally, the optimal solution is equal to

z * = f (n + 1, 1) -D n+1 (23)
This dynamic programming algorithm can be implemented in O(c 2 n 2 ).

Theorem 4.2 If the travel times are constant, then the problem P 5( j D j ) is solved to optimality with dynamic programming algorithm in polynomial time O(c 2 n 2 ).

4.1.2 Problem P 6( j D j ) with constant travel times

In this section, we consider the case where the sequence of jobs is not fixed and travel times are constant.

Proposition 4.3 There exists an optimal schedule in which the jobs are ordered according to the Shortest Processing Time (SPT) rule.

Proof. Suppose first that the jobs are numbered according to the SPT rule. It means that σ SP T = {J 1 , J 2 , . . . , J n }. Suppose that the SP T sequence is not optimal, then there exists in the optimal solution σ * two jobs J i and J j with J i before J j and i > j. We show by using a pairwise interchange reasoning that by maintaining the same round trips, i.e. the same number of jobs and the same starting time of the round trips, σ SP T is such that D SP T j ≤ D * j and thus is optimal.

Suppose that J i and J j are in the same round trip. The swap of these two jobs, leading to σ does not change the sum of the delivery dates, and thus D j = D * j . Suppose that these jobs are not in the same round trip. It means that the round trip of J i terminates with J i and the round trip of J j starts with J j . After the swap of these jobs, the departure times of these two round trips are still feasible, and thus the quality of the solution is unchanged. But putting J j before J i may allow to deliver J j earlier, and then to reduce the total delivery time. We deduce that σ SP T is optimal.

Problem P 7 with processing times equal to zero

We consider in this section the case where the processing times of jobs are equal to zero: p j = 0, ∀j, 1 ≤ j ≤ n. The vehicle has a capacity equal to c and travel times are arbitrary (satisfying the triangular inequality).

One can see that if the vehicle capacity is equal to n, in the optimal solution all the jobs are delivered in a single tour. This solution is called "ideal" and denoted by σ id and the total delivery time is equal to D id j . Clearly, σ id is not feasible when c < n. From the ideal solution σ id , a feasible and optimal solution can be obtained in polynomial time.

We define a graph G = (V, A) with n + 1 vertices in V (0 ≤ j ≤ n) where vertex 0 is a dummy job denoted by M (manufacturer site) and vertex j, 1 ≤ j ≤ n corresponds to J j . There is an edge in A between i and j if i + 1 ≤ j ≤ i + c, corresponding to a round trip with jobs {J i+1 , ..., J j } (see Fig. 9). This round trip generates an additional cost to D id j equal to t j,M + t M,j+1 -t j,j+1 for each job scheduled after J j , i.e. (n -j) times. The cost of edge (i, j) is equal to c i,j = (t j,M + t M,j+1 -t j,j+1 )(n -j). Notice that this cost does not depend on J i . We define now f (j) the value of the smallest possible degradation until J j of the "ideal" solution which makes the restricted problem to the j first jobs feasible and optimal. Because there is no edge between (i, j) with j > i + c, f (j) is equal to the potential of j in a shortest path in G from 0 to j. Then, we have:

f (j) = min i+1≤j≤i+c {f (i) + c i,j } (24)
with f (0) = 0. The optimal value of the shortest path is given by f (n). Finally, the optimal solution z * is equal to:

z * = n j=1 D id j + f (n) ( 25
)
This dynamic programming algorithm can be implemented in O(cn). The above reasoning immediately yields the following theorem.

Theorem 4.4 If the processing times are equal to zero, then the problem P 7( j D j ) is solved to optimality by a dynamic programming algorithm in O(cn) time.

Conclusion

In this paper, we focus on the coordination of a single machine production scheduling problem and a single vehicle delivery problem. The jobs are processed on a single machine and delivered in batches to customers by a single vehicle with limited capacity. The production sequence is given, and is supposed to be the same as the delivery sequence. The problem is to form batches of jobs and the objective is to minimize the sum of the delivery times. We prove that the problem is NP-hard and propose a pseudopolynomial time dynamic programming algorithm. Some particular cases of the problem are proved to be NP-hard (The limited number of sites and preemptive delivery cases) and polynomial time algorithms are proposed for some more restricted problems.

In the future, we propose to investigate the general case where the sequence is not fixed and has to be determined. We will propose exact algorithms as well as heuristic approaches.

Figure 1 :

 1 Figure 1: Round trips with options A and B.

Figure 4 :

 4 Figure 4: Round trips with option A only and option B only

Figure 5 :

 5 Figure 5: Special case with K locations

Figure 7 :

 7 Figure 7: Illustration of a N SS

Figure 9 :

 9 Figure 9: Construction of a feasible and optimal solution from σ id

j=1 p j = 1 + 1 + 4x 1 + b 1 -2 = 4x 1 + b 1 .Therefore, as a 1 > b 1 , the vehicle can immediately start the delivery of the jobs of T 2 as soon as it is back to the depot. For the

ACKNOWLEDGEMENT

This work was supported by the financial support of the ANR ATHENA project, grant ANR-13-BS02-0006 of the French Agence Nationale de la Recherche.


Florentina Nicolau

Witold Respondek

Flatness of two-input control-affine systems linearizable via a two-fold prolongation

We study flatness of two-input control-affine systems, defined on an n-dimensional state-space. We give a geometric characterization of systems that become static feedback linearizable after a two-fold prolongation of a suitably chosen control. They form a particular class of flat systems: they are of differential weight n + 4. We present a normal form compatible with the minimal flat outputs.

I. INTRODUCTION

In this paper, we study flatness of nonlinear control systems of the form

Ξ : ẋ = F(x, u),
where x is the state defined on a open subset X of R n and u is the control taking values in an open subset U of R m (more generally, an n-dimensional manifold X and an m-dimensional manifold U, respectively). The dynamics F are smooth and the word smooth will always mean C ∞ -smooth.

The notion of flatness has been introduced in control theory in the 1990's, by Fliess, Lévine, Martin and Rouchon [START_REF] Fliess | Sur les systemes non linéaires différentiellement plats[END_REF], [START_REF] Fliess | Flatness and defect of non-linear systems: introductory theory and examples[END_REF], see also [START_REF] Isidori | A sufficient condition for full linearization via dynamic state feedback[END_REF], [START_REF] Jakubczyk | Invariants of dynamic feedback and free systems[END_REF], [START_REF] Martin | Contribution à l'étude des systèmes différentiellement plats[END_REF], [START_REF] Pomet | A differential geometric setting for dynamic equivalence and dynamic linearization[END_REF], and has attracted a lot of attention because of its multiple applications in the problem of constructive controllability and motion planning (see, e.g. [START_REF] Fliess | A Lie-Bäcklund approach equivalence and flatness of nonlinear systems[END_REF], [START_REF] Pomet | On dynamic feedback linearization of fourdimensional affine control systems with two inputs[END_REF], [START_REF] Van Nieuwstadt | Differential flatness and absolute equivalence of nonlinear control systems[END_REF], [START_REF] Pereira Da Silva | Relative flatness and flatness of implicit systems[END_REF], [START_REF] Martin | Flat systems, equivalence and trajectory generation[END_REF], [START_REF] Respondek | Symmetries and minimal flat outputs of nonlinear control systems[END_REF], [START_REF] Schlacher | Construction of flat outputs by reduction and elimination[END_REF]). Flat systems form a class of control systems whose set of trajectories can be parametrized by m functions and their time-derivatives, m being the number of controls. More precisely, the system Ξ : ẋ = F(x, u) is flat if we can find m functions, ϕ i (x, u, . . . , u (l) ) such that x = γ(ϕ, . . . , ϕ (s-1) ) and u = δ(ϕ, . . . , ϕ (s) ), [START_REF] Brockett | Feedback invariants for nonlinear systems[END_REF] for a certain integer s, where ϕ = (ϕ 1 , . . . , ϕ m ) is called a flat output. Therefore the time-evolution of all state and control variables can be determined from that of flat outputs without integration and all trajectories of the system can be completely parameterized. A similar notion, of systems of undetermined differential equations integrable without integration, has been studied by Hilbert [START_REF] Hilbert | Über den Begriff der Klasse von Differentialgleichungen[END_REF] and Cartan [START_REF] Cartan | Sur l'équivalence absolue de certains systèmes d'équations différentielles et sur certaines familles de courbes[END_REF], see also [START_REF] Van Nieuwstadt | Differential flatness and absolute equivalence of nonlinear control systems[END_REF], where connections between Cartan prolongations and flatness were studied.

Flatness is closely related to the notion of feedback linearization. It is well known that systems linearizable a INRIA Sophia Antipolis Mditerrane, 2004 Route des Lucioles, 06902 Valbonne, France, florentina.nicolau,@inria.fr b INSA-Rouen, Laboratoire de Mathématiques, 76801 Saint-Etiennedu-Rouvray, France witold.respondek@insa-rouen.fr via invertible static feedback are flat. Their description (1) uses the minimal possible, which is n + m, number of time-derivatives of the components of the flat output ϕ. In general, a flat system is not linearizable by static feedback, with the exception of the singleinput case where flatness reduces to static feedback linearization, see [START_REF] Charlet | Sufficient conditions for dynamic state feedback linearization[END_REF] and [START_REF] Pomet | A differential geometric setting for dynamic equivalence and dynamic linearization[END_REF]. For any flat system, that is not static feedback linearizable, the minimal number of time-derivatives of ϕ i needed to express x and u (which is called the differential weight [START_REF] Respondek | Symmetries and minimal flat outputs of nonlinear control systems[END_REF]) is thus bigger than n + m and measures actually the smallest possible dimension of a precompensator linearizing dynamically the system. The simplest systems for which the differential weight is bigger than n + m are systems linearizable via one-dimensional precompensator (namely one-fold prolongation), thus of differential weight n + m + 1. That class of systems have been studied in details in [START_REF] Nicolau | Two-inputs control-affine systems linearizable via one-fold prolongation and their flatness[END_REF], [START_REF] Nicolau | Flatness of multi-input controlaffine systems linearizable via one-fold prolongation[END_REF], see also [START_REF] Nicolau | Flatness of two-inputs controlaffine systems linearizable via one-fold prolongation[END_REF], [START_REF] Nicolau | Multi-input control-affine systems linearizable via one-fold prolongation and their flatness[END_REF], [START_REF] Nicolau | Normal forms for flat controlaffine systems linearizable via one-fold prolongation[END_REF], where the authors presented a complete geometric verifiable characterization, gave normal forms, computed all minimal flat outputs and discussed their uniqueness. The goal of this paper is to generalize those results to control-affine systems that become static feedback linearizable after a two-fold prolongation (thus of differential weight n + m + 2). We will consider the case of two-input control systems only. Our aim is to give necessary and sufficient conditions for flatness of differential weight n + m + 2 = n + 4 and to describe and understand the geometry of that class of systems. Solving that problem in the simplest case of two controls is interesting for few reasons; firstly, it yields a complete analysis of flatness for a well defined class of systems, secondly, it shows what kind of difficulties one must face when trying to characterize flatness for more general systems (like those requiring more than two prolongations), thirdly, it allows to observe new phenomena like the necessity of distinguishing a special drift.

The paper is organized as follows. In Section II, we recall the definitions of flatness and of differential weight of a flat system as well as the results describing flatness of differential weight n + 3 for twoinput control-affine systems. In Section III, we give our main results: we characterize control-affine systems that become static feedback linearizable after a twofold prolongation, that is, flat systems of differential weight n + 4. We also present a normal forms and explain how to compute the to-be-prolonged control. Finally, we provide the proof of our main theorem in Section IV.

II. FLATNESS: DEFINITION AND KNOWN RESULTS

The fundamental property of flat systems is that all their solutions may be parametrized by a finite number of functions and their time-derivatives. Fix an integer l ≥ -1 and denote U l = U × R ml and ūl = (u, u, . . . , u (l) ). For l = -1, the set U -1 is empty and ū-1 in an empty sequence.

Definition 1: The system Ξ : ẋ = F(x, u) is flat at (x 0 , ūl 0 ) ∈ X × U l , for l ≥ -1, if there exists a neighborhood O l of (x 0 , ūl 0 ) and m smooth functions

ϕ i = ϕ i (x, u, u, . . . , u (l) ), 1 ≤ i ≤ m, defined in O l ,
having the following property: there exist an integer s and smooth functions γ i , 1 ≤ i ≤ n, and δ j , 1 ≤ j ≤ m, such that 1) ) and u j = δ j (ϕ, φ, . . . , ϕ (s) )

x i = γ i (ϕ, φ, . . . , ϕ (s-
for any C l+s -control u(t) and corresponding trajectory x(t) that satisfy (x(t), u(t), . . . , u (l) (t)) ∈ O l , where ϕ = (ϕ 1 , . . . , ϕ m ) and is called a flat output.

Whenever necessary to specify the number of derivatives of u on which the components of the flat outputs ϕ depend, we say that the system Ξ is (x, u, . . . , u (r) )flat if ϕ i = ϕ i (x, u, . . . , u (r) ), for 1 ≤ i ≤ m, and at least one of them depends explicitly on u (r) . In the particular case ϕ i = ϕ i (x), we say that the system is x-flat.

In general, r is not bigger than the integer l needed to define the neighborhood O l . In our study, r will be proved to be -1, i.e., the flat outputs depend on x only, and l is -1 or 0.

The minimal number of derivatives of components of a flat output, needed to express x and u, will be called the differential weight of that flat output and is formalized as follows. By definition, for any flat output ϕ of Ξ there exist integers s 1 , . . . , s m such that x = γ(ϕ 1 , φ1 , . . . , ϕ

(s 1 ) 1 , . . . , ϕ m , φm , . . . , ϕ (s m ) m ) u = δ(ϕ 1 , φ1 , . . . , ϕ (s 1 ) 1 , . . . , ϕ m , φm , . . . , ϕ (s m ) m ).
Moreover, we can choose (s 1 , . . . , s m ), γ and δ such that (see [START_REF] Respondek | Symmetries and minimal flat outputs of nonlinear control systems[END_REF]) if for any other m-tuple (s 1 , . . . , sm ) and functions γ and δ, we have

x = γ(ϕ 1 , φ1 , . . . , ϕ (s 1 ) 1 , . . . , ϕ m , φm , . . . , ϕ (s m ) m ) u = δ(ϕ 1 , φ1 , . . . , ϕ (s 1 ) 1 , . . . , ϕ m , φm , . . . , ϕ (s m ) m ), then s i ≤ si , for 1 ≤ i ≤ m. We will call ∑ m i=1 (s i + 1) = m + ∑ m
i=1 s i the differential weight of ϕ. A flat output of Ξ is called minimal if its differential weight is the lowest among all flat outputs of Ξ. We define the differential weight of a flat system to be equal to the differential weight of a minimal flat output.

Consider a control-affine system

Σ : ẋ = f (x) + m ∑ i=1 u i g i (x), (2)
where f and g 1 , • • • , g m are smooth vector fields on X.

The system Σ is linearizable by static feedback if it is equivalent via a diffeomorphism z = φ(x) and an invertible static feedback transformation, u = α(x) + β(x)v, to a linear controllable system Λ : ż = Az + Bv.

The problem of static feedback linearization was solved by Brockett [START_REF] Brockett | Feedback invariants for nonlinear systems[END_REF] (for a smaller class of transformations) and then by Jakubczyk and Respondek [START_REF] Jakubczyk | On linearization of control systems[END_REF] and, independently, by Hunt and Su [START_REF] Hunt | Linear equivalents of nonlinear time varying systems[END_REF], who gave geometric necessary and sufficient conditions. The following theorem recalls their result and, furthermore, gives an equivalent way of describing static feedback linearizable systems from the point of view of differential weight.

Define inductively the sequence of distributions

D i+1 = D i + [ f , D i ], where D 0 is given by D 0 = span {g 1 , • • • , g m } and [ f , D i ] = {[ f , g] : g ∈ D i }.
Theorem 1: The following conditions are equivalent: (FL1) Σ is locally static feedback linearizable, around

x 0 ∈ X; (FL2) Σ is locally static feedback equivalent, around

x 0 ∈ X, to the Brunovsk ý canonical form

(Br) : żj i = z j+1 i żρ i i = v i where 1 ≤ i ≤ m, 1 ≤ j ≤ ρ i -1,
and ∑ m i=1 ρ i = n; (FL3) For any q ≥ 0, the distributions D q are of constant rank, around x 0 ∈ X, involutive and D n-1 = TX; (FL4) Σ is flat at x 0 ∈ X, of differential weight n + m.

The geometry of static feedback linearizable systems is given by the following sequence of nested involutive distributions:

D 0 ⊂ D 1 ⊂ • • • ⊂ D n-1 = TX.
It is well known that a feedback linearizable system is static feedback equivalent to the Brunovsk ý canonical form, see [START_REF] Brunovsky | A classification of linear controllable systems[END_REF], and is clearly flat with

ϕ = (ϕ 1 , • • • , ϕ m ) = (z 1 1 , • • • , z 1 m
) being a minimal flat output (of differential weight n + m). Therefore, for static feedback linearizable systems, the representation of all states and controls uses the minimal possible, which is n + m, number of time-derivatives of ϕ i and an equivalent way of describing them is that they are flat systems of differential weight n + m.

In general, a flat system is not linearizable by static feedback, with the exception of the single-input case. Any single input-system is flat if and only if it is static feedback linearizable, see [START_REF] Charlet | Sufficient conditions for dynamic state feedback linearization[END_REF], [START_REF] Pomet | A differential geometric setting for dynamic equivalence and dynamic linearization[END_REF], and thus of differential weight n + 1. Flat systems can be seen as a generalization of static feedback linearizable systems. Namely they are linearizable via dynamic, invertible and endogenous feedback, see [START_REF] Fliess | Flatness and defect of non-linear systems: introductory theory and examples[END_REF], [START_REF] Fliess | Sur les systemes non linéaires différentiellement plats[END_REF], [START_REF] Martin | Contribution à l'étude des systèmes différentiellement plats[END_REF], [START_REF] Pomet | On dynamic feedback linearization of fourdimensional affine control systems with two inputs[END_REF]. In [START_REF] Nicolau | Two-inputs control-affine systems linearizable via one-fold prolongation and their flatness[END_REF], [START_REF] Nicolau | Flatness of two-inputs controlaffine systems linearizable via one-fold prolongation[END_REF], the authors described the simplest flat systems that are not static feedback linearizable: control-affine systems that become static feedback linearizable after a one-fold prolongation (which is the simplest dynamic feedback) thus of differential weight n + m + 1. In this paper we will characterize systems (with two controls, i.e. m = 2) that become static feedback linearizable after a two-fold prolongation, that is of differential weight n + 4.

III. MAIN RESULTS

Throughout, we will consider two-input controlaffine systems of the form

Σ : ẋ = f (x) + u 1 g 1 (x) + u 2 g 2 (x), (3)
where x ∈ X, u = (u 1 , u 2 ) t ∈ R 2 and f , g 1 , and g 2 are C ∞ -smooth vector fields on X. We make the following assumption:

Assumption 1: From now on, unless stated otherwise, we assume that all ranks are constant in a neighborhood of a given x 0 ∈ X. All results presented here are thus valid on an open and dense subset of either X or X × U, where all ranks are constant, and hold locally, around any point of that set.

Throughout, we deal only with systems that are not static feedback linearizable. Therefore one of distributions D i fails to satisfy the condition (FL3) of Theorem 1. Flat systems are always accessible so D n-1 = TX holds and all distributions D i are supposed of constant rank according to Assumption 1. So there exists an integer k such that D k is not involutive. Suppose that k is the smallest integer satisfying that property.

Flat systems of differential weight n + 4 form a particular class of dynamic feedback linearizable systems, namely, they become static feedback linearizable after two-fold prolongations of a suitably chosen control. More precisely, we have the following result:

Proposition 1: Consider the system Σ, given by (3). The following conditions are equivalent:

(i) Σ is flat at (x 0 , u 0 , u0 , . . . , u (l) 0 ), of differential weight n + 4, for a certain l ≥ -1; (ii) Σ is x-flat at either x 0 or (x 0 , u 0 ), of differential weight n + 4; (iii) There exists, around x 0 , an invertible static feed- back transformation u = α(x) + β(x) ũ, bringing the system Σ into the form Σ : ẋ = f (x) + ũ1 g1 (x) + ũ2 g2 (x), such that the prolongation Σ(2,0) :    ẋ = f (x) + y 1 g1 (x) + v 2 g2 (x) ẏ1 = y 2 ẏ2 = v 1 is locally static feedback linearizable at (x 0 , y 0 ), with y 1 = ũ1 , v 2 = ũ2 , f = f + αg and g = gβ,
where g = (g 1 , g 2 ) and g = ( g1 , g2 ). A system Σ satisfying (iii) will be called dynamically linearizable via an invertible two-fold prolongation. Notice that Σ(2,0) is, indeed, obtained by applying an invertible static feedback u = α + β ũ and then prolonging the first control ũ1 twice as v 1 = ü1 and not prolonging ũ2 (which explains the notation). The above result asserts that, as for flatness of differential weight n + 3 (see [START_REF] Nicolau | Two-inputs control-affine systems linearizable via one-fold prolongation and their flatness[END_REF]), for systems of differential weight n + 4, flatness and x-flatness coincide and that, moreover, they are equivalent to linearizability via twofold prolongations of a suitably chosen control.

Before giving our main results, we state the following proposition needed in the proofs, but also having an independent interest.

Proposition 2: Consider the system Σ, given by (3), dynamically linearizable via invertible two-fold prolongation and let D k be its first noninvolutive distribution. Then the distribution D k is feedback invariant and cork

(D k ⊂ D k ) ≤ 2.
According to the above proposition, at most two directions of D k stick out of D k . In this paper, we will study only the case when the noninvolutivity of D k is maximal, i.e., when cork Our main result describing flat systems of differential weight n + 4 is given by the three following theorems corresponding to the first noninvolutive distribution D k being either D 0 , i.e., k = 0 (Theorem 3) or D 1 , i.e., k = 1 (Theorem 4) or D k , for k ≥ 2 (Theorem 2). For all theorems, we assume that Assumptions 1 and 2 hold.

(D k ⊂ D k ) = 2. The particular case cork (D k ⊂ D k ) = 1
Theorem 2: Assume that k ≥ 2 and consider the twoinput control system Σ, given by (3). The system Σ is flat at x 0 , of differential weight n + 4, if and only if the following conditions hold:

(A1) rk (D k + [ f , D k ]) = 2k + 5, implying the existence of a non-zero vector field g 2c ∈ D 0 such that ad k+1 f g 2c ∈ D k ; (A2) ad k+2 f g 2c ∈ D k + D k+1 ; (A3) The distribution L k = span {ad q f c g 1c , ad r f c g 2c , 0 ≤ q ≤ k -2, 0 ≤ r ≤ k} is involutive
, where g 2c is defined by condition (A1), g 1c ∈ D 0 is independent of g 2c and such that [g 1c , g 2c ] = 0 mod span {g 2c } and f c satisfies ad k+2

f c g 2c ∈ D k ; (A4) The distributions L i+1 = L i + [ f c , L i ], for i ≥ k, are involutive;
(A5) There exists ρ such that L ρ = TX. The geometry of the systems described by the previous theorem can be summarized by the following sequence of inclusions:

D 0 ⊂ 2 • • • ⊂ 2 D k-1 ⊂ 2 D k ⊂ 2 D k 2 ⊂ 1 ⊂ = L k ⊂ 2 L k+1 ⊂ 2 L k+2 • • •⊂ 2 L µ ⊂ 1 L µ+1 • • • ⊂ 1 L ρ = TX
where all distributions, except D k , are involutive and the integers beneath the inclusion symbol "⊂" indicate coranks. According to condition (A1), if we take the brackets of D k with f , we gain only one new direction with respect to D k implying the existence of a distinguished vector field g 2c in D 0 that allows us to define another vector field g 1c ∈ D 0 and a distinguished drift f c that is used to define the involutive subdistribution L k of corank two in D k (which is essential for flatness of differential weight n + 4). While, the computation of g 2c involves derivations and algebraic operations only, calculating g 1c and f c requires solving two partial differential equations (which always admit solutions), defined and discussed in Section III-A. Contrary to flatness of differential weight n + 3, for which only the definition of a control vector field g 2c is needed (see [START_REF] Nicolau | Two-inputs control-affine systems linearizable via one-fold prolongation and their flatness[END_REF]), for flatness of differential weight n + 4, it is necessary to distinguish also g 1c and f c . Indeed, it can be shown that not all control vector fields g 1 and not all drifts f lead to a static feedback linearizable prolongation Σ (2,0) . This can also be observed when proving the above theorem, see Section IV. The geometry of flat systems of differential weight n + 4 recalls very much that of flat systems of differential weight n + 3, see [START_REF] Nicolau | Two-inputs control-affine systems linearizable via one-fold prolongation and their flatness[END_REF]. Similarly to flat systems of differential weight n + 3, for which the the main structural condition is the existence of an involutive subdistribution H k of corank one in D k , see [START_REF] Nicolau | Two-inputs control-affine systems linearizable via one-fold prolongation and their flatness[END_REF], the most important structural property of flat systems of differential weight n + 4 is the existence of an involutive subdistribution L k of corank two in D k . Indeed, similarly to H k , the distribution L k is essential: it takes the role of the noninvolutive distribution D k and, moreover, its successive brackets with the distinguished drift f c are again involutive (replacing the distributions D k+i ). Contrary to H k , the definition of L k is more involved since, in order to construct L k , we have to compute the vector fields g 1c and f c and, therefore, to solve some PDE's (that always admit solutions). The involutive subdistribution L k is invariant under feed- back transformations consistent with the definitions of g 1c , g 2c and f c . Notice that the sequence of inclusions between the distributions L i and D i is no longer as simple as between H i and D i . Indeed, in the latter case, we simply have

D k-1 ⊂ 1 H k ⊂ 1 D k ⊂ 1 D k = H k+1 , while
the counterpart of that sequence, in the case of L i and D i , can be written as

D k ⊂ 2 ⊂ 2 D k-2 ⊂ 2 L k D k = L k+2 ⊂ 2 ⊂ 2 L k+1
It is easy to check that D k = L k+2 . Indeed, by definition, L k+2 = D k + span {ad k+1 f c g 2c , ad k+2 f c g 2c } and its involutivity is given by (A4). Moreover, rk L k+2 = 2k + 4, otherwise D k would be involutive or cork (D k ⊂ D k ) would be one. It follows that D k = L k+2 . Thus the directions completing D k to D k are, modulo D k , in the plane spanned by ad k+1 f c g 2c and ad k+2 f c g 2c . If k = 0 or k = 1, i.e., the first noninvolutive distribution is D 0 or D 1 , then a similar result holds, but in the chain of involutive subdistributions

L 1 ⊂ L 2 ⊂ • • • (playing the role of L k ⊂ L k+1 ⊂ L k+2 ⊂ • • • ),
the distributions L 1 and L 2 are not defined as L k+1 and L k+2 (see condition (A4) of Theorem 3, resp. the statement of Theorem 4). Moreover, flat systems with k = 0 or k = 1 exhibit singularities in the control space (created by a two-fold prolongation of the tobe-prolonged control and excluded by condition (RC)) which are defined by

U sing (x) = {u ∈ R 2 : (g 1c ∧ g 2c ∧ ad f c +g c u g 2c ∧ ad 2 f c +g c u g 2c )(x) = 0}, with f c + g c u = f c + g 1c u 1 + g 2c u 2
, where the vector fields f c , g 1c and g 2c are defined in the statements of Theorems 3 and 4. Theorem 3: Assume that k = 0 and consider the twoinput control system Σ, given by (3). The system Σ is flat at (x 0 , u 0 ), of differential weight n + 4, if and only if the following conditions hold:

(A1)' The ranks of the distributions G 0 = D 0 , G 1 = G 0 + [G 0 , G 0 ], and G 2 = G 1 + [G 0 , G 1
] are, respectively two, three, and four implying the existence of a characteristic vector field

g 2c ∈ D 0 for the distribution G 1 , i.e., [g 2c , G 1 ] ∈ G 1 ; (A2)' ad f g 2c ∈ G 1 ; (A3)' ad f [g 1 , g 2c ], ad 2 f g 2c ∈ D 0 + [ f , D 0 ]; (A4)' The distributions L i , for i ≥ 2, are involutive, where L 2 = D 0 and L i+1 = L i + [ f , L i ], for i ≥ 2;
(A5)' There exists ρ such that L ρ = TX;

(RC) u 0 / ∈ U sing (x 0 ), where g 2c is defined by condition (A1), g 1c ∈ D 0 is independent of g 2c and such that span {g 2c , [g 1c , g 2c ]} is involutive and f c satisfies ad f c g 2c ∈ span {g 2c , [g 1c , g 2c ]}. Notice that the involutive distribution span {g 2c , [g 1c , g 2c ] plays the role of L k+1 for the case k ≥ 2. Since the distribution D 0 is supposed noninvolutive, the vector field g 1c cannot be defined in the same way as for the case k ≥ 2. Consequently, the definition of f c changes as well.

Theorem 4: Assume k = 1 and consider the twoinput control system Σ, given by (3). The system Σ is flat at (x 0 , u 0 ), of differential weight n + 4, if and only if conditions (A1)-(A5) of Theorem 2 hold for k = 1, with L 1 = span {g 2c , ad f c g 2c }, L 2 = span {g 1c , g 2c , ad f c g 2c , ad 2 f c g 2c , [g 1c , ad f c g 2c ]}, and L i , for i ≥ 3, defined as in (A4), and u 0 / ∈ U sing (x 0 ). The conditions of our theorems enable us to define the control to be prolonged in order to obtain a locally static feedback linearizable prolongation Σ(2,0) . We explain in the next subsection, the construction of that control.

A. To-be-prolonged control

In this section, we will define the control u 1p to be prolonged (preintegrated) in order to dynamically linearize the system. We will study only the cases k ≥ 2 and k = 1. If the first noninvolutive distribution is D 0 , then a similar analysis can be done.

Let us first show that under the condition (A1) of Theorem 2, there exists a non-zero vector field g 2c ∈ D 0 such that ad k+1 f g 2c ∈ D k . We have rk

D k = 2k + 4 and, acccording to (A1), rk (D k + [ f , D k ]) = 2k + 5,
thus we can always assume (permute g 1 and g 2 , if necessary) that ad k+1 f g 1 ∈ D k . Hence there exists a smooth function ν, defined in a neighborhood of x 0 , such that ad k+1 f g 2 = νad k+1 f g 1 mod D k . The vector field g 2c = g 2νg 1 is obviously nonzero (since g 1 and g 2 are independent everywhere on X) and satisfies ad k+1 f g 2c ∈ D k and it is clear that any vector field g2c = β 1 g 1 + β 2 g 2 , collinear with g 2νg 1 satisfies ad k+1 f g2c ∈ D k . It follows that g 2c is not unique and all vector fields g 2c form a subdistribution of D 0 = span {g 1 , g 2 } of rank one. We explain next how to find the vector field g 1c = βg 1 + γg 2c ∈ D 0 , independent of g 2c , and such that [g 1c , g 2c ] = 0 mod span {g 2c }. Since k ≥ 1, the distribution D 0 is involutive and there exists a smooth function λ such that [g 1 , g 2c ] = λg 1 mod span {g 2c }. Then the function β has to satisfy L g 2c ββλ = 0 (which always admits solutions, so β always exists) and γ can be any. It is immediate that any vector field g1c = βg 1c + γg 2c , where the function β is non zero and satisfies that L g 2c β = 0 and γ is any, verifies [ g1c , g 2c ] = 0 mod span {g 2c }. Now, we are looking for a couple of functions (α 1 , α 2 ) such that f c = f + α 1 g 1c + α 2 g 2c satisfies ad k+2 f c g 2c ∈ D k . Using Proposition 5 (see Section IV), it can be proven that ad k+2 f c g 2c = ad k+2 f g 2c -(L g 2c α 1 )ad k+1 f g 1c mod D k . According to item (A2) of Theorem 2, there exists a smooth function δ such that ad k+2 f g 2c = δad k+1 f g 1c mod D k . We deduce that the function α 1 has to satisfy L g 2c α 1 = δ (which always admits solutions, so α 1 always exists) and α 2 can be any. Notice that any vector field fc = f c + α1 g 1c + α2 g 2c , where α1 is such that L g 2c α1 = 0 and α2 is any, verifies ad k+2

fc g 2c ∈ D k .
We define the to-be-prolonged control by the relation:

u 1 u 2 = α 1 (β -γν) -να 2 α 1 ν + α 2 + β -γν -ν γ 1 u 1p u 2p .
Consider the system

Σ c : ẋ = f c + u 1p g 1c + u 2p g 2c
which is static feedback equivalent to the original system Σ, and its prolongation

Σ (2,0) c :      ẋ = f c (x) + u 0 1p g 1c (x) + v 2 g 2c (x) u0 1p = u 1 1p u1 1p = v 1 controlled by (v 1 , v 2 ) = ( ü1p , u 2p ) and evolving on the prolonged state space X p = X × R 2 , where (x, u 0 1p , u 1 1p ) ∈ X × R 2 .
We can now restate all our theorems using just one statement for the prolonged system.

Theorem 5: The control system Σ is flat at (x 0 , u 0 ) of differential weight n + 4 if and only if the prolonged system Σ (2,0) c is locally static feedback linearizable around (x 0 , u 0 p0 , u 1 p0 ), i.e., it satisfies the equivalent conditions of Theorem 1.

B. Normal form

The following proposition gives a normal form for the class of two-input flat systems of differential weight n + 4. The integers ρ i that show up in the normal form are related to ρ and µ defined via the nested sequence of distributions L i . Let µ be the smallest integer such that corank (L µ ⊂ L µ+1 ) is one and ρ is the smallest integer such that L ρ = TX. It follows that ρ + µ = n. Define the pair of indices (ρ 1 , ρ 2 ) by ρ = max(ρ 1 , ρ 2 + 2) and µ = min(ρ 1 , ρ 2 + 2). We have ρ 1 + ρ 2 + 2 = n, implying ρ i ≥ k + 1, and since we have supposed D k = TX, at least one of them is greater than k + 2.

For i = 1, 2, denote zj i = (z 1 i , • • • , z j i ). Proposition 3: The system Σ is flat at x 0 (at (x 0 , u 0 ), such that u 0 = (u 10 , u 20 ) / ∈ U sing (x 0 ), if k = 0 or 1) of differential weight n + 4 if
and only if it is locally, around x 0 , static feedback equivalent to the following normal form in a neighborhood Z of z 0 ∈ R n :

(NF)                    ż1 1 = z 2 1 ż1 2 = z 2 2 . . . . . . żρ 1 -1 1 = z ρ 1 1 żρ 2 -1 2 = z ρ 2 2 żρ 1 1 = ũ1 żρ 2 2 = a( zρ 1 1 , zρ 2 +1 2 )+b( zρ 1 1 , zρ 2 +1 2 ) ũ1 żρ 2 +1 2 = c(z) + d(z) ũ1 żρ 2 +2 2 = ũ2 where -either k = 0 and then b = z ρ 2 +1 2 , d = z ρ 2 +2 2
, a and c are any functions (a not depending on z

ρ 2 +2 2 ) sat- isfying ∂a ∂z ρ 2 +1 2 (z 0 ) + u 10 = 0, ∂c ∂z ρ 2 +2 2 (z 0 ) + u 10 = 0; -or k = 1 and then c = z ρ 2 +2 2 , d = d( zρ 1 1 , zρ 2 +1
2

) and either a = z

(z 0 ) + u 10 = 0; -or k ≥ 2 and then a = z ρ 2 +1 2 , c = z ρ 2 +2 2 , b = b( zρ 1 -k+2 1 , zρ 2 -k+2 2
), d = d( zρ 1 -k+2 1 , zρ 2 -k+2 2
) and

∂b ∂z ρ 1 -k+2 1 + b ∂b ∂z ρ 2 -k+2 2 = 0, ∂d ∂z ρ 1 -k+2 1 -∂b ∂z ρ 1 -k+1 1 - b ∂b ∂z ρ 2 -k+1 2 + b ∂d ∂z ρ 2 -k+2 2 -d ∂b ∂z ρ 2 -k+2 2 = 0;
and with a, b, c and d such that the distribution D k is noninvolutive and cork

(D k ⊂ D k ) = 2, for k ≥ 1.
Moreover, the minimal x-flat outputs and the normal form (NF) are compatible: if (ϕ 1 , ϕ 2 ) is a minimal xflat output at x 0 , then there exists an invertible static feedback transformation bringing the system Σ into (NF) with

ϕ 1 = z 1 1 and ϕ 2 = z 1 2 .
At first sight there are four arbitrary functions involved in the normal form, but, in fact, we can always normalize two of them. This is due to the fact that D k is squeezed between two involutive distributions L k and D k = L k+2 and both inclusions are of corank two (see the sequence of inclusions summarizing the geometry of flat systems of differential weight n + 4), so only two directions of D k stick out of D k . The normal form (NF) is valid around z 0 ∈ R n , which may be zero or not. Therefore it can be used around any point (equilibrium or not). It is immediate to see that (NF) is flat with ϕ = (z 1 1 , z 1 2 ) being a minimal flat output and a simple computation shows that its differential weight is, indeed, n + 4. It is clear that (NF) becomes locally static feedback linearizable after a twofold prolongation of ũ1 . The normal form applies to all cases k ≥ 2, k = 1 and k = 0, and it is clear that in the cases k = 1 and k = 0 (and only in those cases!), the precompensator creates singularities in the control space (depending on the state). Indeed, the controls ũ0 satisfying ∂a ∂z ρ 2 +1 2

(z 0 ) + ũ10 = 0 or ∂c ∂z ρ 2 +2 2 (z 0 ) + u 10 = 0 (resp. ∂a ∂z ρ 2 +1 2 (z 0 ) + ũ10 ∂b ∂z ρ 2 +1 2 (z 0 ) = 0, where either a = z ρ 2 +1 2 or b = z ρ 2 +1 2
) are singular for (NF), if k = 0 (resp. if k = 1). We do not give here explicit conditions for a, b, c and d such that the distribution D k is noninvolutive and cork (D k ⊂ D k ) = 2 for the cases k ≥ 2 and k = 1.

They can be found by a straightforward computation.

IV. PROOFS

A. Notations and useful results

Consider a control system of the form Σ : ẋ = f (x) + u 1 g 1 (x) + u 2 h 2 (x). By Σ (2,0) we will denote the system Σ with two-fold prolongation of the first control, that is, Σ (2,0) :

   ẋ = f (x) + y 1 g 1 (x) + +v 2 h 2 (x) ẏ1 = y 2 ẏ2 = v 1 ,
with y 1 = u 1 and v 2 = u 2 . The first control is prolonged, but the second is not, thus the corresponding vector fields do not play the same role and hence we denote them by g 1 and h 2 instead of g 1 and g 2 . Denote by f p , g 1p and g 2p , respectively, the drift and the control vector fields of the prolonged canonical system Σ (2,0) , i.e., f p = ∑ n i=1 (

f i + y 1 g 1i ) ∂ ∂x i + y 2 ∂ ∂y 1 , g 1p = ∂ ∂y 2
and

g 2p = ∑ n i=1 h 2i ∂ ∂x i
. To Σ (2,0) , we associate the distributions D 0 p = span {g 1p , g 2p } and D i+1 p

= D i p + [ f p , D i p ]
, for i ≥ 0 (the subindex p referring to the prolonged system Σ (1,0) ).

We start by stating two propositions needed in the proofs of our main results, but also having an independent interest. Proposition 4 is a complete version of Proposition 2.

Proposition 4: Consider the system Σ, given by (3), dynamically linearizable via invertible two-fold prolongation and let D k be its first noninvolutive distribution. Then the following conditions are satisfied (i

) D k is feedback invariant; (ii) If k ≥ 2, then cork (D k-2 ⊂ D k-1 ) = 2; (iii) cork (D k ⊂ D k ) ≤ 2; (iv) If cork (D k ⊂ D k ) = 2, then rk D k = 2k + 2.
Proposition 5: Consider the system Σ, given by (3), and let D k be its first noninvolutive distribution. Assume k ≥ 2 and that conditions (A1) -(A3) of Theorem 2 are satisfied. Then the distribution H k-1 = D k-2 + span {ad k-1 f g 2c } is involutive and its involutivity implies that of all istributions

H i = D i-1 + span {ad i f g 2c }, for 1 ≤ i ≤ k -2. Moreover, all distribu- tions L i = span {ad q f c g 1c , ad r f c g 2c , 0 ≤ q ≤ i -2, 0 ≤ r ≤ i}, for 1 ≤ i ≤ k -1 (where L 1 = span {g 2c , ad f c g 2c }), are involutive.

B. Proof of Theorem 2

Necessity. Consider the control system Σ : ẋ = f (x) + u 1 g 1 (x) + u 2 g 2 (x) and assume that it is flat of differential weight n + 4. According to Proposition 1, there exists an invertible static feedback transformation u = α(x) + β(x) ũ, bringing Σ into the form Σ : ẋ = f (x) + ũ1 g1 (x) + ũ2 h2 (x), such that the prolongation Σ(2,0) :

   ẋ = f (x) + y 1 g1 (x) + v 2 h2 (x) ẏ1 = y 2 ẏ2 = v 1 ,
with y 1 = ũ1 and v 2 = ũ2 , is locally static feedback linearizable. For simplicity of notation, we will drop the tildes, but we will keep distinguishing g 1 from h 2 (which could also be denoted g 2 ) whose control is not preintegrated. Since Σ (2,0) is locally static feedback linearizable, for any i ≥ 0, the distributions D i p are involutive, of constant rank, and there exists an integer ρ such that rk D ρ p = n + 1. We have

D 0 p = span { ∂ ∂y 2 , h 2 }, D 1 p = span { ∂ ∂y 1 , ∂ ∂y 2 , h 2 , ad f h 2 + y 1 [g 1 , h 2 ]}.
Since k ≥ 2 and rk D 1 = 4, we deduce from the involutivity of D 1 p , that we necessarily have [g 1 , h 2 ] = 0 mod span {h 2 } and that D

1 p = span { ∂ ∂y 1 , ∂ ∂y 2 , h 2 , ad f h 2 }. The distribution D 2 p = span { ∂ ∂y 1 , ∂ ∂y 2 , g 1 , h 2 , ad f h 2 , ad 2 f h 2 + y 1 [g 1 , ad f h 2 ]} is involutive, thus we actually have D 2 p = span { ∂ ∂y 1 , ∂ ∂y 2 , g 1 , h 2 , ad f h 2 , ad 2 f h 2 , [g 1 , ad f h 2 ]}. Since k ≥ 2, the distribution D 1 = span {g 1 , h 2 , ad f g 1 , ad f h 2 }
is involutive, and thus there exists a smooth function α such that [g 1 , ad f h 2 ] = α ad f g 1 mod span {g 1 , h 2 , ad f h 2 }. We will show that α is identically zero. According to our assumptions rk D 2 = 6 (because k ≥ 2 and rk D k = 2k + 2 as a direct consequence of the corank assumption cork (D k ⊂ D k ) = 2) and, if α is non zero, we would have rk D 2 p = 7 which is impossible. Hence

D 2 p = span { ∂ ∂y 1 , ∂ ∂y 2 , g 1 , h 2 , ad f h 2 , ad 2 f h 2 }.
It is easy to prove (by an induction argument) that, for i ≥ 2,

D i p = span { ∂ ∂y 1 , ∂ ∂y 2 , g 1 , • • • , ad i-2 f g 1 , h 2 , • • • , ad i f h 2 }.
Since the intersection of involutive distributions is an involutive distribution, it follows that D

i p ∩ TX = span {g 1 , • • • , ad i-2 f g 1 , h 2 , • • • , ad i f h 2 } is involutive, for 1 ≤ i ≤ k. We deduce that L k = span {g 1 , • • • , ad k-2 f g 1 , h 2 , • • • , ad k f h 2 }
is involutive (below we will justify denoting this distribution by L k ). It is immediate that

D k-2 ⊂ L k ⊂ D k ,
= span { ∂ ∂y 1 , g 1 , • • • , ad k f g 1 , h 2 , • • • , ad k f h 2 , ad k+1 f h 2 , ad k+2 f h 2 } implies that of D k + span {ad k+1 f h 2 ,
k + [ f , D k ] = D k .
Therefore, for the prolonged system we obtain

D k+3 p = span { ∂ ∂y 1 } + D k + [ f , D k ] = D k+2 p ,
thus contradicting the existence of ρ such that rk D ρ p = n + 1 (recall that D k = TX) and implying that Σ (2,0) is not static feedback equivalent to a controllable linear system. By Proposition 1, the system Σ would not be flat of differential weight n + 4 and thus rk (D k + [ f , D k ]) = 2k + 5 and (A1) holds. At the beginning of Section III-A, we have shown that (A1) implies the existence of g 2c ∈ D 0 such that ad k+1 f g 2c ∈ D k . We noticed above that ad k+1 f g 1 ∈ D k , therefore g 2c = h 2 . Furthermore, we have ad k+2 f h 2 ∈ D k , thus (A2) holds and, moreover, we have f c = f , with f c defined by item (A3). At the beginning of the proof, we have also observed that [g 1 , h 2 ] = 0 mod span {h 2 }, thus g 1c = g 1 . It follows that L k = span {ad q f c g 1c , ad r f c g 2c , 0 ≤ q ≤ k -2, 0 ≤ r ≤ k} = span {ad q f g 1 , ad r f h 2 , 0 ≤ q ≤ k -2, 0 ≤ r ≤ k} which justifies denoting the above involutive distribution by L k and shows (A3). Recall that L i = L i-1 + [ f c , L i-1 ], for i ≥ k + 1. We thus have Consequently, the involutivity of D k+i p implies that of L k+i , for i ≥ 1. Moreover, rk D ρ p = n + 2, implying that rk L ρ = n, i.e., L ρ = TX, which proves (A4) and (A5).

Sufficiency. Consider the control system Σ : ẋ = f (x) + u 1 g 1 (x) + u 2 g 2 (x) satisfying (A1) -(A5). Transform Σ via a static feedback transformation into the form Σ : ẋ = f c (x) + ũ1 g 1c (x) + ũ2 g 2c (x), where g 1c , g 2c and f c are defined by conditions (A1) and (A3). By Proposition 5, the involutivity of L i = span {ad q f g 1 , ad r f h 2 , 0 ≤ q ≤ i -2, 0 ≤ r ≤ i} follows for 1 ≤ i ≤ k -1. It is immediate to see that the prolongation Σ (2,0) :

   ẋ = f c (x) + y 1 g 1c (x) + v 2 g 2c (x) ẏ1 = y 2 ẏ2 = v 1
with y 1 = ũ1 and v 2 = ũ2 is locally static feedback linearizable. Indeed, the linearizability distributions D i p , associated to Σ (2,0) , are of the form

D i p = span { ∂ ∂y 1
, ∂ ∂y 2 } + L i , i ≥ 1. The involutivity of L i implies that of D i p . Moreover, rk L ρ = n, thus rk D ρ p = n + 2 and Σ (2,0) is locally static feedback linearizable. By Proposition 1, the system Σ is flat of differential weight n + 4.

Remark 1 :

 1 needs a separate analysis, it reminds the results for flatness of differential weight n + 3, but it has a slightly different geometry. In order to respect the length of conference paper, we do not discuss it here. Moreover, we suppose D k = TX. The particular cases, cork (D k ⊂ D k ) = 1 and D k = TX will be presented in a future paper. Thus, from now on, we make the following assumption Assumption 2: We assume cork (D k ⊂ D k ) = 2 and D k = TX. If cork (D k ⊂ D k ) = 2, then it can be shown that we necessarily have rk D k = 2k + 2 (see Proposition 4, in Section IV).

2 } 2 }

 22 + L k + [ f , L k ] = span { ∂ ∂y 1, ∂ ∂y 2 } + L k+1 and, by an induction argument, + L k+i , i ≥ 2.

  ad k+2 f h 2 } and, since we have supposed cork(D k ⊂ D k ) = 2, it yields D k = D k + span {ad k+1 f h 2 , ad k+2 f h 2 }, where D k is the involutive closure of D k .We show next that rk(D k + [ f , D k ]) = 2k + , if not,the rank in question is, indeed, 2k + 5. Hence for any vector field ξ ∈ D k , we have [ f , ξ] ∈ D k . By successive applications of the Jacobi identity, it follows immediately that D

	5. We have D k+2 p	= span { ∂ ∂y 1	, ∂ ∂y 2 } + D	k . Assume
	ad k+1 f g 1 ∈ D

k


N Schaeffer

M A Pais

E Lora Silva

Core Flows inferred from Geomagnetic Field Models and the Earth's Dynamo

Are the presently inverted large scale core velocity fields enough to explain the geodynamo?

Our kinematic dynamo calculations use largescale, quasi-geostrophic (QG) flows inverted from geomagnetic field models, which, as such, incorporate flow structures that are Earth-like, as the large eccentric gyre and the anticyclone under North Pacific. Furthermore, the QG hypothesis allows straightforward prolongation of the flow from the core surface to the bulk.

We obtain magnetic field growth only when the QG flow is perturbed by magnetic pumping [7] that parameterizes the effect of an internal toroidal magnetic field of Elsasser number Λ on the flow. The magnetic pumping distorts the columnar flow and introduces helicity. Dynamo action is observed for Λ ≥ 0.25 and magnetic Reynolds numbers Rm ≥ 200. This suggests that our large scale flow captures the relevant features for the generation of the Earth's magnetic field and that the invisible small scale flow may not be directly involved in the process.

. We find that time periods from 120 to 50 years do not affect the mean growth rate of the kinematic dynamos.

METHOD

• Surface core flow is inferred from the geomagnetic secular variation.

• Assuming a Quasi-Geostrophic (QG) flow, we can prolongate the symmetric part of the flow in the whole core [START_REF] Gillet | Rationale and geophysical evidence for quasi-geostrophic rapid dynamics within the earth's outer core[END_REF][START_REF] Schaeffer | On symmetry and anisotropy of Earth-core flows[END_REF].

• Principal Component Analysis (PCA) is used to extract the main spatial patterns and associated timeseries [START_REF] Pais | Variability modes in core flows inverted from geomagnetic field models[END_REF].

• The XSHELLS code [START_REF] Schaeffer | XSHELLS code[END_REF] is used to solve the kinematic dynamo problem (by time-stepping the induction equation).

• The time-dependence of each main spatial structure is prescribed as periodic, with a period obtained by fitting a sinisoid to each retrieved time-series [START_REF] Schaeffer | Can core flows inferred from geomagnetic field models explain the earth's dynamo[END_REF].

• A magnetic-pumping parameterization allows to introduce helicity and produce a dynamo.

CORE FLOWS

The flow is split into symmetric v + and anti-symmetric v -parts.

• The v + QG flow (columnar flow) satisfies the following relation at the core surface:

∇ H • u + = 2u + θ tan θ (1)
• No kinematical constraint applied on u -.

• We penalize azimuthal gradients as in [START_REF] Schaeffer | On symmetry and anisotropy of Earth-core flows[END_REF].

R A = CMB 1 sin θ ∂u ∂φ 2 dS ∝ m 2 (2)
• Weak small scale damping, as the small viscosity and magnetic diffusivity in the core should not damp the flow at the scales that can be probed by magnetic field models; we thus also weakly penalize radial vorticity and horizontal divergence. On centenial time-scales the influence of the Lorentz force on the flow should be taken into account. We assume the Earth permeated by a simple toroidal field B 0 of dipolar symmetry (Fig. 1, left). The resulting magnetic pumping [START_REF] Sreenivasan | Helicity generation and subcritical behaviour in rapidly rotating dynamos[END_REF] is proportional to the local vorticity and to the square of the magnetic field and adds helicity to the flow. The Elsasser number Λ = B 2 0 /µ 0 ρΩη controls the strength of the magnetic pumping, where B 0 is the maximum of the amplitude of the large scale magnetic field, ρ is the fluid density and Ω the rotation rate of the Earth.

MAGNETIC PUMPING

We prescribe, for all azimuthal wavenumber m:

v mp z = Λ V 0 f (z/H(s)) b(s) m 2 ξ m (s) (3)
where ξ m (s) is the quasi-geostrophic streamfunction, b(s) = 4s(r c -s)/r 2 c captures magnetic field variations with s, while f (x) = - 7 2 x(1 -x) 2 (1 + x) 2 captures vertical variations due to the magnetic field geometry.

We have approximated the local vorticity by m 2 ξ m . This allows us to conveniently satisfy the mass-conservation by adding a contribution v mp φ to the azimuthal flow:

v mp φ = ΛV 0 ism ξ m (s) b(s) 1 H(s) f (z/H(s)) (4)
A meridional cross-section of the resulting flow is shown in Fig. 1 (right).

KINEMATIC DYNAMOS WITH CORE-FLOWS

Magnetic pumping leads to dynamo action for Λ ≥ 0.25 and Rm ≥ 200.

OUTLOOK

• The growing surface field is connected to the bulk field by magnetic diffusion only. Can we use this property to estimate magnetic diffusion at the Earth's core surface? Would the flow inverted from the growing field resemble the actual flow?

• Is this parameterized magnetic pumping realistic? What is the effect of the magnetic field on convective columns for Rm 1 and long time-scales?

• Can we construct a self-consistent quasi-geostrophic dynamo model [START_REF] Schaeffer | Quasi-geostrophic kinematic dynamos at low magnetic prandtl number[END_REF] with a dynamic magnetic-pumping (that depends on the actual magnetic field)? LOGOS

Figure 1 :

 1 Figure 1: Left: the toroidal field B 0 that enters the magnetic pumping. Right: the flow distorted by the magnetic pumping (flow component perpendicular to the plane containing the axis).

Figure 2 :

 2 Figure 2: Growth rate (normalized by the magnetic diffusion time) as a function of the magnetic Reynolds number Rm and the Elsasser number Λ controlling the magnetic pumping. Black squares are failed dynamos (for which the magnetic field decays) while red circles are dynamos (exhibiting growing magnetic field).

Figure 3 :

 3 Figure 3: Growing radial magnetic field (colormap) and streamlines of the surface mean flow for Rm = 978 and Λ = 0.9. Left: Aitoff projection at the core surface centered on the pacific; Right: north-pole view projected onto the equatorial plane. The thickness of the streamlines is proportional to the velocity. The dashed circle marks the boundary of the Earth's inner-core.