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

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.

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.

16393

01/01/2017

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

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.

16232

31/12/2016

E.HEBRARD, M.J.HUGUET, N.JOZEFOWIEZ, A.MAILLARD, C.PRALET, G.VERFAILLIE

ROC, ONERA

Revue Scientifique : Discrete Applied Mathematics, Vol.215, pp.126-135, Décembre 2016, doi 10.1016/j.dam.2016.07.003 , N° 16232

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

Diffusable

Plus d'informations

We consider the problem of minimizing the makespan of a schedule on m parallel machines of n jobs, where each job requires exactly one of s additional unit resources. This problem collapses to P ||C max if every job requires a different resource. It is therefore NP-hard even if we fix the number of machines to 2 and strongly NP-hard in general. Although very basic, its approximability is not known, and more general cases, such as scheduling with conflicts, are often not approximable. We give a (2 − 2 /(m+1))-approximation algorithm for this problem, and show that when the deviation in jobs processing times is bounded by a ratio ρ, the same algorithm approximates the problem within a tight factor 1 + ρ (m−1)/n. This problem appears in the design of download plans for Earth observation satellites, when scheduling the transfer of the acquired data to ground stations. Within this context, it may be required to process jobs by batches standing for the set of files related to a single observation. We show that there exists a (2 − 1/m)-approximation algorithm respecting such batch sequences. Moreover, provided that the ratio ρ, between maximum and minimum processing time, is bounded by ⌊s−1/ m−1⌋, we show that the proposed algorithm approximates the optimal schedule within a factor 1 + (s−1)/n.

16495

20/12/2016

L.BEAUDOU, P.COUPECHOUX, A.DAILLY, S.GRAVIER, J.MONCEL, A.PARREAU, E.SOPENA

UBP, ROC, LIRIS, UJF, LABRI

Rapport LAAS N°16495, Décembre 2016, 21p.

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

Diffusable

Plus d'informations

Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, an octal game on a path Pn is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.

16424

09/12/2016

M.NATTAF, T.KIS, C.ARTIGUES, P.LOPEZ

ROC, MTA

Rapport LAAS N°16424, Décembre 2016, 9p.

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

Diffusable

Plus d'informations

This paper addresses a scheduling problem with a cumulative, continuously-divisible and renewable resource with limited capacity. During its processing, each task consumes a part of this resource, which lies between a minimum and a maximum requirement. A task is finished when a certain amount of energy is received by it within its time window. This energy is received via the resource and an amount of resource is converted into an amount of energy with a non-decreasing, continuous and linear efficiency function. The goal is to minimize the resource consumption. The paper focuses on an event based mixed integer linear program, providing several valid inequalities which are used to improve the performance of the model. Furthermore, we give a minimal description of the polytope of all feasible assignments to the on/off binary variable for a single activity along with a dedicated separation algorithm. Computational experiments are reported in order to show the effectiveness of the results.

16409

09/12/2016

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

MAC, ROC

Rapport LAAS N°16409, Décembre 2016, 8p.

Diffusable

138289 16408

09/12/2016

C.GAZZINO, C.LOUEMBET, D.ARZELIER, H.YAMAKAWA

MAC, ROC, Kyoto

Rapport LAAS N°16408, Décembre 2016, 37p.

Diffusable

138288Les 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 à