10documents trouvés
Scheduling scientific experiments on the Rosetta/Philae mission
G.SIMONIN, C.ARTIGUES, E.HEBRARD, P.LOPEZ
MOGISA
Manifestation avec acte : International Conference on Principles and Practice of Constraint Programming (CP) 2012 du 08 octobre au 12 octobre 2012, Québec (Canada), 2012, 15p. , N° 12344
Lien : http://hal.archives-ouvertes.fr/hal-00713858
Diffusable
Plus d'informations
Abstract
The Rosetta/Philae mission was launched in 2004 by the European Space Agency (ESA). It is scheduled to reach the comet 67P/ChuryumovGerasimenko in 2014 after traveling more than six billion kilometers. The Philae module will then be separated from the orbiter (Rosetta) to attempt the first ever landing on the surface of a comet. If it succeeds, it will engage a sequence of scientific exploratory experiments on the comet. In this paper we describe a constraint programming model for scheduling the different experiments of the mission. A feasible plan must satisfy a number of constraints induced by energetic resources, precedence relations on activities, or incompatibility between instruments. Moreover, a very important aspect is related to the transfer (to the orbiter then to Earth) of all the data produced by the instruments. The capacity of inboard memories and the limitation of transfers within visibility windows between lander and orbiter, make the transfer policy implemented on the lander's CPU prone to data loss. We introduce a global constraint to handle data transfers. The goal of this constraint is to ensure that data-producing activities are scheduled in such a way that no data is lost. Thanks to this constraint and to the filtering rules we propose, mission control engineers are now able to compute feasible plans in a few seconds for scenarios where minutes or even hours were previously often required. Moreover, in many cases, data transfers are now much more accurately simulated, thus increasing the reliability of the plans.
An optimal arc consistency algorithm for a chain of atmost constraints with cardinality
M.SIALA, E.HEBRARD, M.J.HUGUET
MOGISA
Manifestation avec acte : International Conference on Principles and Practice of Constraint Programming (CP) 2012 du 08 octobre au 12 octobre 2012, Québec (Canada), Article primé "Honorable Mention", Octobre 2012, 15p. , N° 12343
Lien : http://hal.archives-ouvertes.fr/hal-00713860
Diffusable
Plus d'informations
Abstract
The ATMOSTSEQCARD constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n - q + 1 constraints ATMOST u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In [18], two algorithms designed for the AMONGSEQ constraint were adapted to this constraint with a O(2^q n) and O(n^3) worst case time complexity, respectively. In [10], another algorithm with a O(n2 log n) worst case time complexity and similarly adaptable to filter ATMOSTSEQCARD in O(n log n) was proposed. In this paper, we introduce an algorithm for achieving Arc Consistency on the ATMOSTSEQCARD constraint with a O(n) (hence optimal) worst case time complexity. We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.
A study of branching heuristics for the car-sequencing problem
M.SIALA, E.HEBRARD, M.J.HUGUET
MOGISA
Manifestation avec acte : International Workshop on Search Strategies and Non-standard Objectives (SSNOWorkshop'12), Nantes (France), 29 Mai 2012, 15p. , N° 12287
Diffusable
127405Algorithme optimal d'arc-consistance pour une séquence de contraintes AtMost avec cardinalité
E.HEBRARD, M.J.HUGUET, M.SIALA
MOGISA
Manifestation avec acte : Journées Francophones de Programmation par Contraintes (JFPC'2012), Toulouse (France), 22-24 Mai 2012, 10p. , N° 12288
Diffusable
127407Plans sur la comète !
G.SIMONIN, C.ARTIGUES, E.HEBRARD, P.LOPEZ
MOGISA
Manifestation sans acte : Congrès Annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012), Angers (France), 11-13 Avril 2012, 2p. , N° 12173
Diffusable
126982Complete characterization of near-optimal sequences for the two-machine flow shop scheduling problem
J.C.BILLAUT, E.HEBRARD, P.LOPEZ
LI, MOGISA
Rapport LAAS N°12171, Avril 2012, 16p.
Lien : http://hal.archives-ouvertes.fr/hal-00676783
Diffusable
Plus d'informations
Abstract
In a two-machine flow shop scheduling problem, the set of $\epsilon$-approximate sequences (i.e., solutions within a factor $1+\epsilon$ of the optimal) can be mapped to the vertices of a permutation lattice. We introduce two approaches, based on properties derived from the analysis of permutation lattices, for characterizing large sets of near-optimal solutions. In the first approach, we look for a sequence of minimum level in the lattice, since this solution is likely to cover many optimal or near-optimal solutions. In the second approach, we look for all sequences of minimal level, thus covering all $\epsilon$-approximate sequences. Integer linear programming and constraint programming models are first proposed to solve the former problem. For the latter problem, a direct exploration of the lattice, traversing it by a simple tree search procedure, is proposed. Computational experiments are given to evaluate these methods and to illustrate the interest and the limits of such approaches.
Models and strategies for variants of the job shop scheduling problem
D.GRIMES, E.HEBRARD
Cork, MOGISA
Manifestation avec acte : Principles and Practice of Constraint Programming - CP 2011, Perugia (Italie), 12-16 Septembre 2011, pp.356-372 , N° 11496
Lien : http://hal.archives-ouvertes.fr/hal-00626799/fr/
Diffusable
Plus d'informations
Abstract
Recently, a variety of constraint programming and Boolean satisfiability approaches to scheduling problems have been introduced. They have in common the use of relatively simple propagation mechanisms and an adaptive way to focus on the most constrained part of the problem. In some cases, these methods compare favorably to more classical constraint programming methods relying on propagation algorithms for global unary or cumulative resource constraints and dedicated search heuristics. In particular, we described an approach that combines restarting, with a generic adaptive heuristic and solution guided branching on a simple model based on a decomposition of disjunctive constraints. In this paper, we introduce an adaptation of this technique for an important subclass of job shop scheduling problems (JSPs), where the objective function involves minimization of earliness/tardiness costs. We further show that our technique can be improved by adding domain specific information for one variant of the JSP (involving time lag constraints). In particular we introduce a dedicated greedy heuristic, and an improved model for the case where the maximal time lag is 0 (also referred to as no-wait JSPs).
Soft constraints of difference and equality
E.HEBRARD, D.MARX, B.O'SULLIVAN, I.RAZGON
MOGISA, Universität Berlin, Cork, Leicester
Revue Scientifique : Journal of Artificial Intelligence Research, Vol.41, pp.97-130, Juillet 2011 , N° 11387
Diffusable
124987Job shop scheduling with setup times and maximal time-lags: A simple constraint programming approach
D.GRIMES, E.HEBRARD
Cork, MOGISA
Manifestation avec acte : International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010), Bologne (Italie), 14-18 Juin 2010, pp.147-161 , N° 10856
Lien : http://hal.archives-ouvertes.fr/hal-00561633/fr/
Diffusable
Plus d'informations
Abstract
In previous work we introduced a simple constraint model that combined generic AI strategies and techniques (weighted degree heuristic, geometric restarts, nogood learning from restarts) with naive propagation for job shop and open shop scheduling problems. Here, we extend our model to handle two variants of the job shop scheduling problem: job shop problems with setup times; and job shop problems with maximal time lags. We also make some important additions to our original model, including a solution guidance component for search. We show empirically that our new models often outperform the state of the art techniques on a number of known benchmarks for these two variants, finding a number of new best solutions and proving optimality for the first time on some problems.We provide some insight into the performance of our approach through analysis of the constraint weighting procedure.
Constraint programming and combinatorial optimisation in numberjack
E.HEBRARD, E.O'MAHONY, B.O'SULLIVAN
MOGISA, Cork
Manifestation avec acte : International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010), Bologne (Italie), 14-18 Juin 2010, pp.181-185 , N° 10855
Lien : http://hal.archives-ouvertes.fr/hal-00561698/fr/
Diffusable
Plus d'informations
Abstract
Python benets from a large and active programming com- munity. Numberjack is a modelling package written in Python for embed- ding constraint programming and combinatorial optimisation into larger applications. It has been designed to seamlessly and efficiently support a number of underlying combinatorial solvers. Currently, Numberjack supports three constraint programming solvers, one MIP solver, and one satisability solver -- all available as open-source software. This paper illustrates many of the features of Numberjack through the use of several combinatorial optimisation problems.We also demonstrate a cloud-based congurator built with Numberjack, using services provided by Google to support a user-interface and back-end reasoning capabilities.