Frédéric Fauberteau
email: frederic.fauberteau@cea.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Sustainability in static-priority restricted-migration scheduling

Keywords: C.3 [Special-purpose and application-based systems]: Real-time and embedded systems; J.7 [Computers in other systems]: Real time Real-Time, Scheduling, Multiprocessor, Sustainability

In this paper, we focus on the static-priority scheduling of periodic hard real-time tasks upon identical multiprocessor platforms. In order to bound the inter-processor migrations, we consider the restricted-migration scheduling policy for which a task is allowed to migrate only at job boundaries. Several jobs of the same task can then be assigned on different processors but a given job can not migrate. It has been shown that this scheduling policy can suffer from scheduling anomalies. These anomalies occur when a decrease in execution requirement of a job causes a deadline miss. We present a static-priority restricted-migration scheduling algorithm and we prove it does not suffer from these anomalies. We also review the scheduling anomalies according to the scheduling tests for this algorithm.

INTRODUCTION

The recent improvements in the embedded systems induce more powerful and complex systems on which we can reasonably run a modern operating system. In the case of the realtime embedded applications, a Real-Time Operating System (RTOS) can be a good solution to provide security and reliability. A RTOS also enables to implement an advanced scheduler without suffering from intolerable overrides due to costly computations of scheduling decisions. In the case of the multiprocessor embedded systems, the choice of the scheduler is very important in order to reduce the number of context switches and migrations.

The literature about real-time multiprocessor scheduling often states two main approaches (a third one is presented bellow) to schedule sets of tasks. These two multiprocessor scheduling approaches are referenced as global and partitioned scheduling. The first one allows inter-processor migrations while the second one prevents them. Although the superiority of partitioned scheduling over global scheduling has been highlighted according to the best known schedulability tests [START_REF] Baker | Comparison of empirical success rates of global vs. partitioned fixed-priority and EDF scheduling for hard real time[END_REF], these two approaches are incomparable. Some set of tasks can be scheduled with partitioned algorithm and not by a global one and vice versa. It remains difficult to choose among one of these two approaches. As presented in [START_REF] Carpenter | Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms[END_REF], the intermediate restricted-migration approach has to be considered. This approach allows task-level migrations but no job-level migrations. A non-hybrid 1 multiprocessor scheduling algorithm can be classified among one of the following classes:

• partitioned: Each task is assigned on a processor.

For a given task, each job is released on the processor on which the task has been assigned. No migration is allowed (e.g. [START_REF] Oh | Utilization bounds for n -processor rate monotone scheduling with static processor assignment[END_REF], EDF-FF [START_REF] López | Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems[END_REF]).

• restricted-migration: At each time a job is released, it can be assigned on a different processor. The tasklevel migrations are allowed but a job can not migrate during its execution (e.g. r-EDF [START_REF] Baruah | Multiprocessor fixed-priority scheduling with restricted interprocessor migrations[END_REF], r-SP wl [START_REF] Fauberteau | Laxity-based restricted-migration scheduling[END_REF]).

• global: The job-level migrations are allowed. A job can start on a first processor and finishes on a second one (e.g. RM-US[m/(3m -2)] [1]), PriD [START_REF] Goossens | Priority-driven scheduling of periodic task systems on multiprocessors[END_REF]).

This classification reminds the one made for the three main classes of uniprocessor scheduling algorithm. A uniprocessor scheduling algorithm can be classified among one of the following classes:

• fixed-task-priority or static-priority: A priority is attributed to each task composing the system. For a given task, each job inherits the priority of the task which generates it. The priority of a job is constant during its execution. (e.g. Rate-Monotonic [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], Deadline-Monotonic [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF], ... ). 1 An hybrid algorithm exploits behavior from two different classes for two different subsets of tasks (See [START_REF] George | Job vs. portioned partitioning for the earliest deadline first semi-partitioned scheduling[END_REF] for more details)

• fixed-job-priority: At each time a job is released, its priority is computed and it is constant during the execution of the job (e.g. Earliest-Deadline-First [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]).

• dynamic-priority: The priority of any job can change during its execution (e.g. Least-Laxity-First [START_REF] Mok | Fundamental Design Problems of Distributed Systems for Hard-Real-Time Environments[END_REF])

We refer to a fixed-priority scheduling algorithm in the case where the scheduling algorithm is either fixed-taskpriority or fixed-job-priority and only jobs are considered.

In multiprocessor context, a non-hybrid scheduling algorithm can reasonably be referred according to both how the prioritization is done (fixed-task / fixed-job / dynamic) and how the migrations are allowed (no / task-level / job-level).

Although the restricted-migration scheduling has been less studied than the two main multiprocessor scheduling approaches, we can exhibit some interesting works. Ha and Liu have studied the fixed-priority restricted-migration scheduling of a set of jobs and have shown this kind of scheduling is prone to a problem of predictability (scheduling anomaly which occurs when the execution requirement of jobs is decreased). Baruah and Carpenter have proposed r-EDF, an EDF-based algorithm for periodic tasks on identical processors [START_REF] Baruah | Multiprocessor fixed-priority scheduling with restricted interprocessor migrations[END_REF]. In the same paper, they also proposed an extension of PriD [START_REF] Goossens | Priority-driven scheduling of periodic task systems on multiprocessors[END_REF] to r-PriD (which exploits restricted-migration). Funk has studied in her thesis [START_REF] Funk | EDF Scheduling on Heterogeneous Multiprocessors[END_REF] the restricted-migration scheduling approach in the case of an uniform multiprocessor. Fisher has studied in his thesis [START_REF] Fisher | The Multiprocessor Real-Time Scheduling of General Task Systems[END_REF] the restrictedmigration scheduling approach in the case of scheduling of a set of jobs. Fauberteau et al. have proposed r-SP wl, a static-priority algorithm for periodic tasks on identical processors [START_REF] Fauberteau | Laxity-based restricted-migration scheduling[END_REF]. The contribution of this paper is to propose a proof of sustainability for r-SP wl algorithm in the case of the constrained deadline period sets of tasks.

The remainder of this paper is organized as follows. In Section 2, we remind the model that we consider and we introduce the notations that we use. In Section 3, we define the concept of sustainability and we give an example illustrating a scheduling anomaly which can occur with a non-predictable algorithm. In Section 4, we present our static-priority restricted-migration scheduling algorithm and we prove that it is sustainable according to our considered model. We conclude in Section 5 by giving some future work perspectives.

SYSTEM MODEL

We consider a set τ of n constrained deadline periodic tasks indexed from 1 to n. (i.e. τ = {τ1, . . . , τn}). The index of the task is in inverse proportion to its priority. The less is the task index the higher its priority is.

A task τi is characterized by:

• its Worst Case Execution Time (WCET) denoted Ci,

• its relative deadline denoted Di,

• its period denoted Ti.

A task τi (Ci, Di, Ti) consists of an infinite recurrence of jobs where each job J i,k is characterized by:

• its release time denoted r i,k ,

• its execution requirement denoted e i,k such that 0 ≤ e i,k ≤ Ci,

• its absolute deadline denoted d i,k such that d i,k = r i,k + Di.

For readability, we can consider a job independently of the task which generates it and we denote it J k (r k , e k , d k ). By definition, the utilization of a periodic task is given by ui = C i T i . By extension, we define the utilization of a set of tasks as the sum of the utilization of the tasks which compose it and its value is given by U (τ ) = n i ui. We also denote Umax(τ ) the maximum utilization of τ and we define it as: Umax(τ ) = max n i ui. We also consider a set Π of m processors πj indexed from 1 to m (i.e. Π = {π1, . . . , πm}). We consider the processors as identical (homogeneous case). In other terms, each job is executed as the same rate on any processor.

SUSTAINABILITY

In order to analyze a given hard real-time system, a technique consists in highlighting the worst case scenario in which the worst response time could be met. Intuitively, this scenario has to occur when the utilization of the set of tasks is maximum. In other words, it has to occur when the execution requirement of each job is maximum and when the inter-arrival time of each task is minimum.

But it has been shown that some classes of algorithms are prone to scheduling anomalies [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF][START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF]. In particular, it has been shown that a fixed-priority restricted-migration job assignment is not predictable. Let J k denote a job generated by a task τi. Let S k denote the start time of J k and S - k its minimum start time. In the same manner, let F k denote the finish time of J k and F + k its maximum finish time. The non-predictability of a scheduling algorithm is a scheduling anomaly which occurs when the execution time e k of J k is such that e - k ≤ e k ≤ e + k and (i) either S k < S - k or (ii)

F k > F + k .
In Figure 1, we show an example from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] illustrating this kind of scheduling anomaly. The Table 1(a) represents the arrival time r k , the absolute deadline d k and the execution requirement e k of the job J k for 1 ≤ k ≤ 6. The priority of the jobs are given in decreasing order of their index (J1 is the higher priority and J6 is the lower priority). In this example, the execution requirement of J2 can vary from 2 to 6. In Figure 1(b), respectively 1(c), J2 runs for its maximum, respectively its minimum, execution requirement. We notice that all deadlines are met. Intuitively, we could conclude that no deadlines can be missed in all cases. But in Figure 1(d), J2 runs for 3 time units and J4 misses its deadline. Finally, in Figure 1(e), when J2 runs for 5 time units, the finish time F4 of J4 is minimum.

The predictability is a notion linked to the execution requirement of the jobs. It consists in guaranteeing that a scheduling algorithm can successfully schedule a set of jobs when the execution requirement of one or many jobs is reduced. The concept of sustainability comes from the notion of predictability but it is extended to the relaxation of other parameters as relative deadlines or arrival times.

Definition 1 (Sustainable algorithm). Let A denote a scheduling algorithm. Let τ denote any set of tasks that is A-schedulable. Let J denote a collection of jobs generated by τ . Scheduling algorithm A is said to be sustainable if and only if A meets all deadlines when scheduling any collection of jobs obtained from J by changing the parameters (e) e2 = 5 Figure 1: A example illustrating scheduling anomalies from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF].

job r k d k [e - k , e + k ] job r k d k [e - k ,
of one or more individual jobs in any, some, or all the following ways: (i) decreased execution requirements; (ii) larger relative deadlines and (iii) latter arrival times.

In addition to the scheduling algorithms, the concept of sustainability can be used in the case of schedulability tests. In the same manner a scheduling policy can suffer from scheduling anomalies when job or task parameters are relaxed, a schedulability test can argue that a set of tasks is schedulable and invalidate this response if one or many of the scheduling parameters is relaxed.

Definition 2 (Sustainable test). Let A denote a scheduling algorithm and F a schedulability test for A. Let τ denote any set of tasks that is A-schedulable. Let J denote a collection of jobs generated by τ . Scheduling test F is said to be sustainable if and only if A meets all deadlines when scheduling any collection of jobs obtained from J by changing the parameters of one or more individual jobs in any, some, or all the following ways: (i) decreased execution requirements; (ii) larger relative deadlines and (iii) latter arrival times.

In the case of uniprocessor scheduling, the schedulability tests have been studied in order to highlight which of them are sustainable [START_REF] Baruah | Sustainable scheduling analysis[END_REF][START_REF] Burns | Sustainability in real-time scheduling[END_REF]. This work has been extended in the case of the multiprocessor scheduling [START_REF] Baker | Sustainable multiprocessor scheduling of sporadic task systems[END_REF].

SCHEDULING ALGORITHM

In Section 4.1 below, we describe the behavior of the fixed-priority restricted-migration scheduling algorithm as presented in [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF]. In Section 4.2, we define r-SP wl, a staticpriority restricted-migration multiprocessor scheduling algorithm for scheduling periodic sets of tasks upon identical multiprocessor platforms. In Section 4.3, we prove that r-SP wl is sustainable according to decreased execution time, later arrival times and larger relative deadlines. In Section 4.4, we review the sustainability of the schedulability tests of r-SP wl.

Non-predictable algorithm

We have reminded in Section 3 that a fixed-priority restricted-migration scheduling algorithm is not predictable. By extension, a static-priority restricted-migration suffers from the same scheduling anomaly. In order to propose a predictable scheduling algorithm of this class, it is necessary to analyze the properties of the scheduling algorithm given in [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] to discover which property is responsible of the nonpredictability. This scheduling algorithm is described by the Algorithm 1.

Algorithm 1: Fixed-priority restricted-migration scheduling algorithm from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF]. This algorithm is designed to assign jobs on the multiprocessor platform when they are released only if a processor is available. In this last case, the assignment is postponed to a time at which a processor becomes available (the finish time of a higher priority job). The ready job J k is tested to be assigned on one of the m available processors (Lines 1-11). If one of these processors is free -in the sense of no higher priority job is running on this processor -then J k starts on πj (Lines 2-7). If a lower priority job is already running, it is preempted and put in the πj local queue (Lines 3-6). Otherwise, if no processor is free for J k at its release time, its start is postponed and it is put in the global queue Q g (Lines 8-9). For readability, we voluntarily omit the algorithm part corresponding to the finish time of a job. But when a job finishes its execution, the scheduler is called to check the pending local and global job queues in order to start the higher priority waiting job.

Input

Definition 3 (Lower-priority-agnostic test).

A schedulability test is lower-priority-agnostic if for a given job J k , no lower priority than J k job has to be considered to decide the schedulability of J k .

As shown in Figure 1(d), the fixed-priority restrictedmigration scheduling algorithm from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] is lower-priority-agnostic since J3 is assigned on processor π2 without consideration in J4 which will miss deadline because of lake of processor execution time.

Definition 4 (Processor-available assignment).

An assignment is processor-available if the assignment of a job J k is made when a processor becomes available.

As shown in Figures 1(b) and 1(c), the algorithm from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] performs a processor-available assignment. The job J3 released at time 4 is either assigned on processor π1 at time 5 because no processor is available before or on processor π2 at time 4 because of lower priority job runs and can be preempted.

Definition 5 (Work-conserving algorithm).

A multiprocessor scheduling algorithm is work-conserving if no processor is idled while there are active jobs.

As explained above, when a job finishes its execution, the scheduler is executed in order to wake up a potential pending job from both the processor local queues and the global system queue. This behavior leads to produce a workconserving scheduler.

We have shown that the fixed-priority restricted-migration scheduling algorithm from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] is a work-conserving algorithm and that its job assignment is processor-available using a schedulability test which is lower-priority-agnostic.

Algorithm r-SP wl

According to the previous cited properties, we now examine how to design a predictable static-priority restrictedmigration scheduling algorithm. In a more general purpose, we extend this property of predictability to a sustainability one. This algorithm is designed to assign jobs on the multiprocessor platform at their release time even if no processor is available. In this last case, jobs are put in the local queue of the chosen processor. The ready job J k is tested to be assigned on one of the m available processor (Lines 1-15). If one of these processors is free then J k starts on πj (Lines 2-11). With r-SP wl, a processor πj is considered free for the job J k if all jobs Jj ∈ J(πj) (with J(πj) = J(πj) ∪ J k ) have enough laxity Lj(πj, r k ) on processor πj at their released time rj to be scheduled. The laxity values are computed and maintained by the scheduler. If a lower priority job is already running, it is preempted and put in the πj local queue (Lines 3-8). If no processor is free for job J k at its release time, it is considered unschedulable. Like the algorithm presented in [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF], the scheduler has to be executed at a time when a job finishes its execution but it has only to examine the local queue of the processor on which this job finishes. The laxity has also to be decreased for a job J k at time r k + C k in order to guarantee the predictability of the schedule.

Definition 6 (Laxity). The laxity L k (πj, t) of a job J k on a processor πj at time t is given by:

L k (πj, t) = D k -C k - J h ∈hp(π j ,J k ) e * h (t)
where e * h (t) denotes the remaining execution requirement of the job J h at time t.

A static-priority schedulability test is in general lowerpriority-agnostic. In uniprocessor, this behavior is completely justified because a higher priority job has to be scheduled before other jobs even if these last ones do not meet their deadline. But in the multiprocessor case, this behavior can lead to the case that the job is assigned on a processor on which a lower priority task could miss its deadline or migrate while another processor could discard this eventuality. In the case of a global scheduler, a lower-priority-agnostic test can lead to a more important number of migrations without impacting the schedulability. But in the case of restricted-migration approach, it can cause deadline misses.

Definition 7 (Lower-priority-aware test). A schedulability test is lower-priority-aware if for a given job J k , lower priority than J k jobs have to be considered to decide the schedulability of J k .

In the case of fixed-priority restricted-migration, one of the main causes of the predictability problem is the processoravailable assignment. During the release time of a job and when a processor becomes free to admit it, many changes can occur in the scheduling scenario. These changes can lead to the job assigned on a completely different processor. At this point, it is impossible to predict the worst case behavior of this job since it is not allowed to migrate on another processor in order to continue its execution after a preemption by a higher priority job. Definition 8 (Release-time assignment). An assignment is release-time if the assignment of a job J k is made when J k becomes active (at its release time) instead of the time at which a processor becomes available.

The algorithm r-SP wl is driven by the laxity of the jobs at time t. We can notice that this value of laxity is computed using the WCET of the task which generates the job. If a job J k finishes its execution earlier than this WCET, it can result in an idle time on the processor on which J k was executed.

Definition 9 (Idle algorithm).

A multiprocessor scheduling algorithm is idle if at least one processor can be idled while there are active jobs. Impact of idle times in restrictedmigration scheduling.

We illustrate in Figure 2 the problems which we can encounter with restricted-migration scheduling in the case of work-conserving algorithms and lower-priority-agnostic schedulability tests. The system depicted in this figure is generated by three tasks τ1(5, 5, 5), τ2 [START_REF] Baker | Sustainable multiprocessor scheduling of sporadic task systems[END_REF][START_REF] Burns | Sustainability in real-time scheduling[END_REF][START_REF] Burns | Sustainability in real-time scheduling[END_REF] and τ3 [START_REF] Baker | Sustainable multiprocessor scheduling of sporadic task systems[END_REF][START_REF] Burns | Sustainability in real-time scheduling[END_REF][START_REF] Burns | Sustainability in real-time scheduling[END_REF] and scheduled among two processors. In Figure 2(a), we represent a set of jobs schedulable with respect to the staticpriority restricted-migration scheduling. In Figure 2(b), we represent the same set of jobs but the job J1,5 has an execution requirement of 4 instead of 5. In this case, the processor π1 becomes idle at time 24. In this scenario, the job J2,5 can be assigned to the processor π1 and start its execution. But at time 25, the sixth job of τ1 is released and preempts the job of τ2 since τ1 is higher priority. At this time, it is possible to know that J2,5 will miss its deadline because it has not enough laxity to finish its execution. In Figure 2, the same set of jobs is depicted, but the lower-priority-aware test of r-SP wl is used. Since the laxity of a job on a processor is updated at the time of its worst case finish time, the laxity of J1,5 at time 24 is always 0 and therefore the laxity of J2,5 is also 0. The processor π1 can not be considered as available for the assignment of this last job. This behavior leads to produce idle times in scheduling. It is also important to notice that the lower-priority-aware schedulability test of r-SP wl does not allow J1,6 to be assigned on π1 because the laxity of lower priority job J2,6 would not be enough to permit it to finish its execution before its deadline.

We shown that r-SP wl differs from the fixed-priority restricted-migration from [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] in three points. We now prove that it is sustainable.

Sustainability of r-SP wl

In order to prove the sustainability of r-SP wl, we must verify that it can successfully schedule a set of tasks according to the three relaxations of parameters which are (i) execution requirement decreasing (ii) relative deadline increasing (iii) arrival time increasing. We verify these points by the three following lemmas.

Lemma 1. Let τ denote any set of tasks that is schedulable by r-SP wl. Let J denote a collection of jobs generated by τ The algorithm r-SP wl meets all deadlines when scheduling any collection of jobs obtained from J by changing the parameters of one or more jobs by decreasing execution requirements.

Proof. The proof comes from a mathematical induction over the priority of the jobs. Let J be a set of n jobs. We denote J - i the job for which the execution requirement is such that e - i < ei. We also denote L - i (πj, t) = Di -Ci -J - h ∈hp(π j ,J - i ) e - * j (t) the laxity of J - i on the processor πj at time t. The induction hypothesis is ∀ 1 ≤ i ≤ n, L - i (πj, t) ≥ Li(πj, t). The hypothesis is true at step one by definition of the laxity since Ji is the most priority job: L - i (πj, t) = Li(πj, t). We suppose the induction is true at step i. We verify that the relation L - i+1 (πj, t) ≥ Li+1(πj, t) is true for the job Ji+1. By contradiction:

L - i+1 (πj, t) < Li+1(πj, t) (1)
⇒ J - h ∈hp(π j ,J - i ) e - * j (t) > J h ∈hp(π j ,J i ) e * j (t) (2)
Since πj stay idle when higher priority jobs than J - i have finished their execution before their WCET, we obtain

J - h ∈hp(π j ,J - i ) e - * j (t) = J h ∈hp(π j ,J i ) e * j (t)
which is in contradiction with (2). The induction hypothesis follows.

Lemma 2. Let τ denote any set of tasks that is schedulable by r-SP wl. Let J denote a collection of jobs generated by τ The algorithm r-SP wl meets all deadlines when scheduling any collection of jobs obtained from J by changing the parameters of one or more jobs by enlarging relative deadlines.

Proof. The scheduling decisions are made considering the laxity at time t of the jobs. The deadline of the jobs is not used to compute this laxity then scheduling decision can not be changed if a deadline is enlarged. Lemma 3. Let τ denote any set of tasks that is schedulable by r-SP wl. Let J denote a collection of jobs generated by τ The algorithm r-SP wl meets all deadlines when scheduling any collection of jobs obtained from J by changing the parameters of one or more jobs by enlarging arrival times.

Proof. The considered tasks are periodic then the arrival time of a job can not be increased.

Proposition 1. The static-priority restricted-migration scheduling algorithm r-SP wl is sustainable with respect to WCET, relative deadlines and period.

Proof. The proof is made from Lemmas 1, 2 and 3.

Sustainability of r-SP wl tests

In order to decide the schedulability of a set of tasks with r-SP wl, we proposed a sufficient schedulability test based on the notion of LOAD. LOAD at level k represents the maximum processor demand of the jobs of priority greater than and equal to k at any time t.

Theorem 1 (From [START_REF] Fauberteau | Laxity-based restricted-migration scheduling[END_REF]). Any set τ of periodic tasks satisfying:

∀k : 1 ≤ k ≤ n : LOAD(k) ≤ 1 + (m -1)Umin(k) 1 + 2(Dmax(k)/D k )
is r-SP wl schedulable upon identical multiprocessor platforms where Umin(k) is the minimum utilization and Dmax(k) the maximum deadline of the tasks of priority from 1 to k.

The sufficient schedulability condition given by Theorem 1 is not sustainable. In order to decide schedulability of a set of tasks without sustainability problem, it is necessary to consider the schedule over the feasibility interval given by [X1, Sn + P ] where Xn is given by Xn = Sn and Xi = Oi +

X i+1 -O i T i
Ti and where Sn is given by S1 = O1 and Si = max(Oi, Oi + S i-1 -O i T i Ti). P denotes the hyperperiod of the set of tasks and Oi the offset of the task τi.

CONCLUSION

In the case of embedded real-time multiprocessor scheduling, the restricted-migration scheduling is an interesting approach. But it has been shown that it suffers from sustainability problems in the case of fixed-priority. In this paper, we review the notion of sustainability and we analyze a non-predictable algorithm in order to propose a sustainable alternative. We highlight the properties of lower-priorityagnostic test, processor-available assignment and work-conserving algorithm which are responsible of the non-predictability. We propose for our algorithm r-SP wl the properties of lowerpriority-aware test, release-time assignment and idle algorithm. We prove that it does not suffer from scheduling anomaly with the model of tasks we consider.

In a previous work, we proposed a sufficient schedulability test for r-SP wl. Unfortunately, this test is not sustainable and we intend to develop a sustainable one in a future work.

  (c) Schedulable set of jobs with idle times.

Figure 2 :

 2 Figure 2:Impact of idle times in restrictedmigration scheduling.

:

  Ready job J k Input: Global pending jobs queue Q g Input: Local pending jobs queues Q = {Q1, . . . , Qm} 1 foreach πj ∈ Π do 2 if πj is free then 3 if there is a lower priority job J l running on πj

		then
	4	stop J l ;
	5	put J l in Qj;
	6	end
	7	start J k on πj;
	8	else
	9	put J k in Q g ;
	10	end
	11 end


Mathieu Claeys

Denis Arzelier

Didier Henrion

Jean-Bernard Lasserre

Moment LMI approach to LTV impulsive control

In the 1960s, a moment approach to linear time varying (LTV) minimal norm impulsive optimal control was developed, as an alternative to direct approaches (based on discretization of the equations of motion and linear programming) or indirect approaches (based on Pontryagin's maximum principle). This paper revisits these classical results in the light of recent advances in convex optimization, in particular the use of measures jointly with hierarchy of linear matrix inequality (LMI) relaxations. Linearity of the dynamics allows us to integrate system trajectories and to come up with a simplified LMI hierarchy where the only unknowns are moments of a vector of control measures of time. In particular, occupation measures of state and control variables do not appear in this formulation. This is in stark contrast with LMI relaxations arising usually in polynomial optimal control, where size grows quickly as a function of the relaxation order. Jointly with the use of Chebyshev polynomials (as a numerically more stable polynomial basis), this allows LMI relaxations of high order (up to a few hundreds) to be solved numerically.

Introduction

In the 1960s, it was realized that many physically relevant problems of optimal control were inappropriately formulated in the sense that the optimum control law (a function of time and/or state) cannot be found if the admissible functional space is too small. This observation was the main driving force of the papers [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF][START_REF] Rishel | An extended Pontryagin principle for control systems whose control laws contain measures[END_REF][START_REF] Schmaedeke | Optimal control theory for nonlinear vector differential equations containing measures[END_REF] which introduce optimal control problems formulated in the space of measures. The approach is well summarized in the textbook [START_REF] Luenberger | Optimization by vector space methods[END_REF], which contains some (academic) examples of optimal control problems without solutions. This motivated the introduction of many concepts of functional analysis (density, completeness, duality, separability) in control engineering, building up on the advances on mathematical control theory and calculus of variations. As promoted in [START_REF] Luenberger | Optimization by vector space methods[END_REF], an optimal control problem should be formulated in the dual of a Banach space which is large enough for the solution to be attained.

Most of the literature on numerical optimal control focuses on direct approaches (based on discretization of the equations of motions and linear programming) or indirect approaches (based on the necessary optimal conditions of Pontryagin's maximum principle). When applied to optimal control problems whose optima cannot be attained, these numerical approaches typically face difficulties. In this context, we believe that it is timely to revisit classical results by Neustadt [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF] on the formulation of optimal control problems for linear time varying (LTV) systems as a problem of moments, where the decision variables (from which an optimal control law can be extracted) are measures subject to a finite number of linear constraints.

There is an important literature, especially from the 1960s, on moment formulations to optimal control of ordinary differential equations (ODEs) and partial differential equations (PDEs), see e.g. [START_REF] Avdonin | Families of exponentials: the method of moments in controllability problems for distributed parameter systems[END_REF] and references therein, as well as the comments of [7, p. 586]. Currently, this approach is not frequently used by engineers, and in our opinion this may be due, on the one hand, to the technicality of the underlying concepts of functional analysis, and, on the other hand, to the absence of numerical methods to deal satisfactorily with optimization problems in large functional spaces such as spaces of measures or distributions. Regarding the first point, we strongly recommend the textbook [START_REF] Luenberger | Optimization by vector space methods[END_REF] which is a very readable account of elementary functional analysis useful for engineers. Regarding the second point, there has been recent advances in convex optimization, especially semidefinite programming (optimization over linear matrix inequalities, LMIs), for solving numerically generalized problems of moments, i.e. linear programming (LP) problems in Banach spaces of measures, see [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF][START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] and references therein.

Our contribution is therefore to revisit the classical formulation by Neustadt [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF] in the light of recent advances on LMI hierarchies for solving generalized problems of moments. In our previous work [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], we formulated polynomial optimal control problems with semialgebraic state and control constraints as generalized problems of moments that can be solved with asymptotically converging LMI hierarchies. The optimal control problem is relaxed to an LP problem in the space of occupation measures, which are measures of time, state and control encoding the trajectories of the system. The main drawback of this approach is the rapid growth of the size of the LMI problems in the hierarchy, making the approach applicable to small-size problems only (say at most 3 states and 2 controls). In the current paper, which focuses on the specific case of LTV dynamics depending affinely on the control variable, we first replace control variables by interpreting them as measures of time. This is similar to our previous work [START_REF] Claeys | Measures and LMI for impulsive optimal control with applications to space rendezvous problems[END_REF] which also dealt with impulsive control design in a more general setting. Second, we get rid of the state variables by integrating numerically the LTV ODE. This is possible because the ODE depends linearly on the state and the control. As a result, the optimal control problem is relaxed to an LP on measures depending only on time. It follows that there is no need for an LMI hierarchy since in the univariate case finite-dimensional moment LMI conditions are necessary and sufficient. However, there is still a hierarchy of LMI conditions in connection with the polynomial approximations of increasing degree we use to model the integrated system trajectories. To deal with those high degree univariate polynomials and moment matrices, we use Chebyshev polynomials instead of monomials. Indeed, high degree Chebyshev polynomials behave much better numerically than monomials, and we can rely on functionalities of the chebfun package for Matlab [START_REF] Trefethen | Chebfun Version 4.2, The Chebfun Development Team[END_REF][START_REF] Trefethen | Approximation theory and approximation practice[END_REF] to integrate the LTV ODE and manipulate polynomials. To illustrate the above methodology, we show on some examples how to obtain very good approximations of impulse times and amplitudes of an optimal solution.

Relaxed linear optimal control

Consider the linear time varying (LTV) optimal control problem

q * := inf u 1 := m j=1 t F t I |u j (t)|dt s.t. ẋ(t) = A(t)x(t) + B(t)u(t) x(t I ) ∈ R n given x(t F ) ∈ R n given (1)
where the minimization is w.r.t. a vector of control functions

u j ∈ L 1 ([t I , t F ]), j = 1, . . . , m, and A ∈ L ∞ ([t I , t F ]; R n×n ), B ∈ C([t I , t F ]; R n×m ), on a given bounded time interval [t I , t F ] ⊂ R.
In general the infimum is not attained, and the optimal control problem is relaxed to

p * := inf µ T V := m j=1 t F t I |µ j |(dt) s.t. x(dt) = A(t)x(t)dt + B(t)µ(dt) x(t I ) ∈ R n given x(t F ) ∈ R n given (2)
where the minimization is w.r. Lemma 1 The infimum is attained in problem (2) and it is equal to the infimum of problem (1), i.e. q * = p * .

The proof of Lemma 1 is relegated to the end of Section 3. We will introduce a numerical method to deal directly with relaxed problem (2) in measure space M , bypassing the potential difficulties coming from the fact that the infimum in problem (1) is typically not attained in function space L 1 . Before this, we need to reformulate optimal control problem (2) as a problem of moments.

F (t) := f 1 (t) • • • f n (t) ∈ W 1,1 ([t I , t F ]; R n×n ) therefore satisfies 1 the matrix ODE Ḟ (t) = A(t)F (t), F (t I ) = I n , t ∈ [t I , t F ].
From [5, Theorem 2.2.3]2 , matrix F -1 (t) is differentiable and any function x(t) satisfying

x(t F ) = F (t F ) x(t I ) + t F t I F -1 (t)B(t)µ(dt)
is a solution to the differential equation

x(dt) = A(t)x(t)dt + B(t)µ(dt), t ∈ [t I , t F ]. (3)
Letting

G(t) := (F -1 (t)B(t)) T = g 1 (t) • • • g n (t) ∈ C([t I , t F ]; R m×n ), h := F -1 (t F )x(t F ) -x(t I ) ∈ R m ,
we can replace the differential equation ( 3) with the integral equation:

t F t I G T (t)µ(dt) = h.
It follows that problem (2) can be written equivalently as

p * = min µ T V s.t. g i , µ = h i , i = 1, . . . , n (4)
where 4) is a problem of moments consisting of finding m measures subject to n linear constraints.

g i , µ := t F t I g T i (t)µ(dt) = m j=1 t F t I g i,j (t)µ j (dt) denotes the duality bracket between C([t I , t F ]; R m ) and its dual M ([t I , t F ]; R m ), a bilinear form pairing C([t I , t F ]; R m ) and M ([t I , t F ]; R m ). Problem (
Proof: (of Lemma 1) The proof that the infimum of problem ( 2) is attained follows from [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF]Theorem 1]. Moreover, in [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF]Theorem 4] it is shown that there exists a solution µ to problem (4), hence to problem (2), which is the (signed) sum of at most n Dirac measures. Finally, it is shown in [17, pp. 45-46] that there is a sequence of functions

u k ∈ L 1 ([t I , t F ]; R m ), k = 1, 2, .
. . which are admissible for problem (1), i.e. µ(dt) = u k (t)dt satisfies the constraints in problem ( 4), and which are such that lim k→∞ u k 1 = p * .

Primal and dual conic LP

By decomposing each signed measure µ j as a difference of two nonnegative measures (using the Jordan decomposition theorem, see e.g. [19, Section 17.2]), i.e.

µ j = µ + j -µ - j , µ + j ≥ 0, µ - j ≥ 0, j = 1, . . . , m, problem (4
) can be written as a linear programming (LP) problem on the cone of nonnegative measures

p * = inf 1, µ + + 1, µ - s.t. g i , µ + -g i , µ -= h i , i = 1, . . . , n µ + ≥ 0, µ -≥ 0 (5)
where 1 denotes the m-dimensional vector of functions identically equal to one, and the above minimization is w.r.t. two vector-valued nonnegative measures

µ + ∈ M ([t I , t F ]; R m ), µ -∈ M ([t I , t F ]; R m ).
It is easy to show that problem ( 5) is equivalent to problem (4).

Problem ( 5) is the dual of the following LP on the cone of nonnegative continuous functions (see [START_REF] Shapiro | Chapter 7 in Semi infinite programming: Recent Advances[END_REF] for details of the derivation):

d * = sup n i=1 y i h i s.t. z + (t) := 1 + n i=1 y i g i (t) ≥ 0 t ∈ [t I , t F ] z -(t) := 1 - n i=1 y i g i (t) ≥ 0 t ∈ [t I , t F ] (6)
where the maximization is w.r.t. a vector y ∈ R n parametrizing two vector-valued nonnegative continuous functions 6) can be also written as

z + ∈ C([t I , t F ]; R m ), z -∈ C([t I , t F ]; R m ). Denoting z ∞ := sup t∈[t I ,t F ],j=1,...,m |z j (t)| for any z ∈ C([t I , t F ]; R m ), remark that LP problem (
d * = sup h T y s.t. G(t)y ∞ ≤ 1. ( 7
)
Lemma 2 There is no duality gap between LP ( 5) and ( 6), i.e. p * = d * .

Proof: Define the vector r(µ + , µ -) ∈ R n+1 with entries r 0 (µ

+ , µ -) := 1, µ + + 1, µ -, r i (µ + , µ -) := g i , µ + -g i , µ -, i = 1, . . . ,
]; R m ) then lim k→∞ r(µ + n k , µ - n k ) = r(µ + , µ -) ∈ R.
Zero duality gap implies that any optimal pair ((µ + , µ -), (z + , z -)) solving LPs (5-6) satisfies the complementarity conditions

z + j , µ + j = 0, z + j , µ - j = 0, j = 1, . . . , m.
This means that the support of each measure

µ + j , resp. µ - j , is included in the set {t ∈ [t I , t F ] : z + j (t) = 0}, resp. {t ∈ [t I , t F ] : z - j (t) = 0}
, for j = 1, . . . , m. Note that formulation [START_REF] Fattorini | Infinite dimensional optimization and control theory[END_REF] of the dual problem dates back to the work of Neustadt [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF] and was preferred to the primal formulation for numerical solution of the optimal control problem. One objective of this paper is to show that the recent advances on the moment problem give an efficient computation procedure for the primal problem. In particular, one obtains very good approximations of an optimal solution of (5) (impulse times and amplitudes).

Remark 1

The vector G(t)y involved in LP problem ( 6) is known as the primer vector introduced in the seminal work [START_REF] Lawden | Optimal trajectories for space navigation[END_REF]. This primer vector is defined as the velocity adjoint vector arising by the application of Pontryagin's maximum principle to optimal trajectory problems. The primer vector must satisfy Lawden's well-known necessary conditions for an optimal impulsive trajectory.

Integration of the LTV ODE

In order to compute matrix F (t), the last step before obtaining a tractable problem, we have to integrate numerically the ODE ẋ(t) = A(t)x(t). Matrix G(t) solves numerically the LTV system of equations F (t)G T (t) = B(t). In practice, we use the Matlab software package Chebfun [START_REF] Trefethen | Chebfun Version 4.2, The Chebfun Development Team[END_REF] to build Chebyshev polynomial interpolants of the problem data A(t) and B(t). Some of its specialized numerical routines to compute F (t) and G(t) have been used here.

We want to characterize the error of approximating G(t) by its Chebyshev polynomial interpolant on d points, see [START_REF] Trefethen | Approximation theory and approximation practice[END_REF] for an introduction on this subject. Define G d (t) as the Chebyshev interpolant of G(t) on d points. Assume furthermore that the error induced by algebraic manipulations for obtaining G d (t) can be properly controlled. Then the approximation error e d := G d -G ∞ for large d is conditionned by the regularity of G(t). We recall the main results of approximation theory which can all be found in [START_REF] Trefethen | Approximation theory and approximation practice[END_REF]:

• if G(t) is k-times continuously differentiable, then e d → 0 at the algebraic rate of O(d -k ) as d → ∞;
• if G(t) is k-times differentiable with its k-th derivative of bounded variation, then the algebraic rate is O(d -k );

• if G(t) is analytic, then there exists a positive ρ such that the algebraic rate is

O(ρ -d ).
This imposes some minimal requirements for A(t) and B(t) for our numerical approach to work. Indeed, assuming A(t) of bounded variation and B(t) differentiable with derivative of bounded variation guarantees that the error converges to zero for large approximation orders.

We now show that if e d → 0 as d → ∞, we can build a hierarchy of moment relaxations of (4) involving only approximate data and converging to p * . For this, let F d (t) denote the Chebyshev interpolant of F (t) on d points, and let

h d := F -1 d (t F )x(t F ) -F -1 d (t I )x(t I ).
Lemma 3 Consider the following relaxed moment problem with approximate data:

p * d = min µ T V s.t. G T d dµ -h d ≤ e d ( B |x(t F )| + µ T V ). ( 8
)
Then p * d ↑ p * as d → ∞

Proof: By the same argument as Lemma 1, a solution for (8) is attained. Furthermore, any solution µ * of ( 4) is feasible for [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF], as

G T d dµ * -h d ≤ G T dµ * -h + (G T d -G T ) dµ * + ||B|| |x(t F )| |h d -h| ≤ 0 + e d ||µ * || TV + e d ||B|| |x(t F )|.
Therefore, p * e ≤ p * holds. For the convergence, consider the auxiliary relaxed problem with the true data instead:

p * d = min µ T V s.t. G T dµ -h ≤ 2e d ( B |x(t F )| + µ T V ). ( 9
)

Solving the LP on measures

To summarize, we have formulated our LTV optimal control problem as a primal-dual LP pair [START_REF] Bressan | Introduction to the mathematical theory of control[END_REF][START_REF] Claeys | Measures and LMI for impulsive optimal control with applications to space rendezvous problems[END_REF]. The coefficients in these LP problems are entries of matrix function G(t) and vector h. These data are calculated by numerical integration, using Chebyshev polynomial approximations, as explained in the last section. For a given degree d of the polynomial approximation, LP problem ( 5) is a particular instance of a generalized problem of moments. It can be seen as an extension of the approach of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] which was originally designed for classical optimal control problems with polynomial dynamics. Alternatively, it can also be understood as an application of the approach of [START_REF] Claeys | Measures and LMI for impulsive optimal control with applications to space rendezvous problems[END_REF], but after integration of the ODE, which is here possible because of linearity of the dynamics in the state and control.

An infinite-dimensional LP on measures can be solved approximately by a hierarchy of finite-dimensional linear matrix inequality (LMI) problems, see [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Claeys | Measures and LMI for impulsive optimal control with applications to space rendezvous problems[END_REF][START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] for details (not reproduced here). The main idea behind the hierarchy is to manipulate each measure via its moments truncated to degree d. Note that here the measures are univariate (depending on time only). Therefore, for a problem involving polynomials up to degree d, the d-th LMI condition is necessary and sufficient. The hierarchy presented in this paper comes thus from the polynomial approximation of the continuous data, not from the moment truncation. In contrast, when dealing with multivariate measures as in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Claeys | Measures and LMI for impulsive optimal control with applications to space rendezvous problems[END_REF][START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF], we use a hierarchy of necessary LMI conditions which become sufficient only asymptotically.

Generally speaking, the number of variables in an LMI relaxation of order d of a multivariate measure LP grows polynomially in d, but the exponent is the number of variables entering the measures. If the number of variables is equal to 5 or more, the growth is fast, and only LMI relaxation of small orders can be solved at a reasonable computational cost. It is therefore crucial to reduce as much as possible the number of variables entering the measures, so as to reduce the overall computational burden. One contribution of our paper is precisely to show that for LTV optimal control problems, we can manipulate measures of the time variable only. This allows for LMI relaxations of large order to be solved, with d a few hundreds.

Examples

Scalar polynomial example

Consider the optimal control problem (1):

p * = inf u 1 := 1 0 |u(t)|dt s.t. ẋ(t) = t(1 -t)u(t) x(0) = 0, x(1) = 1
where the minimization is w.r.t. a function u ∈ L 1 ([0, 1]). Since L 1 ([0, 1]) is not the dual of any normed space, the problem must be relaxed to the optimal control problem (2):

p * = min µ T V := 1 0 |µ|(dt) s.t. x(dt) = t(1 -t)µ(dt) x(0) = 0, x(1) = 1
where the minimization is now w.r.t. a measure µ ∈ M ([0, 1]). Following the approach of Section 3, we readily obtain

F (t) = 1, G(t) = t(1 -t)
and hence the moment problem (4):

p * = min µ T V s.t. t(1 -t), µ := 1 0 t(1 -t)µ(dt) = 1.
Decomposing µ = µ + -µ -as a difference of two nonnegative measures we obtain the LP (5):

p * = inf 1, µ + + 1, µ - s.t. t(1 -t), µ + -t(1 -t), µ -= 1 µ + ≥ 0, µ -≥ 0
where the minimization is w.r.t. measures µ + , µ -, and the LP ( 6):

d * = sup y s.t. -1 ≤ t(1 -t)y ≤ 1, ∀ t ∈ [0, 1]
where the maximization is w.r.t. y ∈ R. For this latter problem, we readily obtain that the maximum d * = 4 is attained for the choice y = 4. Since polynomial 4t(1 -t) attains its maximum at t = 1 2 it follows from the discussion after Lemma 2 that the optimal measure solution is µ + = 4δ1 2 and µ -= 0, achieving p * = 4.

As this problem has polynomial data, we can readily find the optimal solution, with the following GloptiPoly 3 script [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF], instead of using the approximation techniques of Section V: >> mpol tp tn; >> mp = meas(tp); % measure \mu^+ >> mn = meas(tn); % measure \mu^->> P = msdp(min(mass(mp)+mass(mn)), .

Nonsmooth trajectories

This example is meant to illustrate the numerical difficulty we may face when integrating LTV ODEs with discontinuous state matrix A(t). Consider the following optimal control problem (1):

p * = inf u 1 s.t. ẋ(t) = sign(t)x(t) + u(t) x(-1) = -1, x(1) = 1
where the minimization is w.r.t. a function u ∈ L 1 ([-1, 1]). Upon solving the ODE Ḟ (t) = sign(t)F (t), F (-1) = 1 we obtain F (t) = e -1+|t| , G(t) = e 1-|t| and hence the moment problem (4):

p * = inf µ T V s.t. e 1-|t| , µ = 2
where the minimization is now w.r.t. a signed measure µ ∈ M ([-1, 1]). The dual problem (6) reads:

d * = sup 2y s.t. -1 ≤ ye 1-|t| ≤ 1 ∀ t ∈ [-1, 1]
where the maximization is w.r.t. a real scalar y. The optimal dual solution can easily be found analytically as y * = e -1 , from which it follows that the optimal primal solution is If we want to apply the numerical integration approach of Section 5, discontinuity of A(t) = sign(t) turns out to be a problem. Indeed, we can check that G(t) presents a cusp at t = 0. That is, for an even number d of Chebyshev interpolation points, the maximum

µ * = 2e -1 δ t=0 . d G -G d ∞ |p * -p d |/
A(t) =          0 0 1 0 0 0 0 1 n2 e cos ν(t) 1 + e cos ν(t) 1 -e 2 3 -2 n2 e sin ν(t) 1 + e cos ν(t) 1 -e 2 3 0 2n (1 + e cos ν(t)) 2
1 -e 2 3/2

2 n2 e sin ν(t)

1 + e cos ν(t)

1 -e 2 3 n2 (3 + e cos ν(t))

1 + e cos ν(t)

1 -e 2 3 -2n (1 + e cos ν(t)) 2 1 -e 2 3/2 0          B(t) =     0 0 0 0 n2 0 0 n2     (10)
interpolation error G -G d ∞ is located where the optimal impulse should be, while for an odd d the interpolant is exact at the cusp. In Table 1 we present the approximation errors on function G and on the optimal cost p * d as functions of d, found by our numerical method. The results exhibit the expected linear decrease in the approximation error, resulting in a linear decrease in the optimal cost. The error for moderate orders (d ≈ 100) is acceptable though far from excellent. Now, if we split the time interval around the cusp, the restrictions of G(t) on the intervals [-1, 0] and [0, 1] are respectively G L (t) := e 1+t and G R (t) := e 1-t which are both analytic.

d G -G d ∞ |p * -p d |/|p * | 2 2.1187 • 10 -1 3.4307 • 10 -3 4 1.0851 • 10 -3 1.0406 • 10 -5 6 2.2540 • 10 -6
The updated moment problem with piecewise analytic data reads:

p * = inf µ L T V + µ R T V s.t. 0 -1 G L (t)µ L (dt) + 1 0 G R (t)µ R (dt) = 2.
In Table 2, we present the updated polynomial approximation errors, which show the expected exponential decrease. For the cost, the decrease is exponential until a relative error of about 10 -10 after which the error comes from the semidefinite solver (used to solve the LMI hierarchy of the moment problem), not from the polynomial approximation.

7.3 A fuel-optimal linear impulsive guidance rendezvous problem for an elliptic reference orbit

Finally, an illustration based on a realistic case of a far range rendezvous in a linearized gravitational field is given. The general framework of the minimum-fuel fixed-time copla-nar rendezvous problem in a linear setting is recalled in [START_REF] Arzelier | Using polynomial optimization to solve the fuel-optimal impulsive rendezvous problem[END_REF], where an indirect method based on primer vector theory is proposed. Under Keplerian assumptions and for an elliptic reference orbit, the complete rendezvous problem may be decoupled between the out-of-plane rendezvous problem for which an analytical solution may be found and the coplanar problem. Therefore, only a coplanar elliptic rendezvous problem based on the Tschauner-Hempel equations [START_REF] Tschauner | Rendevous zu einem in elliptischer Bahn umlaufenden Ziel[END_REF] is studied thereafter. The associated optimal control problem (1) has a 4-dimensional (n = 4) state vector composed of the relative positions (denoted here x(t), z(t)) and respective velocities in the LVLH frame [START_REF] Louembet | Robust rendezvous planning under navigation and manoeuvering errors[END_REF] and a 2-dimensional (m = 2) control vector u(t) (one control in the x-direction, one control in the z-direction). The state space matrices A(t) and B(t) are given in equ. [START_REF] Larsson | Fuel efficient relative orbit control strategies for formation flying and rendezvous within PRISMA[END_REF], with n = 34.0094 is the mean angular motion, e = 4.0000 • 10 -3 is the eccentricity, ν(t) is the true anomaly of the reference orbit satisfying for all t ≥ 0 the Kepler equation:

nt = E(t) -e sin E(t) tan ν(t) 2 = 1 + e 1 -e 1/2 tan E(t) 2
where E(t) is the eccentric anomaly.

For this problem, G(t) can be approximated below the 10 -8 resolution of the SDP solver by polynomials of degree 100 on the given time interval. This implies that the problem can be solved numerically by LMI relaxations of order 50, with a computational load of a few seconds. The assembly of G(t) using Chebfun routines take a few seconds as well.

All of this was done without any sort of problem-specific optimization, and with standard Matlab code.

To solve the optimal control problem, direct methods based on the solution of a linear programming (LP) problem can be used as in [START_REF] Mueller | Collision avoidance maneuver planning with robust optimization[END_REF][START_REF] Louembet | Robust rendezvous planning under navigation and manoeuvering errors[END_REF]. For an a priori fixed number of impulsive maneuvers at given times, an LP problem is formulated and solved numerically. Its solution is therefore suboptimal, depending strongly upon the number of impulsions. This makes it hard to evaluate how far the solution could be from the global optimum.

The particular instance, studied in this paper, is borrowed from the PRISMA test bed and GNC experiments from [START_REF] Berges | CNES formation flying experiment on PRISMA: spacecraft reconfiguration and rendezvous within FFIORD mission[END_REF]. PRISMA programme is a cooperative effort between the Swedish National Space Board (SNSB), the French Centre National d'Etudes Spatiales (CNES), the German Deutsche Zentrum für Luft-und Raumfahrt (DLR) and the Danish Danmarks Tekniske Universitet (DTU) [START_REF] Larsson | Fuel efficient relative orbit control strategies for formation flying and rendezvous within PRISMA[END_REF]. Launched on June 15, 2010 from Yasny (Russia), it was intended to test in-orbit new guidance schemes (particularly autonomous orbit control) for formation flying and rendezvous technologies. This mission includes the FFIORD experiment led by CNES, which features a rendezvous maneuver (formation acquisition). To save fuel and allow for in-flight testing throughout the FFIORD experiment, the rendezvous maneuver must last several orbits. Duration of the rendezvous is approximately 14.25 orbital periods, each of duration 5920s, i.e. t I = 0 and t F = 84360 in problem (1).

The moment LMI approach is compared to the classical 2-impulse solution and to the direct approach with 20 and 2000 pre-assigned evenly distributed impulses. These results are presented in prohibitive cost when compared to the optimal solution found by the direct method and the moment LMI approach. This is mainly due to the extra thrusts in the z-direction that are not necessary to realize this particular rendezvous. Indeed, a remarkable feature of the optimal solution is that it exhibits a terminal coast, unlike the 2-impulse and direct 20-impulse solution. Note also that the 2-impulse solution leads to a very different trajectory in the orbital plane as shown by Figure 1. The optimal fuel-cost computed via the moment LMI approach is less than half the one obtained in [START_REF] Berges | CNES formation flying experiment on PRISMA: spacecraft reconfiguration and rendezvous within FFIORD mission[END_REF] via a pseudo-closed loop technique (0.086 m/s). Figure 2 shows the importance of the pre-assigned number of impulses for the direct method to recover the optimal solution. Indeed, for a small number of impulses, the solution given by the direct method is a crude approximation of the optimal solution obtained by the moment LMI approach and by the direct approach with 2000 pre-assigned impulses. The impulse locations are indicated on the trajectories (red triangles for the optimal solution and red squares for the 20-impulse solution). The differences of locations of the impulses for the four methods used on the PRISMA example are depicted on Figure 3.

Conclusion

In this paper, we revisit classic impulsive control theory from the 1960s with modern numerical tools stemming from convex programming and approximation theory. The theory leads to the reformulation of a control problem as a one-dimensional problem of moments. The numerical tools allow for its efficient numerical solution without any expert knowledge needed.

Several extensions of our work are possible and will be included in an extended version of this paper. First of all, the class of dynamics can easily be extended to cover those with with w(t) ∈ C 1 ([t I , t F ], R n ). The second main extension is to enforce positivity constraints on linear combinations of the states using additional positive measures. Finally, the method can also consider other norms of the form ||u(•)|| p := |u(t)| p dt with p = 2, 3, ..., instead of the p = 1 case that is the focus of this paper. This can be done since norms with integer exponents are semidefinite representable.

For the specific case of orbital rendezvous as exemplified in Section 7.3, one can exploit the specific symmetries of [START_REF] Larsson | Fuel efficient relative orbit control strategies for formation flying and rendezvous within PRISMA[END_REF] to approximate G(t) off-line on half an orbital period, and partition the time interval accordingly such as presented in Ex. 7.2. This will lead to accurate, low order polynomial approximations, and one could expect to obtain computational loads compatible for an online implementation of a model predictive control loop.

Figure 1 :

 1 Figure 1: Trajectories in the orbital plane: 2-impulse solution (pink), optimal solution (blue), Direct 20-impulses solution (cyan).

Figure 2 :

 2 Figure 2: Trajectories in the orbital plane: optimal solution (blue), Direct 20-impulses solution (cyan) .

Figure 3 :

 3 Figure 3: Impulses for 2-impulse solution (red and blue), direct 20-impulse solution (cyan), optimal solution (black).

  n and the set R := {r(µ + , µ -) : (µ + , µ -) ∈ M 2m + } ⊂ R n+1 where M 2m + denotes the cone of nonnegative measures in M ([t I , t F ]; R 2m ). Let us invoke [1, Theorem 3.10] which states that p * = d * provided p * is finite and R is closed. Finiteness of p * follows immediately since we minimize the total variation. To prove closedness, we have to show that all accumulation points of any sequence r(µ + n , µ - n ) belong to R. Since the supports of the measures are compact and p * is finite, hence µ + and µ -are bounded, the sequence (µ + n , µ - n ) is bounded. By the weak-* compactness of the unit ball in the Banach space of bounded signed measures with compact support (Alaoglu's Theorem, see e.g.[START_REF] Luenberger | Optimization by vector space methods[END_REF] Section 5.10] or[START_REF] Royden | Real analysis[END_REF] Section 15.1]), there is a subsequence (µ + n k , µ - n k ) that converges weakly-* to an element (µ + , µ -) ∈ M 2m + . As 1 and all g i belong to C([t I , t F

Table 1 :

 1 Approximation errors vs. polynomial approximation orders for discontinuous dynamics.

	|p * |

  1.5281 • 10 -8 8 2.5115 • 10 -9 1.3166 • 10 -11 10 1.7422 • 10 -12 5.9438 • 10 -13 12 1.1336 • 10 -15 5.8093 • 10 -12

	14	< 10 -15	1.3729 • 10 -11
	16	< 10 -15	3.1846 • 10 -12
	18	< 10 -15	2.5462 • 10 -10

Table 2 :

 2 Approximation errors vs. polynomial approximation orders for piecewise analytic dynamics.

Table 3

 3

		2-impulse LP (20 i.) LP (2000 i.)	LMI
	t 0	0	0	0	0
	t 1	-	8880	2321	2140
	t 2	-	75480	2363	82350
	t 3	84360	84360	82334	-
	u(t 0 )	0.02 -0.1985	0.0006 0	0.0174 0	0.0172 0
	u(t 1 )	-	0.0014 0	0.0193 0	0.0011 0
	u(t 2 )	-	-0.0146 0	-0.0003 0	-0.019 0
	u(t 3 )	-0.0215 0.218	-0.0207 0	-0.019 0	-
	cost m/s	0.4588	0.04072	0.03736	0.03736

, where t k are the impulsion times and u(t k ) the impulsion directions, for k = 0, 1, 2, 3. It is interesting to note that the 2-impulse solution has a

Table 3 :

 3 Comparisons of results of moment LMI approach, two-impulse solution and direct LP solution for 200 and 2000 impulses for the PRISMA case study

A function belongs to the Sobolev space W 1,1 of absolutely continuous functions if it is the integral of a function of Lebesgue space L 1 .

In this reference the authors define the fundamental matrix solution as a bivariate matrix M (t, s) such that ∂M (t, s)/∂t = A(t)M (t, s), M (s, s) = I n . The connection with our definition is that F (t) = M (t, t I ).


Abdel Aissat

Alix De Becdelièvre

Lisa Golmard

Christian Vasseur

Catherine Costa

Asma Chaoui

Natacha Martin

Bruno Costes

Michel Goossens

Emmanuelle Girodon

Combined Computational-Experimental Analyses of CFTR Exon Strength Uncover Predictability of Exon-Skipping Level

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

Table 1 . Summary of exons harboring weak core splicing signals according to each splicing tool used for the analyses

 1 All the calculated values, with each software, are recapitulated in the Supp. TableS3and all CI90 boxplots are illustrated in the supp Fig.S1. na: not available. The complete list of the link and publications for each splicing tool are summarized in Suppl. TableS1.

	Name of the software	Exon(s) with a weak AS	Exon(s) with a weak DS	Exon(s) with a weak BP	Exon(s) with a weak PPT
	1) ESEfinder3.0	9; 12; 14; 20	5; 20; 25	-	-
	2) FSplice	7; 9; 20	5; 21	-	-
	3) GeneID	7; 15; 20; 27	20; 25	-	-
	4) GenSCAN	7; 14; 15; 18; 20; 27	5; 9; 10; 12; 25	-	-
	5) H-Bond	na	10; 12; 25	-	-
	6) Human Splicing Finder	14; 21	5; 6; 10; 17; 20; 25	-	-
	7) MaxEntScan	7; 11; 15; 20; 27	6 ; 9	-	-
	8) NetGene2	14; 15; 20	5; 6; 9; 12; 25	-	-
	9) NNSplice	7; 9; 11; 14; 15; 20	4; 9; 10; 16; 22	-	-
	10) SplicePort	13; 14	12; 20; 22	-	-
	11) SplicePredictor	7; 11; 20; 27	3; 4; 9; 17	-	-
	12) SpliceSiteFrame	14; 20; 27	6; 20; 25	-	-
	13) SpliceView	7; 14; 20	5; 7; 20	-	-
	14) SROOGLE			2; 22	7; 10
		Exon 20 (10 out of 12)	Exon 25 (7 out of 13)
	Most represented exons	Exon 14 (8 out of 12) Exon 7 (7 out of 12) Exon 15 (5 out of 12)	Exon 5 (6 out of 13) Exon 20 (6 out of 13) Exon 9 (5 out of 13)
		Exon 27 (5 out of 12)

. Weak splicing signals are defined as those in the outliers inferior or equal to the lower inner fence when comparing the strength values with the median value of all CFTR exons (confidence interval of 90%, CI90).

Table 2 . Quantification of basal WT exon skipping.

 2 The percentage of exon skipping, plus or minus SD, is represented. Skill of each exon was assigned according to its basal skipping percentage using minigene (weak when superior or equal to 5%, strong if under or not detectable). Experiments were repeated three to nine times for each condition. Relative strength of splicing signals of each exon was tagged as weak when at least one splicing signal was predicted as weak by each in silico tool and strong if none. nd: not detected. na: not

available. Success rate of prediction was calculated by confronting in vitro skills with predictions by each in silico tool.