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

665documents trouvés

18414
03/12/2018

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

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

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
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
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
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
18376
11/09/2018

Earth observation systems optimization for free-space optical communications

M.CAPELLE

ROC

Doctorat : Septembre 2018146, 146p., Président: J.C.BILLAUT, Rapporteurs: O.PETON, S.DEMASSEY, Examinateurs: C.PRALET, F.CLAUTIAUX, Directeurs de thèse: M.J.HUGUET, N.JOZEFOWIEZ , N° 18376

Non diffusable

Plus d'informations

Résumé

Depuis plusieurs années, les satellites sont utilisés pour explorer, surveiller et photographier la Terre depuis l’espace. Ces satellites prennent un nombre croissant d’images avec une résolution de plus en plus de plus élevée, générant ainsi de gros volumes de données qui doivent être envoyés vers la Terre. Afin de transférer de telles quantités de données, de nouvelles technologies de communication sont étudiées. Parmi elles, les liaisons optiques en espace libre sont considérées aujourd’hui comme une alternative intéressante aux technologies actuelles basées sur les radio-fréquences. Avec des débits bien supérieurs à ceux actuels, les liaisons optiques sont capables de transférer d’important volumes de données journaliers en à peine quelques minutes. Cependant, les liaisons optiques sont fortement perturbées par les turbulences atmosphériques et, en particulier, les nuages. Afin de limiter l’impact de la couverture nuageuse, il est nécessaire de créer des réseaux de stations sol optiques efficacement réparties dans le monde. De plus, les prévisions météorologiques n’étant pas exactes, des procédures opérationnelles doivent être établies afin de pouvoir planifier les transferts d’images depuis le satellite vers la Terre, en prenant en compte les incertitudes liées aux nuages et aux prévisions de couverture nuageuse. Dans cette thèse, nous nous intéressons à l’utilisation de communications optiques pour la télémétrie image. Dans un premier temps, nous considérons le problème de la création de réseaux terrestres de stations optiques prenant en compte l’impact des nuages. Nous résolvons ce problème en combinant un algorithme de programmation dynamique avec un algorithme de type branch-and-bound. Dans un second temps, nous nous intéressons au problème de planification des transferts d’images d’un point de vue opérationnel, en prenant en compte les incertitudes sur les volumes des images acquises (dues à la compression bord) et celles liées aux communications optiques. Nous proposons une approche flexible où le processus de décision est partagé entre le système sol (centre mission) et le système à bord du satellite.

Abstract

For many years, satellites have been used to explore, analyse and monitor Earth from space. Nowadays, low-earth orbiting satellites are taking a steadily increasing number of pictures, with higher and higher precision, thus generating huge volumes of data that needs to be downloaded. In order to manage such amount of data, new communication technologies are investigated. In this context, free-space optical communications are seen as a key alternative to current radio-frequency ones. With their orders of magnitude higher data rates, free-space optical communications could be able to download daily acquisition volumes in a matter of minutes. Unfortunately, optical communications are strongly impacted by atmospheric turbulence and clouds. In order to cope with the latter, it is necessary to design efficient distributed networks of optical ground stations. Furthermore, since weather forecasts are imperfect, custom operational procedures should be established to schedule the downloads of acquisitions using optical communications to take into account uncertainties regarding clouds. In this thesis, we investigate the use of free-space optical communications for image telemetry. We first consider the problem of designing efficient networks of optical ground stations taking into account the impact of clouds. We solve this problem using a combination of a dynamic programming algorithm and a branch-and-bound algorithm. Then, we look at the operational problem of planning downloads of acquisitions under download channel and image volume uncertainties. We propose a flexible approach where the decision process is shared between ground and on-board systems.

Mots-Clés / Keywords
Optimisation combinatoire; Observation spatiale; Communications optiques; Combinatorial optimization; Spatial observation; Optical telecommunications;

145257
18163
01/09/2018

A Dial-a-Ride evaluation for solving the job-shop with routing considerations

M.GONDRAN, M.J.HUGUET, P.LACOMME, A.QUILLIOT, N.TCHERNEV

LIMOS, ROC

Revue Scientifique : Engineering Applications of Artificial Intelligence, Vol.74, pp.70-89, Septembre 2018 , N° 18163

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

Diffusable

Plus d'informations

Abstract

The Job-Shop scheduling Problem with Transport (JSPT) is a combinatorial optimization problem that combines both scheduling and routing problems. It has received attention for decades, resulting in numerous publications focused on the makespan minimization. The JSPT is commonly modeled by a disjunctive graph that encompasses both machine-operations and transport-operations. The transport-operations define a sub-problem which is close to the DARP where pickup and delivery operations have to be scheduled. The vast majority of the evaluation functions used into disjunctive graphs of JSPT, minimizes the makespan and there is no routing criteria in the objective function. Commonly used evaluation functions lead to left-shifted solutions for both machine-operations and transport-operations. The present work investigates a new evaluation function for the JSPT which integrates routing problematic to compute non semi-active solutions but which minimize the makespan first and maximize the Quality of Service second thanks to a time-lag max based modeling and an iterative process. The Quality of Service proposed in this paper, is extended from the Quality of Service defined by (Cordeau and Laporte, 2003) for the DARP. The procedure performance is benchmarked with a CPLEX resolution and the numerical experiments proved that the proposed evaluation function is nearly optimal and provides new solutions with a high Quality of Service.

143875
17395
01/09/2018

Minimum-fuel fixed time impulsive elliptic glideslope guidance algoriths using semidefinite programming

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

MAC, ROC

Revue Scientifique : Journal of Guidance, Control, and Dynamics, Vol.41, N°9, pp.1873-1887, Septembre 2018 , N° 17395

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

Diffusable

Plus d'informations

Abstract

A new minimum-fuel glideslope guidance algorithm for approaching autonomously a target evolving on an elliptic orbit is proposed in this paper. Assuming chemical propulsion, the present work aims at enhancing Hablani's seminal method. Although this reference method is efficient and easy to implement, there is no direct control on the fuel consumption and the guidance error. By identifying some relevant degrees of freedom, a new formulation of the glideslope guidance algorithm is proposed to address these issues. For a fixed-time rendezvous and a given number of maneuvers, the fuel-optimal multipulse glideslope is expressed as a semidefinite programming problem. A solution to this optimization problem provides an impulsive control sequence that guarantees a minimal consumption and makes sure the chaser's trajectory remains included inside a user-defined corridor. Besides, if trajectory constraints are removed, or if a specific direction is considered (V-bar or R-bar), then the formulation is reduced to a simple linear programming problem. Three realistic scenarios of rendezvous are simulated to illustrate the benefit of the proposed methodology.

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