Laboratoire d’analyse et d’architecture des systèmes

17006

01/06/2017

T.GUEROUT, P.LOPEZ, T.MONTEIL, C.ARTIGUES, Y.GAOUA, G.DA COSTA

SARA, ROC, IRIT-UPS

Revue Scientifique : Future Generation Computer Systems, Vol.71, pp.1-17, Juin 2017 , N° 17006

Lien : https://hal.archives-ouvertes.fr/hal-01438550

Diffusable

Plus d'informations

The analysis of the Quality of Service (QoS) level in a Cloud Computing environment becomes an attractive research domain as the utilization rate is daily higher and higher. Its management has a huge impact on the performance of both services and global Cloud infrastructures. Thus, in order to nd a good trade-off, a Cloud provider has to take into account many QoS objectives, and also the manner to optimize them during the virtual machines allocation process. To tackle this complex challenge, this article proposed a multiobjective optimization of four relevant Cloud QoS objectives, using two different optimization methods: a Genetic Algorithm (GA) and a Mixed Integer Linear Programming (MILP) approach. The complexity of the virtual machine allocation problem is increased by the modeling of Dynamic Voltage and Frequency Scaling (DVFS) for energy saving on hosts. A global mixed-integer non linear programming formulation is presented and a MILP formulation is derived by linearization. A heuristic decomposition method, which uses the MILP to optimize intermediate objectives, is proposed. Numerous experimental results show the complementarity of the two heuristics to obtain various trade-offs between the different QoS objectives.

17126

23/05/2017

A.CHEREF, A.AGNETIS, C.ARTIGUES, J.C.BILLAUT

ROC, UNISI, LI

Rapport LAAS N°17126, Mai 2017

Diffusable

Plus d'informations

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 NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.

17110

27/04/2017

C.GAZZINO, D.ARZELIER, L.CERRI, D.LOSA, C.LOUEMBET, C.PITTET-MECHIN

MAC, ROC, CNES, Thalès Alenia Space

Rapport LAAS N°17110, Avril 2017, 6p.

Lien : https://hal.laas.fr/hal-01511019

Diffusable

Plus d'informations

In this paper, a fuel optimal rendezvous problem is tackled in the Hill-Clohessy-Wiltshire framework with several operational constraints as bounds on the thrust, non linear non convex and disjunctive operational constraints (on-off profile of the thrusters, minimum elapsed time between two consecutive firings...). An indirect method and a decomposition technique have already been combined in order to solve this kind of optimal control problem with such constraints. Due to a great number of parameters to tune, satisfactory results are hard to obtain and are sensitive to the initial condition. Assuming that no singular arc exists, it can be shown that the optimal control exhibits a bang-bang structure whose optimal switching times are to be found. Noticing that a system with a bang-bang control profile can be considered as two subsystems switching from one with control on to with control off, and vice-versa, a technique coming from the switching systems theory is used in order to optimise the switching times.

17095

12/04/2017

Y.ARIBA, D.ARZELIER, L.URBINA IGLESIAS

MAC, ROC

Rapport LAAS N°17095, Avril 2017, 6p.

Diffusable

139535 17066

31/03/2017

Y.ARIBA, D.ARZELIER, L.URBINA IGLESIAS

MAC, ROC

Rapport LAAS N°17066, Mars 2017, 8p.

Lien : https://hal.laas.fr/hal-01482341

Diffusable

Plus d'informations

This paper presents a new minimum-fuel glideslope guidance algorithm for approaching autonomously a target evolving on an elliptic orbit. In addition to the usual rectilinear profile to follow as in Hablani's seminal paper, two new features are requested for the new algorithm. The first one imposes bounds on the guidance error inherent to chemical propulsion glideslope guidance, such that the chaser's trajectory does not escape from an admissible domain. The second one minimizes the consumption during rendezvous. Indeed, unlike the classical glideslope algorithm for which there is no direct control on the fuel consumption, additional degrees of freedom and relevant decision variables may be identified. By combining a useful parametrization of the Tschauner-Hempel relative equations of motion and results from polynomial optimization, a semidefinite formulation of the constraints on the maximal guidance error is obtained. For a fixed-time glideslope rendezvous with a pre-assigned number of maneuvers, a fuel-optimal solution with a bounded guidance error is obtained by solving a semidefinite programming problem. Two numerical examples illustrate the usefulness of the method compared to the classical ones when the approach corridor has to verify stringent geometrical restrictions such as line-of-sight constraints.

17047

21/03/2017

M.BRENTARI, L.URBINA IGLESIAS, D.ARZELIER, C.LOUEMBET, L.ZACCARIAN

Trento, MAC, ROC

Rapport LAAS N°17047, Mars 2017, 13p.

Diffusable

Plus d'informations

We focus on the problem of satellite rendezvous between two spacecraft in elliptic orbits. Using a linearized model of the relative dynamics, we first propose a periodic similarity transformation based on Floquet-Lyapunov theory, leading to a set of coordinates under which the free motion is linear time-invariant. Then we address the problem of impulsive control of satellite rendezvous as a hybrid dynamical system, and we show that the arising elegant representation enables designing impulsive control laws with different trade-offs between computational complexity and fuel consumption. The adopted hybrid formalism allows us to prove suitable stability properties induced by the proposed controllers. The results are comparatively illustrated on simulation examples.

17025

03/03/2017

C.ARTIGUES

ROC

Revue Scientifique : Operations Research Letters, Vol.45, N°2, pp.154-159, Mars 2017 , N° 17025

Lien : https://hal.archives-ouvertes.fr/hal-01461447

Diffusable

Plus d'informations

For non-preemptive scheduling, time-indexed zero-one linear programming formulations have been deeply analyzed. This note clarifies the current knowledge about the strength of these formulations and shows that some formulations that have been proposed " new " in the literature are in fact weaker or equivalent to those already known. Much of the arguments used follow from a PhD thesis by Sousa, which has been largely overlooked in the literature.

15589

10/02/2017

R.BALDACCI, S.U.NGUEVEU , R.WOLFER CALVO

Bologne, ROC, LIPN

Revue Scientifique : Transportation Science, 47p., Février 2017, doi http://dx.doi.org/10.1287/trsc.2016.0711 , N° 15589

Diffusable

Plus d'informations

This paper proposes an exact method for solving an optimization problem arising in several distribution networks where customers can be served directly, using vehicle routes from a central depot, or through transhipment facilities. The problem consists of optimizing the following inter-dependent decisions: selecting transhipment facilities, allocating customers to these facilities, and designing vehicle routes emanating from a central depot to minimize the total distribution cost. This problem is called the Vehicle Routing Problem with Transhipment Facilities (vrptf). The paper describes two integer-programming formulations for the vrptf, i.e., an edge-flow based formulation and a Set Partitioning (SP) based formulation. The LP-relaxation of the two formulations are further strengthened by the addition of different valid inequalities. We also describe two new route relaxations used by dual ascent heuristics to find near-optimal dual solutions of LP-relaxation of the SP model. The valid inequalities and the route relaxations are used in a branch-and-cut-and-price approach to solve the problem to optimality. The proposed method is tested on a large family of instances, including real-world examples. The computational results obtained indicate the effectiveness of the proposed method.

15296

01/02/2017

L.VARGAS SUAREZ, N.JOZEFOWIEZ, S.U.NGUEVEU

ROC

Revue Scientifique : Journal of Heuristics, Vol.23, N°1, pp.53-80, Février 2017 , N° 15296

Diffusable

Plus d'informations

This paper presents an evaluation operator for single-trip vehicle routing problems where it is not necessary to visit all the nodes. Such problems are known as Tour Location Problems. The operator, called Selector, is a dynamic programming algorithm that converts a given sequence of nodes into a feasible tour. The operator returns a subsequence of this giant tour which is optimal in terms of length. The procedure is implemented in an adaptive large neighborhood search to solve a specific tour location problem: the Covering Tour Problem. This problem consists in finding a lowest-cost Hamiltonian cycle over a subset of nodes such that nodes outside the tour are within a given distance from a visited node. The metaheuristic proposed is competitive as shown by the quality of results evaluated using the output of a state-of-the-art exact algorithm.

17009

31/01/2017

E.HEBRARD, M.J.HUGUET, D.VEYSSEIRE, L.SAUVAN, B.CABON

ROC, Airbus Defence & Sp

Revue Scientifique : Constraints, Vol.22, N°1, pp.73-89, Janvier 2017 , N° 17009

Lien : https://hal.laas.fr/hal-01443817

Diffusable

Plus d'informations

The payload of communications satellites must go through a series of tests to assert their ability to survive in space. Each test involves some equipment of the payload to be active, which has an impact on the temperature of the payload. Sequencing these tests in a way that ensures the thermal stability of the payload and minimizes the overall duration of the test campaign is a very important objective for satellite manufacturers. The problem can be decomposed in two sub-problems corresponding to two objectives: First, the number of distinct configurations necessary to run the tests must be minimized. This can be modeled as packing the tests into configurations, and we introduce a set of implied constraints to improve the lower bound of the model. Second, tests must be sequenced so that the number of times an equipment unit has to be switched on or off is minimized. We model this aspect using the constraint Switch, where a buffer with limited capacity represents the currently active equipment units, and we introduce an improvement of the propagation algorithm for this constraint. We then introduce a search strategy in which we sequentially solve the sub-problems (packing and sequencing). Experiments conducted on real and random instances show the respective interest of our contributions.

Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à