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

650documents trouvés

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
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
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
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
18282
31/08/2018

Clause Learning and New Bounds for Graph Coloring

E.HEBRARD, G.KATSIRELOS

ROC, INRA Castanet

Manifestation avec acte : International Conference on Principles and Practice of Constraint Programming ( CP ) 2018 du 27 août au 31 août 2018, Lille (France), Août 2018, 17p. , N° 18282

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

Diffusable

Plus d'informations

Abstract

Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov's tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.

144615
18292
24/08/2018

Algorithms for the Flexible Cyclic Jobshop Problem

F.QUINTON, I.HAMAZ, L.HOUSSIN

ROC

Manifestation avec acte : IEEE International Conference on Automation Science and Engineering ( CASE ) 2018 du 20 août au 24 août 2018, Munich (Allemagne), Août 2018, 5p. , N° 18292

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

Diffusable

Plus d'informations

Abstract

This paper considers the cyclic jobshop problem in a flexible context. The aim is to find the minimum cycle time of a periodic schedule. The flexibility feature comes from the ability of the machines or robots to perform several kinds of tasks. Hence, the scheduling problem does not only concern starting time of tasks but also on which machines the tasks will be performed. We propose an exact method to solve this problem and two heuristics.

144659
18226
20/08/2018

Connected Subtraction Games on Subdivided Stars

A.DAILLY, J.MONCEL, A.PARREAU

LIRIS, ROC

Rapport LAAS N°18226, Août 2018, 21p.

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

Diffusable

Plus d'informations

Abstract

The present paper deals with connected subtraction games in graphs, which are generalization of takeaway games. In a connected subtraction game, two players alternate removing a connected sub-graph from a given connected game-graph, provided the resulting graph is connected, and provided the number of vertices of the removed subgraph belongs to a prescribed set of integers. We derive general periodicity results on such games, as well as specific results when played on subdivided stars.

144258
18281
19/07/2018

Reasoning About NP-complete Constraints

E.HEBRARD

ROC

Manifestation avec acte : International Joint Conference on Artificial Intelligence ( IJCAI ) 2018 du 13 juillet au 19 juillet 2018, Stockholm (Suede), Juillet 2018, 5p. , N° 18281

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

Diffusable

Plus d'informations

Abstract

The concept of local consistency-making global deductions from local infeasibility-is central to constraint programming. When reasoning about NP-complete constraints, however, since achieving a "complete" form of local consistency is often considered too hard, we need other tools to design and analyze propagation algorithms. In this paper, we argue that NP-complete constraints are an essential part of constraint programming , that designing dedicated methods has lead to, and will bring, significant breakthroughs, and that we need to carefully investigate methods to deal about a necessarily incomplete inference. In particular, we advocate the use of fixed-parameter tractability and kernelization to this purpose.

144613
18299
19/07/2018

Conflict Directed Clause Learning for the Maximum Weighted Clique Problem

E.HEBRARD, G.KATSIRELOS

ROC, INRA Castanet

Manifestation avec acte : International Joint Conference on Artificial Intelligence ( IJCAI ) 2018 du 13 juillet au 19 juillet 2018, Stockholm (Suede), Juillet 2018, 8p. , N° 18299

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

Diffusable

Plus d'informations

Abstract

The maximum clique and minimum vertex cover problems are among Karp's 21 NP-complete problems , and have numerous applications: in combi-natorial auctions, for computing phylogenetic trees, to predict the structure of proteins, to analyse social networks, and so forth. Currently, the best complete methods are branch & bound algorithms and rely largely on graph colouring to compute a bound. We introduce a new approach based on SAT and on the "Conflict-Driven Clause Learning" (CDCL) algorithm. We propose an efficient implementation of Babel's bound and pruning rule, as well as a novel dominance rule. Moreover, we show how to compute concise explanations for this inference. Our experimental results show that this approach is competitive and often outperforms the state of the art for finding cliques of maximum weight.

144717
18213
29/06/2018

Mixed-integer and constraint programming formulations for a multi-skill project scheduling problem with partial preemption

O.POLO MEJIA, M.C.ANSELMET, C.ARTIGUES, P.LOPEZ

ROC, CEA Cadarache

Manifestation avec acte : International Conference on Modeling, Optimization & Simulation ( MOSIM ) 2018 du 27 juin au 29 juin 2018, Toulouse (France), Juin 2018, 8p. , N° 18213

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

Diffusable

Plus d'informations

Abstract

In this paper, we consider the weekly scheduling problem of activities within one of the research facilities of the French Alternative Energies and Atomic Energy Commission (CEA in short for French). To better represent this problem we propose a new variant of the multi-skill project scheduling problem (MSPSP) involving partial preemption. We describe the new MSPSP variant and we present two formulations for the problem: one using mixed-integer linear programming (MILP) and a second one using constraint programming (CP). Computational experiments on realistic data are carried out and discussed.

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