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

670documents trouvés

18024
18/02/2019

Long-term electric geostationary station-keeping via integer programming

C.GAZZINO, D.ARZELIER, C.LOUEMBET

MAC, ROC

Revue Scientifique : Journal of Guidance, Control, and Dynamics, Février 2019, doi10.2514/1.G003644 , N° 18024

Diffusable

Plus d'informations

Abstract

The problem of the computation of correction maneuvers for the fuel-optimal long-term station-keeping within a predefined longitude and latitude window of a geostationary satellite equipped with electric propulsion is investigated. The use of electric thrusters imposes some additional operational constraints on actuation that can be reformulated as logical constraints on the control function. The resulting fuel-optimal station-keeping problem is therefore transformed into a mixed linear integer programming problem. The long-term horizon of station-keeping is divided in shorter control cycles synchronized with the cycles of orbit determination, and the long-term station-keeping problem amounts to solve a sequence of similar mixed linear integer programming problems with different initial conditions. Two different terminal constraints on geographical positions and/or linear velocities are added to the formulation of the mixed linear integer programming problems to ease the feasibility of the whole sequence of successive resolutions. Nonlinear perturbed simulations of the computed control strategies show their efficiency on a long-term station-keeping problem lasting one year.

146604
18414
03/12/2018

Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique

I.HAMAZ

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 3 Décembre 2018, 148p., Président: A.ROSSI, Rapporteurs: P.CHRETIENNE, M.POSS, Examinateurs: C.ARTIGUES, Directeurs de thèse: L.HOUSSIN, S.CAFIERI , N° 18414

Lien : https://hal.laas.fr/tel-01975512

Diffusable

Plus d'informations

Abstract

Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by ("the" a effacer) uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.

Résumé

Plusieurs problèmes d’ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d’incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d’ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d’ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d’incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d’incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d’ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d’optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d’optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d’ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d’évaluer l’efficacité de notre méthode nous l’avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d’une manière uniforme et dont l’objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l’arbre de recherche consiste à calculer le volume d’un polytope. Enfin, pour montrer l’efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

Mots-Clés / Keywords
Ordonnancement cyclique; Optimisation robuste; Optimisation combinatoire; Cyclic scheduling; Robust optimization; Combinatorial optimization;

145533
18538
01/12/2018

Robust Static Output Feedback Design with Deterministic and Probabilistic Certificates

D.ARZELIER, F.DABBENE, S.FORMENTIN, D.PEAUCELLE, L.ZACCARIAN

ROC, CNR-IEIIT, Torino, Politecnico, MAC

Ouvrage (contribution) : Uncertainty in Networked Systems, Springer, N°ISBN 978-3-030-04629-3, Décembre 2018, pp.121-148 , N° 18538

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

Diffusable

Plus d'informations

Abstract

Static output feedback design for linear plants is well known to be a challenging non-convex problem. The presence of plant uncertainty makes this challenge even harder. In this chapter, we propose a new BMI formulation with S-variables which includes an interesting link between state feedback, output injection , state injection and static output feedback gains in a unified framework. Based on this formulation, the robust design problem is suitably addressed by iterative optimization procedures with either deterministic or probabilistic viewpoints exploiting the fact that Lyapunov certificates are separated from the control gain design variables. The deterministic approach is for affine polytopic systems. The proba-bilistic approach requires no assumption on the uncertain system and is based on the Scenario with Certificates (SwC) method which was recently proposed to address certain static anti-windup design problems. Numerical results illustrate the effectiveness of the approach in both deterministic and stochastic cases.

146393
18339
06/11/2018

Energy management optimization of a smart wind power plant comparing heuristic and linear programming methods

R.BOURBON, S.U.NGUEVEU , X.ROBOAM, B.SARENI, C.TURPIN, D.HERNANDEZ-TORRES

LAPLACE, ROC

Revue Scientifique : Mathematics and Computers in Simulation, Novembre 2018, doi 10.1016/j.matcom.2018.09.022 , N° 18339

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

Diffusable

Plus d'informations

Abstract

This paper aims at optimizing the energy management of a smart power plant composed of wind turbines coupled with a Lithium Ion storage device in order to fulfill a power production commitment to the utility grid. The application of this case study is typically related to islanded electric grids. Our work particularly investigates and compares two classes of energy management strategies for design purpose: a first capable of providing the global optimum of the power flow planning from a Linear Programming (LP) approach thanks to a priori knowledge of future events in the environment; a second, based on a classical control heuristic without any a priori knowledge on the future, applicable in real time. Beyond the future objectives in terms of system design (techno-economical sizing optimization), the comparison of both approaches also aims at improving the predefined heuristic from the analysis of the ideal reference provided by the global LP optimizer. In this scope, a linear power flow model of the power plant is developed in compliance with a LP solver (Cplex). A particular attention is paid to the techno-economic optimization including storage cost evaluation, commitment failure penalties and exploitation gains. Simulations and optimizations are carried out over one year in order to take variability and seasonal features of the wind potential into account.

144994
18338
06/11/2018

Optimizing ground station networks for free space optical communications: maximizing the data transfer

M.CAPELLE, M.J.HUGUET, N.JOZEFOWIEZ, X.OLIVE

ROC, LCOMS, Thalès Alenia Space

Revue Scientifique : Networks, Novembre 2018, DOI : 10.1002/net.21859 , N° 18338

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

Diffusable

Plus d'informations

Abstract

Free space optical communications are becoming a mature technology to cope with the needs of high data rate payloads for future low‐earth orbiting observation satellites. However, they are strongly impacted by clouds. In this paper, we aim to find a network of optical ground stations maximizing the percentage of data acquired by a low‐earth orbiting satellite that can be transferred to the Earth, taking into consideration cloud information. This problem can be separated in two parts and solved hierarchically: the selection of a network of optical ground stations and the assignment of downloads to visibility windows of the stations. We present theoretical and practical results regarding the complexity of the latter subproblem and propose a dynamic programming algorithm to solve it. We combine this algorithm with two methods for the enumeration of the stations, and compare them with a mixed integer linear program (MILP). Results show that even if the MILP can solve scenarios over small horizons, the hierarchical approaches outperform it in term of computation time while still achieving optimality for larger instances.

144992
18543
01/11/2018

Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods

S.U.NGUEVEU

ROC

Revue Scientifique : European Journal of Operational Research, Novembre 2018 , N° 18543

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

Diffusable

Plus d'informations

Abstract

Various optimization problems result from the introduction of nonlinear terms into combinatorial optimization problems. In the context of energy optimization for example, energy sources can have very different characteristics in terms of power range and energy demand/cost function, also known as efficiency function or energy conversion function. Introducing these energy sources characteristics in combinatorial optimization problems, such as energy resource allocation problems or energy-consuming activity scheduling problems may result into mixed integer nonlinear problems neither convex nor concave. Approximations via piecewise linear functions have been proposed in the literature. Non-convex optimization models and heuristics exist to compute optimal breakpoint positions under a bounded absolute error-tolerance. We present an alternative solution method based on the upper and lower bounding of nonlinear terms using non necessarily continuous piecewise linear functions with a relative epsilon-tolerance. Conditions under which such approach yields a pair of mixed integer linear programs with a performance guarantee are analyzed. Models and algorithms to compute the non necessarily continuous piecewise linear functions with absolute and relative tolerances are also presented. Computational evaluations performed on energy optimization problems for hybrid electric vehicles show the efficiency of the method with regards to the state of the art.

146403
18311
18/10/2018

Trains do not vanish: the ROADEF/EURO challenge 2014

C.ARTIGUES, E.BOURREAU, V.JOST, S.KEDAD SIDHOUM, F.RAMOND

ROC, LIRMM, UGA, LIP6-CNRS, SNCF

Revue Scientifique : Annals of Operations Research, 15p., Octobre 2018 , N° 18311

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

Diffusable

Plus d'informations

Abstract

The ROADEF/EURO challenge is a contest jointly organized by the French Operational Research and Decision Aid society (ROADEF) and the European Operational Research society (EURO). The contest has appeared on a regular basis since 1999 and always concerns an applied optimization problem proposed by an industrial partner. The 2014 edition of the ROADEF/EURO challenge was led by the Innovation & Research department of SNCF, a global leader in passenger and freight transport services, and infrastructure manager of the French railway network. The objective of the challenge was to find the best way to store and move trains on large railway sites, between their arrivals and departures. Since trains never vanish and traffic continues to increase, in recent years some stations have been having real congestion issues. Train management in large railway sites is of high interest for SNCF, which is why it was submitted to the operations research community as the industrial problem for the 2014 edition of the ROADEF/EURO challenge. This paper introduces the special section of the Annals of Operations Research volume devoted to the ROADEF/EURO challenge 2014, as well as the methods of the finalist teams and their results.

144794
18214
05/10/2018

Fuel-optimal impulsive fixed-time trajectories in the linearized circular restricted 3-body-problem

R.SERRA , D.ARZELIER, F.BREHARD, M.M.JOLDES

MAC, ROC

Manifestation avec acte : International Astronautical Congress ( IAC ) 2018 du 01 octobre au 05 octobre 2018, Breme (Allemagne), Octobre 2018, 9p. , N° 18214

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

Diffusable

Plus d'informations

Abstract

The problem of fixed-time fuel-optimal trajectories with high-thrust propulsion in the vicinity of a Lagrange point is tackled via the linear version of the primer vector theory. More precisely, the proximity to a Lagrange point i.e. any equilibrium point-stable or not-in the circular restricted three-body problem allows for a linearization of the dynamics. Furthermore, it is assumed that the spacecraft has ungimbaled thrusters, leading to a formulation of the cost function with the 1-norm for space coordinates, even though a generalization exists for steerable thrust and the 2-norm. In this context, the primer vector theory gives necessary and sufficient optimality conditions for admissible solutions to two-value boundary problems. Similarly to the case of rendezvous in the restricted two-body problem, the in-plane and out-of-plane trajectories being uncoupled, they can be treated independently. As a matter of fact, the out-of-plane dynamics is simple enough for the optimal control problem to be solved analytically via this indirect approach. As for the in-plane dynamics, the primer vector solution of the so-called primal problem is derived by solving a hierarchy of linear programs, as proposed recently for the aforementioned rendezvous. The optimal thrusting strategy is then numerically obtained from the necessary and sufficient conditions. Finally, in-plane and out-of-plane control laws are combined to form the complete 3-D fuel-optimal solution. Results are compared to the direct approach that consists in working on a discrete set of times in order to perform optimization in finite dimension. Examples are provided near various Lagrange points in the Sun-Earth and Earth-Moon systems, hinting at the extensive span of possible applications of this technique in station-keeping as well as mission analysis, for instance when connecting manifolds to achieve escape or capture.

144218
18029
27/09/2018

A Three-step Decomposition Method for Solving the Minimum-Fuel Geostationary Station Keeping of Satellites Equipped with Electric Propulsion

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

MAC, ROC, CNES, Thalès Alenia Space

Revue Scientifique : 14p., Septembre 2018 , N° 18029

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

Diffusable

Plus d'informations

Abstract

In this paper, a control scheme is elaborated in order to perform the station keeping of a geostationary satellite equipped with electric propulsion while minimizing the fuel consumption. The use of electric thrusters imposes to take into account some additional non linear and operational constraints that make the overall station keeping optimal control problem difficult to solve directly. That is why the station keeping problem is decomposed in three successive control problems. The first one consists in solving a classical optimal control problem with an indirect method initialized by a direct method without enforcing the thrusters operational constraints. Starting from this non feasible solution for the genuine problem, the thrusters operating constraints are incorporated in the second problem, whose solution produces a feasible but non optimal control profile via two different ways. Finally, the third optimizes the commutation times thanks to a method borrowed to the switched systems theory. Simulation results on a realistic example validate the benefit of this particular control scheme in the reduction of the fuel consumption for the geostationary station keeping problem.

144554
18264
27/09/2018

Energy-efficient planning for supplying assembly lines with vehicles

C.BRIAND, Y.HE, S.U.NGUEVEU

ROC

Revue Scientifique : EURO Journal on Transportation and Logistics, Septembre 2018, doi 10.1007/s13676-018-0129-8 , N° 18264

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

Diffusable

Plus d'informations

Abstract

This paper focuses on minimizing the energy consumed by vehicles for parts supplying to workstations in mixed-model assembly lines. The parts are assumed to be packed in bins (or pallets). The bins are shipped from a so-called “supermarket” and delivered periodically to the workstations using tow trains with wagons. For each time period, depending on the production plan, a workstation has a specific demand of parts expressed as a portion of a bin. The problem is to define the sequence of workstations to be visited by the tow train at each time period, as well as the number of bins to be delivered at each stop, so as to avoid any material shortage. This paper provides an analysis of the computational complexity related to this problem and proposes two original mixed integer linear programming formulations. We also provide computational analysis and experiments that put the efficiency of one particular formulation into evidence and show the conditions under which energy-efficient supplying is not in contradiction with economic efficiency.

144553
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/