Retour au site du LAAS-CNRS

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

Publications de l'équipe ROC

Choisir la langue : FR | EN

592documents trouvés

17006
01/06/2017

Mixed integer linear programming for quality of service optimization in Clouds

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

Abstract

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.

139662
17110
27/04/2017

A minimum-fuel fixed-time low-thrust rendezvous solved with the switching systems theory

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

Abstract

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.

139665
17095
12/04/2017

A new glideslope guidance algorithm for minimum-fuel fixed-time elliptic rendezvous using semidefinite programming

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

MAC, ROC

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

Diffusable

139535
17066
31/03/2017

Optimal Glideslope guidance algorithm for minimum-fuel fixed-time elliptic rendezvous

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

Abstract

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.

139394
17047
21/03/2017

A hybrid control framework for impulsive control of satellite rendezvous

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

Abstract

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.

139292
17025
03/03/2017

On the strength of time-indexed formulations for the resource-constrained project scheduling problem

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

Abstract

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.

139077
15589
10/02/2017

The vehicle routing problem with transhipment facilities

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

Abstract

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.

138955
15296
01/02/2017

A dynamic programming operator for tour location problems applied to the covering problem

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

Abstract

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.

139601
17009
31/01/2017

Constraint programming for planning test campaigns of communications satellites

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

Abstract

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.

138720
16393
01/01/2017

Finding a Nash Equilibrium and an optimal sharing policy for multi-agent network expansion game

N.CHAABANE, A.AGNETIS, C.BRIAND, M.J.HUGUET

ROC, UNISI

Revue Scientifique : Networks, Vol.69, N°1, pp.94-109, Janvier 2017 , N° 16393

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

Diffusable

Plus d'informations

Abstract

In this work, a multi-agent network flow problem is addressed , aiming at characterizing the properties of stable flows and allowing their computation. Two types of agents are considered: transportation-agents, that carry a flow of products on a given network and another agent, either a producer or a customer, who is willing to ship (receive, respectively) products. Every transportation-agent controls a set of arcs, each having a capacity that can be increased up to a certain point at a given cost. The other agent (i.e., the customer/producer) is interested in maximizing the flow transshipped through the network. To this aim, we assume it offers the transportation-agents a reward that is proportional to the realized flow value. This particular multi-agent framework is referred to as a Multi-Agent network expansion game. We characterize and find particular stable strategies (i.e., Nash equilibria) that are of interest for this game. We particularly focus on the problem of finding a Nash Equilibrium and a sharing policy that maximize the value of the total flow. We prove that this problem is NP-hard in the strong sense and show how such a strategy can be characterized considering paths in specific auxiliary graphs. We also provide a mixed integer linear programming (MILP) formulation to solve the problem. Computational experiments are provided to prove the effectiveness of our approach and derive some insights for practitioners.

138233
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 à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/