Laboratoire d’analyse et d’architecture des systèmes
M.BRENTARI, L.URBINA IGLESIAS, D.ARZELIER, C.LOUEMBET, L.ZACCARIAN
Trento, MAC, ROC
Rapport LAAS N°17047, Mars 2017, 13p.
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.
Revue Scientifique : Operations Research Letters, Vol.45, N°2, pp.154-159, Mars 2017 , N° 17025
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.
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
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.
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
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.
N.CHAABANE, A.AGNETIS, C.BRIAND, M.J.HUGUET
Revue Scientifique : Networks, Vol.69, N°1, pp.94-109, Janvier 2017 , N° 16393
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.
E.HEBRARD, M.J.HUGUET, N.JOZEFOWIEZ, A.MAILLARD, C.PRALET, G.VERFAILLIE
Revue Scientifique : Discrete Applied Mathematics, Vol.215, pp.126-135, Décembre 2016, doi 10.1016/j.dam.2016.07.003 , N° 16232
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.
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.
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.
M.NATTAF, T.KIS, C.ARTIGUES, P.LOPEZ
Rapport LAAS N°16424, Décembre 2016, 9p.
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.
Y.ARIBA, D.ARZELIER, L.URBINA IGLESIAS, C.LOUEMBET
Rapport LAAS N°16409, Décembre 2016, 8p.
C.GAZZINO, C.LOUEMBET, D.ARZELIER, H.YAMAKAWA
MAC, ROC, Kyoto
Rapport LAAS N°16408, Décembre 2016, 37p.